International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Characterizing Collision and Second-Preimage Resistance in Linicrypt

Authors:
Ian McQuoid
Trevor Swope
Mike Rosulek
Download:
DOI: 10.1007/978-3-030-36030-6_18
Search ePrint
Search Google
Abstract: Linicrypt (Carmer & Rosulek, Crypto 2016) refers to the class of algorithms that make calls to a random oracle and otherwise manipulate values via fixed linear operations. We give a characterization of collision-resistance and second-preimage resistance for a significant class of Linicrypt programs (specifically, those that achieve domain separation on their random oracle queries via nonces). Our characterization implies that collision-resistance and second-preimage resistance are equivalent, in an asymptotic sense, for this class. Furthermore, there is a polynomial-time procedure for determining whether such a Linicrypt program is collision/second-preimage resistant.
BibTeX
@article{tcc-2019-29982,
  title={Characterizing Collision and Second-Preimage Resistance in Linicrypt},
  booktitle={Theory of Cryptography},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={11891},
  pages={451-470},
  doi={10.1007/978-3-030-36030-6_18},
  author={Ian McQuoid and Trevor Swope and Mike Rosulek},
  year=2019
}