Cryptology ePrint Archive: Report 2018/458

Characterizing Collision and Second-Preimage Resistance in Linicrypt

Ian McQuoid and 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.

Category / Keywords: foundations / collision resistance, second-preimage resistance

Original Publication (with minor differences): IACR-TCC-2019

Date: received 15 May 2018, last revised 24 Jul 2020

Contact author: rosulekm at eecs oregonstate edu

Available format(s): PDF | BibTeX Citation

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

Version: 20200724:182001 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]