On the (In)security of optimized Stern-like signature schemes

• URL: http://arxiv.org/abs/2408.15843v1
• Date: Wed, 28 Aug 2024 15:03:38 GMT
• Title: On the (In)security of optimized Stern-like signature schemes
• Authors: André Chailloux, Simona Etinski,
• Abstract summary: A crucial optimization of Stern's signature scheme is to generate pseudo-random vectors and a permutation instead of random ones. We show that for some parameters, there is an attack that exploits this optimization and breaks the scheme in time. By adding a string $salt in 0,12lambda$ to the scheme, and changing slightly how the pseudo-random strings are generated, we prove not only that our attack doesn't work but that for any attack, the scheme preserves $lambda$ bits of security.
• Score: 0.5755004576310334
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Stern's signature scheme is a historically important code-based signature scheme. A crucial optimization of this scheme is to generate pseudo-random vectors and a permutation instead of random ones, and most proposals that are based on Stern's signature use this optimization. However, its security has not been properly analyzed, especially when we use deterministic commitments. In this article, we study the security of this optimization. We first show that for some parameters, there is an attack that exploits this optimization and breaks the scheme in time $O(2^{\frac{\lambda}{2}})$ while the claimed security is $\lambda$ bits. This impacts in particular the recent Quasy-cyclic Stern signature scheme [BGMS22]. Our second result shows that there is an efficient fix to this attack. By adding a string $salt \in \{0,1\}^{2\lambda}$ to the scheme, and changing slightly how the pseudo-random strings are generated, we prove not only that our attack doesn't work but that for any attack, the scheme preserves $\lambda$ bits of security, and this fix increases the total signature size by only $2\lambda$ bits. We apply this construction to other optimizations on Stern's signature scheme, such as the use of Lee's metric or the use of hash trees, and we show how these optimizations improve the signature length of Stern's signature scheme.

Related papers

• Spinel: A Post-Quantum Signature Scheme Based on $\mathrm{SL}_n(\mathbb{F}_p)$ Hashing [1.6930974360601116]
  We introduce Spinel, a post-quantum digital signature scheme with security rooted in the hardness of navigating expander graphs over $mathrmSL_n(mathbbF_p)$.<n>Our approach lays the foundations for the design of hash-based signature schemes, expanding the toolkit of post-quantum cryptography.
  arXiv  Detail & Related papers  (2026-02-10T15:22:01Z)
• A Simple and Efficient One-Shot Signature Scheme [7.043920979018913]
  One-shot signatures (OSS) are a powerful and uniquely quantum cryptographic primitive.<n>We construct a new, simple, direct, and efficient one-shot signature scheme which can sign messages of any length.<n>Unlike the Shmueli-Zhandry construction, our scheme achieves perfect correctness.
  arXiv  Detail & Related papers  (2025-10-13T01:53:00Z)
• MIRANDA: short signatures from a leakage-free full-domain-hash scheme [10.228787876075266]
  We present $mathsfMiranda$, the first family of full-domain-hash signatures based on matrix codes.<n>Our trapdoor is very simple and generic: if we propose it with matrix codes, it can actually be instantiated in many other ways.
  arXiv  Detail & Related papers  (2025-10-08T19:24:24Z)
• Optimal Threshold Signatures in Bitcoin [0.0]
  We formulate the design of a threshold signature scheme as made possible on cryptocurrency protocols like Bitcoin.<n>A user designs this scheme knowing that a malicious attacker can also obtain the signatures with some probability.<n> Interventions like increasing the security or usability of the signatures allow for higher thresholds.
  arXiv  Detail & Related papers  (2025-09-29T19:04:19Z)
• How to Copy-Protect Malleable-Puncturable Cryptographic Functionalities Under Arbitrary Challenge Distributions [11.781645368622517]
  A quantum copy-protection scheme encodes a functionality into a quantum state.<n>We show how to copy-protect even a larger class of schemes.
  arXiv  Detail & Related papers  (2025-07-25T07:40:44Z)
• Sign Operator for Coping with Heavy-Tailed Noise: High Probability Convergence Bounds with Extensions to Distributed Optimization and Comparison Oracle [77.3806516979843]
  We show that SignSGD achieves optimal sample complexity $tildeO(varepsilon-frac3kappa - 2kappa 1right)$ with high accuracy. We also explore the application of the sign operator in zeroth-order optimization with an oracle that can only compare function values at two different points.
  arXiv  Detail & Related papers  (2025-02-11T19:54:11Z)
