International Association
for Cryptologic Research

We propose a new cryptographic primitive called verifiably encrypted threshold key derivation (VETKD) that extends identity-based encryption with a decentralized way of deriving decryption keys. We show how VETKD can be leveraged on modern blockchains to build scalable decentralized applications (or dapps) for a variety of purposes, including preventing front-running attacks on decentralized finance (DeFi) platforms, end-to-end encryption for decentralized messaging and social networks (SocialFi), cross-chain bridges, as well as advanced cryptographic primitives such as witness encryption and one-time programs that previously could only be built from secure hardware or using a trusted third party. And all of that by secret-sharing just a single secret key...

We construct new multi-signature schemes that provide new functionality. Our schemes are designed to reduce the size of the Bitcoin blockchain, but are useful in many other settings where multi-signatures are needed. All our constructions support both signature compression and public-key aggregation. Hence, to verify that a number of parties signed a common message m, the verifier only needs a short multi-signature, a short aggregation of their public keys, and the message m. We give new constructions that are derived from Schnorr signatures and from BLS signatures. Our constructions are in the plain public key model, meaning that users do not need to prove knowledge or possession of their secret key.In addition, we construct the first short accountable-subgroup multi-signature (ASM) scheme. An ASM scheme enables any subset $$ S $$ of a set of n parties to sign a message m so that a valid signature discloses which subset generated the signature (hence the subset $$ S $$ is accountable for signing m). We construct the first ASM scheme where signature size is only $$O(\kappa )$$ bits over the description of $$ S $$, where $$\kappa $$ is the security parameter. Similarly, the aggregate public key is only $$O(\kappa )$$ bits, independent of n. The signing process is non-interactive. Our ASM scheme is very practical and well suited for compressing the data needed to spend funds from a t-of-n Multisig Bitcoin address, for any (polynomial size) t and n.