Optimized Collision Search for STARK-Friendly Hash Challenge Candidates

Reference : Optimized Collision Search for STARK-Friendly Hash Challenge Candidates


	Document type :	E-prints/Working papers : First made available on ORBilu
	Discipline(s) :	Engineering, computing & technology : Computer science
	Focus Areas :	Security, Reliability and Trust
	To cite this reference:	http://hdl.handle.net/10993/42379

Title :	Optimized Collision Search for STARK-Friendly Hash Challenge Candidates
Language :	English
Author, co-author :	Udovenko, Aleksei [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >]
Publication date :	Jan-2020
Peer reviewed :	No
Keywords :	[en] Symmetric cryptography ; Hash functions ; Cryptanalysis ; Multiparty Computation
Abstract :	[en] In this note, we report several solutions to the STARK-Friendly Hash Challenge: a competition with the goal of finding collisions for several hash functions designed specifically for zero-knowledge proofs (ZKP) and multiparty computations (MPC). We managed to find collisions for 3 instances of 91-bit hash functions. The method used is the classic parallel collision search with distinguished points from van Oorshot and Wiener (1994). As this is a general attack on hash functions, it does not exhibit any particular weakness of the chosen hash functions. The crucial part is to optimize the implementations to make the attack cost realistic, and we describe several arithmetic tricks.
Research centres :	University of Luxembourg: High Performance Computing - ULHPC
Funders :	Fonds National de la Recherche - FnR
Target :	Researchers ; Professionals ; Students
Permalink :	http://hdl.handle.net/10993/42379
FnR project :	FnR ; FNR11684537 > Alex Biryukov > FinCrypt > Security, Scalability, and Privacy in Blockchain Applications and Smart Contracts > 01/08/2018 > 31/07/2021 > 2017

File(s) associated to this reference

Fulltext file(s):

	File	Commentary	Version	Size	Access
Open access	STARK_Friendly_Hash_Challenge.pdf		Author preprint	456.41 kB	View/Open

All documents in ORBi^lu are protected by a user license.