---
_id: '7966'
abstract:
- lang: eng
  text: "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."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Benedikt
  full_name: Auerbach, Benedikt
  id: D33D2B18-E445-11E9-ABB7-15F4E5697425
  last_name: Auerbach
  orcid: 0000-0002-7553-6606
- first_name: Federico
  full_name: Giacon, Federico
  last_name: Giacon
- first_name: Eike
  full_name: Kiltz, Eike
  last_name: Kiltz
citation:
  ama: 'Auerbach B, Giacon F, Kiltz E. Everybody’s a target: Scalability in public-key
    encryption. In: <i>Advances in Cryptology – EUROCRYPT 2020</i>. Vol 12107. Springer
    Nature; 2020:475-506. doi:<a href="https://doi.org/10.1007/978-3-030-45727-3_16">10.1007/978-3-030-45727-3_16</a>'
  apa: 'Auerbach, B., Giacon, F., &#38; Kiltz, E. (2020). Everybody’s a target: Scalability
    in public-key encryption. In <i>Advances in Cryptology – EUROCRYPT 2020</i> (Vol.
    12107, pp. 475–506). Springer Nature. <a href="https://doi.org/10.1007/978-3-030-45727-3_16">https://doi.org/10.1007/978-3-030-45727-3_16</a>'
  chicago: 'Auerbach, Benedikt, Federico Giacon, and Eike Kiltz. “Everybody’s a Target:
    Scalability in Public-Key Encryption.” In <i>Advances in Cryptology – EUROCRYPT
    2020</i>, 12107:475–506. Springer Nature, 2020. <a href="https://doi.org/10.1007/978-3-030-45727-3_16">https://doi.org/10.1007/978-3-030-45727-3_16</a>.'
  ieee: 'B. Auerbach, F. Giacon, and E. Kiltz, “Everybody’s a target: Scalability
    in public-key encryption,” in <i>Advances in Cryptology – EUROCRYPT 2020</i>,
    2020, vol. 12107, pp. 475–506.'
  ista: 'Auerbach B, Giacon F, Kiltz E. 2020. Everybody’s a target: Scalability in
    public-key encryption. Advances in Cryptology – EUROCRYPT 2020. EUROCRYPT: Theory
    and Applications of Cryptographic Techniques, LNCS, vol. 12107, 475–506.'
  mla: 'Auerbach, Benedikt, et al. “Everybody’s a Target: Scalability in Public-Key
    Encryption.” <i>Advances in Cryptology – EUROCRYPT 2020</i>, vol. 12107, Springer
    Nature, 2020, pp. 475–506, doi:<a href="https://doi.org/10.1007/978-3-030-45727-3_16">10.1007/978-3-030-45727-3_16</a>.'
  short: B. Auerbach, F. Giacon, E. Kiltz, in:, Advances in Cryptology – EUROCRYPT
    2020, Springer Nature, 2020, pp. 475–506.
conference:
  end_date: 2020-05-15
  name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
  start_date: 2020-05-11
date_created: 2020-06-15T07:13:37Z
date_published: 2020-05-01T00:00:00Z
date_updated: 2023-09-05T15:06:40Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-030-45727-3_16
ec_funded: 1
external_id:
  isi:
  - '000828688000016'
intvolume: '     12107'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2019/364
month: '05'
oa: 1
oa_version: Submitted Version
page: 475-506
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '682815'
  name: Teaching Old Crypto New Tricks
publication: Advances in Cryptology – EUROCRYPT 2020
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783030457266'
  - '9783030457273'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: 'Everybody’s a target: Scalability in public-key encryption'
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 12107
year: '2020'
...