McFly: Verifiable Encryption to the Future
Made PracticalNico Döttling1⋆ , Lucjan Hanzlik1 , Bernardo Magri2 , and Stella Wohnig1,3
1

CISPA Helmholtz Center for Information Security{doettling,hanzlik,stella.wohnig}@cispa.de
2
The University of Manchester
bernardo.magri@manchester.ac.uk
3
Saarland University

Abstract. Blockchain protocols have revolutionized the way individuals
and devices can interact and transact over the internet. More recently, a
trend has emerged to harness blockchain technology as a catalyst to enable advanced security features in distributed applications, in particularfairness. However, the tools employed to achieve these security features
are either resource wasteful (e.g., time-lock primitives) or only efficientin theory (e.g., witness encryption). We present McFly, a protocol thatallows one to efficiently “encrypt a message to the future” such that thereceiver can efficiently decrypt the message at the right time. At theheart of the McFly protocol lies a novel primitive that we call signaturebased witness encryption (SWE). In a nutshell, SWE allows to encrypta plaintext with respect to a tag and a set of signature verification keys.
Once a threshold multi-signature of this tag under a sufficient number ofthese verification keys is released, this signature can be used to efficiently
decrypt an SWE ciphertext for this tag. We design and implement apractically efficient SWE scheme in the asymmetric bilinear setting. The
McFly protocol, which is obtained by combining our SWE scheme witha BFT blockchain (or a blockchain finality layer) enjoys a number ofadvantages over alternative approaches: There is a very small computational overhead for all involved parties, the users of McFly do not needto actively maintain the blockchain, are neither required to communicate
with the committees, nor are they required to post on the blockchain. To
demonstrate the practicality of the McFly protocol, we implemented ourSWE scheme and evaluated it on a standard laptop with Intel i7 @2,3
GHz. For the popular BLS12-381 curve, a 381-bit message and a committee of size 500 the encryption time is 9.8s and decryption is 14.8s. The
scheme remains practical for a committee of size 2000 with an encryption
time of 58s and decryption time of 218s.
⋆

Funded by the European Union (ERC, LACONIC, 101041207). Views and opinions
expressed are however those of the author(s) only and do not necessarily reflect thoseof the European Union or the European Research Council. Neither the European
Union nor the granting authority can be held responsible for them.

1Introduction

Blockchain protocols have become increasingly popular as they revolutionized
the way peer-to-peer transactions can be made. In their most basic form, blockchain protocols are run by independent parties, the so-called miners, that keep
their own copy of the blockchain and verify the contents of all transactions theyreceive before appending them to their own copy of the blockchain. The factthat the content of the transactions can be verified before its inclusion in theblockchain is fundamental to the validity of the transactions and the consistencyof the blockchain. However, there are many scenarios where one would like tokeep the contents of a transaction secret for some time even after inclusion in theblockchain. One simple example is running sealed-bid auctions on the blockchain;
one would like for its bid to be included in the blockchain, but at the same timesuch a bid should remain hidden until the end of the auction.4 Another example that recently became very relevant with the popularization of decentralizedexchanges (DEX) is the hurtful practice of transaction frontrunning, where malicious actors try to profit by taking advantage of possible market fluctuations
that could happen after some target transaction is added to the ledger. To exploit this, the adversary tries to get its own transaction included in the ledger
before the target transaction, by either mining the block itself and changing theorder of transactions, or by offering considerably more fees for its own transaction. Hiding parts of the content of the transactions until they are final in
the ledger would make it harder for adversaries to target those transactions forfrontrunning. A more general application for such a mechanism, that can keep
the contents of a blockchain transaction secret for some pre-defined time, would
be to simply use it as a tool to realize timed-release encryption [34] without atrusted third party.
In previous works [20,7], solutions to the problems above were based ontime-lock primitives, such as time-lock puzzles (TLP) or verifiable delay functions (VDF). An inherent problem of time-lock type primitives is that they arewasteful in terms of computational resources and notoriously difficult to instantiate with concrete parameters. Usually, a reference hardware is used to measure
the “fastest possible” time that it takes to solve a single operation of the puzzle(e.g., modular squaring) and this reference number is used to set the security
parameters. Moreover, in a heterogeneous and decentralized system such as a
blockchain, where different hardware can have gaps in speed of many orders ofmagnitude, an approach like this could render the system impractical. An operation that takes one time unit in the reference hardware could take 1000 timeunits on different hardware used in the system.
Moreover, the environmental problems that proof-of-work blockchains, whereminers invest computation power to create new blocks, can cause have been
intensively debated by the community and regulators. This made the majority
4

Clearly, the auction should run on an incentive-compatible transaction ledger, wheretransactions paying the required fees are guaranteed to be included in the ledger
within some fixed time.

2

of blockchain systems adopt a proof-of-stake (PoS) consensus for being a much
more sustainable solution. In PoS systems, typically a subset of users is chosen
as a committee, which jointly decides which blocks to include in the chain. This
selection can be by a lottery with winning probability proportional to the amountof coins parties hold on the chain or by the parties applying by locking a relatively
big amount of their coins, preventing them from spending them. In light of that,any solution employing a time-lock type primitive completely defeats the purposeof achieving a more resource-efficient and environmentally conscious system.

1.1

Our Contributions

In that vein, we diverge from the time-lock primitive approach and propose
McFly, an efficient protocol to keep the contents of a message (e.g., a blockchaintransaction) secret for some pre-specified time period. McFly is based on a newprimitive that we call signature witness encryption (SWE), that combined with abyzantine fault tolerance (BFT) blockchain or with any blockchain coupled witha finality layer such as Ethereum’s Casper [15] or Afgjort [21] allows users to
encrypt messages to a future point in time by piggybacking part of the decryption
procedure on the tasks already performed by the underlying committee of theblockchain (or the finality layer) - namely voting for and signing blocks. In BFT
blockchains this happens for every new potential block to reach consensus, while
in a finality layer this is done for blocks at regular intervals to make them “final”.
We detail our contributions next.
Signature Witness Encryption We formally define a new primitive that wecall signature-based witness encryption (SWE). To encrypt a message m, the encryption algorithm takes a set of verification keys for a (potentially aggregatable)
multi-signature scheme5 and a reference message r as an input and produces aciphertext ct. The witness to decrypt ct consists of a multi-signature of the reference message r under a threshold number of keys. Note that if the receiver of sucha ciphertext ct is external to the key holders, they may only observe and wait forthe signatures to be made; this is sensible in a setting where we expect parties
to sign the reference message naturally as a committee naturally signs blocks ona blockchain. We instantiate SWE with an aggregatable multi-signature schemethat is a BLS scheme [10] with a modified aggregation mechanism. We show, that
this signature scheme fulfills the same security notions as previous aggregatable
BLS multi-signatures.
Concretely, the guarantees for SWE are that (1) it correctly allows to decrypt a ciphertext given a multi-signature on the underlying reference and (2)if the adversary does not gain access to a sufficient number of signatures on
the reference then ciphertext-indistinguishability holds. The security guarantee
is conceptually closer related to that of identity-based encryption, rather than
5This type of signature schemes allows to compress multiple signatures by different
signers on the same messages into just one verifiable signature. In aggregatable
schemes, this works even on different messages.

3that of fully-fledged witness encryption; decryption is possible when a threshold number of key holders participate to unlock. We achieve this in the bilinear
group setting from the bilinear Diffie-Hellman assumption. Also, unlike general
witness encryption constructions [25] that are highly inefficient, we demonstrate
SWE to be practicable. Furthermore, to ensure that decryption is always possible
we make SWE verifiable by designing specially tailored proof systems to show
well-formedness of ciphertexts as well as additional properties of the encrypted
message.
McFly protocol We build an “encryption to the future” protocol by combining
SWE with a BFT blockchain or a blockchain finality layer. The main idea of thisis to leverage the existing committee infrastructure of the underlying blockchainthat periodically signs blocks in the chain to piggyback part of the decryption
procedure of the SWE scheme. At a high level, a message is encrypted withrespect to a specified block height of the underlying blockchain (representing
how far into the future the message should remain encrypted) and the set ofverification keys of all the committee members that are supposed to sign theblock at that height; once the block with the specified height is created by
the committee, it automatically becomes the witness required to decrypt the
ciphertext. We have the following requirements on the underlying blockchain:– BFT-style or finality layer. Every (final) block in the chain must be
signed by a committee of parties. These committees are allowed to be staticor dynamic, with the only requirement that the committee responsible forsigning a block at a particular height must be known some time in advance.
How much “time in advance” the committee is known is what we call horizon (following the nomenclature of [26]). For simplicity, we will explicitly
assume that all blocks are immediately finalized, but our results can be easily adapted to the more general setting where the height of the next final
block is known.
– Block structure. We assume that blocks have a predictable header, which
we will model by a block counter, and some data content. When finalizing a
block the committee signs the block as usual, but additionally, it also signs
the block counter separately.6– Public Key Infrastructure. The public keys of the committee members
must have a proof of knowledge. This can be achieved, e.g., by registering
the keys with a PKI.
– Honest majority committee.7 The majority of the committee behaves
honestly. That is, there will not be a majority of committee members colluding to prematurely sign blocks.
6

They use the same keys for this. This is safe whenever the underlying signature is ahash-and-sign scheme as is commonly the case.
7
The honest majority requirement must be strengthened to honest supermajority(i.e. at least 2/3 of members being honest) if the underlying blockchain or finality
layer considers a partially synchronous network model. For simplicity, we choose todescribe it in the synchronous network model where honest majority plus PKI issufficient.

4

– Constant block production rate. To have a meaningful notion of “wallclock time”, the blocks must be produced at a near constant rate.
To model the requirements above, we present a blockchain functionality in Appendix F and later we show the security of the McFly protocol in this hybrid
model. For concreteness, we informally discuss in Section 3.3 how a modified
version of Ethereum 2.0 running with Casper “The friendly finality gadget” [15]satisfies our blockchain functionality. Intuitively, to make Ethereum 2.0 compatible with our model we only need to add the public key infrastructure andrequire the committee members to sign a block counter separately for each finalized block. This enables encryption up to the horizon where a future committee isalready known. Unfortunately, in Ethereum 2.0 this leads to a maximum horizonof 12.8 minutes. If we use “sync committees” instead, which were only introducedin Ethereum Altair [14], we can have a horizon of up to 27 hours. However, it isunclear whether sync committees enjoy the same level of trust as standard ones.
Implementation To demonstrate the practicality of McFly, we implement the
SWE scheme and run a series of benchmarks on a standard Macbook Pro withan Intel i7 processor @2,3 GHz. In Appendix B we show that for the popular
BLS12-381 curve, it is possible to encrypt 381-bit messages in under 1 minutefor even up to 2000 verification keys, i.e. committee size. For the same setting,decrypting takes only around 4 minutes. In the case of a supermajority threshold,the encryption time remains the same but the decryption time increases, as to be
expected, to around 6 minutes. Lowering the size of the verification key set to 500
increases the efficiency. The same message can now be encrypted in 10 seconds.
Depending on the threshold decryption takes 14.6 seconds for the majority ofsigners and 26.6 seconds for the supermajority of signers. For small committees≤ 200 we even get encryption and decryption times smaller than 5 seconds. We
stress that our results should be treated as a baseline since we used JavaScript,
and any native implementation of the SWE scheme will significantly outperform
our prototype.
1.2

Technical Overview

As detailed above, the key ingredient and main technical challenge of the McFly
protocol is Signature Witness Encryption (SWE). In the following, we will provide an outline of our construction of practically efficient SWE.
SWE based on BLS Our construction of Signature-based Witness Encryption
is based on the BLS signature scheme [11] and its relation to identity-based
encryption [9]. Recall that BLS signatures are defined over a bilinear group, i.e.
we have 3 groups G1 , G2 , GT (with generators g1 , g2 , gT ) of prime-order p andan efficiently computable bilinear map e : G1 × G2 → GT . A verification key vk
is of the form vk = g2x , where x ∈ Zp is the corresponding signing key. To sign amessage T ∈ {0, 1}∗ , we compute σ = H(T )x , where H : {0, 1}∗ → G1 is a hashfunction (which is modeled as a random oracle in the security proofs). To verify
a signature σ for a message T , all we need to do is check whether e(σ, g2 ) =e(H(T ), vk). The BLS signature scheme is closely related to the identity-based5encryption scheme of Boneh and Franklin [9]. Specifically, in the IBE schemeof [9] BLS verification keys take the role of the master public key, the signing
key takes the role of the master secret key and signatures take the role of identity
secret keys, where the signed messages correspond to the identities, respectively.
In this sense, the BF scheme can be seen as a witness encryption scheme thatallows to encrypt plaintexts m with respect to a verification key vk and a message
T , such that anyone in possession of a valid signature of T under vk will be able
to decrypt the plaintext m. Specifically, we can encrypt a message m ∈ {0, 1}
by computing ct = (g2r , e(H(T ), vk)r · gTm ). Given a signature σ = H(T )x , wecan decrypt a ciphertext ct = (c1 , c2 ) by computing d = c2 /e(σ, c1 ) and taking
the discrete logarithm of d with respect to gT (which can be done efficiently asm ∈ {0, 1}).
SWE for BLS Multi-Signatures The BLS scheme can be instantiatedas an aggregatable multi-signature scheme [10]. Specifically, assume that fori = 1, . . . , n we have messages Ti with a corresponding signature σi with respect to a verification key vki . Then we can combine
Qn the signatures σ1 , . . . , σninto a single compact aggregate signature σ = i=1Qσi . Verifying such a signnature can be done by checking whether e(σ, g2 ) = i=1 e(H(Ti ), vki ), where
correctness follows routinely. We can adapt the BF IBE scheme to aggregate
signatures in a natural way: To encrypt a plaintext m ∈ {0, 1} to messages
T1 , . . . , Tn and corresponding
verification keys vk1 , . . . , vkn compute a cipherQn
text ct via ct = (g2r , ( i=1 e(H(Ti ), vki ))r · gTm ). Such a ciphertext ct = (c1 , c2 )can be decrypted analogously to the above by computing d = c2 /e(σ, c1 ) andtaking the discrete logarithm with respect to gT . To decrypt ct we need an aggregate signature σ of all Ti under their respective verification keys vki . For
our envisioned applications this requirement is too strong, instead, we need athreshold scheme where a t-out-of-n aggregate signature suffices as a witness todecrypt a ciphertext. Thus, we will rely on Shamir’s secret sharing scheme [35]to implement a t-out-of-n access structure. This, however, leads to additional
challenges. Recall that Shamir’s secret sharing scheme allows us to share a message r0 ∈ Zp into shares s1 , . . . , sn ∈ Zp , such that r0 can be reconstructed
via a (public) linear combination of any t of the si , while on the other hand,
any set of less than t shares si reveals no information about r0 . The coefficients
Lij of the linear combination required to reconstruct r0 from a set of sharessi1 , . . . , sit (for indices i1 , . . . , it ) can be obtained from a corresponding
set ofPt
Lagrange polynomials. Given such Lij , we can express r0 as r0 = j=1 Lij sij .
We can now modify the above SWE scheme for aggregate signatures as follows. To encrypt a plaintext m ∈ {0, 1}, we first compute a t-out-of-n secretsharing s1 , . . . , sn of the plaintext m. The ciphertext ct is then computed by
ct = (g2r , (e(H(Ti ), vki )r · gTsi )i∈[n] ). Security of this scheme can be establishedfrom the same assumption as the BF IBE scheme, namely from the bilinear
Diffie-Hellman (BDH) assumption [28]. We would now like to be able to decrypt
such a ciphertext using an aggregate signature. For this purpose, however, we will
have to modify the aggregation procedure of the aggregatable multi-signaturescheme. Say we obtain t-out-of-n signatures σij , where σij is a signature of Tij
6

