Homomorphic Threshold Encryption

The core of the flow encryption system requires a partially homomorphic encryption scheme, which allows for users to publish transactions that contain encrypted values. These encrypted values are then aggregated, using the homomorphism, by validators. The aggregate value (the “batched flow”) is then decrypted using the threshold decryption scheme described here.

Desired Properties

For our threshold encryption scheme, we require three important properties:

• Homomorphism: we must be able to operate over ciphertexts, by combining balance commitments from many participants into a batched value.
• Verifiability: we must be able to verify that a given value $v_i$ was encrypted correctly to a given ciphertext $c_i$
• Robustness: up to $n-t$ validators must be permitted to either fail to provide a decryption share or provide in invalid decryption share.

Concrete Instantiation: Homomorphic ElGamal

Setup

Compute a lookup table $LUT$ for every $v_i\in [0,2^{23})$ by setting $LUT[v_i]=v_{i}G$ where $G$ is the basepoint of decaf377. Store $LUT$ for later use in value decryption.

Value Encryption

                                  ┌───────────────────┐                           
                                  │DKG Public Key (D) │                           
                                  │                   │                           
                                  └───────────────────┘                           
                                            │                                     
                                  ┌─────────▼─────────┐    ┌──────────────┐       
                                  │                   │    │     v_e      │       
                                  │                   │    │  (encrypted  │       
                                  │                   │    │    value)    │       
                  ┌──────────┐    │ElGamal Encryption │    │ ┌──────────┐ │       
               ┌─▶│v_0 (u16) │────▶   D: DKG Pubkey   ├────┼▶│   c_0    │ │       
               │  └──────────┘    │     M = v_i*G     │    │ └──────────┘ │       
               │  ┌──────────┐    │     e <- F_q      │    │ ┌──────────┐ │       
┌────────────┐ ├─▶│v_1 (u16) │────▶ c_i = (e*G, M+eD) ├────┼▶│   c_1    │ │       
│            │ │  └──────────┘    │                   │    │ └──────────┘ │       
│v [0, 2^64) │─┤  ┌──────────┐    │                   │    │ ┌──────────┐ │       
│            │ ├─▶│v_2 (u16) │────▶ Correctness Proof ├────┼▶│   c_2    │ │       
└────────────┘ │  └──────────┘    │         σ         │    │ └──────────┘ │       
               │  ┌──────────┐    │                   │    │ ┌──────────┐ │       
               └─▶│v_3 (u16) │────▶                   ├────┼▶│   c_3    │ │       
                  └──────────┘    │                   │    │ └──────────┘ │       
                                  │                   │    │              │       
                                  │                   │    │              │       
                                  └───────────────────┘    └──────────────┘       
                                            │                                     
                                            │           ┌────────────────────────┐
                                            └──────────▶│proofs σ_ci = (r, s, t) │
                                                        └────────────────────────┘

A value $v$ is given by an unsigned 64-bit integer $v\in [0,2^{64})$. Split $v$ into four 16-bit limbs

$$v_q=v_0+v_1{2}^{16}+v_2{2}^{32}+v_3{2}^{48}$$ with $v_i\in [0,2^{16}]$.

Then, perform ElGamal encryption to form the ciphertext $v_e$ by taking (for each $v_i$)

$$M_i=v_i\ast G$$ $$e\stackrel{rand}{\leftarrow }{\mathbb{F}}_q$$ $$c_i=(e\ast G,M_i+e\ast D)$$

Where $G$ is the basepoint generator for decaf377, ${\mathbb{F}}_q$ is the large prime-order scalar field for decaf377, and $D$ is the public key output from DKG.

Next, compute a proof of correctness of the ElGamal encryption by executing the following sigma protocol:

$$k_1\stackrel{rand}{\leftarrow }{\mathbb{F}}_q$$ $$k_2\stackrel{rand}{\leftarrow }{\mathbb{F}}_q$$ $$\alpha =k_1\ast G$$ $$\gamma =k_1\ast D+k_2\ast G$$ $$t=H(c_{i0},c_{i1},D,\alpha ,\gamma )$$ $$r=k_1-e\ast t$$ $$s=k_2-v_i\ast t$$

The proof is then ${\sigma }_{c_i}=(r,s,t)$. The encryption of value $v$ is given as $v_e=[c_1,c_2,c_3,c_4]$.

Upon receiving an encrypted value $v_e$ with proofs ${\sigma }_{c_i}$, a validator or validating full node should verify each proof ${\sigma }_{c_i}$ by checking

$$\alpha \leftarrow G\ast r+c_{i0}\ast t$$ $$\gamma \leftarrow D\ast r+G\ast s+c_{i1}\ast t$$ $$H(c_{i0},c_{i1},D,\alpha ,\gamma )\stackrel{?}{=}t$$

Considering the value invalid if the proof fails to verify.

This protocol proves, in NIZK, the relation $$R=\{((e,v_i),c_{i0},c_{i1})\in {\mathbb{F}}_q\times \mathbb{G}:c_{i0}=eG\wedge c_{i1}=v_{i}G+eD\}$$