• The Nonlinear Filter Model of Stream Cipher Redivivus [28.8640336189986]
  The nonlinear filter model is an old and well understood approach to the design of secure stream ciphers. We put forward concrete suggestions of stream ciphers which are $kappa$-bit secure against known types of attacks. For the $80$-bit, $128$-bit, and the $256$-bit security levels, the circuits for the corresponding stream ciphers require about 1743.5, 2771.5, and 5607.5 NAND gates respectively.
  arXiv  Detail & Related papers  (2025-02-03T07:01:21Z)
• An Attack on $p$-adic Lattice Public-key Cryptosystems and Signature Schemes [3.444630356331766]
  In this paper, we improve the LVP algorithm in local fields. We utilize this algorithm to attack the above schemes so that we are able to forge any message and decrypt any ciphertext. Although these schemes are broken, this work does not mean that $p$-adic lattices are not suitable in constructing cryptographic primitives.
  arXiv  Detail & Related papers  (2024-09-13T12:31:57Z)
• RANDAO-based RNG: Last Revealer Attacks in Ethereum 2.0 Randomness and a Potential Solution [0.5917100081691199]
  RANDAO 2.0 is a major upgrade to improve its scalability, throughput, and security. A vulnerability, referred to as the Last Revealer Attack' (LRA), compromises the randomness of this scheme. We propose a Shamir's Secret Sharing (SSS)-based RANDAO scheme to mitigate the LRA.
  arXiv  Detail & Related papers  (2024-03-14T16:28:33Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Signatures From Pseudorandom States via $\bot$-PRFs [0.11650821883155184]
  We introduce new definitions for $bot$-PRG and $bot$-PRF. Our main application is a (quantum) digital signature scheme with classical public keys and signatures.
  arXiv  Detail & Related papers  (2023-11-01T20:54:50Z)
• Transferable Sparse Adversarial Attack [62.134905824604104]
  We introduce a generator architecture to alleviate the overfitting issue and thus efficiently craft transferable sparse adversarial examples. Our method achieves superior inference speed, 700$times$ faster than other optimization-based methods.
  arXiv  Detail & Related papers  (2021-05-31T06:44:58Z)
• Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions [91.8283876874947]
  We consider a best arm identification (BAI) problem for Sequential bandits with adversarial corruptions in the fixed-budget setting of T steps. We design a novel randomized algorithm, Probabilistic Shrinking($u$) (PSS($u$)), which is agnostic to the amount of corruptions. We show that when the CPS is sufficiently large, no algorithm can achieve a BAI probability tending to $1$ as $Trightarrow infty$.
  arXiv  Detail & Related papers  (2020-10-15T17:34:26Z)
• SMYRF: Efficient Attention using Asymmetric Clustering [103.47647577048782]
  We propose a novel type of balanced clustering algorithm to approximate attention. SMYRF can be used as a drop-in replacement for dense attention layers without any retraining. We show that SMYRF can be used interchangeably with dense attention before and after training.
  arXiv  Detail & Related papers  (2020-10-11T18:49:17Z)
• Black-Box Certification with Randomized Smoothing: A Functional Optimization Based Framework [60.981406394238434]
  We propose a general framework of adversarial certification with non-Gaussian noise and for more general types of attacks. Our proposed methods achieve better certification results than previous works and provide a new perspective on randomized smoothing certification.
  arXiv  Detail & Related papers  (2020-02-21T07:52:47Z)
• Optimistic Policy Optimization with Bandit Feedback [70.75568142146493]
  We propose an optimistic trust region policy optimization (TRPO) algorithm for which we establish $tilde O(sqrtS2 A H4 K)$ regret for previous rewards. To the best of our knowledge, the two results are the first sub-linear regret bounds obtained for policy optimization algorithms with unknown transitions and bandit feedback.
  arXiv  Detail & Related papers  (2020-02-19T15:41:18Z)
• Randomized Smoothing of All Shapes and Sizes [29.40896576138737]
  We show that for an appropriate notion of "optimal", the optimal smoothing for any "nice" norms have level sets given by the norm's *Wulff Crystal* We show fundamental limits to current randomized smoothing techniques via the theory of *Banach space cotypes*.
  arXiv  Detail & Related papers  (2020-02-19T11:41:09Z)

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.