under vkij . Let Lij be the corresponding Lagrange coefficients. Our new aggreQt
Ligation procedure computes σ = j=1 σij j . That is, instead of merely taking the
product of the σij we need to raise each σij to the power of its corresponding
Lagrange coefficient Lij . We can show that this modification does not hurt the
security of the underlying aggregatable BLS multi-signature scheme. To decrypta ciphertext ct = (c0 , c1 , . . . , cn ) using such an aggregate signature σ, we comQt
Lipute d = j=1 cij j /e(σ, c0 ) and take the discrete logarithm of d with respect togT . Correctness follows via a routine calculation.
Moving to the Source Group While the above scheme provides our desired
functionality, implementing this scheme leads to a very poor performance profile.
There are two main reasons: (1) Each ciphertext encrypts just a single bit. Thus,
to encrypt any meaningful number of bits we need to provide a large number of
ciphertexts. Observe that each ciphertext contains more than n group elements.
Thus, encrypting k bits would require a ciphertext comprising kn group elements,
which would be prohibitively large even for moderate values of k and n. (2) Bothencryption and decryption rely heavily on pairing operations and operations in
the target group. From an implementation perspective, pairing operations andoperations in the target group are typically several times slower than operations
in one of the source groups (see Appendix B).
To address these issues, we will design a scheme that both allows for ciphertext
packing and shifts almost all group operations into one of the two source groups(in our case this will be G2 ). This scheme is provided in Section 2.1 and we will
only highlight a few aspects here.
– Instead of computing a secret sharing of the plaintext m, we compute a secretsharing of a random value r0 ∈ Zp . The value r0 can be used to randomize
many batch-ciphertext components, leading to ciphertexts comprising onlyO(k + n) group elements.
– We encrypt each share si in the source group G2 instead of GT . That is,
we compute the ciphertext-component ci via ci = vkri · g2si . This necessitates a corresponding modification of the decryption algorithm and requiresthat all messages Ti are identical, but this requirement is compatible with
our envisioned applications. Somewhat surprisingly, this modification does
not necessitate making a stronger hardness assumption, but only requires arather intricate random-self-reduction procedure in the security proof. Thatis, even with this modification we can still rely on the hardness of the standard BDH assumption.
– Instead of just encrypting single bits m ∈ {0, 1}, we allow the message mto come from {0, . . . , 2k − 1}. This will allow us to pack k bits into eachciphertext component. Recall that decryption requires the computation ofa discrete logarithm with respect to a generator gT . We can speed up thiscomputation by relying on the Baby-Step-Giant-Step (BSGS) algorithm [37]to O(2k/2 ) group operations. This leads to a very efficient implementation
as the required discrete logarithm table for the fixed generator gT can beprecomputed. For details see Appendix B.
7

A Compatibility-Layer for Efficient Proof Systems Our scheme so far
assumes that encryptors behave honestly, i.e. the ciphertext ct is well-formed.
A malicious encryptor, however, may provide ciphertexts that do not decrypt
consistently, i.e. the decrypted plaintext m may depend on the signature σ used
for decryption. Furthermore, for several of the use cases, we envision it is crucial to ensure that the encrypted message m satisfies additional properties. To
facilitate this, we provide the following augmentations.
– We provide an efficient NIZK proof8 in the ROM which ensures that ciphertexts decrypt consistently, i.e. the result of decryption does not depend on
the signature which is used for decryption. This is provided in Appendix D.1.
– We augment ciphertexts with efficient proof-system enabled commitments
and provide very efficient plaintext equality proofs in the ROM. In essence,
we provide an efficient NIZK proof system that allows to prove that a ciphertext ct and a Pedersen commitment C commit to the same value. Thisis discussed in Appendix D.2.
– We can now rely on efficient and succinct proof systems such as Bulletproofs [13] to establish additional guarantees about the encrypted plaintext.
For instance, we can rely on the range-proofs of [13] to ensure that theencrypted messages are within a certain range to ensure that our BSGS decryption procedure will recover the correct plaintext. This is discussed inAppendix D.3.
To make this construction efficient, we include additional homomorphic commitments into SWE ciphertexts.
Related work. Due to lack of space, we defer the related work section toAppendix A.
Preliminaries and cryptographic building blocks. Due to lack of space, wedefer the preliminaries and cryptographic building blocks section to Appendix E.

2

Signature-based Witness Encryption

In this section we introduce the new cryptographic primitive SWE that is thecore technical component of the McFly protocol. We formally define it next.
Definition 1 (Signature-based Witness Encryption). A t-out-of-n SWE
for an aggregate signature scheme Sig = (KeyGen, Sign, Vrfy, Agg, AggVrfy, Prove,
Valid) is a tuple of two algorithms (Enc, Dec) where:– ct ← Enc(1λ , V = (vk1 , . . . , vkn ), (Ti )i∈[ℓ] , (mi )i∈[ℓ] ): Encryption takes as input a set V of n verification keys of the underlying scheme Sig, a list ofreference signing messages Ti and a list of messages mi of arbitrary lengthℓ ∈ poly(λ). It outputs a ciphertext ct.
8

Technically speaking, since our systems are only computationally sound, we provide
non-interactive argument systems. However, to stay in line with the terminology of[24,13] we refer to them as proof systems.

8

– m ← Dec(ct, (σi )i∈[ℓ] , U, V ): Decryption takes as input a ciphertext ct, a listof aggregate signatures (σi )i∈[ℓ] and two sets U, V of verification keys of theunderlying scheme Sig. It outputs a message m.
We require such a scheme to fulfill two properties: robust correctness andsecurity. The idea is to model fine-grained access; When we encrypt messages
mi under reference messages Ti , then we can decrypt mind at a specific index ind
iff we get an aggregated signature of Tind under at least t keys for that index.
Definition 2 (Robust Correctness). A t-out-of-n SWE scheme SWE =(Enc, Dec) for an aggregate signature scheme Sig = (KeyGen, Sign, Vrfy, Agg,
AggVrfy, Prove, Valid) is correct if for all λ ∈ N and ℓ = poly(λ) there is no PPT
adversary A with more than negligible probability of outputting an index ind ∈ [ℓ],a set of keys V = (vk1 , . . . , vkn ), a subset U ⊆ V with |U | ≥ t, message lists(mi )i∈[ℓ] , (Ti )i∈[ℓ] and signatures (σi )i∈[ℓ] , such that AggVrfy(σind , U, (Tind )i∈[|U |] ) =1, but Dec(Enc(1λ , V, (Ti )i∈[ℓ] , (mi )i∈[ℓ] ), (σi )i∈[ℓ] , U, V )ind ̸= mind .
Definition 3 (Security). A t-out-of-n SWE scheme SWE = (Enc, Dec) for an
aggregate signature scheme Sig = (KeyGen, Sign, Vrfy, Agg, AggVrfy, Prove, Valid)
is secure if for all λ ∈ N, such that t = poly(λ), and all ℓ = poly(λ), subsets
SC ⊆ [ℓ], there is no PPT adversary A that has more than negligible advanA
λtage in the experiment
Sec (A, 1 ). We define A’s advantage by AdvSec =
 Exp
1
λ
| Pr ExpSec (A, 1 ) = 1 − 2 |.
Experiment ExpSec (A, 1λ )1. Let Hpr be a fresh hash function from a keyed family of hash functions,available to the experiment and A.
2. The experiment generates n − t + 1 key pairs for i ∈ {t, . . . , n} as (vki , ski ) ←Sig.KeyGen(1λ ) and provides vki as well as Sig.ProveHpr (vki , ski ) for i ∈{t, . . . , n} to A.
3. A inputs V C = (vk1 , . . . , vkt−1 ) and (π1 , . . . , πt−1 ). If for any i ∈ [t − 1],
Sig.Valid(vki , πi ) = 0, we abort. Else, we define V = (vk1 , . . . , vkn ).
4. A gets to make signing queries for pairs (i, T ). If i < t, the experiment aborts,
else it returns Sig.Sign(ski , T ).
5. The adversary announces challenge messages m0i , m1i for i ∈ SC, a list of
messages (mi )i∈[ℓ]\SC and a list of signing reference messages (Ti )i∈[ℓ] . If asignature for a Ti with i ∈ SC was previously queried, we abort.
6. The experiment flips a bit b ←$ {0, 1}, sets mi = mbi for i ∈ SC and sends
Enc(1λ , V, (Ti )i∈[ℓ] , (mi )i∈[ℓ] ) to A.
7. A gets to make further signing queries for pairs (i, T ). If i ≥ t and T ̸= Ti
for all i ∈ SC, the experiment returns Sig.Sign(ski , T ), else it aborts.
8. Finally, A outputs a guess b′ .
9. If b = b′ , the experiment outputs 1, else 0.

Definition 4 (Verifiable Signature-based Witness Encryption). A scheme
SWE = (Enc, Dec, Prove, Vrfy) is a verifiable SWE for relation R, if Enc, Dec are
9as above and Prove, Vrfy are a NIZK proof system for a language given by thefollowing induced relation R′ , where V = (vk1 , . . . , vkn ) is a set of keys:(V,(Ti )i∈[ℓ] , ct), ((mi )i∈[ℓ] , w, r)) ∈ R′ ⇔ct = Enc(1λ , V, (Ti )i∈[ℓ] , (mi )i∈[ℓ] ); r) and (m =X

2(i−1)k mi , w) ∈ R

i∈[ℓ]

2.1

Construction

In the following, we describe a t-out-of-n SWE. Let two base groups G1 , G2 ofprime order p with generators g1 , g2 which have a bilinear map e : G1 ×G2 → GT
into a target group GT with generator g. Also, we assume full-domain hashfunctions H : {0, 1}∗ → G1 , H2 : {0, 1}∗ → Zp and Hpr : {0, 1}∗ → Zp .
Let Sig′ be our modified aggregate multi-signature based on BLS as describedin Section 1.2 with (Sig′ .Prove, Sig′ .Vrfy) being the non-interactive variant of thewell-known Schnorr proofs due to Fischlin [24]. This is to provide an onlineextractable proof-of-knowledge showing that a key issuer actually possesses thesecret key. The full construction and proofs, that Sig′ is in fact an aggregate
multi-signature can be found in Appendix I due to space reasons.
Protocol SWE for signature scheme Sig′
SWE.Enc(1λ , (vkj )j∈[n] , (Ti )i∈[ℓ] , (mi )i∈[ℓ] ):– Choose random
P r, rj ←j$ Zp for j ∈ {0, . . . , t − 1} .
– Let f (x) = t−1
j=0 rj · x . This will satisfy f (0) = r0 .
– For j ∈ [n], set ξj = H2 (vkj ), sj = f (ξj ).
– Compute c = g2r .
– Choose h ← G2 uniformly at random.
– Compute c0 = hr · g2r0 .
s– For j ∈ [n], compute cj = vkrj · g2j .
r0′– For i ∈ [ℓ], set ci = e(H(Ti ), g2 ) · gTmi .
– Output ct = (h, c, c0 , (cj )j∈[n] , (c′i )i∈[ℓ] ).
SWE.Dec(ct, (σi )i∈[ℓ] , U, V ):– Parse ct = (h, c, c0 , (cj )j∈[n] , (c′i )i∈[ℓ] ).
– Parse V = (vk1 , . . . , vkn ), U = (vk′1 , . . . , vk′k ).
– If k < t or U ̸⊆ V , abort.
– Define as I the indices j ∈ [n] s.t. vkj ∈ U .
– Compute ξj = H
Q2 (vkj ) for ji ∈ I.
– Compute Lj = i∈I,i̸=j ξj−ξ
for j ∈ I.
−ξi
Q
Lj
∗
– Compute c = j∈I cj .
– For i ∈ [ℓ], computezi = c′i · e(σi , c)/e(H(Ti ), c∗ ).
– For i ∈ [ℓ], compute m′i = dloggT (zi ).
– Output (m′i )i .

10

Notice, that we only do the expensive computation of c∗ in SWE.Dec once.9
Further, we require that all messages Ti are from the range {0, . . . , 2k − 1} forsome k to enable efficient discrete log computation via the baby-step giant-stepmethod (see Appendix B).
Adding Verifiability Following the outline given in Section 1.2, we can construct two efficient algorithms SWE.Prove, SWE.Vrfy that complete SWE to beverifiable for a given relation R. Full details of the algorithms and proofs arefound in Appendix D. We will briefly discuss how this is enabled by our choices
in Enc, Dec.
A critical part of the construction is, that we add a proof-system-friendly
Pedersen commitment C to ct and provide an efficient NIZK proof guaranteeingthat they encrypt the same value. This is enabled by us making the domains
match, as we choose mi from Zp . Further, the redundant terms h and c0 are
included to essentially make the ciphertext a statistically binding commitment(see Appendix D.2, in fact, part of ct constitutes a homomorphic commitment).
Security properties SWE = (Enc, Dec, Prove, Vrfy) as above fulfills the requirements for a signature-based witness encryption stated in Section 2.
Theorem 1. The following statements hold:
1. SWE for the signature scheme Sig′ has robust correctness, given that H2 iscollision resistant.
2. Assume that the hash functions H, H2 , Hpr are modelled as random oracles.
Then SWE for the signature scheme Sig′ is secure under the BDH assumptionin (G1 , G2 ). The security reduction is tight.
3. SWE.Prove, SWE.Vrfy extend SWE to be a verifiable SWE.
We show statements 1,2 in Appendix J and statement 3 in Appendix D. In
our proof of unforgeability of Sig′ , we use the extractability of Schnorr to extract
secret keys for all keys registered by the adversary. We use them to remove all
but one signatures (by re-creating and dividing them out) from the aggregate
signature. This last signature will constitute a forgery under regular BLS, which
implies breaking the computational Co-Diffie-Hellman assumption. In the proofof security of SWE, we build a simulation of the experiment, which is distributed
exactly like the real experiment if given a BDH tuple g1x , g2x , g1α , g2r , gTαxr , butwhich has an output which is independent of the encrypted message if given
a random tuple. We also use extractability of the proof of knowledge, to gain
access to the adversary’s private keys in the simulation.
Efficiency of SWE Our construction is specifically optimized to push as many
operations as possible into the source group G2 . This leads to significant performance improvements over a naive approach if we choose G2 to be the one of
the two source groups with cheaper group operations. Below, we briefly analyze
the number of group operations in each group required for encryption and decryption. We regard the numbers n, ℓ to be fixed and give upper bounds on the9

In case the sets of signers are the same for all Ti . Otherwise we compute it once per
relevant set U of signers.

11

operations needed. We need no multiplications or exponentiations in G1 . Notealso, that the extraction of the discrete logarithm does not cause a large overhead
as we use the baby-step giant-step methodology (compare Appendix B).
encryption decryption
evaluations of H, H2
ℓ, n
ℓ, n
multiplications, exponentiations in G2 n, 2 + 2n n − 1, n
multiplications, exponentiations in GT
ℓ, ℓ
2ℓ, 0
ℓ
2ℓ
pairing evaluations
dlog in GT
0ℓ3

The McFly protocol

In this section, we describe how to build a general-purpose time-release encryption mechanism, that we call McFly, by integrating a verifiable signature-based
witness encryption SWE with a blockchain. The time-release mechanism is available to all users of the underlying blockchain.
3.1

Formal model and guarantees

In Appendix F we introduce a simplified model for blockchains in the form of
the BC λ,H functionality reflecting the requirements introduced in Section 1.1.
Protocol guarantees Let L0 be an NP language defined by relation R0 via
m ∈ L0 ⇔ ∃w s.t. (m, w) ∈ R0 . Our protocol McFly consists of five algorithms(Setup, Enc, Dec, Prove, Vrfy) in a hybrid model where access to the public interface of the functionality BC = BC λ,H is assumed with committee size n = poly(λ)
and corruption threshold c < n/2. The syntax of these algorithms is as follows:
CRS ← Setup(1λ ): Setup takes a security parameter λ. It outputs a common
reference string CRS.
ct ← EncBC (1λ , m, d): Encryption takes a security parameter λ, a message mand an encryption depth d. It outputs a ciphertext ct.
m ← DecBC (ct, d): Decryption takes a ciphertext ct and an encryption depth
d. It outputs a message m.
π ← ProveBC (1λ , CRS, ct, m, d, w0 , r): The proving algorithm takes a security
parameter λ, CRS, a message m, an encryption depth d, a witness w0 and
randomness r. It outputs a proof π.
b ← VrfyBC (CRS, ct, π, d): The verification algorithm takes CRS, a ciphertext
ct, a proof π and an encryption depth d. It outputs a bit b.
We prove the following security guarantees for McFly, which are inspired bytraditional time-lock puzzles:
Definition 5 (Correctness). A protocol McFly = (Setup, Enc, Dec, Prove, Vrfy)
is correct, if for any parameter λ, message m, depth d, and algorithm A running
the adversarial interface in BC, if ct ← EncBC (1λ , m, d) is run at any point and
McFly.DecBC (ct, d) is run, when the number of finalized blocks BC.QueryTime isat least d, it will output m, except with negligible probability.
12Definition 6 (Security). A protocol McFly = (Setup, Enc, Prove, Vrfy, Dec) is
secure, if for any parameter λ and committee size n = poly(λ), corruption threshold c < n/2 there is no P P T adversary A with more than negligible advantage
1
′
λ
AdvA
Lock = | Pr [b = b ] − 2 | in the experiment ExpLock (A, 1 ).
Experiment ExpLock (A, 1λ )1. The experiment computes CRS ← Setup(1λ ) and outputs it to A.
2. A gets to use the adversarial interface in BC, which is run by the experiment.
3. At some point, A sends two challenge messages m0 , m1 and a depth d > 0.
|m0 | = |m1 | must hold.
4. The experiment draws b ←$ {0, 1}.
5. Run ct ← EncBC (1λ , mb , d) and send ct to A.
6. A can submit a bit b′ at any point while ctr < d in BC
7. Once ctr ≥ d on BC with no prior input from A, b′ ←$ {0, 1} is set instead.