Showing that the ciphertext $c_i$ is an actual encryption of $v_i$ for the DKG pubkey $D$, and using the hash transcript to bind the proof of knowledge of $(e,v_i)$ to each $c_i$.

Each ciphertext $c_i$ is two group elements, accompanied by a proof ${\sigma }_{c_i}$ which is three scalars. decaf377 group elements and scalars are encoded as 32-byte values, thus every encrypted value $v_e$ combined with its proof ${\sigma }_{ci}$ is $5\ast 32\ast 4$ = 640 bytes.

Value Aggregation

                          n (batch size)                         
┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐
│┌──────────────┐   ┌──────────────┐            ┌──────────────┐│
 │              │   │              │            │              │ 
 │   v_{e0}     │   │    v_{e1}    │            │    v_{ek}    │ 
 │              │   │              │            │              │ 
 │ ┌──────────┐ │   │ ┌──────────┐ │            │ ┌──────────┐ │ 
 │ │   c_0    │ │   │ │   c_0    │ │            │ │   c_0    │ │ 
 │ └──────────┘ │   │ └──────────┘ │            │ └──────────┘ │ 
 │ ┌──────────┐ │   │ ┌──────────┐ │            │ ┌──────────┐ │ 
 │ │   c_1    │ │   │ │   c_1    │ │            │ │   c_1    │ │ 
 │ └──────────┘ │   │ └──────────┘ │            │ └──────────┘ │ 
 │ ┌──────────┐ │   │ ┌──────────┐ │    ...     │ ┌──────────┐ │ 
 │ │   c_2    │ │   │ │   c_2    │ │            │ │   c_2    │ │ 
 │ └──────────┘ │   │ └──────────┘ │            │ └──────────┘ │ 
 │ ┌──────────┐ │   │ ┌──────────┐ │            │ ┌──────────┐ │ 
 │ │   c_3    │ │   │ │   c_3    │ │            │ │   c_3    │ │ 
 │ └──────────┘ │   │ └──────────┘ │            │ └──────────┘ │ 
 │              │   │              │            │              │ 
 │              │   │              │            │              │ 
 └──────────────┘   └──────────────┘            └──────────────┘ 
         │                  │             │             │        
         │                  │             │             │        
         └──────────────────┴─────┬───────┴─────────────┘        
                                  │             ┌──────────────┐ 
                                  ▼             │              │ 
                                ┌───┐           │   v_{agg}    │ 
                                │ + │───────────▶              │ 
                                └───┘           │ ┌──────────┐ │ 
                                                │ │   c_0    │ │ 
                                                │ └──────────┘ │ 
                                                │ ┌──────────┐ │ 
                                                │ │   c_1    │ │ 
                                                │ └──────────┘ │ 
                                                │ ┌──────────┐ │ 
                                                │ │   c_2    │ │ 
                                                │ └──────────┘ │ 
                                                │ ┌──────────┐ │ 
                                                │ │   c_3    │ │ 
                                                │ └──────────┘ │ 
                                                │              │ 
                                                │              │ 
                                                └──────────────┘  

To batch flows, we must use the homomorphic property of ElGamal ciphertexts. Aggregation should be done component-wise, that is, on each limb of the ciphertext ($c_i$). To aggregate a given $v_e,v_e^{\prime }$, simply add each limb:

$$v_{agg}=v_e+v_e^{\prime }=[c_0+c_0^{\prime },c_1+c_1^{\prime },c_2+c_2^{\prime },c_3+c_3^{\prime }]=\cdots =v_q+v_q^{\prime }=v+v^{\prime }$$

This holds due to the homomorphic property of ElGamal ciphertexts.

The block producer aggregates every $v_{ei}$, producing a public transcript of the aggregation. The transcript can then be publicly validated by any validator or full node by adding together each $v_{ei}$ in the transcript and verifying that the correct $v_{agg}$ was committed by the block producer.

Value Decryption

