Error Correction Capabilities of Non-Linear Cryptographic Hash Functions

Linear hashes are known to possess error-correcting capabilities. However, in most applications, non-linear hashes with pseudorandom outputs are utilized instead. It has also been established that classical non-systematic random codes, both linear and non-linear, are capacity achieving in the asymptotic regime. Thus, it is reasonable to expect that non-linear hashes might also exhibit good error-correcting capabilities. In this paper, we show this to be the case. Our proof is based on techniques from multiple access channels. As a consequence, we show that Systematic Random Non-Linear Codes (S-RNLC) are capacity achieving in the asymptotic regime. We validate our results by comparing the performance of the Secure Hash Algorithm (SHA) with that of Systematic Random Linear Codes (SRLC) and S-RNLC, demonstrating that SHA performs equally.

• Publication year

  2024

• Venue

  International Symposium on Information Theory

• Publication date

  2024-05-02

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/ISIT57864.2024.10619370arXiv 2405.01495
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Partial Encryption after Encoding for Security and Reliability in Data Systems

  2022cited by this paper
• AES as Error Correction: Cryptosystems for Reliable Communication

  2022cited by this paper
• Linear hash-functions and their applications to error detection and correction

  2020cited by this paper
• Capacity-Achieving Guessing Random Additive Noise Decoding

  2018influential reference
• Sufficiently myopic adversaries are blind

  2015cited by this paper
• Cryptographic Hash Functions: A Review

  2012cited by this paper
• P-Coding: Secure Network Coding against Eavesdropping Attacks

  2010cited by this paper
• Coding against myopic adversaries

  2010cited by this paper
• On the Secure Hash Algorithm family

  2008cited by this paper
• A Mathematical Theory of Communication

  2006cited by this paper
• Elements of Information Theory

  2005influential reference
• Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance

  2004cited by this paper
• Network Information Theory

  2001cited by this paper
• Report on the Development of the Advanced Encryption Standard (AES)

  2001cited by this paper
• US Secure Hash Algorithm 1 (SHA1)

  2001cited by this paper
• Lecture Notes on Cryptography

  2001cited by this paper
• National Institute of Standards and Technologyにおける超伝導研究及び生活

  2001cited by this paper
• Error correcting codes and collision-resistant hashing

  1999cited by this paper
• Analysis and design of cryptographic hash functions

  1999cited by this paper
• HCC: A Hash Function Using Error Correcting Codes

  1997cited by this paper
• Secure Hash Standard

  1995cited by this paper
• Random oracles are practical: a paradigm for designing efficient protocols

  1993cited by this paper
• Standards

  1987cited by this paper
• The random coding bound is tight for the average code (Corresp.)

  1973cited by this paper

• No citing papers are available for this paper.