---
_id: '12176'
abstract:
- lang: eng
  text: "A proof of exponentiation (PoE) in a group G of unknown order allows a prover
    to convince a verifier that a tuple (x,q,T,y)∈G×N×N×G satisfies xqT=y. This primitive
    has recently found exciting applications in the constructions of verifiable delay
    functions and succinct arguments of knowledge. The most practical PoEs only achieve
    soundness either under computational assumptions, i.e., they are arguments (Wesolowski,
    Journal of Cryptology 2020), or in groups that come with the promise of not having
    any small subgroups (Pietrzak, ITCS 2019). The only statistically-sound PoE in
    general groups of unknown order is due to Block et al. (CRYPTO 2021), and can
    be seen as an elaborate parallel repetition of Pietrzak’s PoE: to achieve λ bits
    of security, say λ=80, the number of repetitions required (and thus the blow-up
    in communication) is as large as λ.\r\n\r\nIn this work, we propose a statistically-sound
    PoE for the case where the exponent q is the product of all primes up to some
    bound B. We show that, in this case, it suffices to run only λ/log(B) parallel
    instances of Pietrzak’s PoE, which reduces the concrete proof-size compared to
    Block et al. by an order of magnitude. Furthermore, we show that in the known
    applications where PoEs are used as a building block such structured exponents
    are viable. Finally, we also discuss batching of our PoE, showing that many proofs
    (for the same G and q but different x and T) can be batched by adding only a single
    element to the proof per additional statement."
acknowledgement: "We would like to thank the authors of [BHR+21] for clarifying several
  questions we had\r\nregarding their results. Pavel Hubá£ek was supported by the
  Grant Agency of the Czech\r\nRepublic under the grant agreement no. 19-27871X and
  by the Charles University project\r\nUNCE/SCI/004. Chethan Kamath is supported by
  Azrieli International Postdoctoral Fellowship\r\nand ISF grants 484/18 and 1789/19.
  Karen Klein was supported in part by ERC CoG grant\r\n724307 and conducted part
  of this work at Institute of Science and Technology Austria."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Charlotte
  full_name: Hoffmann, Charlotte
  id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
  last_name: Hoffmann
  orcid: 0000-0003-2027-5549
- first_name: Pavel
  full_name: Hubáček, Pavel
  last_name: Hubáček
- first_name: Chethan
  full_name: Kamath, Chethan
  last_name: Kamath
- first_name: Karen
  full_name: Klein, Karen
  last_name: Klein
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
citation:
  ama: 'Hoffmann C, Hubáček P, Kamath C, Klein K, Pietrzak KZ. Practical statistically-sound
    proofs of exponentiation in any group. In: <i>Advances in Cryptology – CRYPTO
    2022</i>. Vol 13508. Springer Nature; 2022:370-399. doi:<a href="https://doi.org/10.1007/978-3-031-15979-4_13">10.1007/978-3-031-15979-4_13</a>'
  apa: 'Hoffmann, C., Hubáček, P., Kamath, C., Klein, K., &#38; Pietrzak, K. Z. (2022).
    Practical statistically-sound proofs of exponentiation in any group. In <i>Advances
    in Cryptology – CRYPTO 2022</i> (Vol. 13508, pp. 370–399). Santa Barbara, CA,
    United States: Springer Nature. <a href="https://doi.org/10.1007/978-3-031-15979-4_13">https://doi.org/10.1007/978-3-031-15979-4_13</a>'
  chicago: Hoffmann, Charlotte, Pavel Hubáček, Chethan Kamath, Karen Klein, and Krzysztof
    Z Pietrzak. “Practical Statistically-Sound Proofs of Exponentiation in Any Group.”
    In <i>Advances in Cryptology – CRYPTO 2022</i>, 13508:370–99. Springer Nature,
    2022. <a href="https://doi.org/10.1007/978-3-031-15979-4_13">https://doi.org/10.1007/978-3-031-15979-4_13</a>.
  ieee: C. Hoffmann, P. Hubáček, C. Kamath, K. Klein, and K. Z. Pietrzak, “Practical
    statistically-sound proofs of exponentiation in any group,” in <i>Advances in
    Cryptology – CRYPTO 2022</i>, Santa Barbara, CA, United States, 2022, vol. 13508,
    pp. 370–399.
  ista: 'Hoffmann C, Hubáček P, Kamath C, Klein K, Pietrzak KZ. 2022. Practical statistically-sound
    proofs of exponentiation in any group. Advances in Cryptology – CRYPTO 2022. CRYYPTO:
    International Cryptology Conference, LNCS, vol. 13508, 370–399.'
  mla: Hoffmann, Charlotte, et al. “Practical Statistically-Sound Proofs of Exponentiation
    in Any Group.” <i>Advances in Cryptology – CRYPTO 2022</i>, vol. 13508, Springer
    Nature, 2022, pp. 370–99, doi:<a href="https://doi.org/10.1007/978-3-031-15979-4_13">10.1007/978-3-031-15979-4_13</a>.
  short: C. Hoffmann, P. Hubáček, C. Kamath, K. Klein, K.Z. Pietrzak, in:, Advances
    in Cryptology – CRYPTO 2022, Springer Nature, 2022, pp. 370–399.
conference:
  end_date: 2022-08-18
  location: Santa Barbara, CA, United States
  name: 'CRYYPTO: International Cryptology Conference'
  start_date: 2022-08-15
date_created: 2023-01-12T12:12:07Z
date_published: 2022-10-13T00:00:00Z
date_updated: 2023-09-05T15:12:27Z
day: '13'
department:
- _id: KrPi
doi: 10.1007/978-3-031-15979-4_13
external_id:
  isi:
  - '000886792700013'
intvolume: '     13508'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2022/1021
month: '10'
oa: 1
oa_version: Preprint
page: 370-399
publication: Advances in Cryptology – CRYPTO 2022
publication_identifier:
  eisbn:
  - '9783031159794'
  eissn:
  - 1611-3349
  isbn:
  - '9783031159787'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Practical statistically-sound proofs of exponentiation in any group
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 13508
year: '2022'
...