Post-quantum hash functions using $\mathrm{SL}_n(\mathbb{F}_p)$

• URL: http://arxiv.org/abs/2207.03987v3
• Date: Thu, 22 Aug 2024 19:32:01 GMT
• Title: Post-quantum hash functions using $\mathrm{SL}_n(\mathbb{F}_p)$
• Authors: Corentin Le Coz, Christopher Battarbee, Ramón Flores, Thomas Koberda, Delaram Kahrobaei,
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We define new families of Tillich-Z\'emor hash functions, using higher dimensional special linear groups over finite fields as platforms. The 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. We justify the claim that the resulting hash functions are post-quantum secure.

Related papers

• Girth of the Cayley graph and Cayley hash functions [0.0]
  Cayley hash functions are based on a simple idea of using a pair of semigroup elements, A and B, to hash the 0 and 1 bit. In this article, we survey some of the previously proposed Cayley hash functions and single out a very simple hash function whose security has not been compromised up to date.
  arXiv  Detail & Related papers  (2025-02-18T17:56:47Z)
• GraphHash: Graph Clustering Enables Parameter Efficiency in Recommender Systems [51.64666652517944]
  This paper introduces GraphHash, the first graph-based approach that leverages modularity-based bipartite graph clustering to reduce embedding table sizes. By employing fast clustering algorithms, GraphHash serves as a computationally efficient proxy for message-passing during preprocessing. In experiments, GraphHash substantially outperforms diverse hashing baselines on both retrieval and click-through-rate prediction tasks.
  arXiv  Detail & Related papers  (2024-12-23T03:37:58Z)
• A Flexible Plug-and-Play Module for Generating Variable-Length [61.095479786194836]
  Nested Hash Layer (NHL) is a plug-and-play module designed for existing deep supervised hashing models. NHL simultaneously generates hash codes of varying lengths in a nested manner. NHL achieves superior retrieval performance across various deep hashing models.
  arXiv  Detail & Related papers  (2024-12-12T04:13:09Z)
• 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)
• Cryptanalysis of a Cayley Hash Function Based on Affine Maps in one Variable over a Finite Field [0.0]
  Cayley hash functions are cryptographic hashes constructed from Cayley graphs of groups. The hash function proposed by Shpilrain and Sosnovski, based on linear functions over a finite field, was proven insecure. This paper shows that the proposal by Ghaffari and Mostmaghi that uses the hash in its construction is also insecure.
  arXiv  Detail & Related papers  (2023-08-30T05:13:55Z)
• 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)
• PHPQ: Pyramid Hybrid Pooling Quantization for Efficient Fine-Grained Image Retrieval [68.05570413133462]
  We propose a Pyramid Hybrid Pooling Quantization (PHPQ) module to capture and preserve fine-grained semantic information from multi-level features. Experiments on two widely-used public benchmarks, CUB-200-2011 and Stanford Dogs, demonstrate that PHPQ outperforms state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-09-11T07:21:02Z)
• Quantum collision finding for homomorphic hash functions [0.0]
  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.
  arXiv  Detail & Related papers  (2021-07-30T23:01:02Z)
• Additive Feature Hashing [0.0]
  We show that additive feature hashing can be performed directly by adding the hash values and converting them into high-dimensional numerical vectors. We show that the performance of additive feature hashing is similar to the hashing trick, and we illustrate the results numerically using synthetic, language recognition, and SMS spam detection data.
  arXiv  Detail & Related papers  (2021-02-07T23:15:04Z)
• Generative Semantic Hashing Enhanced via Boltzmann Machines [61.688380278649056]
  Existing generative-hashing methods mostly assume a factorized form for the posterior distribution. We propose to employ the distribution of Boltzmann machine as the retrievalal posterior. We show that by effectively modeling correlations among different bits within a hash code, our model can achieve significant performance gains.
  arXiv  Detail & Related papers  (2020-06-16T01:23:39Z)
• 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.