---
res:
bibo_abstract:
- "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.@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: Christoph Ullrich
foaf_name: Günther, Christoph Ullrich
foaf_surname: Günther
foaf_workInfoHomepage: http://www.librecat.org/personId=ec98511c-eb8e-11eb-b029-edd25d7271a1
- foaf_Person:
foaf_givenName: Krzysztof Z
foaf_name: Pietrzak, Krzysztof Z
foaf_surname: Pietrzak
foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9139-1654
bibo_doi: 10.1007/978-3-031-58734-4_11
bibo_volume: 14653
dct_date: 2024^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0302-9743
- http://id.crossref.org/issn/1611-3349
- http://id.crossref.org/issn/9783031587337
dct_language: eng
dct_publisher: Springer Nature@
dct_title: Trapdoor memory-hard functions@
...