Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Gluing Random Unitaries with Inverses and Applications to Strong Pseudorandom Unitaries
Get PDFGluing theorem for random unitaries [Schuster, Haferkamp, Huang, QIP 2025] have found numerous applications, including designing low depth random unitaries [Schuster, Haferkamp, Huang, QIP 2025], random unitaries in [Foxman, Parham, Vasconcelos, Yuen\u2725] and generically shortening the key length of pseudorandom unitaries [Ananth, Bostanci, Gulati, Lin EUROCRYPT\u2725]. We present an alternate method of combining Haar random unitaries from the gluing lemma from [Schuster, Haferkamp, Huang, QIP 2025] that is secure against adversaries with inverse query access to the joined unitary. As a consequence, we show for the first time that strong pseudorandom unitaries can generically have their length extended, and can be constructed using only bits of randomness, for any constant , if any family of strong pseudorandom unitaries exists
PERSEUS – Probabilistic Evaluation of Random probing SEcurity Using efficient Sampling
Get PDFCryptographic implementations are inherently vulnerable to side-channel attacks, which exploit physical leakages such as power consumption. Masking has become the most widely adopted countermeasure to mitigate these threats, as it randomizes intermediate values and makes the leakage less exploitable. Yet, a central challenge remains: how to rigorously assess the concrete security level of masked implementations.
To tackle this issue, the random probing model has emerged as a powerful abstraction. It formalizes leakage as random probes in the circuit and, importantly, the security in the noisy leakage model, which closely reflects the behavior of real embedded devices, reduces to security in the random probing model. Hence, proving security in the random probing model provides sound guarantees of practical resistance against side-channel attacks.
Yet, the current state of the art on random probing compilers and verifiers suffers from a clear limitation: scalable approaches yield prohibitively large and inefficient circuits, while tighter methods do not scale to practical circuit sizes. In this work, we bridge this gap by introducing a new methodology that directly estimates the random probing security of large circuits through Monte Carlo sampling, combined with a pruning strategy that drastically reduces the sampling space.
We implement our approach in a new tool, PERSEUS, which supports both gate and wire leakage models. Our experiments demonstrate that PERSEUS can efficiently evaluate masked implementations of AES-128 with shares, achieving security levels beyond 32 bits, thereby significantly advancing the state of the art in practical verification of side-channel countermeasures
Compact, Efficient and CCA-Secure Updatable Encryption from Isogenies
Get PDFUpdatable Encryption (UE) allows ciphertexts to be updated under new keys without decryption, enabling efficient key rotation. Constructing post-quantum UE with strong security guarantees is challenging: the only known CCA-secure scheme, COM-UE, uses bitwise encryption, resulting in large ciphertexts and high computational costs.
We introduce DINE, a CCA-secure, isogeny-based post-quantum UE scheme that is both compact and efficient. Each encryption, decryption, or update requires only a few power-of-2 isogeny computations in dimension 2 to encrypt 28B messages, yielding 320B ciphertexts and 224B update tokens at NIST security level 1---significantly smaller than prior constructions. Our full C implementation demonstrates practical performances: updates in 7ms, encryptions in 48ms, and decryptions in 86ms.
Our design builds on recent advances in isogeny-based cryptography, combining high-dimensional isogeny representations with the Deuring correspondence. We also introduce new algorithms for the Deuring correspondence which may be of independent interest. Moreover, the security of our scheme relies on new problems that might open interesting perspectives in isogeny-based cryptography
Security Analysis of Privately Verifiable Privacy Pass
Get PDFPrivacy Pass is an anonymous authentication protocol which was initially designed by Davidson et al. (PETS’18) to reduce the number of CAPTCHAs that TOR users must solve. It issues single-use authentication tokens with anonymous and unlinkable redemption guarantees. The issuer and verifier of the protocol share a symmetric key, and tokens are privately verifiable. The protocol has sparked interest from both academia and industry, which led to an Internet Engineering Task Force (IETF) standard. While Davidson et al. formally analyzed the original protocol, the IETF standard introduces several changes to their protocol. Thus, the standardized version’s formal security remains unexamined. We fill this gap by analyzing the IETF standard’s privately verifiable Privacy Pass protocol.
In particular, there are two main discrepancies between the analyzed and standardized version: First, the IETF version introduces a redemption context, that can be used for blindly embedding a validity period into the Privacy Pass tokens. We show that this variant has significant differences to public metadata extension that has been proposed for the same purpose in the literature. Redemption context offers better privacy and security than public metadata. We capture both stronger guarantees through game-based security definitions and show that the currently considered one-more unforgeability notion for Privacy Pass is insufficient when a redemption context is used. Thus, we propose a new property, targeted context unforgeability, and prove its incomparability to one-more unforgeability. Second, Davidson et al. focused on a concrete Diffie-Hellman based construction, whereas the IETF version is built generically from a verifiable oblivious pseudorandom function (VOPRF). Further, the analyzed protocol omitted the full redemption phase needed to prevent double-spending. We prove that the generic IETF construction satisfies the desired security and privacy guarantees covering the full life-cycle of tokens. Our analysis relies on natural security properties of VOPRFs, providing compatibility with any secure VOPRF instantiation. This enables crypto agility, e.g., allowing to switch to efficient quantum-safe VOPRFs when they become available
Collusion-Resistant Quantum Secure Key Leasing Beyond Decryption
Get PDFSecure key leasing (SKL) enables the holder of a secret key for a
cryptographic function to temporarily lease the key using quantum
information. Later, the recipient can produce a deletion
certificate—a proof that they no longer have access to the secret
key. The security guarantee ensures that even a malicious
recipient cannot continue to evaluate the function, after producing
a valid deletion certificate.
Most prior work considers an adversarial recipient that obtains a single
leased key, which is insufficient for many applications. In
the more realistic collusion-resistant setting, security must
hold even when polynomially many keys are leased (and subsequently
deleted). However, achieving collusion-resistant SKL from standard
assumptions remains poorly understood, especially for
functionalities beyond decryption.
We improve upon this situation by introducing new pathways for
constructing collusion-resistant SKL. Our main contributions
are as follows:
- A generalization of quantum-secure collusion-resistant traitor
tracing called multi-level traitor tracing (MLTT), and a compiler
that transforms an MLTT scheme for a primitive into a
collusion-resistant SKL scheme for primitive .
- The first bounded collusion-resistant SKL scheme for PRFs, assuming
LWE.
- A compiler that upgrades any single-key secure SKL scheme for
digital signatures into one with unbounded collusion-resistance,
assuming OWFs.
- A compiler that upgrades collusion-resistant SKL schemes with
classical certificates to ones having verification-query resilience,
assuming OWFs
Fault to Forge: Fault Assisted Forging Attacks on LESS Signature Scheme
Get PDFLESS is a digital signature scheme that is currently in the second round of the National Institute of Standards and Technology\u27s (NIST\u27s) ongoing additional call for post-quantum standardization. LESS has been designed using a zero-knowledge identification scheme using a Fiat-Shamir transformation. The design of LESS is based on the hardness of the linear equivalence problem. However, the designers updated the scheme in the second round to improve efficiency and signature size. As we have seen before, in the NIST standardization process, analysis of physical security attacks such as side-channel and fault-injection attacks is considered nearly as important as mathematical security. In recent years, several works have been shown on LESS version 1 (LESS-v1). Among these, the work by Mondal et al. that appeared in Asiacrypt-2024 is most notable. This work showed several attack surfaces on LESS-v1 that can be exploited using different fault attacks. However, the implementation of LESS version 2 (LESS-v2) has not yet been explored in this direction.
In this work, we analyze the new structure of LESS-v2 signature scheme and propose a process of signature forgery. These techniques do not require the full signing key, but some other secret-related information. Our attacks uncovered multiple such attack surfaces in the design of LESS-v2 from where we can recover this secret-related information. We assume an adversary can use interrupted execution techniques, such as fault attacks, to recover this extra information. We have analyzed the average number of required faults for two particular fault models to recover the secret equivalent component and observed that we need only faulted signature for most of the parameter sets. Our attacks rely on very simple and standard fault models. We demonstrated these using both simulation and a simple experimental setup
New Straight-Line Extractable NIZKPs for Cryptographic Group Actions
Get PDFNon-interactive zero-knowledge proofs (NIZKPs) used as components in advanced cryptographic protocols typically require straight-line extractability to enable security analysis. While the widely-used Fiat-Shamir transform produces efficient and compact NIZKPs from Sigma protocols, its security proofs rely on adversary rewinding, which prevents straight-line extractability. The Fischlin transform offers an alternative that produces straight-line extractable NIZKPs from Sigma protocols, but typically sacrifices compactness in the process. In the post-quantum setting, Group-action-based Sigma protocols have proven to be truly flexible for the design of advanced cryptosystems. These Sigma protocols have a small challenge space that requires tailored optimizations to improve compactness of the derived NIZKPs and signatures. Some specific techniques for Fiat-Shamir NIZKPs have been studied. Among the most established solutions, the fixed-weight technique leverages on the use of seed trees to encode the majority of the transcripts in the proof. However, the implementation of the same techniques within the Fischlin transform encounters significant obstructions. In particular, its impact is limited, and a closed analysis of its effectiveness appears to be intractable.
This work introduces the GAO (Group Action Oriented) transform, a new generic compiler that produces straight-line extractable NIZKPs from Sigma protocols while significantly simplifying the analysis of the fixed-weight framework. The GAO transform is then optimized in two different ways, defining a collision predicate (yielding the Coll-GAO transform) and adopting a technique (Stretch-and-Compress) that can be applied to improve both GAO and Coll-GAO (yielding the SC-GAO and SC-Coll-GAO transforms). The practical advantages of the SC-Coll-GAO transform are theoretically motivated and concretely tested on the LESS digital signature, a code-based candidate that recently advanced to the second round of the NIST standardization process specifically purposed for post-quantum signatures. Remarkably, when compared to the Fiat-Shamir LESS baseline, SC-Coll-GAO incurs a computational cost increase by 50-60%, while signature sizes grow by only 10-20%
Anchored Merkle Range Proof for Pedersen Commitments
Get PDFWe present a simple range-proof mechanism for Pedersen commitments that avoids per-
transaction heavy ZK verification and pairings. The idea is to commit once to a Merkleized
range table of points {(U, aX·G)}X∈{1,...,2n} for a secret a ∈ Zq and a public anchor U = a·B.
At transaction time, a prover shows set membership of the leaf (U, ax · G), proves via a
Chaum–Pedersen DLEQ that logB U = logC C′ where C′ = a · C and C is the Pedersen
commitment, and finally proves (Schnorr) that C′ − (ax·G) lies in the H-direction. These
three checks enforce x to be the in-range value indexed by the Merkle leaf while preserving
privacy. Verification costs a single Merkle proof plus a DLEQ and a Schnorr discrete-log
proof over an elliptic curve group
Olingo: Threshold Lattice Signatures with DKG and Identifiable Abort
Get PDFWe present Olingo, a framework for threshold lattice signatures that is the first to offer all desired properties for real-world implementations of quantum-secure threshold signatures: small keys and signatures, low communication and round complexity, non-interactive online signing, distributed key generation (DKG), and identifiable abort.
Our starting point is the framework of Gur, Katz, and Silde (PQCrypto 2024). We change the underlying signature scheme to Raccoon (Katsumata et al., Crypto 2024), remove the trapdoor commitments, and apply numerous improvements and optimizations to achieve all the above properties. We provide detailed proofs of security for our new framework and present concrete parameters and benchmarks.
At the -bit security level, for up to parties and supporting signatures, our scheme has KB public keys and KB signatures; while signing requires communication of KB per party. Using the LaBRADOR proof system (Beullens and Seiler, Crypto 2023), this can be further reduced to KB. An optimistic non-interactive version of our scheme requires only KB communication per party
Unified Approach to UOV-like Multivariate Signature Schemes
Get PDFThis article develops a unified framework for analyzing and enhancing a family of multivariate signature schemes based on UOV. We conduct a comparative study of three recent UOV-like schemes—QR-UOV, MAYO, and SNOVA—and identify a common design principle: employing tensor product constructions to enlarge the dimension of the oil subspace. Building on this perspective, we propose a new multivariate signature scheme called TSUOV that synthesizes these insights to provide improved key and signature sizes without compromising security