Threshold Encryption Scheme

Based on A Simple and Efficient Threshold Cryptosystem from the Gap Diffie-Hellman Group

Overview

The threshold encryption scheme allows the encrypter to derive a shared secret \(s\) from the threshold public key \(Y\), such that sufficient threshold of validators holding private key shares \(Z_i\) associated with \(Y\) can also derive the shared secret. Both encrypter and decrypter use the shared secret to derive a symmetric key for a key-committing AEAD via HKDF.

To encrypt

  1. Let \(r\) be a random scalar
  2. Let \(s = e([r] Y, H)\)
  3. Let \(U = [r] G\)
  4. Let \(W = [r] H_{\mathbb{G}_2} (U)\)
  5. Let \(k = HKDF(s)\)

The public key portion of the ciphertext is \((U,W)\) and the derived shared secret is \(s\).

To Validate Ciphertext (for IND-CCA2 security)

Check that \(e(U, H_{\mathbb{G}_2} (U))= e(G, W)\) for ciphertext validity.

To Decrypt

  1. Check ciphertext validity.
  2. Let \(s = e(U, Z)\)

Threshold Decryption (simple method)

  1. Check ciphertext validity.
  2. Each decryption share is \(C_i = e(U, Z_i)\).
  3. To combine decryption shares, s = \(\prod C_i^{\lambda_i(0)}\) where \(\lambda_i(0)\) is the lagrange coefficient over the appropriate size domain.

Threshold Decryption (fast method)

Thanks to Kobi Gurkan for this approach.

Each validator generates a random scalar \(b\) and blinds their private key shares \([b] Z_{i, \omega_j}\). The blinded private key shares are publicly distributed, either by gossip or by posting to the blockchain.

  1. Check ciphertext validity
  2. The validator's decryption share is \(D_i = [b^{-1}] U\)

Note that to create a decryption share takes only one \(\mathbb{G}_1\) multiplication, and not one pairing as in the simple method.

To combine decryption shares, an aggregator computes for each decryption share \(D_i = [b^{-1}] U\):

\[ S_i = e( D_i, [\sum_{\omega_j \in \Omega_i} \lambda_{\omega_j}(0)] [b] Z_{i,\omega_j} ) \]

The shared secret is then \(s = \prod S_i\).

Public verification of decryption shares

The decryption shares can be made verifiable if each validator posts a blinded public key \(P_i = [b] H\). Validity of a decryption share \(D_i\) is then checked by:

\[ e(D_i, P_i) = e(U, H) \]

Proof sketch

The non-threshold version of the scheme is IND-CCA2 secure.

Suppose there is an adversary that wins the IND-CCA2 game. Then on input \((G, [a]G, [b]G, H)\), there exists an adversary that computes \(e(G,H)^{ab}\).

Rekeyability

The shared secret \(s\) can be rekeyed with respect to the secret key \(Z_1\) to a new secret key \(\hat{Z} = [\alpha] Z_1 + Z_2\), as the new shared secret \(\hat{s} = s^{\alpha} e(U, Z_2) = e(U, [\alpha] Z_2)e(U, Z_2) = e(U, [\alpha]Z_1 + Z_2)\).

The shared secret \(s\) can be rekeyed with respect to the public key \(Y_1\) to a new public key \(\hat{Y} = [\alpha] Y_1 + Y_2\) as the new shared secret \(\hat{s} = s^{\alpha} e([r] Y_2, H) = e([r\alpha] Y_1, H)e([r]Y_2, H) = e([r]([\alpha]Y_1 + Y_2), H)\).