---
_id: '17051'
abstract:
- lang: eng
  text: "Memory-hard functions (MHF) are functions whose evaluation provably requires\r\na
    lot of memory. While MHFs are an unkeyed primitive, it is natural to consider
    the\r\nnotion of trapdoor MHFs (TMHFs). A TMHF is like an MHF, but when sampling\r\nthe
    public parameters one also samples a trapdoor which allows evaluating the\r\nfunction
    much cheaper.\r\nBiryukov and Perrin (Asiacrypt’17) were the first to consider
    TMHFs and put\r\nforth a candidate TMHF construction called Diodon that is based
    on the Scrypt\r\nMHF (Percival, BSDCan’09). To allow for a trapdoor, Scrypt’s
    initial hash chain\r\nis replaced by a sequence of squares in a group of unknown
    order where the order of\r\nthe group is the trapdoor. For a length n sequence
    of squares and a group of order\r\nN, Diodon’s cumulative memory complexity (CMC)
    is O(n2log N) without the\r\ntrapdoor and O(n log(n) log(N)2) with knowledge of
    it.\r\nWhile Scrypt is proven to be optimally memory-hard in the random oracle\r\nmodel
    (Alwen et al., Eurocrypt’17), Diodon’s memory-hardness has not been\r\nproven
    so far. In this work, we fill this gap by rigorously analyzing a specific\r\ninstantiation
    of Diodon. We show that its CMC is lower bounded by Ω( n2log nlog N)\r\nwhich
    almost matches the upper bound. Our proof is based Alwen et al.’s lower\r\nbound
    on Scrypt’s CMC but requires non-trivial modifications due to the algebraic\r\nstructure
    of Diodon. Most importantly, our analysis involves a more elaborate\r\ncompression
    argument and a solvability criterion for certain systems of Diophantine\r\nequations."
acknowledgement: We thank the Eurocrypt reviewers for their thorough review and for
  pointing out related works. This research was funded in whole or in part by the
  Austrian Science Fund (FWF) 10.55776/F85.
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: Christoph Ullrich
  full_name: Günther, Christoph Ullrich
  id: ec98511c-eb8e-11eb-b029-edd25d7271a1
  last_name: Günther
- 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: 'Auerbach B, Günther CU, Pietrzak KZ. Trapdoor memory-hard functions. In: <i>43rd
    Annual International Conference on the Theory and Applications of Cryptographic
    Techniques</i>. Vol 14653. Springer Nature; 2024:315-344. doi:<a href="https://doi.org/10.1007/978-3-031-58734-4_11">10.1007/978-3-031-58734-4_11</a>'
  apa: 'Auerbach, B., Günther, C. U., &#38; Pietrzak, K. Z. (2024). Trapdoor memory-hard
    functions. In <i>43rd Annual International Conference on the Theory and Applications
    of Cryptographic Techniques</i> (Vol. 14653, pp. 315–344). Zurich, Switzerland:
    Springer Nature. <a href="https://doi.org/10.1007/978-3-031-58734-4_11">https://doi.org/10.1007/978-3-031-58734-4_11</a>'
  chicago: Auerbach, Benedikt, Christoph Ullrich Günther, and Krzysztof Z Pietrzak.
    “Trapdoor Memory-Hard Functions.” In <i>43rd Annual International Conference on
    the Theory and Applications of Cryptographic Techniques</i>, 14653:315–44. Springer
    Nature, 2024. <a href="https://doi.org/10.1007/978-3-031-58734-4_11">https://doi.org/10.1007/978-3-031-58734-4_11</a>.
  ieee: B. Auerbach, C. U. Günther, and K. Z. Pietrzak, “Trapdoor memory-hard functions,”
    in <i>43rd Annual International Conference on the Theory and Applications of Cryptographic
    Techniques</i>, Zurich, Switzerland, 2024, vol. 14653, pp. 315–344.
  ista: 'Auerbach B, Günther CU, Pietrzak KZ. 2024. Trapdoor memory-hard functions.
    43rd Annual International Conference on the Theory and Applications of Cryptographic
    Techniques. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS,
    vol. 14653, 315–344.'
  mla: Auerbach, Benedikt, et al. “Trapdoor Memory-Hard Functions.” <i>43rd Annual
    International Conference on the Theory and Applications of Cryptographic Techniques</i>,
    vol. 14653, Springer Nature, 2024, pp. 315–44, doi:<a href="https://doi.org/10.1007/978-3-031-58734-4_11">10.1007/978-3-031-58734-4_11</a>.
  short: B. Auerbach, C.U. Günther, K.Z. Pietrzak, in:, 43rd Annual International
    Conference on the Theory and Applications of Cryptographic Techniques, Springer
    Nature, 2024, pp. 315–344.
conference:
  end_date: 2024-05-30
  location: Zurich, Switzerland
  name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
  start_date: 2024-05-26
corr_author: '1'
das_tickbox: '0'
date_created: 2024-05-26T22:00:58Z
date_published: 2024-05-01T00:00:00Z
date_updated: 2026-10-16T08:09:46Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-031-58734-4_11
external_id:
  isi:
  - '001274940200011'
fulldoi: https://doi.org/10.1007/978-3-031-58734-4_11
intvolume: '     14653'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2024/312
month: '05'
oa: 1
oa_version: Preprint
page: 315-344
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
  grant_number: F8509
  name: Security and Privacy by Design for Complex Systems
publication: 43rd Annual International Conference on the Theory and Applications of
  Cryptographic Techniques
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783031587337'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Trapdoor memory-hard functions
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 14653
year: '2024'
...