Remark. There are two different points in time that are used in these guarantees- When ctr is incremented, can be seen as the point in time when it is clearthat the committee has reached agreement, and that a new finalized block will
be added. When the aggregated signature is added to T symbolizes the point
in time when the finalized block (including the committee signatures) becomes
available to all honest users on the blockchain (even outside of the committee).
For reference compare to our blockchain model in Appendix F. We point out
that our synchronous network model guarantees that all honest parties receive
the messages of other honest parties by the end of each round. However, the bestpractical guarantee that we can hope to achieve is that an adversary corrupting
up to n/2 − 1 committee members is unable to decrypt a ciphertext before
seeing any honest member’s signature. However, this might occur before a blockis made available to honest users. In practice, such a gap exists naturally, as
we also need to account for communication and network delay. We additionallyrequire a verifiability property:
Definition 7 (Verifiability). A protocol McFly = (Setup, Enc, Dec, Prove, Vrfy)
is verifiable for an NP language L0 with witness relation R0 , if (Prove, Vrfy) is
a NIZK proof system for a language L′ given by the following induced relation
R′ :(V =(vk1 , . . . , vkn ), d, ct), (m, r, w0 )) ∈ R′ ⇔ct = McFly.Enc(1λ , m, d; r, V ) ∧ (m, w0 ) ∈ R0 .
Here, Enc(. . . ; r, V ) denotes, that the randomness used is r and the keys
obtained from the blockchain are V . Note that this guarantees that (1) a receiverof a verifying pair (ct, π) can be sure to retrieve an output in L0 after block d
was made and (2) outputting π alongside ct reveals no further information.
13

3.2

Protocol description

Let COM = (Setup, Commit, Vrfy) be a Pedersen commitment, H be the hashfunction in BC and H2 be another hash function. H, H2 are implicitly madeavailable in all calls to SWE, which is set up for parameters t = n/2 out of n. k
is the upper bound on the message lengths for SWE10 . We now describe McFly:
Protocol McFly
Setup(1λ ): Return COM.Setup(1λ ).
McFly.EncBC (1λ , m, d):– Get the keys V by calling QueryKeys to BC.
– Split m = (mi )i∈[ℓ] where mi are from {0, . . . , 2k − 1} with m =P(i−1)kmi .
i∈[ℓ] 2– ct ← SWE.Enc(1λ , V, (H(d))i∈[ℓ] , (mi )i∈[ℓ] ).
– Output ct.
McFly.DecBC (ct, d):– If QueryTime returns less than d, abort.
– Get (σ, U ) by calling (QueryAt, d) and V by calling QueryKeys to BC.
– Call (mi )i∈ℓ ← SWE.Dec(ct, (σ)i∈[ℓ] , U, V ).
P
– Output m = i∈[ℓ] 2(i−1)k mi .
McFly.ProveBC (1λ , CRS, ct, m, d, w0 , r):– Get the keys V by calling QueryKeys
to BC.
P– Split m = (mi )i∈[ℓ] s.t. m = i∈[ℓ] 2(i−1)k mi .
– Output π ← SWE.Prove(CRS, V, (H(d))i∈[ℓ] , ct, (mi )i∈[ℓ] , w0 , r).
McFly.VrfyBC (CRS, ct, π, d):– Get the keys V by calling QueryKeys to BC.
– Output b ← SWE.Vrfy(CRS, V, (H(d))i∈[ℓ] , ct, π)Theorem 2. McFly is correct, given that SWE has robust correctness. McFly issecure given that SWE is secure and H is collision resistant. McFly is verifiable,
given that SWE is a verifiable SWE.
The proofs of correctness and security are deferred to Appendix H due tospace reasons. The proof of verifiability follows immediately by the definition of
McFly.Enc and verifiability of SWE′ .
Extension for dynamic committees In our model, we assumed static committees. However, finality layers advocate for a short-lived dynamic committee [22], as committee members usually become targets of attacks. We can safely
regard a committee as known and static during its lifetime. Thus, our model
naturally extends as long as we only encrypt messages as far into the future as
the committees are currently known.
10

The size limit is required for efficient decryption, see Section 2

14

3.3

Integration with Casper

As a concrete example, we discuss the modifications necessary to the Ethereum
2.0 Altair [27] protocol running with the Casper finality layer [15]. In the Casper
protocol [15] the committees are randomly sampled and become responsible forfinalizing blocks for some period of time, called an epoch. The members of thecommittee can cast votes on the blocks they believe to be final by signing theblocks using their signing keys. Once a majority of the committee votes on thesame block it becomes final. As new committees are chosen only one epoch inadvance and each epoch lasts for about 6.4 minutes, we can at most encrypt to12.8 minutes into the future. Moreover, a final block is only produced roughly
after every epoch duration. So while we have a near-constant block production
rate, the horizon choice is essentially limited to the start of the next epoch. However, an extension of the above is possible in the current version of Ethereum
Altair [27,14]. There, the so-called sync committees have a lifetime of roughly
27 hours and are appointed “one round” in advance.11 These committees periodically sign the header of the newest block to enable faster verification for lightclients. We believe that a horizon of 27 hours is sufficient for most applications,
including the ones we describe in Appendix C. We stress however that the security implications for the concept of sync committees were not formally analyzed
in Ethereum Altair [27,14].
We describe the modifications needed on Ethereum 2.0 in order to instantiate
McFly on top of it:– Since Casper already uses BLS signatures, there are two possible alternatives.
(1) The committee of Casper adopts the aggregation mechanism describedin Appendix I, or (2) decryptors obtain the unaggregated signatures themselves (which is already possible with the Ethereum beacon chain).12 In thelatter case, signature aggregation can be performed locally at the decryptor
and hence no modifications are necessary. One could also envision dedicatedaggregation servers when the system is widely adopted.
– For each finalized block the (sync) committee additionally signs a counter rthat represents the number of finalized blocks (or slot number).
– The public keys of the committee members must have a proof of knowledge.
This can be achieved, e.g., by registering the keys with a PKI.

3.4

Applications

In Appendix C we discuss in more details two applications that can immediately
take advantage of McFly: Decentralized auctions and randomness beacons.
11
12

When a new sync committee becomes active, the next one is sampled.
See https://github.com/ethereum/consensus-specs/blob/dev/specs/phase0/p2p-interface.md#attestation-subnets

15

References
1. Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, L.: Secure multiparty computations on bitcoin. In: 2014 IEEE Symposium on Security and Privacy.
pp. 443–458. IEEE Computer Society Press (May 2014). doi: 10.1109/SP.2014.35
2. Baum, C., David, B., Dowsley, R., Nielsen, J.B., Oechsner, S.: TARDIS: Time andrelative delays in simulation. Cryptology ePrint Archive, Report 2020/537 (2020),
https://eprint.iacr.org/2020/537
3. Bellare, M., Neven, G.: New multi-signature schemes and a general forking lemma(2017)
4. Bellare, M., Palacio, A.: The knowledge-of-exponent assumptions and 3-round zeroknowledge protocols. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp.
273–289. Springer, Heidelberg (Aug 2004). doi: 10.1007/978-3-540-28628-8_17
5. Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designingefficient protocols. In: Denning, D.E., Pyle, R., Ganesan, R., Sandhu, R.S., Ashby,
V. (eds.) ACM CCS 93. pp. 62–73. ACM Press (Nov 1993). doi: 10.1145/168588.
168596
6. Benhamouda, F., Gentry, C., Gorbunov, S., Halevi, S., Krawczyk, H., Lin, C.,
Rabin, T., Reyzin, L.: Can a public blockchain keep a secret? In: Pass, R., Pietrzak,
K. (eds.) TCC 2020, Part I. LNCS, vol. 12550, pp. 260–290. Springer, Heidelberg(Nov 2020). doi: 10.1007/978-3-030-64375-1_10
7. Boneh, D., Bonneau, J., Bünz, B., Fisch, B.: Verifiable delay functions. In:
Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part I. LNCS, vol. 10991, pp.
757–788. Springer, Heidelberg (Aug 2018). doi: 10.1007/978-3-319-96884-1_25
8. Boneh, D., Drijvers, M., Neven, G.: Compact multi-signatures for smaller
blockchains. In: Peyrin, T., Galbraith, S. (eds.) Advances in Cryptology – ASIACRYPT 2018. pp. 435–464. Springer International Publishing, Cham (2018)
9. Boneh, D., Franklin, M.K.: Identity-based encryption from the Weil pairing. In:
Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg(Aug 2001). doi: 10.1007/3-540-44647-8_13
10. Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: Biham, E. (ed.) EUROCRYPT 2003.
LNCS, vol. 2656, pp. 416–432. Springer, Heidelberg (May 2003). doi: 10.1007/
3-540-39200-9_26
11. Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. In:
Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (Dec 2001). doi: 10.1007/3-540-45682-1_30
12. Boneh, D., Naor, M.: Timed commitments. In: Bellare, M. (ed.) CRYPTO 2000.
LNCS, vol. 1880, pp. 236–254. Springer, Heidelberg (Aug 2000). doi: 10.1007/
3-540-44598-6_15
13. Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs:
Short proofs for confidential transactions and more. In: 2018 IEEE Symposium on
Security and Privacy. pp. 315–334. IEEE Computer Society Press (May 2018). doi:
10.1109/SP.2018.00020
14. Buterin, V.: Hf1 proposal, https://notes.ethereum.org/@vbuterin/HF1_
proposal
15. Buterin, V., Griffith, V.: Casper the friendly finality gadget (2019)
16. Camenisch, J., Kiayias, A., Yung, M.: On the portability of generalized Schnorr
proofs. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 425–442.
Springer, Heidelberg (Apr 2009). doi: 10.1007/978-3-642-01001-9_25

1617. Campanelli, M., David, B., Khoshakhlagh, H., Konring, A., Nielsen, J.B.: Encryption to the future: A paradigm for sending secret messages to future (anonymous) committees. Cryptology ePrint Archive, Report 2021/1423 (2021), https://ia.cr/2021/1423
18. Cathalo, J., Libert, B., Quisquater, J.J.: Efficient and non-interactive timed-release
encryption. In: Qing, S., Mao, W., López, J., Wang, G. (eds.) ICICS 05. LNCS,
vol. 3783, pp. 291–303. Springer, Heidelberg (Dec 2005)
19. Cheon, J.H., Hopper, N., Kim, Y., Osipkov, I.: Provably secure timed-release public
key encryption 11(2) (2008). doi: 10.1145/1330332.1330336, https://doi.org/
10.1145/1330332.1330336
20. Deuber, D., Döttling, N., Magri, B., Malavolta, G., Thyagarajan, S.A.K.: Minting
mechanism for proof of stake blockchains. In: Conti, M., Zhou, J., Casalicchio, E.,
Spognardi, A. (eds.) ACNS 20, Part I. LNCS, vol. 12146, pp. 315–334. Springer,
Heidelberg (Oct 2020). doi: 10.1007/978-3-030-57808-4_16
21. Dinsdale-Young, T., Magri, B., Matt, C., Nielsen, J.B., Tschudi, D.: Afgjort: A
partially synchronous finality layer for blockchains. Cryptology ePrint Archive,
Report 2019/504 (2019), https://ia.cr/2019/504
22. Dinsdale-Young, T., Magri, B., Matt, C., Nielsen, J.B., Tschudi, D.: Afgjort: A
partially synchronous finality layer for blockchains. In: Galdi, C., Kolesnikov, V.
(eds.) SCN 20. LNCS, vol. 12238, pp. 24–44. Springer, Heidelberg (Sep 2020). doi:
10.1007/978-3-030-57990-6_2
23. ethereum.org: Ethereum 2.0 keys (2022), https://kb.beaconcha.in/
ethereum-2-keys
24. Fischlin, M.: Communication-efficient non-interactive proofs of knowledge with
online extractors. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 152–
168. Springer, Heidelberg (Aug 2005). doi: 10.1007/11535218_10
25. Garg, S., Gentry, C., Sahai, A., Waters, B.: Witness encryption and its applications.
In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) 45th ACM STOC. pp. 467–
476. ACM Press (Jun 2013). doi: 10.1145/2488608.2488667
26. Gentry, C., Halevi, S., Krawczyk, H., Magri, B., Nielsen, J.B., Rabin, T., Yakoubov, S.: YOSO: You only speak once - secure MPC with stateless ephemeral
roles. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021, Part II. LNCS, vol.
12826, pp. 64–93. Springer, Heidelberg, Virtual Event (Aug 2021). doi: 10.1007/
978-3-030-84245-1_3
27. Altair the beacon chain, https://github.com/ethereum/consensus-specs/blob/
dev/specs/altair/beacon-chain.md
28. Joux, A.: A one round protocol for tripartite diffie–hellman. In: International algorithmic number theory symposium. pp. 385–393. Springer (2000)
29. Lenstra, A.K., Wesolowski, B.: A random zoo: sloth, unicorn, and trx. Cryptology
ePrint Archive, Report 2015/366 (2015), https://eprint.iacr.org/2015/366
30. Liu, J., Jager, T., Kakvi, S.A., Warinschi, B.: How to build time-lock encryption. Des. Codes Cryptogr. 86(11), 2549–2586 (2018). doi: 10.1007/
s10623-018-0461-x, https://doi.org/10.1007/s10623-018-0461-x
31. Miller, P.: micro-bmark (2022), https://github.com/paulmillr/micro-bmark
32. Miller,P.:
noble-bls12-381(2022),
https://github.com/paulmillr/
noble-bls12-381
33. Ristenpart, T., Yilek, S.: The power of proofs-of-possession: Securing multiparty
signatures against rogue-key attacks. In: Naor, M. (ed.) EUROCRYPT 2007.
LNCS, vol. 4515, pp. 228–245. Springer, Heidelberg (May 2007). doi: 10.1007/
978-3-540-72540-4_13

1734. Rivest, R.L., Shamir, A., Wagner, D.A.: Time-lock puzzles and timed-release
crypto. Tech. rep., Massachusetts Institute of Technology, USA (1996)
35. Shamir, A.: How to share a secret. Communications of the Association for Computing Machinery 22(11), 612–613 (Nov 1979)
36. Shamir, A.: Identity-based cryptosystems and signature schemes. In: Blakley, G.R.,
Chaum, D. (eds.) CRYPTO’84. LNCS, vol. 196, pp. 47–53. Springer, Heidelberg(Aug 1984)
37. Shanks, D.: Class number, a theory of factorization, and genera. In: Proc. of Symp.
Math. Soc., 1971. vol. 20, pp. 41–440 (1971)

A

Related Work

Timed-release crypto and “encryption to the future” The notion of
timed-release encryption was proposed in the seminal paper by Rivest, Shamir
and Wagner [34]. The goal is to encrypt a message so that it cannot be decrypted,
not even by the sender, until a pre-determined amount of time has passed. This
allows to “encrypt messages to the future”. In [34] the authors propose two
orthogonal directions for realizing such a primitive. Using trusted third-parties
to hold the secrets and only reveal them once the pre-determined amount oftime has passed, or by using so-called time-lock puzzles, that are computational
problems that can not be solved without running a computer continuously forat least a certain amount of time.
An interesting example of the latter are timed commitments [12], which arecommitments with an additional forced opening phase that requires a specified(big) amount of computation time. This is useful in an optimistic setting, where
cooperation is usually the case, as an honest party can convince the receiver of thecomitted value without needing to do the timely decryption step. This is indeed
also possible for our SWE scheme, as we discuss in Appendix D, that ciphertexts
constitute a statistically binding commitment, but that is not our focus, as ourdecryption is efficient enough to be run. In case of one party aborting, timed
commitments share all drawbacks of time-lock-puzzles, whereas our protocol
works efficiently, even if the encryptor only submits their value and then goesoffline.
Our approach is more closely related to the paradigm of using a trusted party
as in [19,18]. Simply put, these approaches set up a dedicated server that outputs
tokens for decryption at specified times. We could deploy SWE in such a scenario
as well, with the tokens being aggregated signatures on predictable messages.
Specifically both [18] and our scheme achieve that no communication needs totake place between the trusted server and other entities. However, complete
trust in a single (or multiple) server is a strong assumption, thus we re-use thedecentralized architecture, computation and trust structure already present inblockchains.
With the advent of blockchains, multiple proposals to realize timed-release
encryption using the blockchain as a time-keeping tool emerged, already. Theseprevious results, presented here, are all more of theoretical interest, while we18