┌──────────────┐                                                                        
│     v_e      │                                                                        
│  (encrypted  │                                                                        
│    value)    │                                                                        
│ ┌──────────┐ │     ┌─────────────────────────┐                                        
│ │   c_0    │─┼────▶│                         │    ┌─────────────────────────────────┐ 
│ └──────────┘ │     │                         │    │       Gossip (ABCI++ Vote       │ 
│ ┌──────────┐ │     │                         │    │           Extensions)           │ 
│ │   c_1    │─┼────▶│Decryption Shares + Proof│    │                                 │ 
│ └──────────┘ │     │                         │    │        verify share proof       │ 
│ ┌──────────┐ │     │  s_{pi} = d_{p}c_{i0}   │───▶│          σ_pi for s_pi          │ 
│ │   c_2    │─┼────▶│   σ_{pi} = (r, α, γ)    │    │                                 │ 
│ └──────────┘ │     │                         │    │      d = sum(s_pi*λ_{0,i})      │ 
│ ┌──────────┐ │     │                         │    │        v_mi = -d + c_{i1}       │ 
│ │   c_3    │─┼────▶│                         │    │                                 │ 
│ └──────────┘ │     └─────────────────────────┘    └─────────────────────────────────┘ 
│              │                                                     │    ┌───────┐     
│              │                                                    ┌┘    │  LUT  │     
└──────────────┘                                                    │     └───┬───┘     
                   ┌─────────────────────────┐       ┌──────────────▼─────────▼────────┐
                   │                         │       │       Reverse dLog Lookup       │
                   │ Reconstruct from Limbs  │       │                                 │
                   │                         │◀──────│v_q = [LUT[v_mi], ..., LUT[v_mn]]│
                   │                         │       │                                 │
                   └─────────────────────────┘       └─────────────────────────────────┘
                                │                                                       
                                ▼                                                       
                           ┌─────────┐                                                  
                           │         │                                                  
                           │v (u128) │                                                  
                           │         │                                                  
                           └─────────┘                                                   

To decrypt the aggregate $v_{agg}$, take each ciphertext component $c_i$ and perform threshold ElGamal decryption using the participant’s DKG private key share $d_p$ to produce decryption share $s_{p}i$:

$$s_{pi}=d_p{c}_{i0}$$

Next, each participant must compute a proof that their decryption share is well formed relative to the commitment to their secret share ${\varphi }_p=G\cdot d_p$. This is accomplished by adopting the Chaum-Pedersen sigma protocol for proving DH-triples.

With $c_{i0}$, $s_{pi}$, and $d_p$ as inputs, each participant computes their proof ${\sigma }_{pi}$ by taking

$$k\stackrel{rand}{\leftarrow }{\mathbb{F}}_q$$ $$\alpha =k\ast G$$ $$\gamma =k\ast c_{i0}$$ $$t=H(s_{pi},c_{i0},i,p,{\varphi }_p,\alpha ,\gamma )$$ $$r=k-d_p\ast t$$

The proof is the tuple ${\sigma }_{pi}=(r,t)$.

Every participant then broadcasts their proof of knowledge ${\sigma }_{pi}$ along with their decryption share $s_{pi}$ to every other participant.

After receiving $s_{pi},{\sigma }_{pi}=(r,t)$ from each participant, each participant verifies that $s_{pi}$ is valid by checking

$$\alpha =G\ast r+{\varphi }_p\ast t$$ $$\gamma =c_{i0}\ast r+s_{pi}\ast t$$ $$H(s_{pi},c_{i0},i,p,{\varphi }_p,\alpha ,\gamma )\stackrel{?}{=}t$$

and aborting if verification fails. (TODO: should we ignore this participant’s share, or report/slash them?)

This protocol is the Chaum-Pedersen sigma protocol which here proves the relation $$R=\left\{\right(d_p,(c_{i0},{\varphi }_p,s_{pi}))\in {\mathbb{F}}_q\times \mathbb{G}:{\varphi }_p=d_{p}G\wedge s_{pi}=d_p{c}_{i0}\}$$

Showing that the validator’s decryption share is correctly formed for their key share which was committed to during DKG.

Now each participant can sum their received and validated decryption shares by taking

$$d=\sum _{p=0}^n{s}_{pi}{\lambda }_{0,i}$$

where ${\lambda }_i$ is the lagrange coefficient (for x=0) at $i$, defined by

$${\lambda }_{0,i}=\prod _{n\in S,n\ne i}\frac{n}{n-i}$$

where $S$ is the set of all participant indices.

Then, compute the resulting decryption by taking

$$v_m=-d+c_{i1}$$

Now we have the output $v_m=[v_{im}\dots ]$. Each $v_{im}$ is a decaf377 group element. Use our lookup table $LUT$ from the setup phase to transform each value to its discrete log relative to the basepoint: $$v_i=LUT[v_{im}]$$ Now we have the decrypted value $$v_q=[v_0,v_1,v_2,v_3]$$

where each $v_i$ is bounded in $[0,2^{23})$.

To recombine the value, iterate over each $v_i$, packing each $v_i$ into a u16 value $v_{ui}$, performing carries if necessary. This yields the final value

$$v=v_{ui}+v_{ui}\ast 2^{16}+v_{ui}\ast 2^{32}+v_{ui}\ast 2^{48}+v_{ui}\ast 2^{64}$$

This value is bounded by $[0,2^{71}]$, assuming that the coefficients in the previous step were correctly bounded.

Note

On verifiability, this scheme must include some snark proof that coefficients were correctly created from input values. This can be accomplished by providing a SNARK proof $\pi$ that accompanies each value. It may also be desirable to SNARK the sigma protocol given in the value encryption phase in order to save on chain space.

Acknowledgements

Thanks to samczsun for his discussion and review of this spec, and for finding a flaw with an earlier instantiation of the encryption proof.

TODO: end-to-end complexity analysis (number of scalar mults per block, LUT size, etc)