Public-Key Scalability
Benedikt Auerbach
Abstract:
For 1<=m<=n we consider a natural m-out-of-n multi-instance scenario for key-encapsulation mechanisms. An adversary, given n independent instances (public keys) of the same KEM, wins if he breaks at least m out of the n instances. In this work, we are interested in the scaling factor of KEMs, which measures how well the difficulty of breaking m out of the n instances scales in m. That is, a scaling factor of k indicates that breaking m out of n instances is at least k times more difficult than breaking one single instance. A large scaling factor implies better security in the multi-instance scenario, providing improved security against mass surveillance. As a practial example, the Logjam attack (CCS 2015) implicitly exploited (among other things) an almost constant scaling factor of ElGamal over finite fields.
For Hashed ElGamal over elliptic curves we use the generic group model to argue that the scaling factor varies depending on the scheme's granularity. In low granularity, meaning each public key contains its own group, the scheme has an optimal scaling factor of m; In medium and high granularity, where instead all computations are carried out in the same group, the scheme still has a reasonable scaling factor \sqrt{m}.
As main technical contribution we derive a new generic group lower bound on the difficulty of solving the multi-instance gap computational Diffie-Hellman problem over groups of prime order p. First, we derive a new lower bound on the hardness of the multi-instance gap discrete logarithm problem in the generic group model, extending a recent result by Yun (EUROCRYPT 2015). In this problem the adversary is given access to a DDH oracle and has to compute multiple discrete logarithm instances. In a second step we show that multi-instance gapCDH and gapDLOG are equivalent in the algebraic group model, which establishes the desired generic lower bound.