demonstrate practical efficiency of our scheme by our implementation reported
in Section B.
In [30] the authors propose a scheme based on extractable witness encryption using the blockchain as a reference clock; messages are encrypted to future
blocks of the chain that once created can be used as a witness for decryption.
However, extractable witness encryption is a very expensive primitive. Concurrently to this work, [17] proposes an “encryption to the future” scheme basedon proof-of-stake blockchains. Their approach is geared at transmitting messages
from past committee members to future slot winners of the proof-of-stake lottery
and requires active participation in the protocol by the committee members. Our
results differ from this by enabling encrypting to the future even for encryptors
and decryptors that only read the state of the blockchain and we require no active participation of the committee beyond their regular duties, assuming, thatpredictable messages like a block header are already signed in each (finalized)
block. Otherwise, all committees need to only include this one additional signature, irrespective of pending timed-encryptions, so there is no direct involvement
between users of McFly and committees.
Another related line of work is presented in [6], where a message is kept
secret and “alive” on the chain by re-sharing a secret sharing of the message
from committee to committee. This allows to keep the message secret until anarbitrary condition is met and the committee can reveal the message. A moregeneral approach is the recent YOSO protocol [26] that allows to perform securecomputation in that same setting, by using an additive homomorphic encryption
scheme, to which committees hold shares of a secret key and continuously reshare it. While these approaches realize some form of encryption to the future,they require massive communication from parties and are still far from practical.
A spin on timed commitments is also available using blockchains; in [1], a
blockchain contract is introduced, that locks assets of the commitment sender fora set time based on a commitment. If the sender fails to open the commitment
within that time, their assets are made available to the receiver as a penalty however the commitment is not opened in that case.
BLS signatures and Identity based encryption (IBE) The BLS signaturescheme, introduced in [11], is a pairing-based signature scheme with signatures of
one group element in size. Additionally, it is possible to aggregate signatures ofmultiple users on different messages, thus saving space as shown in [10]. Due tothe very space-efficient aggregation, BLS signatures are used in widely deployedsystems such as Ethereum 2.0 [23]. Aggregation for potential duplicate messages
is achieved in [8,33]. The former only allows to aggregate once, so all signatures
have to be combined in one step; the latter uses proofs-of-possessions, whereusers need to show that they know the secret key corresponding to their public
key to a key registration authority.
Identity based encryption was first introduced by Shamir [36]. The initial idea
was to use the identity - e.g. a mailing address - as a public key that messages
can be encrypted to. In a sense, our scheme can be seen as a threshold IBE, as
19

we encrypt with respect to a committee and can only decrypt if a threshold of
the committee members collaborate.

B

Implementation and Evaluation

To show the practicality of our scheme we created a prototype implementationand evaluated its performance.
Setup In our prototype we use the noble-bls javascript library [32] that implements bilinear group operations. This library is a fast implementation of
the BLS12-381 curve used in many popular cryptocurrencies like Zcash andEthereum 2.0 for example. In the noble-bls implementation of BLS signatures
the verification key is given in the group G1 and the signature in group G2 . For
our prototype, we used the same setup and adapted our scheme accordingly,
since the groups are reversed there.
To evaluate the efficiency of our prototype we executed the script on a standard Macbook Pro with an Intel i7 processor @2,3 GHz, 16 GB of RAM using
npm version 8.1.4. For benchmarking we used the micro-bmark library [31] thatis also used by noble-bls.
Operation expG1 expG2 pairing expGT
Time [ms]
8
33
24
21

Table 1: noble-bls execution time on the test machine
Computing Discrete Logarithms Our SWE scheme from Section 2 can beused to batch encrypt small exponents from the set Zp . The caveat is that at
the end of decryption we do not get an element in Zp but an element zi in GT .
To compute the actual message we have to compute the discrete logarithm of zi
to the base of gT .
The most efficient way to compute the discrete logarithm in such a case is to
use the baby-step giant-step algorithm. The key component for this algorithm isia precomputed data structure containing (gT1 , 1), ..., (gT2 , 2i ) for some i. It is also
important that this structure allows for O(1) access to its elements. To this end,
we used a HashMap to store the precomputed values. The map is storing data
in an array of a predetermined size of 232 − 1 and uses a simple hash function
to map keys (i.e. the powers of gT ) to indices of the array.
For our setup, we were able to adapt the hash function in a way that evenfor i = 16 there are no collisions in the HashMap and the discrete logarithm
can be computed correctly. Below we show details about the efficiency of theprecomputation step and the computation of the discrete logarithm.
In Table 2 we show the execution time for the precomputation step and theactual baby-step giant-step computation. We benchmark two scenarios. One is astandard approach to the algorithm to divide precomputation and computation
equally. In the other, we precompute more to get better efficiency of the actual
20

computation. Based on the results we decided to encrypt messages and precompute values for i = 16. The experiments below use this setting. The time it takes
for the baby-step giant-step algorithm to solve the DLP for a 24 bit exponent isthen only 27 ms which is comparable to one pairing operation (see Table 1).
Exponent Bit Size i 8 12 16 20 24 28 32
Precompution 1 6 26 105 412 1622 6350
DL Computation 3 8 27 106 421 1574 5846

Table 2: Execution time in milliseconds for baby-step giant-step precomputationand discrete logarithm computation. Symmetric case with 2i/2 of precomputed
exponents and 2i/2 steps of computation.

Exponent Bit Size 6 9 12 15 18 21 24
Precompution 1 5 25 99 397 1607 6338
DL Computation 2 2 3 5 8 14 27

Table 3: Execution time in milliseconds for baby-step giant-step precomputationand discrete logarithm computation. Asymmetric case with 22/3i of precomputed
exponents and 21/3i steps of computation.

Experiments and Results

Fig. 1: Average timing over 100 executions of our prototype implementation of T out-of-N SWE encryption and decryption procedures. The X-axis is the number
N of verification keys used to encrypt a 381-bit plaintext divided into 16 of 24TT
bit values. Data sets correspond to fractions N= 21 and N= 23 , representing
majority and supermajority.

We will now present evaluation results of our prototype implementation of
the T -out-of-N SWE scheme. We prepared a benchmark that measures the execution time of the 4 main procedures of our SWE implementation: encryption,
21

Fig. 2: Average timing over 100 executions of our prototype implementation of
T -out-of-N SWE procedures for creation and verification of the proof of consistency. The X-axis is the number N of verification keys used to encrypt a
381-bit plaintext divided into 16 of 24-bit values. Data sets correspond to fracTT= 12 and N= 23 , representing majority and supermajority.
tions N

decryption, proof of consistency generation, and verification. For each case wecompare the execution time for different thresholds: majority (T /N = 1/2) andsupermajority (T /N = 2/3).
In Figure 1 we show the results for the encryption and decryption procedures.
Encryption time is only slightly influenced by the different threshold parameters
and takes around 1 min when encrypting for N = 2000 verification keys. Lowering the number N to 500 improves the execution time to around 10 second.
A major difference, as to be expected, is visible in the decryption time. For asmaller threshold, T decryption is more efficient. For the case of a supermajority
of N = 2000 decryption of a 381-bit plaintext divided into 16 blocks of 24-bit
values takes around 6 min. By lowering N to 500 we can get the decryption time
down to around 30 seconds.
In Figure 2 we also show our results for the procedures used to generate
and verify the proof of consistency. Contrary to the decryption procedure theefficiency of generating and verifying the proof of consistency decreases withsmaller T . This follows from the structure of the parity matrix used in the
proof for which size increases if T decreases. Creating a proof of consistency for
N = 1000 takes around 7 min for the majority case and around 4 min for thesupermajority case. For verification of the proof, the parity matrix also has to becomputed which leads to a similar execution time. Lowering N to 500 increases
the efficiency to around 1 min.

C

Applications

In this section we describe two applications that can be easily built using the
McFly protocol.
Decentralized Auctions An auction is a process of trading goods for bids,
and it is run among an arbitrary number of bidders, and an auctioneer. First,
22

in a bidding phase, all the bidders submit their bids. Then, in a final phase theauctioneer, after checking all bids announces the winner. If the auctioneer is not
fully honest, it is easy to see that the outcome of the auction cannot be trusted.
Therefore, protocols for decentralized auctions (or auctioneer-free protocols) areof great interest. Here we focus on sealed-bid auctions that are run exclusively
on a blockchain, i.e., the communication of the parties happens only throughblockchain transactions. Additionally, the set of parties running the blockchain
and bidding on the auction can overlap, making it profitable for malicious parties
to, e.g., not include bids that are greater than their own.
One difficulty in realizing decentralized auctions in blockchains, as notedin [20], is that a bid transaction should be self-contained, i.e., the auction protocol
should be able to terminate and determine the correct winner after collecting all
bid transactions. Particularly, this rules out solutions where the bid transaction
is a commitment to the real bid, and later an opening to this commitment is sent.
The reason is that if no opening is ever received, it is not possible to determine if
the opening was suppressed by malicious parties in the blockchain or a malicious
bidder is refusing to open his bid to DoS the auction. This is handled in [20] by
including in the bidding transaction a time-lock puzzle containing the openingof the commitment to the bid; whenever an opening is not received, the auction
can still terminate by solving the time-lock puzzles and retrieving the bids. This
comes with all the disavantages of timelock puzzles discussed in the introduction.
In contrast, with the proposed time-release encryption mechanism, we caneasily realize the same decentralized auction as [20] without any overhead on
the blockchain, by simply encrypting the bids for a future block. We give next
a high level description of this. Assume we want the bidding phase to start at
final block number r in the underlying blockchain, and span through a sequenceof ℓ final blocks. During the bidding phase, all parties will encrypt their bids
with respect to the committee members’ verification keys and to the counterr + ℓ. After this final block is signed by the committee, the signature can be used
to decrypt all the bids, making it possible to publicly verify who the auction
winner is. Note that with this simple approach there is no bid privacy for thelosing bids, as all the bids are opened at the end of the auction run. Moreover, if
the underlying blockchain is incentive-compatible, the results of [20] show thatthe encrypted bids will always be included in the blockchain given that it pays
the required fees.
Randomness Beacons A randomness beacon is a tool that provides public
randomness at predefined intervals. Blockchains can be a great source of randomness to build decentralized randomness beacons, where distrustful parties
contribute to the randomness output by the beacon. One known problem withusing blockchains for building randomness beacons is that malicious parties could
somehow manipulate the contents to be included in the blockchain as a way tointroduce bias in the beacon output. For that, some solutions [29,7,2] leverage
the use of verifiable-delay functions (VDF) to delay the output of the beacon,such that malicious parties do not have enough time at their disposal to be able
to bias the randomness. However, VDFs carry the same drawbacks as time-lock23

puzzles; they are wasteful and it is usually hard to set parameters that result ina secure and usable system. As the role of VDFs in these randomness beacon
constructions is simply to hide information from the parties for a predetermined
period of time, with only minor modifications one could replace the VDFs forour time-release encryption mechanism in [29,7,2] to get randomness beaconswith almost no overhead on the blockchain.

D

A Compatibility Layer for Proof Systems

We will now construct a compatibility layer for our SWE scheme and common
proof systems.
The high-level idea of this compatibility layer is to attach a proof-systemfriendly commitment to a ciphertext and provide an efficient NIZK proof guaranteeing that ciphertext and commitment encrypt the same value. We can then use
efficient and readily available proof systems such as Bulletproofs [13] to establish
additional properties about the encrypted message.
D.1

Well-Formedness Proofs

In this section we will provide a proof system to efficiently prove that a given
SWE ciphertext is decryptable. More precisely, this proof system will ensure that
the SWE scheme is committing in the sense that regardless of which committeemembers contribute to the aggregated signature, the decrypted message is always
the same. This proof system will not yet ensure that the message mi are in thecorrect range, though. This will be ensured using the proof systems in Sections
D.2 and D.3.
We will provide a proof system to certify that ciphertexts generated by
SWE.Enc are well-formed. That is, we define a NIZK proof (P1 , V1 ) for the language L1 defined by the relationx = (ct, (vkj )j , (Ti )i ), w = ((mi )i , r1 )) ∈ R1 ⇔ct = SWE.Enc(1λ , (vkj )j , (Ti )i , (mi )i ; r1 )The ciphertexts produced by SWE.Enc are of the form ct = (h, c, c0 , (cj )j∈[n] ,(c′i )i∈[ℓ] ) as follows.
c = g2rc0 = hr · g2r0s

cj = vkrj · g2j for j = 1, . . . , nc′i = e(H(Ti ), g2 )r0 · gTmi for i = 1, . . . , ℓwhere (s1 , . . . , sn ) is the vector of shares of r0 under Shamir’s secret sharing
scheme. Since s = (r0 , s1 , . . . , sn ) is a codeword of the Reed-Solomon codes
k×(n+1)
RS[Zq , n + 1, t], it holds that H · s = 0, where H ∈ Zp
is the parity-checkmatrix of RS[Zq , n + 1, t].
24

To prove well-formedness of such a ciphertext, we proceed as follows. Let H ′and H ′′ be hash-functions (modelled as a random oracle).
P1 (ct, (vkj )j , r) : The prover proceeds as follows, requiring only r ∈ Zp as witness.
– Compute v = H ′ (ct) ∈ Zkp and set w⊤ = v⊤ · H.
– Parse w = (w0Q
, w1 , . . . , wn ).
wjn0·– Set c∗ = cw
0
j=1 cj .
Qwn– Set g ∗ = hw0 · j=1 vkj j .
– Choose y ← Zp uniformly at random and set f = g2y and f ∗ = (g ∗ )y .
– Compute α = H ′′ (g2 , c, g ∗ , c∗ , f, f ∗ ).
– Compute z = y + αr.
– Output π = (f, f ∗ , z).
V1 (ct, (vkj )j , π) : To verify a proof π = (f, f ∗ , z), proceed as follows.
– Compute v = Q
H ′ (ct) and set w = v⊤ · H. Parse w = (w0 , w1 , . . . , wn ).
wjn0– Set c∗ = cw·
0
j=1 cj .
Qwn– Set g ∗ = hw0 · j=1 vkj j .
′′– Compute α = H (g2 , c, g ∗ , c∗ , f, f ∗ ).
– Check if (c∗ )α · (f ∗ ) = (g ∗ )z and cα · f = g2z , if so output 1, otherwise 0.
Theorem 3. (P1 , V1 ) is a NIZK proof system for relation R1 assuming H ′ , H ′′are modelled as random oracles. Concretely, if x = (ct, (vkj )j ) ∈/ L1 and P1
makes at most q queries to either H ′ or H ′′ , then V1 rejects x, except withnegligible probability q/p.
Proof. Completeness Completeness of this proof system follows routinely. We
observe that the verifier construct the same values as the prover for v, w, c∗ , g ∗ , α.
Now, assuming the input was such that ct = SWE.Enc(1λ , (vkj )j , ·, ·; r1 ), wherer1 contains r as the random exponent used in ciphertext part c, then it holds
0(c∗ )α · (f ∗ ) = (cw
0 ·

n
Y
w
cj j )α · (g ∗ )yj=1

= ((hr · g2r0 )w0 ·nYs(vkrj · g2j )wj )α · (g ∗ )yj=1

= g2r0 w0 α

n
Y

s w α

g2j j · (g ∗ )y+rα = (g ∗ )z

j=1

since w⊤ (r0 , s1 , . . . , sn ) = v⊤ · H(r0 , s1 , . . . , sn ) = 0 as discussed above. The
other equation checked in P1 can be shown to hold analogously.
Soundness First note the following. A ciphertext ct is well-formed if and only
if s = (r0 , s1 , . . . , sn ) ∈ RS[Zq , n + 1, t], which is exactly the case if Hs = 0.
Thus assume that ct is not a valid ciphertext, i.e. it holds that Hs ̸= 0. Say
that a challenge v is bad, if it holds that v⊤ Hs = 0. Since v is chosen uniformly25

random and Hs ̸= 0 it holds thatPr[v bad] = Pr[w⊤ s = 0] = Pr[v⊤ (Hs) = 0] =1,pwhich is negligible over the random choice of v. Note that it holds that0c∗ = cw
0

n
n
Y
Y
⊤
s
w
(vkrj · g2j )wj = (g ∗ )r · g2w s .
cj j = hrw0 · g2r0 w0
j=1

j=1

Now fix a v which is not bad, i.e. it holds that w⊤ s ̸= 0. Then it holds that⊤
(g2 , c = g2r ) and (g ∗ , c∗ = (g ∗ )r · gTw s ) do not satisfy the same discrete logarithm
relation, in other words the vectors (1, logg2 (c)) and (1, logg∗ (c∗ )) are linearly
independent. But this means that also (1, 1) and (logg2 (c), logg∗ (c∗ )) are linearly
independent.
Now fix any f and f ∗ which may depend on v. Say that an α is bad if there
exists a z ∈ Zp such thatcα · f = g2z(c∗ )α · f ∗ = (g ∗ )z .
Now observe that α is bad if and only ifα(logg2 (c), logg∗ (c∗ )) + (logg2 (f ), logg∗ (f ∗ )) ∈ Span((1, 1)),
which is equivalent toα(logg2 (c), logg∗ (c∗ )) ∈ −(logg2 (f ), logg∗ (f ∗ )) + Span((1, 1)).
As (1, 1) and (logg2 (c), logg∗ (c∗ )) are linearly independent, α(logg2 (c), logg∗ (c∗ ))only lands in the affine subspace −(logg2 (f ), logg∗ (f ∗ )) + Span((1, 1)) only withnegligible probability 1/p over the choice of α. It follows that Pr[α bad] ≤ 1/p.
Now note that V1 rejects if neither v nor α is bad. Now assume that theadversary makes q1 queries to H ′ and q2 queries to H ′′ . By a union bound we
conclude the the probability that one of the queries to H ′ results in a bad v
is at most q1 /p. Furthermore, also by a union bound the probability that oneof the queries to H ′′ results in a bad α is at most q2 /p. We conclude with aunion bound that there are no bad queries to H ′ or H ′′ , except with probability(q1 + q2 )/p, which is negligible.
Zero-Knowledge To show that this proof-system is zero-knowledge, we canroutinely make use of the fact that the underlying Schnorr-like proof-system forequality of discrete logarithms (see e.g.[16]) is zero-knowledge.
Specifically, our simulator can chooses z and α uniformly at random and sets
f = g2z · c−α and f ∗ = (g ∗ )z · (c∗ )−α and programs the random oracle H ′′ tooutput α on the query (g2 , c, g ∗ , c∗ , f, f ∗ ).
It follows routinely that given a YES-instance (ct, (vkj )j ) the simulation isperfect unless the verifier makes makes a hash query (g2 , c, g ∗ , c∗ , f, f ∗ ) to H ′′26

