Characterizing Collision and Second-Preimage Resistance in Linicrypt

Ian McQuoid; Trevor Swope; Mike Rosulek

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 resistance second-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: 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}
}