MIRANDA: short signatures from a leakage-free full-domain-hash scheme

• URL: http://arxiv.org/abs/2510.07479v1
• Date: Wed, 08 Oct 2025 19:24:24 GMT
• Title: MIRANDA: short signatures from a leakage-free full-domain-hash scheme
• Authors: Alain Couvreur, Thomas Debris-Alazard, Philippe Gaborit, Adrien Vinçotte,
• Abstract summary: 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.
• Score: 10.228787876075266
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present $\mathsf{Miranda}$, the first family of full-domain-hash signatures based on matrix codes. This signature scheme fulfils the paradigm of Gentry, Peikert and Vaikuntanathan ($\mathsf{GPV}$), which gives strong security guarantees. Our trapdoor is very simple and generic: if we propose it with matrix codes, it can actually be instantiated in many other ways since it only involves a subcode of a decodable code (or lattice) in a unique decoding regime of parameters. Though $\mathsf{Miranda}$ signing algorithm relies on a decoding task where there is exactly one solution, there are many possible signatures given a message to sign and we ensure that signatures are not leaking information on their underlying trapdoor by means of a very simple procedure involving the drawing of a small number of uniform bits. In particular $\mathsf{Miranda}$ does not use a rejection sampling procedure which makes its implementation a very simple task contrary to other $\mathsf{GPV}$-like signatures schemes such as $\mathsf{Falcon}$ or even $\mathsf{Wave}$. We instantiate $\mathsf{Miranda}$ with the famous family of Gabidulin codes represented as spaces of matrices and we study thoroughly its security (in the EUF-CMA security model). For~$128$ bits of classical security, the signature sizes are as low as~$90$ bytes and the public key sizes are in the order of~$2.6$ megabytes.

Related papers

• Bilinear Compressive Security [4.3725047448751235]
  We study a rather idealized known attack for recovering $Q$ from repeated observations of $y$'s for different, known $x_k$.<n>Our main result for BCS states that under a weak symmetry condition on the filter $h$, recovering $Q$ will require extensive sampling from transmissions of $Omegaleft(maxleft(n,(n/s)2right)$ messages $x_k$ if they are $s$-sparse.
  arXiv  Detail & Related papers  (2025-10-17T07:32:25Z)
• 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)
• The Matrix Subcode Equivalence problem and its application to signature with MPC-in-the-Head [2.123778388986574]
  We introduce two new problems: the Matrix Subcode Equivalence Problem and the Matrix Code Permuted Kernel Problem.<n>We apply the MPCitH paradigm to build a signature scheme.<n>We obtain a signature size of $approx$ 4 800 Bytes, with a public key of $approx$ 275 Bytes.
  arXiv  Detail & Related papers  (2025-07-21T08:33:24Z)
• Optimal Computational Secret Sharing [51.599517747577266]
  In $(t, n)$-threshold secret sharing, a secret $S$ is distributed among $n$ participants.<n>We present a construction achieving a share size of $tfrac|S|t + |K|t$.
  arXiv  Detail & Related papers  (2025-02-04T23:37:16Z)
• 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.<n>We utilize this algorithm to attack the above schemes so that we are able to forge any message and decrypt any ciphertext.<n>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)
• On the (In)security of optimized Stern-like signature schemes [0.5755004576310334]
  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.
  arXiv  Detail & Related papers  (2024-08-28T15:03:38Z)
• A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
  We construct an algorithm that returns a point $hat xin barmathcal X$ such that $f(hat x)$ is as small as possible. We prove that this method is such that the $f(hat x) - min_xin barmathcal X f(x)$ is of smaller order than $d2/sqrtn$ up to poly-logarithmic terms.
  arXiv  Detail & Related papers  (2024-06-26T18:19:10Z)
• A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring [55.17220687298207]
  The threshold secret sharing scheme allows the dealer to distribute the share to every participant that the secret is correctly recovered from a certain amount of shares. We propose a brand-new construction of evolving $k$-threshold secret sharing scheme for an $ell$-bit secret over a ring, with correctness and perfect security.
  arXiv  Detail & Related papers  (2024-02-02T05:04:01Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  We introduce an observation-matrix-based framework for fully asynchronous online Federated Learning with adversaries. Our main result is that the proposed algorithm almost surely converges to the desired mean $mu.$ We derive this convergence using a novel differential-inclusion-based two-timescale analysis.
  arXiv  Detail & Related papers  (2023-04-04T04:32:29Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  We consider the problem of combining and learning over a set of adversarial algorithms with the goal of adaptively tracking the best one on the fly. The CORRAL of Agarwal et al. achieves this goal with a regret overhead of order $widetildeO(sqrtd S T)$ where $M$ is the number of base algorithms and $T$ is the time horizon. Motivated by this issue, we propose a new recipe to corral a larger band of bandit algorithms whose regret overhead has only emphlogarithmic dependence on $M$ as long
  arXiv  Detail & Related papers  (2022-02-12T21:55:44Z)
• On Submodular Contextual Bandits [92.45432756301231]
  We consider the problem of contextual bandits where actions are subsets of a ground set and mean rewards are modeled by an unknown monotone submodular function. We show that our algorithm efficiently randomizes around local optima of estimated functions according to the Inverse Gap Weighting strategy.
  arXiv  Detail & Related papers  (2021-12-03T21:42:33Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)

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.