that the simulator would make, thus prohibiting the simulator to program H ′′accordingly. However, since f is distributed uniformly random, this happens onlywith negligible probability 1/p. Thus we have established the zero-knowledge
property.

D.2

Proofs of Plaintext Equality

First observe the following: A ciphertext ct = (h, c, c0 , (cj )j , (c′i )i ) is a statistically binding commitment to a message m = (mi )i , even if we drop the cj . In
fact, the only purpose of the cj is to facilitate decryption. If we fix h and the0· gTmi )i )hT,i = e(H(Ti ), g2 ), then com(m; r, r0 ) = (c = g2r , c0 = hr · g2r0 , (c′i = hrT,iis in fact a homomorphic commitment scheme13 and it holds thatcom(m; r, r0 )α · com(m′ ; r′ , r0′ )β = com(αm + βm′ ; αr + βr′ , αr0 + βr0′ ),where the exponentiation is component-wise.
Homomorphic operations for this commitment scheme are relatively expensive, as the c′i components reside in the target group GT . To enable efficient
proofs of statements over the commited values m, we will leverage a second commitment scheme COM and provide a highly efficient cross-scheme equality proof
for two commitments com(m) and COM(m). Furthermore, we will choose thecommitment scheme COM to be proof-system friendly. Thus, the natural choice
for COM is a Pedersen commitment in a cryptographic group G of order p. For
simplicity, we may choose e.g. G = G1 , but G could in fact be any group of orderp. Thus, let g, h1 , . . . , hℓ ← G be public but randomly chosen group Q
elementsℓifrom the group G. Then COM(m) is computed by COM(m; ρ) = g ρ · i=1 hmifor a uniformly random ρ ← Zp . This commitment is computationally binding
under the discrete logarithm assumption in G.
We will now provide a non-interactive zero-knowledge proof of knowledge(P2 , V2 ) for the following relation R2 . For given crs = (h ∈ G2 , hT,1 , . . . , hT,ℓ ∈GT ) and CRS = (g, h1 , . . . , hℓ ∈ G) we want to establish that for c and C it holds
that c = com(m; r, r0 ) and C = COM(m; ρ) for some m ∈ Zℓp and r, r0 , ρ ∈ Zp .
Let H : {0, 1}∗ → Zp be a hash-function, which will be modelled as a random
oracle.
P2 ((crs, CRS, c, C), (m, r, r0 , ρ)) :– Choose u ← Zℓp uniformly at random.
– Choose r0′ , r′ , ρ′ ← Zp uniformly at random.
– Compute c′ = comcrs (u; r′ , r0′ ) and C′ = COMCRS (u; ρ′ ).
– Compute α = H(crs, CRS, c, C, c′ , C′ ).
– Compute m̃ = u + αm, r̃ = r′ + αr, r̃0 = r0′ + α.r0 and ρ̃ = ρ′ + αρ.
13The intuition to show the binding property is as follows: If there are r, r0 , m, r′ , r0′ , m′such that com(m; r, r0 ) = com(m′ ; r′ , r0′ ), then as g2 is a generator and c = g2r , r = r′ .
Then, hr becomes fixed and from c0 = hr · g2r0 , we conclude r0 = r0′ . The same holds
for all mi individually as gT is a generator.

27

– Output π = (c′ , C′ , m̃, r̃, r̃0 , ρ̃).
V2 ((crs, CRS, c, C), π = (c′ , C′ , m̃, r̃, r̃0 , ρ̃)) :– Compute α = H(crs, CRS, c, C, c′ , C′ ).
?

?

– Check if c′ · cα = comcrs (m̃; r̃, r̃0 ) and C′ · Cα = COMCRS (m̃; ρ̃), if so
output 1, otherwise 0.
Theorem 4. (P2 , V2 ) is a NIZK proof of knowledge for relation R2 , assuming
H is modelled as random oracle.
Proof. Completeness Completeness of this proof system follows routinely. On
an honestly generated input ((crs, CRS, c, C), π = P2 ((crs, CRS, c, C), (m, r, r0 , ρ)))to V2 we can see that c′ · cα =comcrs (u; r′ , r0′ ) · comcrs (m; r, r0 )α = comcrs (m̃; r̃, r̃0 )by our definitions of m̃, r̃, r˜0 and the underlying scheme being homomorphic.
?
The same holds for C′ · Cα = COMCRS (m̃; ρ̃), so on an honest input, P2 always
outputs 1.
Proof of Knowledge We will now argue that (P2 , V2 ) is a proof of knowledge.
Let CRS be a given common-references string for COM. Fix a statement(crs, CRS, c, C) an let P∗2 be a malicious prover.
In order to use Lemma 2 to construct a knowledge extractor, let A be analgorithm which first runs P∗2 to produce a candidate proof π and then uses V2
to verify π, if it accepts A outputs 1 and auxiliary information π and a response
α for the H-query made by P∗2 .
Now, by Lemma 2 there exists a forking algorithm FP∗2 with expected runtime
only polynomially larger than that of P∗2 which, if a run of P∗2 produces a verifying
proof π, produces a fork π, π ′ .
Our knowledge extractor E is now given as follow.
– Run FP , and if it outputs 0, also output 0.
– Otherwise, if FP∗2 outputs a fork (π, α) and (π ′ , α′ ) proceed as follows.
– Parse π = (c′ , C′ , m̃, r̃, r̃0 , ρ̃) and π ′ = (ĉ, Ĉ, m̂, r̂, r̂0 , ρ̂).
– Compute m̄ = (m̃− m̂)/(α−α′ ), r̄ = (r̃ − r̂)/(α−α′ ), r̄0 = (r̃0 − r̂0 )/(α−α′ )and ρ̄ = (ρ̃ − ρ̂)/(α − α′ ) and output (m̄, r̄, r¯0 , ρ̄).
In case the last step is reached, it holds that′

C′ · Cα = COMCRS (m̃; ρ̃) and C′ · Cα = COMCRS (m̂; ρ̂),from which we can conclude that′Cα−α = COMCRS (m̃ − m̂; ρ̃ − ρ̂),and therefore
C = COMCRS ((m̃ − m̂)/(α − α′ ); (ρ̃ − ρ̂)/(α − α′ )) = COMCRS (m̄; ρ̄).
An analogous argument can be mounted to show that c = comcrs (m̄; r̄, r̄0 ). Thismeans E is a PPT algorithm with extraction probability p′ , thus our knowledge
extractor E is efficient and correct.
28

Zero-Knowledge To argue that (P2 , V2 ) is zero-knowledge, we construct asimulator S which, given a statement (crs, CRS, c, C), chooses a uniformly randomm̃ ← Zℓp , and uniformly random r̃, r̃0 , ρ ← Zp as well as a uniformly randomα ← Zp and sets c′ = comcrs (m̃; r̃, r̃0 ) · c−α and C′ = COMCRS (m̃; ρ̃) · C−α .
Further, the simulator S programs the random oracle H to output α on input(crs, CRS, c, C, c′ , C′ ). The simulated proof π is given by π = (c′ , C′ , m̃, r̃, r̃0 , ρ̃).
It follows routinely that the simulation is perfect, unless A queries H on
(crs, CRS, c, C, c′ , C′ ) before obtaining the proof π. But this only happens withnegligible probability as the commitments c′ and C′ are freshly chosen by S.
D.3

Putting Everything together: Verifiable SWE

We will now briefly discuss how we can extend the SWE scheme constructed in
Section 2 with the proof systems of this section and an efficient proof system(e.g. Bulletproofs [13]) to obtain an efficient verifiable SWE scheme, i.e. an SWE
for which we can efficiently prove statements about the encrypted messages.
Let a relation R for messages m and witnesses w be given
Pand L be its induced
language. We say that a vector m = (m1 , . . . , mℓ ) ∈ L, if i∈[ℓ] 2(i−1)k mi ∈ L.
Let (P1 , V1 ) be the proof system for well-formedness constructed in Section D.1, let (P2 , V2 ) be the proof system for plaintext equality constructed in
Section D.2, and finally let (P3 , V3 ) be a proof system which asserts for a given
C = COMCRS (m; ρ) that m ∈ L. In the following, let w be an auxiliary witness
for m ∈ L, i.e. P3 takes as input a commitment C(m; ρ) and a witness ρ, w. To
ensure efficient decryption even for maliciously generated ciphertexts, the language L at the bare minimum must enforce that each component mi is in theappropriate range, i.e. mi ∈ {0, . . . , 2k − 1} for a small integer k. This will guarantee correctness of efficient decryption with baby-step giant-step. Such efficient
range-proofs are provided by the Bulletproofs proof system [13].
Lemma 1 ([13], Section 4.2). There exists a zero-knowledge range proof(P, V) for the commitment scheme COM where the proofs π consist of 4kℓ + 4
group elements and 5 Zp elements.
In the following, we assume that the commitment scheme COM takes thesame common reference string CRS as provided for (P3 , V3 ). In the following we
describe Prove, Vrfy that extend SWE with Enc, Dec as described in 2 to be averifiable SWE scheme.
We require the random coins r′ used in encryption to be input to the proof,
and then extract the subset of random coins (r, r0 ) as required by (P1 , V1 ) and(P2 , V2 ). Note that executing encryption and the proof in one instance is more
efficient and preferred in practice.
SWE.Prove(CRS, (vkj )j∈[n] , (Ti )i∈[ℓ] , ct, (mi )i∈[ℓ] , w, r′ ) :– Pick necessary random coins r, r0 from r′ .
– Parse ct = (h, c, c0 , (cj )j∈[n] , (c′i )i∈[ℓ] )– Choose ρ ← Zp uniformly at random– Compute C = COMCRS ((mi )i∈[ℓ] ; ρ).
29

– Compute π1 = P1 (ct, r′ ).
– Compute π2 = P2 (crs = (h, H(Ti )i∈[ℓ] ), CRS, (c, c0 , (c′i )i∈[ℓ] ), C), ((mi )i∈[ℓ] ,r, r0 , ρ)).
– Compute π2 = P3 (C, (ρ, w)).
– Output π = (C, π1 , π2 , π3 ).
SWE.Vrfy(CRS, (vkj )j∈[n] , (Ti )i∈[ℓ] , ct, π) :– Output 1 if V1 (ct, π1 ) = 1, V2 ((ct, C, (vkj )j∈[n] , (Ti )i∈[ℓ] ), π2 ) = 1 andV3 (CRS, C, π3 ) = 1, otherwise output 0.
Theorem 5. SWE.Prove, SWE.Vrfy extend SWE to be a verifiable SWE.
Proof. We need to show that Prove, Vrfy are a NIZK proof system for a language
given by the induced relation R′ :(V = (vk1 , . . . , vkn ), (Ti )i∈[ℓ] , ct), ((mi )i∈[ℓ] , w, r)) ∈ R′ ⇔ct = Enc(1λ , V, (Ti )i∈[ℓ] , (mi )i∈[ℓ] ); r) and (m, w) ∈ R,
X
where m =2(i−1)k mii∈[ℓ]

Since we only combine three NIZK proofs (P1 , V1 ), (P2 , V2 ), (P3 , V3 ), we canestablish completeness, soundness and zero-knowledge of the resulting proof system routinely. We will argue now, that the language of Prove, Vrfy is indeed asclaimed. We consider CRS fixed. The input statement (CRS, V = (vkj )j∈[n] ,(Ti )i∈[ℓ] , ct) and witness ((mi )i∈[ℓ] , w, r′ ) match the structure for R′ . Let r, r0 be
as derived from r′ .
P1 , V1 establishes ct = Enc(1λ , V, (Ti )i∈[ℓ] , m = (mi )i∈[ℓ] ); r′ ) for some randomness r′ .
Now, P2 , V2 establishes that there exists some m̄ ∈ Zℓp and randomnessesr, r0 , ρ ∈ Zp such that (c, c0 , (c′i )i∈[ℓ] ) = com(m̄; r, r0 ) and C = COM(m̄; ρ).
The commitment com is defined as com(m; r, r0 ) = (c = g2r , c0 = hr · g2r0 , (c′i =0hrT,i· gTmi )i ), where h, (hTi )i = H(Ti )i from the input ct, (Ti )i are provided via
crs. That implies by definition of SWE.Dec, that there is some (c¯j )j∈[n] , r̄ suchthat (h, c, c0 , (c¯j )j∈[n] , (c′i )i∈[ℓ] ) = Enc(1λ , V, (Ti )i∈[ℓ] , m̄); r̄).
So we receive ct = Enc(1λ , V, (Ti )i∈[ℓ] , m = (mi )i∈[ℓ] ); r′ ) and (h, c, c0 , (c¯j ),j∈[n](c′i )i∈[ℓ] ) = Enc(1λ , V, (Ti )i∈[ℓ] , m̄); r̄) and C = COM(m̄; ρ). Due to the perfect binding of com as discussed above, it must hold that m̄ = m given that(h, c, c0 , (c′i )i ) are fixed. So, We can combine P1 , V1 and P2 , V2 to show there
is some r′ , ρ such that ct = Enc(1λ , V, (Ti )i∈[ℓ] , m = (mi )i∈[ℓ] ); r′ ) and C =COM(m; ρ).
P3 , V3 ensures that there is m′ , ρ such that C = COM(m′ ; ρ) andP Now, (i−1)k( i∈[ℓ] 2
m′i , w) ∈ R. Since C is a perfectly binding commitment, we again′
have m = m. The conjunction language of (V1 , P1 ), (V2 , P2 ), (V3 , P3 ) is thus
indeed identical to the one induced by R′ . This concludes our proof.
30

E

Cryptographic Building Blocks

Preliminaries. We denote by λ ∈ N the security parameter and by x ←A(in; r) the output of the algorithm A on input in where A is randomized withr ← {0, 1}∗ as its randomness. We omit this randomness when it is obvious
or not explicitly required. By AO we denote, that we run A with oracle accessto O, that is it may query the oracle on inputs of its choice and only receives
the corresponding outputs. We denote by x ←$ S an output x being chosen
uniformly at random from a set S. We denote the set {1, . . . , n} by [n]. For agroup element g we denote by ⟨g⟩ a canonic encoding of g as a bitstring. PPT
denotes probabilistic polynomial time. Also, poly(x), negl (x) respectively denoteany polynomial or negligible function in parameter x.
Next, we define the cryptographic building blocks necessary for our protocol.
Aggregatable Multi-Signatures Aggregatable multi-signatures are digital
signatures that allow to compress multiple signatures by multiple users on multiple messages that may contain duplicates into one aggregate signature. We
require all published public keys to come with an online-extractable proof ofknowledge14 that shows, that the issuer knows a corresponding secret key. All
algorithms below implicitly have oracle access to a hash function H as input.
Definition 8 (Aggregatable Multi-signatures). An aggregatable signaturescheme Sig = (KeyGen, Sign, Vrfy, Agg, AggVrfy, Prove, Valid) is a tuple of sevenalgorithms where:– (vk, sk) ← KeyGen(1λ ): The key generation algorithm takes a security parameter and outputs a pair of verification and signing keys (vk, sk).
– σ ← Sign(sk, T ): The signing algorithm takes as input a signing key sk anda message T . It outputs a signature σ.
– b ← Vrfy(vk, T, σ): The verification algorithm takes as input a verification
key vk, a message T and a signature σ. It outputs a bit b.
– σ ← Agg((σ1 , . . . , σk ), (vk1 , . . . , vkk )): The aggregation algorithm takes a listof signatures (σ1 , . . . , σk ) and verification keys (vk1 , . . . , vkk ). It outputs one
aggregate signature σ.
– b ← AggVrfy(σ, (vk1 , . . . , vkk ), (T1 , . . . , Tk )): The verification algorithm for
aggregate signatures takes an aggregate signature σ as well as two lists ofpublic verification keys vki and messages Ti , which may include duplicates.
It outputs a bit b. For convenience, we consider this identical to Vrfy, if only
σ and one key vk1 and message T1 are input.
– π ← Prove(vk, sk): The proving algorithm has access to an additional hashfunction oracle Hpr , takes a verification key vk and a signing key sk. It
outputs a proof π.
– b ← Valid(vk, π): The validity algorithm has access to to an additional hashfunction oracle Hpr , takes a verification key vk and a proof π. It outputs a
bit b.
14

