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

Date: received 15 May 2018, last revised 13 Feb 2019

Contact author: rosulekm at eecs oregonstate edu

Available format(s): PDF | BibTeX Citation

Version: 20190213:232025 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]