Everybody's a Target: Scalability in Public-Key Encryption.
Benedikt Auerbach, Federico Giacon, Eike Kiltz · IACR Cryptology ePrint Archive · 2019
For \(1\le m \le n\), we consider a natural m-out-of-n multi-instance scenario for a public-key encryption (PKE) scheme. An adversary, given n independent instances of PKE, wins if he breaks at least m out of the n instances. In this work, we are interested in the scaling factor of PKE schemes, \(\mathrm {SF}\), which measures how well the difficulty of breaking m out of the n instances scales in m. That is, a scaling factor \(\mathrm {SF}=\ell \) indicates that breaking m out of n instances is at least \(\ell \) times more difficult than breaking one single instance. A PKE scheme with small scaling factor hence provides an ideal target for mass surveillance. In fact, the Logjam attack (CCS 2015) implicitly exploited, among other things, an almost constant scaling factor of ElGamal over finite fields (with shared group parameters).