It can either be appended to the key or registered with a certifying authority.

31

We require that such a signature scheme is correct and unforgeable and that
(Prove, Valid) is an online-extractable zero-knowledge proof of knowledge for the
relation K = {(vk, sk)|∃r s.t. (vk, sk) ← KeyGen(1λ ; r)}15
Definition 9 (Correctness). An aggregatable multi-signature scheme Sig =(KeyGen, Sign, Vrfy, Agg, AggVrfy, Prove, Valid) is correct if for all λ ∈ N, k =poly(λ), all messages T, T1 , . . . , Tk , sets of public keys V = (vk1 , . . . , vkk ) andsignatures (σ1 , . . . , σk ) such that Vrfy(vki , Ti , σi ) = 1 for i ∈ [k] it holds:Pr
Vrfy(vk, T, Sign(sk, T )) = 1 :=1(vk, sk) ← KeyGen(1λ )

and



AggVrfy(σ, V, (T1 , . . . , Tk )) = 1 :Pr= 1.
σ ← Agg((σ1 , . . . , σk ), V )Definition 10 (Unforgeability). An aggregatable multi-signature scheme Sig =(KeyGen, Sign, Vrfy, Agg, AggVrfy, Prove, Valid) is unforgeable if for all λ ∈ N,
N = poly(λ) there is no PPT adversary A with more than negligible advantage
AdvA
Unf = Pr [ExpUnf (A, N ) = 1] in the experiment ExpUnf (A, N ).
Experiment ExpUnf (A, N )– The experiment randomly chooses (vk, sk) ← KeyGen(1λ ) and outputs vk toA.
– A may request signatures from a signing oracle Sign(sk, ·).
– A may also request to see a proof for vk, which the experiment answers withπ ← Prove(vk, sk). If it does, A may not use vk as one of the keys in its forge.
– Eventually, A outputs ((T1 , . . . , Tk ), (vk2 , . . . , vkk ), (π2 , . . . , πk ), σ ∗ ) as aforge. If A requested a proof for vk before, but one of the vki for i ∈ {2, . . . , k}is vk, the experiment outputs 0. The case k = 1, where A outputs no additional keys is explicitly allowed.
– The experiment outputs 1, if AggVrfy(σ ∗ , (vk, vk2 , . . . , vkk ), (T1 , . . . , Tk )) = 1,
T1 was never queried to the oracle Sign(sk, ·), Valid(vki , πi ) = 1 for all i ∈{2, . . . , k} and the number of keys k is upper bounded by N . Otherwise, theoutput is 0.

Hash Functions A keyed family of hash functions H consists of the following
functions:– k ← KeyGen(1λ ): The key generation algorithm takes a security parameterand outputs a key k.
15Note, that this requires implicitly, that it is efficiently checkable, whether a secretkey belongs to a given public key. This will be true for our use-case.

32

– h ← Hk (m): The hash algorithm takes as input a key k and a message m.
It outputs a hash h.
We expect a hash function family to be collision resistant.
Definition 11 (Collision resistance). A family of hash functions is collisionresistant, if for any PPT adversary A
m1 ̸= m2 and Hk (m1 ) = Hk (m2 ) :< negl (λ)
Prk ← KeyGen(1λ ); (m1 , m2 ) ← A(k)In the following, for convenience we will omit the key and assume it has been
handed out as a public hash function H = Hk .
Furthermore, we will be using the random oracle model, in which a hashfunction can only be evaluated by directly querying the hashing oracle [5]. The
output on a message that has not been queried yet is uniform and determinedat the time of the query. This is a heuristic for the behaviour of hash functions
that allows us to simulate the hashing oracle ourselves in our reductions.
Pseudo-random functions A keyed family of functions
PRFk : {0, 1}s → {0, 1}t for keys k ∈ {0, 1}∗ and some s, t = poly(|k|) is a
pseudo-random function (PRF) family, if– given k, m the function PRFk (m) is efficiently computable and– for every PPT distinguisher D, it holds DPRFk (.) ≈c DF (.) ,where k ←$ {0, 1}λ and F is chosen randomly from all functions from{0, 1}s(λ) to {0, 1}t(λ) .
Commitment Schemes A (non-interactive) commitment scheme (CS) CS =(Setup, Commit, Vrfy) is composed of the following algorithms:– CRS ← Setup(1λ ): The setup algorithm takes the security parameter λ andoutputs a common reference string CRS.
– (com, γ) ← Commit(CRS, m): The commit algorithm takes as input a common reference string CRS and a message m. It outputs a commitment com
and opening information γ.
– b ← Verify(CRS, com, m, γ): The verification algorithm takes as input a common reference string CRS, a commitment com, a message m and opening
information γ. It outputs a bit b ∈ {0, 1}.
Definition 12 (Correctness).
We say that a commitment scheme is correct if for all λ ∈ N, CRS ←Setup(1λ ) and every message m we have thatPr [1 ← Verify(CRS, com, m, γ) : (com, γ) ← Commit(CRS, m)] = 1.
Definition 13 (Computational Hiding). We say that a commitment scheme
is computationally hiding if for all λ ∈ N, CRS ← Setup(1λ ) and all PPT adver33

saries A = (A1 , A2 ) we have that :(m0 , m1 , aux ) ← A1 (CRS) 1b ←$ {0, 1}′
Pr  b = b : (com, γ) ← Commit(CRS, mb )  − 2 = negl (λ)
b′ ← A2 (com, aux )Definition 14 (Perfect Binding). We say that a commitment scheme is perfectly binding if for all λ ∈ N, CRS ← Setup(1λ ) and all adversaries A we havethat(com, m0 , γ0 , m1 , γ1 ) ← A(CRS)Pr m0 ̸= m1 ∧ b = b′ = 1 : b ← Verify(CRS, com, m0 , γ0 )  = 0.
b′ ← Verify(CRS, com, m1 , γ1 )Zero-knowledge proofs We require two types of proof systems in the random
oracle model which we will describe below. Definitions are partially taken from[24]:
Definition 15 (Zero-knowledge proof of knowledge). A proof of knowledge for an NP language L defined by an efficiently verifiable binary relation R
via x ∈ L ⇔ ∃w s.t. (x, w) ∈ R consists of the following functions, which haveaccess to a hash function H:– π ← ProveH (x, w): The proof algorithm takes a statement x and a witness
w. It outputs a proof π.
– b ← VrfyH (x, π): The verification algorithm takes as input a statement x anda proof π. It outputs a bit b.
A zero-knowledge proof of knowledge in the random oracle model consist of(Prove, Vrfy) fulfilling completeness, zero-knowledge and the proof-of-knowledge
property as below. An online-extractable zero-knowledge proof of knowledge fulfills the stronger assumption of extractability instead of the proof-of-knowledge
property:
Definition 16 (Completeness). A proof system (Prove, Vrfy) is complete, if
for any (x, w) ∈ R, any hash function H, it holdshiPr VrfyH (x, ProveH (x, w)) = 1 = 1
Definition 17 (Zero-Knowledge). We say that a proof system (Prove, Vrfy)
is zero-knowledge in the random oracle model, if there exists a PPT simulator S
such that for all PPT distinguishers D the following distributions are computationally indistinguishable:– Let H be a random oracle, set π0 = ∅, δ0 = 1λ . Repeat for i = 1, . . . , nuntil D stops: (xi , wi , δi ) ← DH (i, πi−1 , δi−1 ), where πi ← ProveH (xi , wi ) if
(xi , wi ) ∈ R or π ← ⊥ otherwise. Output D’s final output.
34

– Let (H0 , τ0 ) ← S(0, 1λ ), set π0 = ∅, δ0 = 1λ . Repeat for i = 1, . . . , n until D
stops: (xi , wi , δi ) ← DHi−1 (i, πi−1 , δi−1 ), where (Hi , πi , τi ) ← S(i, xi , τi−1 , YES)
if (x, wi ) ∈ R or (Hi , πi , τi ) ← S(i, xi , τi−1 , NO) otherwise. Output D’s final
output.
Definition 18 (Proof of knowledge). We say that a proof system (Prove, Vrfy)
is a proof of knowledge with knowledge error ε, if there exists a PPT extractor
E, such that for every PPT prover P∗ and input x it holds:hi∗P r (x, w) ̸∈ R : w ← E P (x) ≤ P r [Vrfy(x, π) = 0 : π ← P∗ (x)] − ε∗Here E P denotes that the extractor gets full black-box access to the algorithm P∗
including the power to rewind.
Definition 19 (Extractability). There exists a PPT extractor E, such that forevery PPT algorithm A and the simulator S from the zero-knowledge definition,
it holds:
Let (H0 , τ0 ) ← S(0, 1λ ), set π0 = ∅, δ0 = 1λ . Repeat for i = 1, . . . , n until A
stops: (xi , wi , δi ) ← AHi−1 (i, πi−1 , δi−1 ), where (Hi , πi , τi ) ← S(i, xi , τi−1 , YES)
if (x, wi ) ∈ R or (Hi , πi , τi ) ← S(i, xi , τi−1 , NO) otherwise. Let (x, π) be A’s
final output and and QA be the queries that A made to oracles Hi . Let w ←E(x, π, QA ). Then, if (x, π) ̸= (xi , πi ) for all i ∈ [n],hiP r (x, w) ̸∈ R ∧ VrfyHn (vk, π) = 1 ≤ negl (λ)
Extractability essentially follows the same idea as proof-of-knowledge, but additionally doesn’t allow rewinding and was written in the multi-statement model,
because we need these stronger guarantees for part of our construction.
Definition 20 (Non-interactive Zero-knowledge Proof Systems). A NIZK
proof system for an NP language L defined by an efficiently verifiable binary relation R via x ∈ L ⇔ ∃w s.t. (x, w) ∈ R consists of (Prove, Vrfy) as above andfulfills completeness, zero-knowledge and computational soundness16 :Definition 21 (Computational Soundness). We say that a proof system(Prove, Vrfy) has computational soundness if for all λ ∈ N, every collision resistant hash function H, every x ̸∈ L and PPT adversaries A, it holdsPr VrfyH (x, π) = 1 : π ← AH (1λ , x) = negl (λ)
Secret Sharing and Coding Theory
We will briefly introduce some elementary concepts relating to Shamir’s secret sharing and its underlying coding structure, Reed-Solomon codes. Let Zp
be the finite field of prime order p and fix distinct elements ξ = ξ1 , . . . , ξn ∈ Zp .
16

As stated above, this is typically referred to as an argument system, but we call it
a proof for consistency with prior works.

35

The Reed-Solomon code RSn,k [ξ] consists of all vectors c = (f (ξ1 ), . . . , f (ξn ))Pk−1
for some polynomial f (X) = i=0 ai X i of degree k − 1. This code is generated by the matrix G = (ξij )i,j ∈ Zpn×k and has a parity-check matrix H =(n−k)×n
1
i
Q
∈ Zp
ξ
.
j
(ξj −ξl )
l̸=j

i,j

Lagrange Interpolation For a set of supporting points χ1 , . . . , χk from afinite field Zp , where p ∈ N is prime, the Lagrange basis polynomials are given
by L1 , . . . , Lk , whereY x − χj
Li (x) =.
χi − χjj∈[k];j̸=iThese are chosen such that Li (χj ) = 1 iff i = j and 0 otherwise. Consequently, given a set of k data points (χi , yi ), we can output a polynomialfL (x) = Σi∈[k] Li (x) · yi that will run through these points and which has degree
at most k-1. This process is called Lagrange Interpolation.
Bilinear group setting We regard the same setup as in [10], that is we assume
groups G1 , G2 , GT of prime order p with their respective generators g1 , g2 andgT . Additionally, we assume a computable bilinear map e : G1 × G2 → GT . Thatis, e has the following properties:
1. Bilinearity: for all u ∈ G1 , v ∈ G2 and a, b ∈ Z, it holds that e(ua , v b ) =e(u, v)ab .
2. Non-Degeneration: e(g1 , g2 ) ̸= 1.
From these, it follows also that for any u1 , u2 ∈ G1 , v ∈ G2 it holds e(u1 ·u2 , v) =e(u1 , v) · e(u2 , v). We assume that the group operations in all of these groups
as well as e can be computed in one time step and that the computational
Co-Diffie-Hellman assumption holds in (G1 , G2 ) and the bilinear Diffie-Hellman
assumption hold in (G1 , G2 , GT ). In some instances we additionally require theknowledge of exponent assumption to hold in (G1 , G2 , GT ).
Definition 22 (Computational Co-Diffie-Hellman). The computational CoDiffie-Hellman assumption for a pair of groups (G1 , G2 ) states that the probability
P r [A(g1 , g1x , g2 , g2x , h) = hx : x ←$ Zp , h ←$ G1 ]is negligible for polynomial adversaries A, where g1 ∈ G1 , g2 ∈ G2 are generators.
Definition 23 (Bilinear Diffie-Hellman). The bilinear Diffie-Hellman assumption for a triple of groups (G1 , G2 , GT ) of order p states that the following
distributions are computationally close:(g1 , g1x , g1α , g2 , g2x , g2r , gTαxr ) ≈c (g1 , g1x , g1α , g2 , g2x , g2r , gTy ),where x, y, α, r ←$ Zp and g1 ∈ G1 , g2 ∈ G2 , gT = e(g1 , g2 ) ∈ GT are generators.
We will now adapt the knowledge of exponent assumption [4] to the bilinear
setting. Similar to the original one this assumption holds generically.
36

Definition 24 (Knowledge of exponent assumption). For a pair of groups(G1 , G2 , GT ) with generators (g1 , g2 , gT ) of prime orders p as above this assumption states that if there exists a PPT adversary A where:– A takes as input a generator h ∈ G1 .
– A outputs two group elements C ∈ G1 , Y ∈ G2 such that e(h, Y ) = e(C, g2 ),that is (g2 , Y ) and (h, C) have the same dlog relationship.
If such an A exists, then there exists a PPT extractor Ā, that takes the same
input (and potentially randomness) as A and outputs the same C, Y and additionally c, such that C = hc , Y = g2c .
Expected-Time Forking Lemma We will use the following forking lemma
proven secure in [3]:Lemma 2 (Expected-Time Forking Lemma). Let H be a set of size h ≥ 2,
q ≥ 1 and A a randomized algorithm, that on input x, h1 , h2 returns an integer
from 0, 1, 2 in at most TA (|x|) time steps. Let B be a brute-force algorithm, thattakes input x and halts after at most TB (|x|) steps, outputting 1.
Let the accepting probability PA (x) be defined as the probability of the following experiment outputting 1:
Randomly choose coins ρ for A
Pick h1 , . . . , hq ←$ H and set i ← A(x, h1 , . . . , hq ; ρ)If i ≥ 1, return 1, else return 0.
Then it holds that the forking algorithm FA (x) given as:
Randomly choose coins ρ for A
Pick h1 , . . . , hq ←$ H and set i ← A(x, h1 , . . . , hq ; ρ)If i = 0, return 0.
Repeat, in parallel with B(x):Pick h′i , . . . , h′q ←$ H
Set j ← A(x, h1 , . . . , hi−1 , h′i , . . . , h′q ; ρ)
Until (i = j and h′i ̸= hi ) or B has halted.
Return 1
returns 1 with the same probability PA (x) in expected time TFA (|x|) ≤ (4q +1)TA (|x|) + 4q
h TB (|x|).

F

Blockchain ModelIn this section we introduce a simplified blockchain model where the McFly
protocol is built on.

37

Functionality BC λ,HInitialization
T := ()
ctr := 0
C := ∅
Wait until (Corrupt, ·) is called by adversary A
for i ∈ [n] do
if i ̸∈ C thenSample (ski , vki ) ← Sig′ .KeyGen(1λ )Output πi ← Sig′ .Prove(vki , ski ) to A.
V := {vki }i∈[n]▷ Current number of blocks▷ Set of corrupted parties

Public Interface
Input: (QueryAt, CT R)
if CT R ≤ T.len() thenreturn T[CT R]
Input: (QueryTime)
return T.len()
Input: (QueryKeys)
return V
Interface for adversary A▷ This can be called once during
Input: (Corrupt, C ′ , {vk′i }i∈C ′ , {πi }i∈C ′ )initialization, modelling static corruption
if |C ′ | ≤ c and C ′ ⊂ [n] and Sig′ .ValidHpr (vk′i , πi ) for i ∈ C ′ thenC := C ′for i ∈ C do
Set vki = vk′i
Input: (Tick, m)
ctr + = 1
for i ∈ ([n] \ C) do
Output (σi ) ← Sig′ .Sign(ski , H(ctr )) to A
Output (σi′ ) ← Sig′ .Sign(ski , H(ctr , m)) to A
Set S := [n] \ C.
Await input (C ′ , (σi )i∈C ′ ) from A
if for all i ∈ C ′ , Sig′ .Vrfy(vki , H(ctr ), σi ) = 1 thenS := S ∪ C ′ .
Append (Sig′ .Agg((σi )i∈S , (vki )i∈S ), (vki )i∈S ) to T.
Restrictions on the adversary
For each round ri , the adversary is required to send a message (Tick, m) forsome block content m within time ∆τ .

