Paper 2018/458

Characterizing Collision and Second-Preimage Resistance in Linicrypt

Ian McQuoid, Trevor Swope, and Mike Rosulek

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.

Note: Revised the definition of "degeneracy" (Sec 3.1)

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in Tcc 2019
Keywords
collision resistancesecond-preimage resistance
Contact author(s)
rosulekm @ eecs oregonstate edu
History
2020-07-24: last of 2 revisions
2018-05-21: received
See all versions
Short URL
https://ia.cr/2018/458
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/458,
      author = {Ian McQuoid and Trevor Swope and Mike Rosulek},
      title = {Characterizing Collision and Second-Preimage Resistance in Linicrypt},
      howpublished = {Cryptology ePrint Archive, Paper 2018/458},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/458}},
      url = {https://eprint.iacr.org/2018/458}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.