---
res:
bibo_abstract:
- "For 1≤m≤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, SF, which measures how well the difficulty
of breaking m out of the n instances scales in m. That is, a scaling factor SF=ℓ
indicates that breaking m out of n instances is at least ℓ 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).\r\n\r\nFor Hashed
ElGamal over elliptic curves, we use the generic group model to argue that the
scaling factor depends on the scheme's granularity. In low granularity, meaning
each public key contains its independent group parameter, the scheme has optimal
scaling factor SF=m; In medium and high granularity, meaning all public keys share
the same group parameter, the scheme still has a reasonable scaling factor SF=√m.
Our findings underline that instantiating ElGamal over elliptic curves should
be preferred to finite fields in a multi-instance scenario.\r\n\r\nAs our main
technical contribution, we derive new generic-group lower bounds of Ω(√(mp)) on
the difficulty of solving both the m-out-of-n Gap Discrete Logarithm and the m-out-of-n
Gap Computational Diffie-Hellman problem over groups of prime order p, extending
a recent result by Yun (EUROCRYPT 2015). We establish the lower bound by studying
the hardness of a related computational problem which we call the search-by-hypersurface
problem.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Benedikt
foaf_name: Auerbach, Benedikt
foaf_surname: Auerbach
foaf_workInfoHomepage: http://www.librecat.org/personId=D33D2B18-E445-11E9-ABB7-15F4E5697425
orcid: 0000-0002-7553-6606
- foaf_Person:
foaf_givenName: Federico
foaf_name: Giacon, Federico
foaf_surname: Giacon
- foaf_Person:
foaf_givenName: Eike
foaf_name: Kiltz, Eike
foaf_surname: Kiltz
bibo_doi: 10.1007/978-3-030-45727-3_16
bibo_volume: 12107
dct_date: 2020^xs_gYear
dct_identifier:
- UT:000828688000016
dct_isPartOf:
- http://id.crossref.org/issn/0302-9743
- http://id.crossref.org/issn/1611-3349
- http://id.crossref.org/issn/9783030457266
- http://id.crossref.org/issn/9783030457273
dct_language: eng
dct_publisher: Springer Nature@
dct_title: 'Everybody’s a target: Scalability in public-key encryption@'
...