As we are modelling BFT blockchains and blockchains coupled with a finality
layer, all the blocks in our abstraction are final and cannot be rolled-back. Parties
38

only require the signatures of the committee members on the block counterto decrypt ciphertexts, thus the blockchain in our model simply consists of alist T containing these signatures. On every tick, committee members sign theblock and the new counter ctr as the block header. Our model takes a security
parameter λ and two hash functions H, Hpr as parameters.
Let the number of committee members be n and the corruption thresholdof the adversary be c < n/2. We allow the adversary to corrupt up to c parties statically - that is they may choose their signing keys in the beginning of
the execution and input the signatures used in making the aggregated signatures on block counter for these parties later on.17 We additionally require an
online-extractable proof of knowledge for the public keys of committee members.
Further, the adversary gets to decide when to make a new block (up to delay ∆τ
per round) by calling Tick, - we allow them full control over the content of theseblocks, except for the fixed block counters. They also get to see all unagreggatedsignatures by the honest parties.

G

Discussion on proofs of possession

In this case, we have the following proof system:Sig′ .Prove(vk, sk):– Outputs Sig′ .SignHpr (sk, ⟨vk⟩).
′
Sig .Valid(vk, π):– Check whether Sig′ .VrfyHpr (vk, ⟨vk⟩, π).
– If so, output 1, else ⊥.
For our proofs based on Sig′ with proofs of possession, we additionally needa version of the knowledge of exponent assumption [4] adapted to the bilinear
setting. Similar to the original one this assumption holds generically:
Definition 25 (Knowledge of exponent assumption). For a pair of groups(G1 , G2 , GT ) with generators (g1 , g2 , gT ) of prime orders p as above this assumption states that if there exists a PPT adversary A where:– A takes as input a generator h ∈ G1 .
– A outputs two group elements C ∈ G1 , Y ∈ G2 such that e(h, Y ) = e(C, g2 ),that is (g2 , Y ) and (h, C) have the same dlog relationship.
If such an A exists, then there exists a PPT extractor Ā, that takes the same
input (and potentially randomness) as A and outputs the same C, Y and additionally c, such that C = hc , Y = g2c .
17

We consider static corruptions for simplicity. However, we can easily extend ourmodel to allow for delayed active corruptions. In such a model, the committees
are dynamically sampled and the adversary is only allowed to corrupt parties after a
specified delay; this delay can then be set to be larger than the time a new committee
is sampled.

39

