Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
k-Anonymous Group Signatures: Addressing Strict Content Moderation in End-to-End Secure Messaging Platforms
Get PDFWe review k-anonymity in authentication schemes, group signatures and ring signatures. While existing constructions achieve unlinkability, they typically necessitate maintaining state or relying on computationally expensive tracing algorithms. We propose a stateless variant that is efficiently traceable, albeit necessarily fully linkable. To the best of our knowledge, our variant, which we call k-Anonymous Group Signatures (k-AGS), is the first scheme to combine both statelessness and efficient traceability.
Building upon our k-AGS framework, we design k-Anonymous Set Pre-Constrained Group Signatures (k-ASPCGS) which is a threshold extension of the Set Pre-Constrained Group Signatures (SPCGS) introduced by Bartusek et al. (EUROCRYPT 2023).
We show that our notions arise naturally in the context of lawful surveillance, particularly for end-to-end secure messaging platforms, where controlled traceability is essential. Beyond this setting, they may also help mitigate the impact of strict moderation policies in large-scale distributed asynchronous platforms (e.g. Facebook, whistleblowing portals) as well as in spam control, where false positives remain a persistent challenge
Linear-time and Logarithmically-sound Permutation and Multiset SNARKs
Get PDFPermutation and multiset checks underpin many SNARKs, yet existing techniques either incur superlinear prover time or rely on auxiliary commitments with soundness error that grows linearly in the input size. We present new arguments with linear-time provers and logarithmic soundness, without auxiliary commitments.
Prior work achieving logarithmic soundness error arithmetizes the permutation as a product of several multilinear polynomials, a formulation chosen for compatibility with the classic Sumcheck PIOP. A simpler alternative treats permutations as multilinear extensions of their permutation matrices. While this formulation was previously believed to require quadratic prover time, we show that this overhead can be eliminated by taking a linear-algebraic perspective. This viewpoint has a key advantage: partially evaluating the multilinear polynomial of the permutation requires no additional field operations and amounts to applying the inverse permutation to the verifier\u27s challenge vector. This makes the step essentially free in terms of algebraic cost, unlike in prior approaches. Compared to concurrent work BiPerm (Bünz et al., ePrint Archive, 2025), our scheme requires no permutation preprocessing and supports prover-supplied permutations.
We show a sparsity-aware PCS like Dory (Lee, TCC, 2021) can compile our PIOP to a SNARK such that the resulting SNARK prover still runs in time . Our construction is the first logarithmically-sound SNARK with an -time prover for both permutation and multiset checks. We further prove a matching optimal prover lower bound, and we identify specific permutations that can be evaluated by the verifier in -time. The ability to evaluate these permutations in time allows the verifier to avoid relying on prover-supplied commitments or evaluation proofs. As a result, we obtain the first logarithmically sound, field-agnostic SNARK with an -time prover in this setting
Aggregate Signatures Tightly Secure under Adaptive Corruptions
Get PDFAggregate signatures allow compressing multiple single-signer signatures into a single short aggregate signature. This primitive has attracted new attention due to applications in blockchains and cryptocurrencies. In multisig addresses, which is one of such applications, aggregate signatures reduce the sizes of transactions from multisig addresses. Security of aggregate signatures under adaptive corruptions of signing keys is important, since one of the motivations of multisig addresses was a countermeasure against signing key exposures. We propose the first aggregate signature scheme tightly secure under adaptive corruptions using pairings. An aggregate signature includes two source group elements of bilinear groups plus a bit vector whose length is equal to the number of single-signer signatures being aggregated. To construct a scheme, we employ a technique from quasi-adaptive non-interactive zero-knowledge arguments. Our construction can be seen as modularization and tightness improvement of Libert et al.\u27s threshold signature scheme supporting signature aggregation (Theoretical Computer Science 645) in a non-threshold setting
GPV Preimage Sampling with Weak Smoothness and Its Applications to Lattice Signatures
Get PDFThe lattice trapdoor associated with Ajtai\u27s function is the cornerstone of many lattice-based cryptosystems.
The current provably secure trapdoor framework, known as the GPV framework, uses a \emph{strong smoothness} condition, i.e. for smoothing parameter , to ensure the correctness of the security reduction.
In this work, we investigate the feasibility of \emph{weak smoothness}, e.g. or even in the GPV framework and present several positive results.
First, we provide a theoretical security proof for GPV with weak smoothness under a new assumption.
Then, we present Gaussian samplers that are compatible with the weak smoothness condition.
As direct applications, we present two practical GPV signature instantiations based on a weak smoothness condition.
Our first instantiation is a variant of Falcon achieving smaller size and higher security.
The public key sizes are to smaller, and the signature sizes are to smaller than Falcon.
We also showcase an NTRU-based GPV signature scheme that employs the Peikert sampler with weak smoothness.
This offers a simple implementation while the security level is greatly lower.
Nevertheless, at the NIST-3 security level, our scheme achieves a reduction in size compared to Dilithium-3
Hashing-friendly elliptic curves
Get PDFThis article aims to consider batch hashing to elliptic curves. The given kind of hash functions found numerous applications in elliptic curve cryptography. In practice, a hash-to-curve function is often evaluated at a time by the same entity at many different inputs. It turns out that under certain mild conditions simultaneous evaluation can be carried out several times faster than separate ones. In this regard, the article introduces a new class of elliptic curves over finite fields, more appropriate for multiple hashing to them. Moreover, two explicit hashing-friendly Montgomery/twisted Edwards curves (of security bits) have been generated: one of CM discriminant , i.e., a GLV-friendly curve and one of huge CM discriminant, i.e., a CM-secure curve. The new elliptic curves are intentionally covered by so-called Klein\u27s and Bring\u27s curves of geometric genera and , respectively. The latter are well studied in various algebraic geometry contexts, although they have not yet been (reasonably) applied in cryptography to the author\u27s knowledge. Such a mathematical complication is justified, since conventional curves (from existing standards or of -invariants , ) are seemingly less efficient for batch hashing
ALFOMs and the Moirai: Quantifying the Performance/Security Tradeoff for ZK-friendly Hash Functions
Get PDFZero-Knowledge (ZK) protocols rely internally on hash functions for their security arguments. However, the hash functions that are the most efficient in this context differ substantially from e.g. SHA-3: their round function must enable an efficient arithmetization of its verification. In practice, it means that verifying if involves as little finite field multiplications as possible. In turn, this design requirement implies a greater vulnerability to algebraic attacks. In fact, improvement of those have proved devastating, and imply the need to completely rethink the methods used to ensure security against them. In this paper, we show that it is possible to build a simple yet efficient security argument based on a precise estimate of the so-called “ideal degree” of a system of equations. Furthermore, we show that the increase of this quantity across rounds is tightly connected to the cost of the hash function in two different arithmetizations, namely AIR and R1CS. We precisely quantify this relation by introducing ALgebraic Figures Of Merit (ALFOMs) that capture how efficient a specific primitive (and in fact its round function) are at increasing the security per unit of cost. This new insight allows us to better understand sometimes puzzling performance differences between state-of-the-art hash functions in the R1CS and AIR cases, and to provide a fair and simple comparison of their round functions in this context. Furthermore, we present a new group of round functions we called the Moirai which allow us to explore what a round function providing optimal performance/security tradeoff could look like
Differential Fault Attacks on MQOM, Breaking the Heart of Multivariate Evaluation
Get PDFMQOM is one of the fourteen remaining candidates in the
second round of the NIST post-quantum signature standardization process.
Introduced in 2023, MQOM instantiates the Multi-Party Computation
in the Head (MPCitH) paradigm over the well-established hard
problem of solving Multivariate Quadratic (MQ) equations. In this paper,
we present the first fault attacks on MQOM targeting the MQ evaluation
phase, which is a central component of the algorithm. We introduce
four differential fault attacks and demonstrate their effectiveness against
both unprotected and masked implementations. The first two target the
secret key using a random fault model, making them particularly realistic
and practical. With as little as one or two injected faults, depending
on the variant, the entire secret key can be recovered through linear algebra.
The other two attacks exploit faults on the coefficients of the MQ
system directly. Our results highlight that the MQ evaluation, despite
not being identified as a sensitive component until now, can be exploited
using just a few fault injections
Correction Fault Attack on CROSS under Unknown Bit Flips
Get PDFRecognising the need for PQC signature schemes with different size and performance trade-offs than the ML-DSA and SLH-DSA standards, in 2023 NIST launched a competition for additional signature algorithms. Among the current candidates in this competition is CROSS, a code-based scheme derived from the syndrome-decoding problem and suitable for memory-constrained devices.
This paper presents a fault attack on CROSS that recovers the secret key by flipping one or more bits in the scheme’s public parity-check matrix. Unlike previous PQC fault attacks that typically rely on precisely controlled fault injections, which is often an unrealistic assumption, our approach exploits bit flips with unknown position and value, resembling the Rowhammer fault model. The attack builds upon the correction-based methodology introduced for Dilithium (Euro S&P’22; CHES’24) and exploits structural properties of CROSS to substantially relax attacker requirements. We demonstrate the attack on an ARM Cortex-M4 processor using voltage fault injection. We further show that prior work on partial key exposure attacks (CRYPTO\u2722) can be extended to CROSS under non-trivial erasure rates, reducing the attack complexity. The attack remains effective in the presence of memory-integrity protection mechanisms such as error-correcting codes. Finally, we propose countermeasures for hardening CROSS implementations against physical attacks
Binary Codes for Computationally Bounded Errors Under Standard Crypto Assumptions
Get PDFWe study error-detection and error-correction codes for computationally bounded adversarial channels. We consider seeded codes where the polynomial-time encoding and decoding procedures share a public random seed, but are otherwise deterministic. An adversarial channel gets this seed and can perform arbitrary polynomial-time computation to adaptively select both the message to be encoded and a bounded number of errors to be added to the resulting codeword. The goal is to detect or correct such errors with overwhelming probability, while achieving better trade-offs between rate and error tolerance than those possible for computationally unbounded channels.
For large alphabets, prior work (ITCS \u2725) achieves essentially optimal parameters under minimal cryptographic assumptions. However, for the binary alphabet, prior works (TCC \u2720, EUROCRYPT \u2725) either only achieved a weaker notion of selective security under the learning with errors (LWE) assumption, or relied on non-standard cryptographic assumptions to get the full notion of adaptive security.
In this work, we construct binary codes that achieve the full notion of adaptive security assuming trapdoor hashing, which can in turn be instantiated under a variety of standard cryptographic assumptions such as LWE, or Decisional Diffie-Hellman (DDH), or Quadratic Residuosity (QR), or Decisional Composite Residuosity (DCR). For error detection, our codes get essentially optimal rate and relative error tolerance . For error correction, they can uniquely correct fraction of errors with a rate matching that of the best known list-decodable codes for this error tolerance.
As a central technical tool of potentially independent interest, we construct multi-input correlation intractable hashing for ``shifted output relations\u27\u27 under the standard cryptographic assumptions above
0-ART. Asynchronous and Verifiable Group Management for Decentralized Applications
Get PDFThe majority of modern e2e private applications face scalability issues that limit their functionality, broader adoption, and overall user experience. Some of them organize private groups as a set of peer-to-peer chats, which leads to an overall quadratic complexity in the size of group communication and a linear time complexity in the number of members for encryption. Others apply more scalable group key establishment constructions (such as ART), but at the same time, they do not support verifiable and concurrent updates. In this paper, we introduce the 0-ART protocol, which aims to address the aforementioned issues by (1) verifiable group operations; (2) a causal tree construction allowing for multiple concurrent updates and efficient member removal; (3) anonymous credentials, making privacy in the group available while keeping operations authentic. We implemented the 0-ART framework and applied it to a decentralized collaborative work application. According to our benchmark, executing the most complex operation (performing the provable operation in a group of size ) takes 1.57 seconds on the user\u27s device and Kb of proof size