# How to Build a Time Lock Crypto Service based on League of Entropy (drand)
## Vincenzo Iovino, [Aragon ZK Research](https://research.aragon.org/)

## Setting and motivation
We assume the reader to be familiar with the League of Entropy (a.k.a. [drand](https://drand.love)) system but the presentation of our treatment is self-contained.
In the following we denote by $g_1,g_2$ the generators of the groups $G_1,G_2$ of some prime order $p$ used by LOE, and by $PK_L$ the public key of LOE that has the form $PK_L=g_2^{sk_L}$ where $sk_L\in Z_p$ is the corresponding secret key that is shared by the LOE members.
For simplicity, in the following we will often say that at time $C$ LOE releases a secret key $SK_C$ whereas we should actually refer to a round number rather than a time.
We recall that LOE is a coalition of members who, at each time interval $C$, release a BLS signature $\sigma_C=Hash(C)^{SK_L}$, where $Hash$ is a (standardized hash function) that maps bit strings to points in $G_1$ (we skip technical details about the actual encodings of $C$). This signature is jointly computed in a threshold fashion by the LOE members in a way that a minority of the members cannot obtain the secret key $SK_L$ (that is shared by the members).
To ease our presentation, henceforth we denote by $SK_C$ the signature $\sigma_C$ for time $C$ and we say that $SK_C$ is the secret key of LOE for time $C$.
For the purpose of our treatment, the reader does not need to know the details of the LOE protocol but simply that at each time interval $C$ the afore-mentioned secret key $SK_C$ is publicly available.

We want a cryptographic protocol among a set of parties to jointly construct a public key $PK$ whose corresponding secret key $sk$ can be publicly computed only at time greater or equal than $C$ when the secret key $SK_C$ of LOE for time $C$ will be made available; here $C$ is a public input to all parties.
The public key $PK$ should have the form $g^{sk}$ where $g$ is the generator of a group of some prime order $q$, so $sk \in Z_q$. We look for generic approaches so we consider any kind of prime order group in which the Dlog Assumption holds: that is elliptic curve groups (both bilinear and non-bilinear groups) and multiplicative groups of prime order; [later on](#Generalization-to-any-homomorphic-OWF-and-thus-to-RSA) we will also cover a specific RSA setting.
This public key $PK$ can be then used for encryption using any encryption scheme defined over the group generated by $g$ (later on we will also discuss other applications to digital signatures and zero-knowledge proofs).

Observe that this problem, though related, is independent from the recently proposed [timelock encryption](https://eprint.iacr.org/2015/482) primitive. Indeed, a user Alice can use the public key $PK$, that was part of the output of an execution of the TLCS protocol for time $C$, to encrypt measages without specifying any time and only performing cryptographic operations related to the group generated by $g$. After time $C$, using $SK_C$ and the transcript of the TLCS protocol anyone (and thus a smart contract) can compute the secret key $sk$ corresponding to $PK$. Bob can use $sk$ to decrypt Alice's messages. Observe that, unlike timelock encryption, here the computations of Alice and Bob are completely independent from the LOE system.

We assume that there is a blockchain on which anyone (or possibly only registered people to avoid DoS) can post data as a mean to generate a public key PK and some related data that can be used by anyone, and so by a smart contract, to obtain the corresponding secret key $sk$ at time $C$.

Additionally, we want that there is a committee of members that anyone can freely join, that is the set of participants in a particular execution of the protocol is not fixed, and we want the protocol to require just one message of interaction from each participant (assuming a perfect broadcast channel like a blockchain).

## Warmup: a TLCS protocol from general-purpose NIZK proofs
Consider the following protocol.
The generic party $i=1,...$ does the following. It computes $PK_i=g^{sk_i}$, where $sk_i$ is randomly chosen in $Z_q$.
It chooses random $t_i$ from $Z_p$ and computes $T_i=g_2^{t_i}$, $Z_i=e(H(C),PK_L)^{t_i}$ and $y_i=H(Z_i) \oplus sk_i$.
The party $i$ posts on the blokchain:
$(T_i, y_i)$. Note that $Z_i$ is not posted, and the honest party is required to delete $Z_i, t_i,sk_i$ from his memory, so that until time $C$ nobody can get $sk_i$.

At some point, the public key construction phase terminates and no new party can participate.
Then, the public key $PK$ is set to $PK=\prod_i PK_i=g^{sk}$, where $sk=\sum_i sk_i \mod q$.

When the secret $SK_C=H(C)^{sk_L}$ of LOE is published at time $C$, anyone can publicly do the following based on the information posted on the blockchain.
For any $i$ compute $e(SK_C,T_i)=Z_i$ and then can compute $sk_i=y_i \oplus H(Z_i)$.

From all $sk_i$'s, anyone can then recover $sk=\sum_i sk_i \mod q$.

The security here guarantees that if only a single party is trusted in having deleted his memory at the of the computation, then the secret key $sk$ corresponding to $PK$ is protected until time $C$ assuming that the majority of LOE members are honest.
That is, the only added assumption beyond LOE is that there is a single honest party. Observe that, since anyone can publicly participate in the protocol (that is the committee allows on-fly join), if someone does not trust the system can decide on participating in the protocol freely.

To be able to decrypt we need to assume that the values $y_i$'s posted on the blockchain are computed correctly according to the above procedure, so each $y_i$ needs to be accompained with a ZK proof of well-formedness, that is a proof that the tuple $(g_2,PK_L,C,T_i,PK_i,y_i)$ is such that there exist values $t_i\in Z_p$, $sk_i\in Z_q$ such that $T_i=g_2^{t_i}$, $Z_i=e(H(C),PK_L)^{t_i}$, $y_i=H(Z_i) \oplus sk_i$ and $PK_i=g^{sk_i}$.
The proof system needs to be non-malleable to prevent attacks in which the last party can induce a public key of which he knows the corresponding secret key; alternatively, a standard non-interactive Schnorr's proof must be attacked to each partial public key $PK_i$.

This requires a NIZK proof of computation of exponentiation in the target group. Notice that if a tuple $(PK_i,T_i,y_i)$ does not come with a valid proof, it will not be used for the computation of $PK$.

## The muon protocol: an efficient TLCS protocol that avoids general-purpose NIZK proofs
The above NIZK proof could be implemented with general-purpose SNARK for circuits that compute operations in the target group of the LOE's curve.
In this section we show how to implement a variant of the above protocol that avoids general-purpose NIZK proofs that we call the *muon* protocol.

(In the following we will be focusing on a single party so we will remove the subscript $i$ that refers to the parties. So when you read $PK$, this is actually $PK_i$ of the previous notation and not the public key that is the result of the shares of all committee members. We choose to do that to minimize the number of subscripts to fit better in hackmd.)

We will construct an interactive protocol. This can be done non-interactive via the FS transform.

There is a security parameter $k$ that affects the soundness error, precisely the soundness error will be $2^{-k}$ so there is a trade-off: we have freedom to choose $k$ as large as possible to reduce the soundness error and as small as possible to make the system more efficient.

The generic party (the prover) has a public key $PK=g^{sk}$, where $sk\in Z_q$ is known to the prover but not to the verifier.
For $j=1,\ldots,k$ the prover chooses two random values $sk_{j,1},sk_{j,2}$ that sum up to $sk$ and sets $PK_{j,1}=g^{sk_{j,1}},PK_{j,2}=g^{sk_{j,2}}$.

For $j=1,\ldots, k$, the prover chooses random $t_{j,1},t_{j,2}$ from $Z_p$ and computes $T_{j,1}=g_2^{t_{j,1}}$, $Z_{j,1}=e(H(C),PK_L)^{t_{j,1}}$ and $y_{j,1}=H(Z_{j,1}) \oplus sk_{j,1}$ and similarly $T_{j,2},Z_{j,2},y_{j,2}$.
The prover sends to the verifier the value $PK$ and the list of tuples:
$(PK_{j,b},T_{j,b_j},y_{j,b})_{j\in[k],b\in\{1,2\}}$.

(Note: as explained before here we removed the subscript $i$ so $PK$ refers to the contribution of a generic party and not to the final public key that is computed as product of the public keys of all members. We do not include the further subscript $i$ to avoid many subscripts like "$PK_{i,j,b_j}$", etc.)

The verifier chooses a vector of $k$ random values $b_1,\ldots,b_k$ in $\{1,2\}$ and sends it to the prover.
For all $j\in[k]$ the prover sets $t_j=t_{j,b_j}$ and sends back to the verifier the tuple $(t_j)_{j\in[k]}$. The verifier accepts iff all the following checks pass:

- 1. For all $j=1,\ldots,k$ check that $PK_{j,1}* PK_{j,2}=PK$.
That is, the verifier checks that all the pairs of public keys form a $2$ out of $2$ secret sharing of the same public key $PK$. This also convinces the verifier that the same condition holds with respect to the secret keys, that is that for all $i=1,\ldots,k$, $sk_{j,1}+sk_{j,2}=sk$ modulo $q$, where $PK=g^{sk}$.
- 2. The verifier now checks that the tuple $PK_{j,b_j},T_{j,b_j},y_{j,b_j}$ is well-formed in the following way. The verifier computes $Z_j=e(H(C),PK_L)^{t_j}$. If $t_j$ was equal to $t_{j,b_j}$ then it holds that $Z_j=Z_{j,b_j}$. The verifier computes $s_j=H(Z_j) \oplus y_{j,b_j}.$ If $t_j$ was equal to $t_{j,b_j}$ then it holds that $s_j=sk_{j,b_j}$. The verifier checks that $PK_{j,b_j}=g^{s_j}$ and that $T_{j,b_j}=g_2^{t_j}$. This convinces the verifier that $s_j=sk_{j,b_j}$ and that $sk_{j,b_j}$ is the secret key corresponding to $PK_{j,b_j}$.

Let $s_{j,1}$ and $s_{j,2}$ be the values induced by $SK_C$ that should be equal to resp. $sk_{j,1}$ and $sk_{j,2}$ if the prover is honest.
If $PK$ was not invertible (that is if $sk$ is not equal to $s_{j,1}+s_{j,2}\ mod\ q$ then: if the first check with respect to a generic $j$ passes then the second check with respect to the same $j$ can pass only with prob. at most $1/2$ over the choice of $b_j$.
So the prob. that a malicious committee member convinces the verifier is $1/2^k$.

If the proof passes the public key $PK$ of the party is accepted and is used to compute the public key for time $C$ by multiplying together all the public keys of all parties whose proofs were accepted.

At time $C$, to recover the corresponding secret key $sk$ using the value $SK_C=H(C)^{SK_L}$ released by LOE, one runs the following procedure.
- for j=1 to k:

- For all $b\in\{1,2\}$ compute $e(H(C)^{SK_L},T_{j,b})=Z_{j,b}$, $s_{j,b}=H(Z_{j,b}) \oplus y_{j,b}$.
- If $g^{s_{j,1}}=PK_{j,1}$ and $g^{s_{j,2}}=PK_{j,2}$ and $PK_{j,1} * PK_{j,2}=PK$ then return $sk=s_{j,1}+s_{j,2}\ mod\ q$ else continue;

The previous proof can be made non-interactive by having the prover to choose the vector $b_1,...,b_k$ as hash of the string $[PK,(PK_{j,b},T_{j,b_j},y_{j,b})_{j\in[k]}]$.
The verifier does the same to recompute the vector $b_1,...,b_k$ in a deterministic way.
Under mild conditions the non-interactive variant can be made weak simulation sound extractable (see [here](https://eprint.iacr.org/2012/704)) since the previous TLCS protocol is a sigma protocol.
* TODO: check that the conditions are satisfied.

### Variants based on general secret sharing
The above system can be modified having in each repetition e.g. a prob. of error of $1/3$ instead of $1/2$ and with overall shorter proofs.
The idea is the following.
For each $j\in[k]$ we can choose e.g. $3$ secret keys $sk_{j,1},...,sk_{j,3}$ so that they form e.g. a $2$ out of $3$ secret sharing of $sk$. That is, for all $i\in[3]$, $sk_{j,i}=p_j(i)$, where $p_j$ is a random degree one polynomial whose constant term equals $sk$. Thus, by means of the Lagrange coefficients, any subset of size $2$ of such keys can be used to reconstruct $sk$.
Then we let as before $PK_{j,1},...,PK_{j,3}$ be the corresponding public keys.
The verifier in check 1 is changed as follows. The verifier will verify that any subset $S$ of $\{1,...,3\}$ of cardinality $2$ of such public keys is such that $\prod_{l\in S} PK_{j,l}^{\lambda_{S,l}}=PK$, where the values $\lambda_{S,l},l\in S$ are the Lagrange coefficients for set $S$. Since there are $3$ subsets of $\{1,...,3\}$ of cardinality $2$, check $1$ requires $3*2=6$ exponentiations in the cyclic group.
In check $2$ the verifier will do the checks as above except for the following change.
Before, the check was with respect to a single random bit. Now the check is with respect to a random index $k$ in $\{1,...,3\}$.
Now we notice that if the check $1$ passes the party could cheat only if there exists at most one index $k'$ such that the public key $PK_{j,k'}$ is invertible and the verifier happens to choose $k=k'$ and this occurs with prob. $1/3$.
So, with still one exponentiation in the target group per iteration we get error $1/3$ and we decreased the communication (the size of the proof).

Experiments show that, though the time performance may not be much better, this approach is preferable when attempting to reduce the communication cost. The time verification cost depends on the ratio of efficiency between exponentiations in target group and exponentiations in the cyclic groups.
If for some cyclic group this ratio were high (that is exponentiations in the target group were much more expensive than exponentiations in the cyclic group), the approach on general secret sharing would also be more efficient in terms of time costs for the verifier. For example, in some applications the period between publication of the tlock public key and revealing of the corresponding secret key could be short; in such case it could make sense to use cyclic groups with short security parameters so that the secret sharing variant could improve more on verification time. In most cases this variant improves slightly on proof size.

For the concrete case of e.g. a 2 out of 3 SS one can choose the interpolation points so as to make the Lagrange coefficients to be small integers.
#### Random check trick
Another trick to make the SS variant more efficient is the following. Let us assume a 2 out of 4 SS as above. The verifier can be modified so as to choose random scalars $r_j,j\in[k]$ and to set for each $l\in [4]$:

$RPK_{l}=\prod_{j\in[k]}PK_{j,l}^{r_j}$

Then, the verifier can check for each subset $S$ of $[4]$ of cardinality $2$ that:

$\prod_{l\in S} RPK_{l}^{\lambda_{S,l}}=PK^{\sum_{j\in[k]} r_j}$
In this way, the verifier would do a number of exponentiations in the cyclic group of the order $4k+13$ rather than $12k$, and this should make the verifier of the 2 out of 4 SS variant more efficient.
* TODO: check the soundness of the approach and implement it.

### Generalization to any homomorphic OWF and thus to RSA
The previous protocol only uses the following facts:
- The exponentiation in a cyclic group is difficult to invert (for security).
- The exponentiation in a cyclic group is easy to check, that is given $sk$ and $PK$ it is easy to check if $PK=g^{sk}$.
- The exponentiation in a cyclic group is homomorphic, that is the product of two public keys $PK_1,PK_2$ whose secret keys are resp. $sk_1,sk_2$ is a public key $PK$ such that the corresponding secret key $sk$ equals $sk_1+sk_2$ modulo the order of the group.

This can be generalized to any homomorphic one-way function (OWF). Exponentiation in cyclic groups are examples of homomorphic OWFs but another notable example is RSA.
Given a modulus $N$ product of two safe primes and an exponent $d\in Z_{\phi(\phi(N))}$, the RSA function $f_{RSA}$ is the function that maps $x$ to $x^d\ mod\ N$. This function can be seen to be also homomorphic.
Note that we do *not* claim that we can use this directly for OAEP or related RSA-based encryption schemes.

Additionally, we have a trapdoor: if a party has the factorization of the modulus, this party is able to invert the evaluation of the function $PK=f_{RSA}(sk)$ before the prescribed time to get the corresponding secret key $sk$.
Observe that the variant with general secret sharing does not generalize to RSA and all homomorphic OWF.

### Free joins without spamming the blockchain?
Depending on the resources of the blockchain nodes it might be possible only to verify proofs and accept the contribution of a small fraction of the total committee members, especially if huge number of parties want to contribute. For concreteness, it might be that the nodes have resources to work only on $N$ committee members.
In that case, the blockchain can do the following. There is a time $d$ before which parties can submit their contribution. At time $d$ one sees the random beacon published by LOE and this value is used to select (e.g., via a cryptographic hash function) a random subset of committee members of size $N$ among all committee members who took part in the protocol. The unpredictability of the random beacon of LOE makes harder to cheat and allows a fairer choice of the committee members in the limit of the resources of the nodes. This can be combined with other anti-spam techniques to prevent an attacker to submit only contributions under its control.

### From TLCS to timed signatures and timed proofs
Borrowing ideas from the celebrated Feige-Lapidot-Shamir technique, the Schnorr signature scheme can be modified so that the underlying sigma protocol on which it is based proves knowledge of a witness to the following $NP$ statement: "I know a secret key corresponding to $PK_{A}$ OR I know a secret key corresponding to $PK$", where $PK_A$ is a known public key of a user Alice and $PK$ is a TLCS public key $PK$ for some time $C$.

In this way a resulting signature is such that: a valid signature by Alice looks convincing to Bob before time $C$ but if Bob transfers this signature to Peggy after time $C$, such signature will not look convincing to Peggy since it might have been generated by anyone using the simulator algorithm of the sigma protocol using the secret key corresponding to $PK$ (that may be assumed to be known by anyone after time $C$).

The same concept can be extended to general-purpose NIZK proofs that can be made to guarantee the following property: they are publicly verifiable until a given time $C$ but after $C$ they will be no longer transferable (that is, they will no longer look convincing to any receiver).

## Implementations
An implementation in C/C++ of the efficient TLCS protocol described above is available [here](https://github.com/aragonzkresearch/tlcs-c) and a Rust implementation by Najmeh Sorous can be found [here](https://github.com/aragonzkresearch/tlcs-rust).
## Acks
The problem of the existence of a TLCS protocol was first posed by Alex Kampa who also contributed to stabilize the ideas in these notes. Thanks to all the Aragon ZK Research team who provided beneficial comments and the drand community who helped to figure out some inner details of their system.

#### Vincenzo Iovino, May 2023, Aragon ZK Research