Transcript Optimizing Robustness while Generating Shared Secret Safe Primes

Optimizing Robustness
while Generating Shared
Secret Safe Primes
Emil Ong and John Kubiatowicz
<[email protected]>
University of California, Berkeley
Motivation

Several multi-party algorithms need or
benefit from using safe primes


Usually, for RSA moduli (e.g. Shoup’s
RSA signature scheme)
In many of these algorithms, the safe
primes must be shared secrets to
preserve security
Generating safe primes as
shared secrets: Prior Work

Algesheimer, Camenish, and Shoup
(CRYPTO ’00)


Developed several novel
mechanisms for modular arithmetic
Honest-but-curious model
Our contribution
A safe prime generation method which
is robust and “efficient”
 Use a robust form of distributed
sieving to find safe prime candidates
 Provide optimized methods for
multiparty modular arithmetic
High Level Overview
1.
Find a safe prime candidate


2.
Sieve for rough numbers – those
without small prime factors
Ensure the number is  3 mod 4
Test the compositeness via a
distributed Miller-Rabin test
Distributed Sieving
(Malkin, Wu, and Boneh, NDSS’99)
1.
Each player finds a random “rough”
integer ai (i.e. one relatively prime to the
product of the first b primes, M b)
2.
The players generate additive shares bi
such that  bi   ai  a
3.
Players choose a random ri
4.
Locally compute bi  ri M b to obtain an
additive share of a  rM b
Making Distributed Sieving
Robust
1.
2.
3.
4.
Each player finds a random “rough”
integer ai (i.e. one relatively prime to the
product of the first b primes, M b)
Need to prove each ai is genuinely rough
The players generate additive shares bi
such that  bi   ai  a
Prefer threshold (polynomial) sharing
Players choose a random ri
Need to share the ri polynomially, prove
their size
Locally compute bi  ri M b to obtain an
additive share of a  rM b
Robust Distributed Sieving
1.
2.
3.
4.
Each player finds a random “rough”
integer ai
Each ai is shared polynomially along with
a ZK proof
The ai are multiplied using the usual
method (Ben-Or, Goldwasser, and
Wigderson)
Players choose a random ri and share
them polynomially, along with a proof of
size
Locally compute bi  ri M b to obtain an
additive share of a  rM b
High Level Overview
1.
Find a safe prime candidate


2.
Sieve for rough numbers – those
without small prime factors
Ensure the number is  3 mod 4
Test the compositeness via a
distributed Miller-Rabin test
Distributed Miller-Rabin
Input: Secret shares of prime candidate
1. Locally compute e = (φ – 1) / 2
2. Repeat m times:
a.
b.
c.
3.
Choose a random g (0 ≤ g ≤ φ - 1)
Compute shares of ge mod φ
If ge mod φ  {1,1}, output failure
Output success
Modular exponentiation
(Algesheimer, Camenish, and Shoup, CRYPTO ‘00)
Compute shares of ge mod φ
1.
Reshare the bits of e as
β1,…, βn
2.
c=(g-1)* βn+1
3.
For i=n-1 downto 1, Do
1.
2.
4.
d=(g-1)*βi + 1
c=((c2 mod φ) * d) mod φ
Output c
Note that
g  i  ( g  1) *  i  1
Optimization: Lookup tables
Alternate perspective: g   ( g  1) *  i  1
is a “lookup” of a 2 element table: 1
and g
 Problem: Sharing bits of a secret can
be expensive
 Idea: Try to optimize by doing a
lookup in an arbitrarily sized table

i

Break the exponent into larger pieces
than bits → fewer shares
Generalized Modular
Exponentiation
Compute shares of ge mod φ
1.
Precompute g0 mod φ, g1 mod φ, …, gη-1 mod φ
2.
Reshare e in base-η as η1,…,ηω (ω=n/η)
3.
c=LOOKUP(ηω)
4.
For i=ω-1 downto 1, Do
1.
2.
d=LOOKUP(ηi)
c=((cη mod φ) * d) mod φ
Output c
Result: The number of modular multiplications is
reduced from 2log2e to log2e+ω
5.
Lookup procedure
Input: g0 mod φ, g1 mod φ, …, gη-1 mod
φ,   {0,...,  1}
 For i=0 to η-1, do  i  1    i
i



(
g
mod  )
 For i=0 to η-1, do i
i
 Locally compute   i
Normalization (Adapted from Bar-Ilan and
Beaver, PODC 1989):
0, if x  0
x 
1, otherwise
Summary
Robust distributed sieving for safe
prime candidate selection
 Improvements to modular arithmetic in
the multiparty setting
 Current work: implementation

Conclusions and Lessons
Modular arithmetic optimizations can
be useful in general
 Safe prime generation is still slow (up
to 5 minutes locally)
 The algorithm is non-trivial to
implement
 If possible, avoid safe primes for now
while we optimize further ☺

Thank you!
Check our website soon for an
extended version of the paper:
http://oceanstore.cs.berkeley.edu