Quantum collision finding for homomorphic hash functions

• URL: http://arxiv.org/abs/2108.00100v2
• Date: Tue, 10 Aug 2021 13:51:23 GMT
• Title: Quantum collision finding for homomorphic hash functions
• Authors: Juan Carlos Garcia-Escartin, Vicent Gimeno, Julio Jos\'e Moyano-Fern\'andez
• Abstract summary: We present concrete attack examples to provable hash functions, including a preimage attack to $oplus$-linear hash functions. Hash functions which are additive or multiplicative are vulnerable to a quantum attack using the hidden subgroup problem algorithm for quantum computers.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hash functions are a basic cryptographic primitive. Certain hash functions try to prove security against collision and preimage attacks by reductions to known hard problems. These hash functions usually have some additional properties that allow for that reduction. Hash functions which are additive or multiplicative are vulnerable to a quantum attack using the hidden subgroup problem algorithm for quantum computers. Using a quantum oracle to the hash, we can reconstruct the kernel of the hash function, which is enough to find collisions and second preimages. When the hash functions are additive with respect to the group operation in an Abelian group, there is always an efficient implementation of this attack. We present concrete attack examples to provable hash functions, including a preimage attack to $\oplus$-linear hash functions and for certain multiplicative homomorphic hash schemes.

Related papers

• Fully Quantum Hash Function [3.2923780772605604]
  We introduce a novel, textitfully quantum hash (FQH) function within the quantum walk on a cycle framework. FQH requires minimal quantum resources to produce a large hash value, providing security against the birthday attack.
  arXiv  Detail & Related papers  (2024-08-07T10:28:32Z)
• Automated Quantum Circuit Generation for Computing Inverse Hash Functions [0.29998889086656577]
  Several cryptographic systems depend upon the computational difficulty of reversing cryptographic hash functions. Hash functions can be cryptographically secure, and they are employed in encryption, authentication, and other security methods. It has been suggested that such cryptographically-secure hash functions will play a critical role in the era of post-quantum cryptography.
  arXiv  Detail & Related papers  (2024-04-26T03:55:46Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  Sponge hashing is a widely used class of cryptographic hash algorithms. Intrepid permutations have so far remained a fundamental open problem. We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
  arXiv  Detail & Related papers  (2024-03-07T18:46:58Z)
• Generalized Hybrid Search and Applications to Blockchain and Hash Function Security [50.16790546184646]
  We first examine the hardness of solving various search problems by hybrid quantum-classical strategies. We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
  arXiv  Detail & Related papers  (2023-11-07T04:59:02Z)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  We show that targetcollapsing enables publiclyverifiable deletion (PVD) We build on this framework to obtain a variety of primitives supporting publiclyverifiable deletion from weak cryptographic assumptions.
  arXiv  Detail & Related papers  (2023-03-15T15:00:20Z)
• Unified Functional Hashing in Automatic Machine Learning [58.77232199682271]
  We show that large efficiency gains can be obtained by employing a fast unified functional hash. Our hash is "functional" in that it identifies equivalent candidates even if they were represented or coded differently. We show dramatic improvements on multiple AutoML domains, including neural architecture search and algorithm discovery.
  arXiv  Detail & Related papers  (2023-02-10T18:50:37Z)
• A quantum algorithm for finding collision-inducing disturbance vectors in SHA-1 [2.963904090194172]
  Modern cryptographic protocols rely on sophisticated hash functions to generate quasi-unique numbers that serve as signatures for user authentication and other security verifications. The security could be compromised by finding texts hash-mappable to identical numbers, forming so-called collision attack. We propose an algorithm that takes advantage of entangled quantum states for concurrent seeding of candidate disturbance vectors.
  arXiv  Detail & Related papers  (2022-10-23T16:01:17Z)
• A Lower Bound of Hash Codes' Performance [122.88252443695492]
  In this paper, we prove that inter-class distinctiveness and intra-class compactness among hash codes determine the lower bound of hash codes' performance. We then propose a surrogate model to fully exploit the above objective by estimating the posterior of hash codes and controlling it, which results in a low-bias optimization. By testing on a series of hash-models, we obtain performance improvements among all of them, with an up to $26.5%$ increase in mean Average Precision and an up to $20.5%$ increase in accuracy.
  arXiv  Detail & Related papers  (2022-10-12T03:30:56Z)
• Post-quantum hash functions using $\mathrm{SL}_n(\mathbb{F}_p)$ [0.0]
  We define new families of Tillich-Z'emor hash functions, using higher dimensional special linear groups over finite fields as platforms. Cayley graphs of these groups combine fast mixing properties and high girth, which together give rise to good preimage and collision resistance of the corresponding hash functions.
  arXiv  Detail & Related papers  (2022-07-08T16:15:11Z)
• Controlled Alternate Quantum Walk based Block Hash Function [14.540996187637523]
  Controlled quantum walk based hash function is a kind of novel hash function, which is safe, flexible, high-efficient, and compatible. To process message in batch amounts, in this paper, controlled alternate quantum walk based block hash function is presented.
  arXiv  Detail & Related papers  (2022-05-12T09:42:17Z)
• Reinforcing Short-Length Hashing [61.75883795807109]
  Existing methods have poor performance in retrieval using an extremely short-length hash code. In this study, we propose a novel reinforcing short-length hashing (RSLH) In this proposed RSLH, mutual reconstruction between the hash representation and semantic labels is performed to preserve the semantic information. Experiments on three large-scale image benchmarks demonstrate the superior performance of RSLH under various short-length hashing scenarios.
  arXiv  Detail & Related papers  (2020-04-24T02:23:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.