“Extreme” Threshold Cryptosystems:
Adaptively Secure Non-Interactive Threshold Cryptosystems

Benoı̂t Libert1 and Moti Yung2
1Université catholique de Louvain, Crypto Group – F.N.R.S.
2Google Inc. and Columbia University

August 16, 2011
Santa Barbara

Moti Yung (Google Inc.)

Crypto 2011 Rump Session

August 16, 2011

Santa Barbara

1 / 10Threshold Cryptography

Introduced by Desmedt-Frankel (Crypto’89) and Boyd (IMA’89)
Split private keys into n shares SK1 , . . . , SKn so that knowing strictly lessthan t ≤ n shares is useless to the adversary.
At least t ≤ n shareholders must contribute to private key operations.
Decryption requires the cooperation of t decryption servers.
Signing requires at least t servers to run a joint signing protocol.

Robustness: up to t − 1 ≤ n malicious servers cannot prevent a honest
majority from decrypting/signing.

Moti Yung (Google Inc.)

Crypto 2011 Rump Session

August 16, 2011

Santa Barbara

2 / 10Threshold Cryptography
The public-key encryption case:Moti Yung (Google Inc.)

Crypto 2011 Rump Session

August 16, 2011

Santa Barbara

3 / 10Static vs Adaptive corruptions
Static corruptions: adversary corrupts servers before seeing the public key.
Robust threshold cryptosystems with IND-CCA2 security:- Shoup-Gennaro (Eurocrypt’98): in the ROM.
- Canetti-Goldwasser (Eurocrypt’99): requires interaction or storage of many
pre-shared secrets; robust and adaptively secure for t = O(n1/2 ).
- Dodis-Katz (TCC’05): generic constructions; ciphertexts of size O(n).
- Boneh-Boyen-Halevi (CT-RSA’06): no interaction needed for robustness.
- Wee (Eurocrypt’11): generic constructions from (threshold) extractable hashproof systems.

Moti Yung (Google Inc.)

Crypto 2011 Rump Session

August 16, 2011

Santa Barbara

4 / 10Static vs Adaptive corruptions
Adaptive corruptions: adversary corrupts up to t − 1 servers at any time.
- Canetti et al. (Crypto’99) and Frankel-MacKenzie-Yung (ESA’99,Asiacrypt’99): need for erasures.
- Jarecki-Lysyanskaya (Eurocrypt’00): no need for erasures, but interaction atdecryption with Cramer-Shoup.
- Lysyanskaya-Peikert (Asiacrypt’01): adaptively secure signatures withinteraction.
- Abe-Fehr (Crypto’04): adaptively secure UC-secure threshold signatures andencryption with interaction.
- Almansa-Damgaard-Nielsen (Eurocrypt’06): adaptively secure proactive RSAsignatures.

Moti Yung (Google Inc.)

Crypto 2011 Rump Session

August 16, 2011

Santa Barbara

5 / 10Threshold Cryptosystems: Our Goal

Despite more than 10 years of research, adaptive security has not beenachieved with:- CCA2-security for encryption and CMA-security for signatures.
- Non-interactive schemes- Robustness against malicious adversaries- Optimal resilience (t = (n − 1)/2)- No erasures for shareholders- Share size independent of t, n- Proof in the standard model

Moti Yung (Google Inc.)

Crypto 2011 Rump Session

August 16, 2011

Santa Barbara

6 / 10CCA2-Secure Non-interactive Threshold Encryption
Our contribution (ICALP’11):
An adaptively secure fully non-interactive threshold cryptosystem providing- CCA2 security and robustness w/o random oracles- Short (i.e., O(1)-size) private key shares

The construction- Builds on the dual system encryption approach (Waters, Crypto’09) and theLewko-Waters techniques (TCC’10).
- Handles adaptive corruptions by instantiating Boneh-Boyen-Halevi(CT-RSA’06) in bilinear groups of order N = p1 p2 p3 .
⇒ Ciphertexts live in the subgroup Gp1 , private keys in Gp1 p3

Gives adaptively secure non-interactive threshold signatures
Moti Yung (Google Inc.)

Crypto 2011 Rump Session

August 16, 2011

Santa Barbara

7 / 10New Results: An Alternative Approach
All-But-One Perfectly Sound Hash Proof Systems:
Combination between- Universal hash proofs (simulator knows private keys in reduction).
- Simulation-sound proofs of ciphertext validity (publicly verifiable ciphertexts).
- Proofs of validity associated with tags and perfectly sound on all but one tag.

Gives new constructions- Based on the Subgroup Decision assumption in composite order groups withtwo primes N = p1 p2 .
- Or Groth-Sahai proofs (D-Linear/SXDH assumptions) in prime-order groups:⇒ Better efficiency; easier to combine with a DKG protocol.

Moti Yung (Google Inc.)

Crypto 2011 Rump Session

August 16, 2011

Santa Barbara

8 / 10

Example: using the Linear assumption
Use Damgaard’s Elgamal with PK = (g , g1 , g2 , X1 = g1x1 g z , X2 = g2x2 g z ).
C0 = M · X1r · X2s ,C1 = g1r ,C2 = g2s ,C3 = g r +s

Add a simulation-sound proof that (C1 , C2 , C3 ) = (g1r , g2s , g r +s ) using a CRS
that depends on VK, where (SK, VK) ← G(λ) is a one-time key pair.
Security proof works:
CRS is only WI for the challenge ciphertext and only the challenger cangenerate one fake proof.
Adversary can only prove true statements.
Simulator knows the decryption keys (as in HPS-based proofs).

Moti Yung (Google Inc.)

Crypto 2011 Rump Session

August 16, 2011

Santa Barbara

9 / 10Thanks!

Moti Yung (Google Inc.)

Crypto 2011 Rump Session

August 16, 2011

Santa Barbara

10 / 10