we achieve somewhat weaker guarantees compared to 15. The zero-knowledge
and extractability properties additionally need an input set W, such that for vk ∈W, simulation works, while for all other keys extractability works. Simulation
additionally needs an advice string, while we only need to program the oracle
once. Recall K is the relation on public-secret key pairs. We will now state what
guarantees we get for our modified BLS signature with proofs of possession:
A signature (KeyGen, Sign, Vrfy, Agg, AggVrfy, Prove, Valid) has an extractable
proof of possession, if there exists a PPT simulator S = (S0 , S1 ) and a PPT
extractor E, such that for every at most polynomially big set W there is somepolynomial advice-string advice such that the following holds:– Completeness as in definition 20.
– Zero-Knowledge: For all distinguishers D the following distributions are computationally indistinguishable:• Let Hpr be a random oracle. Give D oracle access to Hpr and Prove′ (·, ·),which responds like Prove(vk, sk) on input (vk, sk) ∈ K for vk ∈ W andwith ⊥ otherwise. Let D output a bit b.
• Let (H0 , τ ) ← S0 (W). Give D oracle access to H0 and S ′ (·, ·), which
responds like S1 (τ, vk, advice) on input (vk, sk) ∈ K for vk ∈ W and with⊥ otherwise. Let D output a bit b.
– Extractability: Let (H0 , τ ) ← S0 (W). For every algorithm A it holds:
Let (H0 , τ ) ← S0 (W). Give A oracle access to H0 , S ′ (·, ·). Let A finally output (vk, π), and let QA be the queries that A made to H0 , sk ← E(vk, π, τ, QA ).
Thenih
P r vk ̸∈ W ∧ (vk, sk) ̸∈ K ∧ ValidH0 (vk, π) = vk ≤ negl (λ)
Theorem 6. Given the knowledge of exponent assumption Sig′ with (Prove, Valid)instantiated by the proof of possession fulfills these requirements.
Proof. Completeness holds by the correctness of Sig′ .
Now let us move on: Let W and λ be given. We assume the experimentreceives/knows the generators g1 ∈ G1 , g2 ∈ G2 . We take an optional second
group element h ∈ G1 as parameter or choose h randomly ourselves. We define
the simulator S0 : It takes a pseudorandom function family PRFk with k ∈ {0, 1}asuch that the domain is large enough for any input ⟨vk⟩ for vk generated by
KeyGen(1λ ) and output mapped into Zp . It chooses k ←$ {0, 1}a , sets(
PRF (m)
if m represents ⟨vk⟩ for vk ∈ W
g1 k
H0 (m) =PRFk (m)hotherwiseand outputs τ = k as information to S1 . Let us now argue zero-knowledge
holds: We construct S1 as follows: S1 (k, vk, advice) retrieves r = PRFk (⟨vk⟩) andoutputs (H0 , a(vk)r ) for advice being a function a : W → G1 , such that for every
vk = g2sk ∈ W, a(vk) = g1sk .
In a first hybrid, we can replace Hpr by H0 in the first distribution. D can
not detect the change except with negligible probability, or else it could break40

pseudorandomness of PRF. Since we only have to regard vk ∈ W, as other
inputs prompt the return of ⊥ in both distributions, it holds a(vk)r = g1sk·r =H0 (⟨vk⟩)sk . The distributions are then identical.
It remains to show extractability. Let us assume there is an algorithm Athat produces an accepting output (vk, π) with vk ̸∈ W with non-negligible
probability. We argue that we can build an adversary that internally runs A.
The adversary A′ receives a generator h′ ∈ G1 . It runs the experiment withh = h′ as the optional input. It runs S0 (W) and retrieves H0 , k.
It interacts with A like the experiment would, getting the queries QA made by
A and the outputs vk, π. The simulation via S works without any issues assimulateable and extractable keys are in distinct domains.
If A produces an accepting output vk, π for vk ̸∈ W, it must hold e(π, g2 ) =e(H0 (⟨vk⟩), vk) = e(hPRFk (m) , vk). Thus, (g2 , vk) and (hPRFk (m) , π) share thesame dlog relationship.
As we can see, this constitutes an adversary in the knowledge of exponent assumption. Therefore, we are guaranteed the existence of an efficient extractor Ā′that comes to the same output as A′ - namely π ∈ G1 , vk ∈ G2 and additionallyoutputs x such that vk = g2x .

Now if we want to use this in our proofs, instead of the Schnorr based variant,
we essentially set W as the keys made by the reduction and then can extract for
all keys chosen by the adversary. There are some subtleties to this however; inthe proof of unforgeability above, for example, we may sometimes have to give a
proof for vk∗ and sometimes the adversary may use vk∗ itself. To deal with this,
we guess in the beginning, which case happens and set W = ∅ or W = {vk∗ }with probability 1/2, introducing a factor 1/2 to our success probability. We
constructed all our proofs such that the advice string can always be constructed,
as for all vk = g2sk we give out in reductions, we make sure they already know
g1sk .

H

Proofs of Section 3

We prove the outstanding parts, correctness and security, from theorem 2.
First we establish correctness:
Proof. Let a parameter λ, a message m∗ , a depth d and an algorithm A be given.
Let ct ← EncBC (1λ , m∗ , d) at any point.
We show that if McFlyBC .Dec(ct, d) is run, when the number of finalized
blocks BC.QueryTime is greater or equal d, it outputs m. By construction, we
have ct ← SWE.Enc(1λ , V, (H(d))i∈[ℓ] , (m∗i )i∈[ℓ] ), where V is the (static) set ofkeys obtained from BC and (m∗i )i∈[ℓ] is the result of splitting m∗ into chunks
from {0, . . . , 2k − 1}.
41In our call to Dec, since BC.QueryTime is greater or equal d, we can call
(QueryAt, d) and receive (σ, U ), which is by definition, such that(σ, U ) = (Sig′ .Agg((σi )i∈S , (vki )i∈S ), (vki )i∈S ), where for all i ∈ [S] Sig′ .Vrfy(vki , H(d), σi ) = 1. By correctness of Sig′ , it holds
Sig′ .AggVrfy(σ, U, (H(d))i∈[S] ) = 1. We then call m ← SWE.Dec(ct, (σ)i∈[ℓ] , U, V ).
Now, if there was an index ind such that mind ̸= mind ∗ , forwarding thatind, V , U , (mi )i , (Ti )i and σ to the experiment for robust correctness of SWE
would constitute a winning adversary. Thus, except with negligible probabilitym = m∗ , concluding the proof.
Now, we show security:
Proof. Let λ, committee size n = poly(λ) and a corruption threshold c < n/2 begiven. Let us assume towards contradiction, that there is an adversary A with
non-negligible advantage ε in ExpLock (A, 1λ ).
First, we discuss a hybrid game H1 : It corresponds to the real experiment,but once we received d from A, if A has received a signature on H(d) before, weabort. If they query on a signature on that message afterwards, we also abort.
If A had a non-negligible advantage in differentiating H1 from the experiment,
they would have to have a non-negligible advantage in causing an abort. If thiswere the case, we could directly build a reduction against collision resistance ofH.
Thus, we now assume we have an adversary who wins in H1 with nonnegligible probability. We describe a reduction to security of SWE for t = n/2
out of n for the set of indices S = [n] at which the challenge message is included.
W.l.o.g. we assume n is even.
– The reduction gets access to Hpr from the experiment and sets up BC withaccess to Hpr .
– It computes CRS ← Setup(1λ ) and outputs it to A.
– It honestly simulates BC to A, except in the way it generates the keys andanswers signing queries.
– In the initialization:• Let C ′ be the indices of malicious keys chosen by A and set C̄ = [n] \ C ′ .
Let V ′ = (vki )i∈C ′ be the malicious keys and πi the corresponding proofs.
• The reduction receives n/2 + 1 keys VE = vk′i from the experiment andsets the first n/2 + 1 of the honest keys (vki )i∈C̄ , to be these vk′i . If theadversary chose |C ′ | < n/2 − 1, the remaining honest keys are generated
by Sig′ .KeyGen and saved as VR . The proofs of validity for keys in VE are
received from the experiment and for VR , the reduction computes themhonestly.
– For signing:• For keys in VR we sign honestly.
• For keys in VE we relay signing queries to the experiment.
42

– Then, we output VR ∪ V ′ as challenge keys to the experiment, where we
receive the validity proofs for V ′ from A. These verify by definition of BC.
– We receive messages m0 , m1 and a depth d > 0 from A. We choose (m0i )i ∈ [ℓ]as a split of m0 and (m1i )i ∈ [ℓ] as a split of m1 . We output (mi )i and Ti = d
for all i ∈ [ℓ] to the experiment.
– We receive back a ciphertext ct that we forward to A.
– Now, if A outputs a bit b in time, we output it to the experiment. Otherwise,
we output a random bit.
Note, that by our abort conditions, we have not asked for a signature on Tind
before outputting it nor afterwards, causing the interaction with the experiment
to run through.
If the experiment chooses bit b′ , our output is identically distributed to running H1 with b = b′ . Since we also guess randomly, if A does not output a bit,that means, that we get the same advantage as A does in H1 . Assuming securityof SWE, that concludes the proof.

I

Construction and proofs of our aggregate signaturescheme Sig′

Let two base groups G1 , G2 of prime order p with generators g1 , g2 which havea bilinear map e : G1 × G2 → GT into a target group GT with generator g. Also
we assume full-domain hash functions H : {0, 1}∗ → G1 , H2 : {0, 1}∗ → Zp andHpr : {0, 1}∗ → Zp . Let (Schnorr.Prove,Schnorr.Valid) be the non-interactive
variant of the well-known Schnorr proofs due to Fischlin [24].
Protocol Sig′
Sig′ .KeyGen(1λ ):– Randomly pick x ←$ Zp .
– Output (vk = g2 x , sk = x).
′
Sig .Sign(sk, T ):– Output H(T )sk .
Sig′ .Vrfy(vk, T, σ):– Compute h = H(T ).
– If (e(σ, g2 ) = e(h, vk)), output 1, else output 0.
Sig′ .Agg((σ1 , . . . , σk ), (vk1 , . . . , vkk )):– Compute ξi = H2 (vki ) for i ∈ [k].
Q−ξ– Compute Li = j∈[k],i̸=j ξi −ξj j for i ∈ [k].
Q
– Output σ ← i∈[k] σiLi .
′Sig .AggVrfy(σ, (vk1 ,Q. . . , vkk ), (T1 , . . . , Tk )):– If e(σ, g2 ) = i∈[k] e(H(Ti ), vki )Li , output 1. Output 0 otherwise.
Sig′ .Prove(vk, sk):– Output Schnorr.ProveHpr (vk, sk).
′
Sig .Valid(vk, π):– Output Schnorr.ValidHpr (vk, π).

43

Alternatively, we can use a standard proof of possession, where users sign an
encoding of their public key to show ownership, as in [33] instead of Schnorr,
if we additionally make the knowledge of exponent assumption and still build
SWE and McFly from it. This is discussed in Appendix G.
First, note that (Sig′ .Prove, Sig′ .Valid) constitutes a valid online-extractable
proof of knowledge for the key relation K = {(g x , x) : x ∈ Zp }, as shown in [24].
Theorem 7. Sig′ is correct.
Proof. The first part of correctness follows directly from [11] as the algorithms
and definitions are identical to standard BLS.
Let λ ∈ N, k = poly(λ), messages T1 , . . . , Tk a set of public keys V =(vk1 , . . . , vkk ) and signatures σ1 , . . . , σk be given such that Vrfy(vki , Ti , σi ) = 1
for i ∈ [k]. This means it holds e(σi , g2 ) = e(H(Ti ), vki ) for i ∈ [k]. Letσ ← Agg((σ1 , . . . , σk ), V ). We need to show AggVrfy(σ, V, (TQ
1 , . . . , Tk )) = 1.
By construction, the aggregated multi-signature is σ = i∈[k] σiLi for Li as
defined in our algorithm. Now, in our call to AggVrfy, it holdsYYYe(σ, g2 ) = e(σiLi , g2 ) =e(σi , g2 )Li =e(H(Ti ), vki )Li .
i∈[k]

i∈[k]

i∈[k]

Therefore, the output is 1.
Theorem 8. Assume that H is modelled as a random oracle. Sig′ is unforgeable,
given that the computational Co-Diffie-Hellman assumption holds for (G1 , G2 ).
Proof. Our proof takes some ideas from [33] and [10], but mainly works due tothe extractability of Schnorr. We will regard adversaries A that will be allowed
to make only polynomially many qS queries for signatures.
We assume that A has non-negligible winning probability ε and will only
output a forge (T1 , . . . , Tk ), (vk2 , . . . , vkk ), (π2 , . . . , πk ), σ ∗ where Valid(vki , πi ) =1 for all i ∈ {2, . . . , k} and T1 was not queried to the signing oracle, otherwise
they would not be able to win in the unforgeability experiment. Assuming control
over the random oracle, we can use the fact that (Prove, Valid) constitutes anonline-extractable proof of knowledge.
We define a reduction against co-CDH:
The challenger receives a tuple g1 , h1 = g1x , g2 , h2 = g2x , h with the publicparameters g1 , g2 as generators and is required to output hx .
The experiment executes (Hpr , τ0 ) ← S(0, 1λ ) and provides oracle access to
Hpr to A.
The adversary gets access to the publicly known G1 , G2 , g1 , g2 , H2 . Queries tothe hash function H are being programmed by the reduction.
The reduction provides as public key vk∗ = h2 to A.
Any queries to H are answered as follows:– If the message T was previously queried, we respond as before.
– Else, with probability δ we select its hash as h · g1θ for random θ ←$ [p]and save T to a special list C.
44

– Otherwise, we select its hash as g1θ for random θ ←$ [p]– In both cases, we save A[T ] = θ
If A queries for a proof of knowledge for vk∗ , then we call (H1 , π ∗ , τ ′ ) ← S(1,vk∗ , τ, YES), respond with π ∗ and replace the oracle Hpr by H1 in future
calls. By zero-knowledge of Schnorr, this is indistinguishable from the realexperiment’s output except with negligible probability. We note, that allvk ∈ G2 actually have a valid secret key, making the YES call justified.
Any queries to the signing oracle for a message T under vk∗ are answered asfollows:– We determine H(T ).
– If T is in the special list C, we abort.
– Otherwise, we know the hash H(T ) = g1θ .
– We output as signature hθ1 . Since h1 = g1x for some x such that vk =h2 = g2x , this is simply g1θx = H(T )x , which is a valid signature undervk.
Once we receive (T1 , . . . , Tk ), (vk2 , . . . , vkk ), (π2 , . . . , πk ), σ ∗ from A,– For i ∈ {2, . . . , k}, we call the PPT extractor E(vki , πi , QA ) where QA
are the queries to Hpr so far.
– Since Valid(vki , πi ) holds by assumption, we can extract the ski except
with negligible probability and save them to a table P [vki ] = ski . If wefail to extract for any index, we abort.
– We check whether T1 is on the list C and whether σ ∗ is a valid forge. If
this is not the case, we abort.
– If any of the keys vk2 , . . . , vkn is equal to vk∗ , the adversary may nothave asked for our simulated proof on vk∗ and therefore must have given
a proof of their own which we extracted from - we have x = P [vki ] forthat key by definition and thus Q
can output hx directly.
∗– Otherwise, it holds e(σ , g2 ) = i∈[k] e(H(Ti ), vki )Li where we considervk∗ = vk1 .
– Now for i ∈ {2, . . . , k}, we can make partial signatures σi = H(Ti )P [vki ]LiLiwith e(σi , g2 ) = e(H(TQi ), vki ) .
– We set σ ′ to be σ ∗ / i∈{2,...,k} (σi ). Now, it clearly holds e(σ ′ , g2 ) =A[T ]e(H(T1 ), vk1 )L1 . Therefore, σ ′ = (h · g1 1 )xL1 .
−L1

σ′
= hx . This holds as h1 = g1x .
We output
A[T1 ]L1
h1

Clearly, if no abort occurs, the output is indeed hx .
Now, what is the success probability? Assume the adversary A has advantage
ε in winning the unforgeability experiment. If they win, they can either query
us for a proof on vk∗ or be able to include vk∗ in their forge.
A can only succeed, if its combined probability of successfully registering all
keys vk2 , . . . , vkk it chooses is at least ε, making every one of these probabilities
non-negligible. By extractability of our proof of knowledge and a union bound,
this means we can extract all secret keys in polynomial time except with negligible probability. We note that since the hashes and vk∗ are distributed uniformly
random, this looks indistinguishable from the real experiment for A unless they45

request a signature for one of the messages where T is in C. This probability
can be bounded by (1 − δ)qS , assuming A only queries for messages once, as theprobability is clearly independent for every message requested. Conditioned on
no such request being made, we have a probability of ε of the adversary winning.
Since the hash(es) which we created as h · g1θ are i.i.d. in the view of A, we thenhave a probability of δ of the first message m1 in fact being such that we don’t
abort.
This gives us a winning probability negligibly worse than (1 − δ)qS · δ · ε.
By appropriately choosing δ = 1/qS we get (1 − 1/qS )qS · 1/qS · ε ≥ 0.1/qS · ε,assuming that qS ≥ 2, as (1 − 1/x)x converges to 1/e in a strictly increasingmanner. Therefore the advantage of the reduction will be non-negligible, if ε is
not negligible.
The reduction is clearly running in polynomial time if A is.

J

Proofs of Section 2

We will show theorem 1, by splitting it into its parts and proving each.
Theorem 9. SWE for the signature scheme Sig′ has robust correctness, giventhat H2 is collision resistant.
Proof. Let λ ∈ N, ℓ = poly(λ) be given. Let us assume towards contradiction,that there is an adversary A with non-negligible winning probability against theexperiment.
Let us consider a hybrid H1 : It is identical to the experiment, except if
H2 (vki ) = H2 (vkj ) for any i, j ∈ [n], i ̸= j, we abort. Clearly, except withnegligible probability running H1 with A has the same outcome as the original
experiment. Otherwise, we could build a reduction against the collision resistanceof H2 .
We now show, that in H1 , the probability of winning for the adversary is 0.
Let any index ind ∈ [ℓ], keys V = (vk1 , . . . , vkn ), a subset U ⊆ V with |U | ≥ t,reference messages (Ti )i∈[ℓ] , messages (mi )i∈[ℓ] and (σi )i∈[ℓ] be given by A. Let
I be the set of all indices i for which vki ∈ U .
We note, that since g2 is a generator of G2 , there exist xi such that vki = g2xi
for
AggVrfy(σind , U, (Tind )i∈[|U |] ) = 1, that is e(σind , g2 ) =Q i ∈ [n]. We assumeLii∈I e(H(Tind ), vki ) . Otherwise, A could not win. We now show that
Dec(Enc(1λ , V, (Ti )i∈[ℓ] , (mi )i∈[ℓ] ), (σi )i∈[ℓ] , U, V )ind = mind
The ciphertext ct = (h, c, c0 , (cj )j∈[n] , (c′i )i∈[ℓ] ) = Enc(1λ , V, (Ti )i∈[ℓ] , (mi )i∈[ℓ] )shas the relevant components for decryption c = g2r , cj = vkrj · g2j for j ∈ [n] and′r0mici = e(H(Ti ), g2 ) · g for i ∈ [ℓ], where sj = f (ξj ) for a polynomial such thatf (0) = r0 .
Now, the ξj , Lj computed by Dec are identical to those used in Enc and in
Sig′ .Sign. Note that since no two distinct vkj ̸= vkj ′ collide under H2 , the support46

points ξj = H2 (vkj ) are all distinct and |I| ≥ t so LagrangePinterpolation willcorrectly recover r0 from the sj by computing r0 = f (0) = j∈I sj Lj . Thus it
holds that

r
Y L
Y L
Y sL
c∗ =
cj j =  vkj j  ·g2j j = (vk∗ )r · g2r0 .
j∈Iwhere vk∗ :=

j∈I

j∈I

P

Lj
j∈I xj Lj. Thus, it holds for index ind:j∈I vkj = g2

Q

P
r·

xj Lj

e(H(Tind ), c∗ ) = e(H(Tind ), g2 j∈I· g2r0 )Y=e(H(Tind ), vkj )r·Lj · e(H(Tind ), g2 )r0j∈I= e(σind , g2 )r · e(H(Tind ), g2 )r0= e(σind , c) · e(H(Tind ), g2 )r0 .
Since c′ind = e(H(Tind ), g2 )r0 · gTmind , it follows that zind = c′ind · e(σind , c)/e(H(Tind ),c∗ ) = gTmind . It follows for the ind-th output: m′ind = dloggT (zind ) = mind , androbust correctness follows.
Theorem 10. Assume that the hash functions H, H2 , Hpr are modelled as random oracles. Then SWE for the signature scheme Sig′ is secure under the BDH
assumption in (G1 , G2 ). The security reduction is tight.
Proof. Assume that A is a PPT adversary against the SWE security experiment with distinguishing advantage ε. We will construct a PPT distinguisher Dwith advantage ε against the BDH problem in (G1 , G2 ). The complexity of D isessentially the same as that of A.
Let I = {1, . . . , t − 1} be the set of indices of verification keys vki which arechosen by the adversary. For each i ∈ I let vki = g2xi where ski = xi . In thefollowing we will assume that the distinguisher D has access to all the signingkeys xi for i ∈ I. This can be achieved, by using the fact that Sig′ has an
online-extractable proof of knowledge.
Let SC be the set of indices at which the challenge messages are included inencryption.
The distinguisher D receives as input a tuple (g1 , h1 , v, g2 , h2 , w, z), where g1
is a generator of G1 , g2 is a generator of G2 , h1 = g1x for some x ∈ Zp , h2 = g2x
for the same x ∈ Zp , v = g1α for an α ∈ Zp and w = g2r for an r ∈ Zp . The termz ∈ GT is either of the form gtαxr , in which case we say that this is a BDH tuple,or z is chosen uniformly random from GT , in which case we say this is a random
tuple.
The distinguisher D simulates the security experiment for SWE, except in
the way the verification keys vki for i ∈ I¯ = {t, . . . , n} are chosen, the corresponding signatures for these keys are computed and the challenge-ciphertext
ct∗ is computed. It uses the simulator S to create Hpr and the outputs of Prove47

on its verification keys and it uses the extractor to gain access to the secret keysof the adversary.
To simulate the random oracles H, H2 lazily, D initializes two lists L, L2 = ∅.
D first computes the following auxiliary terms.
– For i ∈ [n] randomly draw ξi ←$ Zp .
– Define the Lagrange polynomials
L′0 (x) =Y x − ξjj∈I

−ξjand L′i (x) =xξiYj∈I\{i}x − ξjξi − ξjfor i ∈ I. That is, the L′i are an interpolation basis for the support points{0} ∪ {ξj | j ∈ I}.
L′ (ξ )– For every i ∈ I¯ choose x′ ← Zp uniformly at random and set h1,i = h 0 i ·x′L′ (ξ )x′i

1

g1 i , h2,i = h2 0 i · g2 i .
– Choose y ← Zp uniformly at random and set A = e(v, g2 )y /z and B =gTy /e(h1 , w).
– The reduction sets (H0 , τ0 ) ← S(0, 1λ ). It also sets a counter ctr = 1.
The verification keys vki , random-oracle queries, signature queries and thechallenge ciphertext ct∗ are now computed as follows.
¯ D computes the verification key vki– For every honest party with index i ∈ I,
as vki = h2,i and generates the associated proof of knowledge by(Hctr , πi , τctr ) ← S(ctr , vki , τctr −1 , YES), incrementing ctr after each call.
Finally, we set Hpr = Hctr and make it available to A. Due to the zeroknowledge property of the proof of knowledge, this is possible without noticeably changing the distribution of the output from the real experiment,
except with negligible probability.
– When A sends (vki , πi ) for i ∈ I, we proceed as follows.
• If ValidHpr (vki , πi ) ̸= 1 for any i ∈ I we return ⊥.
• Otherwise, we compute and store ski ← E(vki , πi , QA ), where QA denotes the queries to Hpr that A made so far.
By extractability, extraction of the secret keys succeeds except with negligible probability. Since A must give a valid proof for all of its polynomiallymany keys, we extract all their secret keys except with negligible probability.
– Every query to H for a message T ̸= Ti for all i ∈ SC (or before the challenge
messages are announced) is answered as follows: If H has been queried on
T before, retrieve the pair (T, αT ) from the list L. Otherwise, choose αT
uniformly at random, add (T, αT ) to L. Output g1αT . We will program H on
(Ti )i∈SC specifically later on.
– Every query to H2 on some input X is treated similarly: Initially, we add(vki , ξi ) to L2 for every i ∈ [n]. If L2 has an entry for X, retrieve the pair(X, βX ) from the list L2 . Otherwise, choose βX uniformly at random, add(X, βX ) to L2 . Output βX .
48

– For every signature query of a message T ̸= Ti for all i ∈ SC (or before the¯ Dchallenge messages are announced) for an honest party with index i ∈ I,
computes the signature σ as follows. Determine H(T ) and retrieve the pairT(T, αT ) from the list L. Output σ = hα1,i .
– D computes the challenge-ciphertext ct∗ as follows.
• Set c = w.
• Draw randomly γ ← Zp .
• Set h = h2 · g2γ .
• Set c0 = wγ · g2y .
• For all i ∈ I choose si uniformly at
random and set ci = wxi · g2si .
P
L′0 (ξi )y+ j∈I L′j (ξi )·sj′
• For all i ∈ I¯ we set ci = g· w xi .
•

2
αT y
j
m
′
For all j ∈ [ℓ] \ SC set cj = e(g1 ,g2 ) αTj gT j where (Tj , αTj ) is from L.
e(h ,w)
1• For i ∈ SC choose γi , δi ← Zp uniformly at random, program H(Ti ) =v γi · g1δi and set c′i = Aγi · B δi · gTmi .
We will now show the following:
1. If (g1 , h1 , v, g2 , h2 , w, z) follows the BDH distribution, i.e. h1 = g1x , h2 = g2x ,v = g1α , w = g2r and z = gTαxr , then D simulates the security experiment of
SWE perfectly from the view of A. Thus, A’s advantage in this simulation
is at least ε.
2. If (g1 , h1 , v, g2 , h2 , w, z) follows the random distribution, i.e. h1 = g1x , h2 =g2x , v = g1α , w = g2r and z = u for a uniformly random u ← GT , then theadvantage of A in D’s simulation is 0.
From these two points it will follow that the distinguishing advantage of Dagainst BDH is at least ε.
We will first analyze the distribution of the vki , the signatures σ and thechallenge-ciphertext components h, c0 , c and ci .
¯ It holds that
We will first calculate the terms h1,i and h2,i for i ∈ I.
L′ (ξi )h1,i = h1 0

L′ (ξi )h2,i = h2 0x′L′ (ξi )x+x′i= g1x̃ix′

L′ (ξi )x+x′i= g2x̃i ,· g1 i = g1 0
· g2 i = g2 0

where we set x̃i = L′0 (ξi )x + x′i . Note that since the x′i are uniformly random, so
are the x̃i .
Hence, for the verification keys vki for i ∈ I¯ it holds thatvki = h2,i = g2x̃i .
Next, we consider the distribution of the signatures σ of a message T created¯ It holds thatupon a signing request for an honest key vki for i ∈ I.
αT ·x̃iT
σ = hα= H(T )x̃i .
1,i = g1

Regarding the challenge-ciphertext ct∗ , let us make some definitions. We
define r0 = y − rx and set f to be the (uniquely defined) polynomial of degree49¯ we now sett − 1 obtained by interpolating the pairs (0, r0 ), (ξi , si )i∈I . For i ∈ I,
si = f (ξi ). Now, the following holds:– c = w = g2r– h = h2 · g2γ is uniformly distributed– c0 = wγ · g2y = g2γr · g2y−xr+xr = (g2γ+x )r · g2r0 = hr · g2r0
– For i ∈ I it holds thatci = wxi · g2si = g2r·xi · g2si = vkri · g2si .
– For i ∈ I¯ it holds thatP
L′ (ξi )·y+ j∈I L′j (ξi )sj

ci = g2 0′· w xiP
L′ (ξi )·(rx+r0 )+rx′i + j∈I L′j (ξi )sj= g2 0Pr(L′ (ξi )x+x′i )+L′0 (ξi )r0 + j∈I L′j (ξi )sj= g2 0r(L′0 (ξi )x+x′i )+f (ξi )= g2= g2rx̃i +si= vkri · g2si .
Note that the si have the proper distribution: r0 as well as the si for i ∈ I are
uniformly random and independent. Thus f is a uniformly random polynomialof degree t − 1. Next, we consider the ciphertext components c′j for j ∈ [ℓ] \ SC.
It holds
e(g1 , g2 )αTj y mjge(h1 , w)αTj Te(g1 , g2 )αTj y mj=ge(g1x , g2r )αTj T

c′j =

m

= e(g1 , g2 )αTj (y−xr) gT jαTm= e(g1 j , g2 )r0 gT jm

= e(H(Tj ), g2 )r0 gT j .
This conforms to the regular distribution.
We will finally consider the ciphertext components c′i for i ∈ SC. In thefirst case, assume that (g1 , h1 , v, g2 , h2 , w, z) follows the BDH distribution, i.e.
z = gTαxr . In this case, it holds thatα(rx+r0 )A = e(v, g2 )y /z = gT

· gT−αxr = gTαr0

and
B = gTy /e(h1 , w) = gTrx+r0 · gT−xr = gTr0 .
It follows that
H(Ti ) = v γi · g1δi = g1γi α+δi = g1αi ,50where we set αi = γi α + δi . Note that since δi is chosen uniformly random, αi is
distributed uniformly random.
Now, c′i is distributed according toc′i = Aγi · B δi · gTmi
= gTαr0 γi · gTr0 δi · gTmi
r ·(γi α+δi )= gT0· gTmi= gTαi r0 · gTmi
= e(g1αi , g2 )r0 · gTmi
= e(H(Ti ), g2 )r0 · gTmi .
Thus, c′i has the same distribution as in the SWE security experiment.
On the other hand, if (g1 , h1 , v, g2 , h2 , w, z) follows the random distribution,then write z as z = gTαxr+τ for a uniformly random and independent τ . Sinceτ is uniformly random, it holds that τ ̸= 0, except with negligible probability
1/p. Thus assume in the following that τ ̸= 0. The terms B and H(Tind ) arecomputed as above. The term A is now of the formα(rx+r0 )A = e(v, g2 )y /z = gT

· gT−αxr−τ = gTαr0 −τ .

Finally, the terms c′i for i ∈ SC are of the form:
c′i = Aγi · B δi · gTmi
r ·(γi α+δi )−τ γi= gT0· gTmir ·(γi α+δi ) −τ γ
gT · gTmi= gT0

Now note that since γi and δi are uniformly random and independent, γi α + δi
and τ γi are also uniformly random and independent as τ ̸= 018 . Since the termgT−τ γ is uniformly random and independent of all other terms, it follows that c′i
is uniformly random and thus independent of mi . Consequently, in this case theadvantage of A is 0.

18This can be seen as the matrix

 α1
has full rank given that τ ̸= 0.
τ 051