Really fast syndrome-based hashing

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2011

Without internal affiliation

  • Author: Bernstein, Daniel J.

    University of Illinois at Chicago, Department of Computer Science

  • Author: Lange, Tanja

    Technische Universiteit Eindhoven

  • Author: Peters, Christiane

    Unknown

  • Author: Schwabe, Peter

    Academia Sinica, Institute of Information Science

View graph of relations

The FSB (fast syndrome-based) hash function was submitted to the SHA-3 competition by Augot, Finiasz, Gaborit, Manuel, and Sendrier in 2008, after preliminary designs proposed in 2003, 2005, and 2007. Many FSB parameter choices were broken by Coron and Joux in 2004, Saarinen in 2007, and Fouque and Leurent in 2008, but the basic FSB idea appears to be secure, and the FSB submission remains unbroken. On the other hand, the FSB submission is also quite slow, and was not selected for the second round of the competition. This paper introduces RFSB, an enhancement to FSB. In particular, this paper introduces the RFSB-509 compression function, RFSB with a particular set of parameters. RFSB-509, like the FSB-256 compression function, is designed to be used inside a 256-bit collision-resistant hash function: all known attack strategies cost more than 2128 to find collisions in RFSB-509. However, RFSB-509 is an order of magnitude faster than FSB-256. On a single core of a Core 2 Quad CPU, RFSB-509 runs at 13.62 cycles/byte: faster than SHA-256, faster than 6 of the 14 secondround SHA-3 candidates, and faster than 2 of the 5 SHA-3 finalists.
Keyword: Compression functions,Tight reduction to L1 cache,Linearization,Collision resistance,Generalized birthday attacks,Information-set decoding
Original languageEnglish
Title of host publicationProgress in Cryptology : 4th International Conference on Cryptology in Africa, Dakar, Senegal, July 5-7, 2011. Proceedings
EditorsAbderrahmane Nitaj, David Pointcheval
PublisherSpringer
Publication date2011
Pages134-152
ISBN (print)978-3-642-21968-9
DOIs
StatePublished

Conference

Conference4th International Conference on Cryptology in Africa
CityDakar, Senegal
Period01/01/11 → …
NameLecture Notes in Computer Science
Number6767
ISSN (Print)0302-9743
CitationsWeb of Science® Times Cited: No match on DOI
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 6462008