Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Learning Parity with Quantization: Achieving Full-Rate Encryption by Exploiting Quantization Noise in Code-Based Cryptography
Get PDFThe Learning Parity with Noise (LPN) problem has become a cornerstone for building lightweight, post-quantum secure encryption schemes. Despite its widespread adoption, LPN-based constructions suffer from a fundamental efficiency limitation: the essential noise term that provides security simultaneously requires error correction coding, leading to bandwidth overhead. We introduce a variant of LPN termed Learning Parity with Quantization (LPQ). While maintaining the ``learning from noisy equations\u27\u27 framework, LPQ generates Bernoulli-like noise from code-aided quantization and enables simultaneous security and compression. Formally, the problem challenges adversaries to distinguish the triplet from uniform, where is a vector quantization function based on an code , and serves as a public dither. We establish the hardness of LPQ through a tight reduction from the LPN problem, maintaining equivalent security guarantees. We demonstrate LPQ’s practical efficacy through a full rate (i.e., rate-1) symmetric key encryption scheme, where LPQ combined with an extendable output function (XOF) achieves optimal ciphertext efficiency ()
Computational Attestations of Polynomial Integrity Towards Verifiable Back-Propagation
Get PDFRecent advancements in machine learning accuracy and utility have been driven by the effective combination of sophisticated models with high-performance computational scaling. As the development of large-scale models shifts away from commodity hardware to outsourced computation, it becomes paramount to ensure that the training process is executed with integrity and transparency. This encompasses verifying that adequate computational resources were expended and that the resulting model is accurate, rather than the product of skipped steps or resource-saving shortcuts by the external provider. Building on our previous efforts, which demonstrated the computational feasibility of using this system to argue correctness for differentially-private linear regression, we extend those results to achieve fully provable back-propagation—a cornerstone operation in modern machine learning training. Our system achieves complete zero-knowledge, revealing nothing about the input data during training, and ensures quantum security by relying on no weak cryptographic primitives. Efficiency is substantially increased through the use of a fixed-point decimal representation, reducing the computational overhead typically associated with floating-point arithmetic. Notably, our solution is doubly efficient, achieving a logarithmic-time verifier and a linear-time prover. Implemented entirely in Rust without reliance on external machine learning libraries, and executed within a cryptographically secure virtual machine, this work represents a significant advancement toward verifiable, secure, and efficient outsourced machine learning computations
Tanuki: New Frameworks for (Concurrently Secure) Blind Signatures from Post-Quantum Groups Actions
Get PDFBlind signatures are fundamental cryptographic primitives enabling privacy-preserving authentication and have seen renewed interest in the post-quantum literature.
Existing efficient constructions predominantly rely on Fischlin’s generic paradigm instantiated over lattice assumptions, while blinding techniques for sigma-protocol-based blind signatures remain sparse beyond lattices. Moreover, achieving provable concurrent security under polynomially many sessions has been a longstanding open challenge for this approach in the post-quantum literature as evidenced by the recent attacks in EC’24 and PKC’24.
This work broadens the landscape of post-quantum blind signatures by introducing novel techniques and proposing four frameworks based on general cryptographic group actions, without requiring commutativity. Our constructions admit instantiations under diverse post-quantum assumptions, including CSIDH (isogeny-based), LESS (code-based, NIST round-two), and more. These frameworks offer flexible trade-offs in assumptions (from interactive one-more to the standard inversion problem) and key/signature sizes, and culminate in a construction that achieves security under polynomially many concurrent sessions. This enables the first efficient blind signatures from isogenies and codes with provable concurrent security with 4.5 and 64.7 KB respectively. We also outline several directions for optimization and further instantiations for future work
Oracle-Based Multistep Strategy for Solving Polynomial Systems Over Finite Fields and Algebraic Cryptanalysis of the Aradi Cipher
Get PDFThe multistep solving strategy consists in a divide-and-conquer approach: when a multivariate polynomial system is computationally infeasible to solve directly, one variable is assigned over the elements of the base finite field, and the procedure is recursively applied to the resulting simplified systems. In a previous work by the same authors (among others), this approach proved effective in the algebraic cryptanalysis of the Trivium cipher.
In this paper, we present a new recursive formulation of the corresponding algorithm based on a Depth-First Search strategy, along with a novel complexity analysis leveraging tree structures. We also introduce the notion of an ``oracle function\u27\u27, which is intended to determine whether evaluating a new variable is required to simplify the current polynomial system. This notion allows us to unify all previously proposed variants of the multistep strategy, including the classical hybrid approach, by appropriately selecting the oracle function.
Finally, we employ the multistep solving strategy in the cryptanalysis of the NSA\u27s recently introduced low-latency block cipher Aradi, achieving a first full-round algebraic attack that exposes structural features in its symbolic model
Combining Oblivious Pseudorandom Functions
Get PDFAn oblivious pseudorandom function (OPRF) is an interactive protocol between a client and server, where the client aims to evaluate a keyed pseudorandom function for a key held by the server, without revealing its input. OPRFs are a versatile tool for enhancing privacy, inciting extensive research and standardization efforts in this area. The round-efficient 2Hash-Diffie-Hellman OPRF is widely deployed, but unfortunately, it is prone to quantum attacks. The search for post-quantum alternatives started in 2019 and is currently more disputed, with several candidates on the table.
Given the lack of test of time of post-quantum OPRFs and their underlying cryptographic assumptions, hybridization can help mitigate risks in this interim period. Most preferably, we want to combine existing classical deployments like 2HashDH with post-quantum candidates. However, analogous two-party settings like oblivious transfer, where both parties have security requirements, indicate that combining OPRFs might be trickier than it is for hashing or encryption.
In this paper, we give combiners for OPRFs with minimal overhead over the combined schemes. We also formally prove that ideal\u27\u27 combiners, i.e., ones that do not make additional assumptions on how an underlying OPRF may break, cannot exist. Our constructions avoid this theoretical result by assuming the underlying OPRFs to satisfy certain statistical guarantees. Crucially, these extra conditions are satisfied by both the 2Hash-Diffie-Hellman OPRF and the currently most efficient post-quantum candidates, rendering our results suitable for upgrading existing deployments with quantum-safe guarantees already today
Uniform Black-Box Separations via Non-Malleable Extractors
Get PDFWe construct -non-malleable extractors---which allow an attacker to tamper with a source times---for high min-entropy sources samplable by poly-time hierarchy circuits and for tampering classes corresponding to poly-time hierarchy functions from derandomization-type assumptions.
We then show an application of this new object to ruling out constructions of succinct, non-interactive, arguments (SNARGs) secure against \emph{uniform} adversaries from \emph{uniform} falsifiable assumptions via a class of black-box reductions that has not been previously considered in the literature. This class of black-box reductions allows the reduction to arbitrarily set the \emph{coins}, as well as the input, of the uniform adversary it interacts with.
The class of reductions we consider is restricted in allowing only non-adaptive queries to the adversary
Rubato: Provably Post-Quantum Secure and Batched Asynchronous Randomness Beacon
Get PDFDistributed Randomness Beacons (DRBs) provide secure, unbiased random numbers for decentralized systems, yet face limitations. Many rely on quantum-vulnerable cryptographic assumptions, compromising security in asynchronous networks with unbounded delays. Traditional Verifiable Secret Sharing (VSS)-based DRBs, following a share-consensus-reconstruct paradigm, are often unsuitable for asynchronous settings due to circular dependencies between beacon generation and consensus. We propose Rubato, a post-quantum secure DRB for asynchronous environments, leveraging a lattice-based batched Asynchronous Verifiable Secret Sharing (bAVSS-PQ) scheme. Unlike Hashrand (ACM CCS’24), which uses heuristic random oracles, Rubato achieves provable security in the Standard Model against quantum adversaries. By integrating with DAG-based consensus protocols (e.g., Bullshark), Rubato\u27s novel epoch-staggered architecture resolves circular dependencies, while leveraging DAGs to enhance consensus throughput. The bAVSS-PQ scheme supports batching of secrets with communication complexity , offering a sound foundation for secure randomness in small-to-medium-scale decentralized systems
Adaptively Secure Threshold ElGamal Decryption from DDH
Get PDFThreshold decryption schemes allow a group of decryptors, each holding a private key share, to jointly decrypt ciphertexts. Over the years, numerous threshold decryption schemes have been proposed for applications such as secure data storage, internet auctions, and voting, and recently as a tool to protect against miner-extractable value attacks in blockchain. Despite the importance and popularity of threshold decryption, many natural and practical threshold decryption schemes have only been proven secure against static adversaries.
In this paper, we present two threshold decryption schemes that withstand malicious adaptive corruption. Our first scheme is based on the standard ElGamal encryption scheme and is secure against chosen plaintext attack~(CPA). Our second scheme, based on the chosen ciphertext attack~(CCA) secure Shoup-Gennaro encryption scheme, is also CCA secure. Both of our schemes have non-interactive decryption protocols and comparable efficiency to their static secure counterparts. Building on the technique introduced by Das and Ren (CRYPTO 2024), our threshold ElGamal decryption scheme relies on the hardness of Decisional Diffie-Hellman and the random oracle model
Not in The Prophecies: Practical Attacks on Nostr
Get PDFDistributed social networking services (SNSs) recently received significant attention as an alternative to traditional, centralized SNSs, which have inherent limitations on user privacy and freedom.
We provide the first in-depth security analysis of Nostr, an open-source, distributed SNS protocol developed in 2019 with more than 1.1 million registered users.
We investigate the specification of Nostr and the client implementations and present a number of practical attacks allowing forgeries on various objects, such as encrypted direct messages (DMs), by a malicious user or a malicious server. Even more, we show a confidentiality attack against encrypted DMs by a malicious user exploiting a flaw in the link preview mechanism and the CBC malleability.
Our attacks are due to cryptographic flaws in the protocol specification and client implementation, some of which in combination elevate the forgery attack to a violation of confidentiality.
We verify the practicality of our attacks via Proof-of-Concept implementations and discuss how to mitigate them
INKE: Fast Isogeny-Based PKE using Intermediate Curves
Get PDFPOKE (Point-Based Key Exchange), proposed by Basso and Maino in Eurocrypt 2025, is currently the fastest known isogeny-based public key encryption scheme, combining a SIDH-like protocol with higher-dimensional isogenies. However, the higher-dimensional representation inherently requires discrete logarithm computations, which restricts the use of torsion points to smooth subgroups. As a result, reducing the size of the underlying prime p is challenging, which limits further efficiency gains. In this work, we propose a variant of POKE that retains the higher-dimensional representation but avoids discrete logarithm computations. By replacing the point with the intermediate curve as a shared secret, we are able to reduce the size of the prime p and decrease the number of point evaluations, resulting in faster key generation, encryption, and decryption at the cost of a larger public key. We provide optimized C implementations of both POKE and our variant. Our results demonstrate that the proposed method improves key generation and encryption by 16% and 21%, respectively, and decryption by more than 60%, for all security levels. These results highlight the practicality of our approach, particularly in computation-constrained environments and applications where fast decryption is essential, such as data processing, network communication, and database encryption. In addition, we also provide an IND-CPA security proof in the random oracle model under the hardness assumption of a variant of the Decisional Supersingular Product (DSSP) problem tailored to our setting