Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Consensus in the Known Participation Model with Byzantine Failures and Sleepy Replicas
Get PDFWe study consensus in the known participation model with both Byzantine failures and sleepy replicas, where honest replicas may unpredictably fall asleep, and replicas know the minimum number of awake honest replicas. Our main contribution is providing a fine-grained treatment of consensus in such a mixed failure model. First, we present a synchronous atomic broadcast protocol with expected latency and best-case latency, where is the bound on network delay and is the actual network delay. Second, in the partially synchronous network (the value of is unknown), we show that one can make a conventional Byzantine fault-tolerant (BFT) protocol tolerate sleepy replicas but has to make the stable storage assumption (where replicas need to store intermediate consensus parameters in stable storage). Finally, in the partially synchronous network but not assuming stable storage, we show several bounds on the relationship between the total number of replicas , the maximum number of Byzantine replicas , and the maximum number of simultaneous sleeping replicas . Using these bounds, we transform HotStuff (PODC\u2719) into a protocol that tolerates sleepy replicas without sacrificing the performance
Fuzzy Extractors are Practical: Cryptographic Strength Key Derivation from the Iris
Get PDFDespite decades of effort, a persistent chasm has existed between the theory and practice of device-level biometric authentication. Theoretical constructions can, in principle, provide biometric authentication with cryptographically secure public enrollment data. However, concrete implementations of these techniques have failed to provide security with real-world parameters. The result is that deployed authentication algorithms rely on data that overtly leaks private information about the biometric; thus systems rely on externalized security measures such as trusted execution environments.
We close this chasm. We introduce a key derivation system with bits of entropy and a true accept rate (TAR) for the iris. Our system advances
1) the feature extraction from the iris and 2) the fuzzy extractor used to derive keys. The fuzzy extractor builds on sample-then-lock (Canetti et al., Journal of Cryptology 2021). We (1) Introduce a new sampling method with a better trade-off between TAR and entropy when features have different quality, (2) Correct Canetti et al.\u27s main security proof, showing the minimum of min-entropy over subsets is the relevant security measure, and (3) Tighten Canetti et al.\u27s concrete analysis, nearly doubling security under reasonable assumptions.
Our final feature extractor incorporates ideas from the new sampling method to produce features optimized for the sample-then-lock construction. The only statistical assumption needed to show security of our system is necessary: the accuracy of min-entropy estimation.
At bits, our quantitative level of security is well above prior work. Simhadri et al. (ISC, 2019) report bits on the iris, but they have a bug in their analysis that reduces their strength. Zhang et al.\u27s (ePrint 2021/1559) system achieves bits on the face but assumes independence between biometrics and the used error-correcting code, an assumption that cannot be easily verified
Client-Efficient Online-Offline Private Information Retrieval
Get PDFPrivate Information Retrieval (PIR) permits clients to query data entries from a public database hosted on untrusted servers while preserving client privacy. Traditional PIR models suffer from high computation and/or bandwidth overhead due to linear database processing for privacy. Recently, Online-Offline PIR (OO-PIR) has been proposed to improve PIR practicality by precomputing query-independent materials to accelerate online access. While state-of-the-art OO-PIR schemes (e.g., S&P’24, CRYPTO’23) successfully reduce online processing cost to sublinear levels, they still impose substantial bandwidth and storage burdens on the client, especially when operating on large databases.
In this paper, we propose Pirex, a new two-server OO-PIR with semi-honest security that offers minimal client inbound bandwidth and storage cost while retaining the sublinear processing efficiency. The Pirex design is simple with most operations are naturally low-cost and streamlined (e.g., XOR, PRF, modular arithmetic). We have fully implemented Pirex and evaluated its real-world performance using commodity hardware. Our results showed that Pirex outperforms existing OO-PIR schemes by at least two orders of magnitude. With a 1 TB database, Pirex takes 55ms to retrieve a 4 KB entry, compared with 9-30s by state-of-the-art. For practical databases with billions of 4 KB entries, Pirex only takes 16 KB of inbound bandwidth, which is up to three orders of magnitude more efficient
Classical Commitments to Quantum States
Get PDFWe define the notion of a classical commitment scheme to quantum states, which allows a quantum prover to compute a classical commitment to a quantum state, and later open each qubit of the state in either the standard or the Hadamard basis. Our notion is a strengthening of the measurement protocol from Mahadev (STOC 2018). We construct such a commitment scheme from the post-quantum Learning With Errors (LWE) assumption, and more generally from any noisy trapdoor claw-free function family that has the distributional strong adaptive hardcore bit property (a property that we define in this work).
Our scheme is succinct in the sense that the running time of the verifier in the commitment phase depends only on the security parameter (independent of the size of the committed state), and its running time in the opening phase grows only with the number of qubits that are being opened (and the security parameter). As a corollary we obtain a classical succinct argument system for QMA under the post-quantum LWE assumption. Previously, this was only known assuming post-quantum secure indistinguishability obfuscation. As an additional corollary we obtain a generic way of converting any X/Z quantum PCP into a succinct argument system under the quantum hardness of LWE
Accumulation without Homomorphism
Get PDFAccumulation schemes are a simple yet powerful primitive that enable highly efficient constructions of incrementally verifiable computation (IVC). Unfortunately, all prior accumulation schemes rely on homomorphic vector commitments whose security is based on public-key assumptions.
It is an interesting open question to construct efficient accumulation schemes that avoid the need for such assumptions.
In this paper, we answer this question affirmatively by constructing an accumulation scheme from *non-homomorphic* vector commitments which can be realized from solely symmetric-key assumptions (e.g. Merkle trees).
We overcome the need for homomorphisms by instead performing spot-checks over error-correcting encodings of the committed vectors.
Unlike prior accumulation schemes, our scheme only supports a bounded number of accumulation steps.
We show that such *bounded-depth* accumulation still suffices to construct proof-carrying data (a generalization of IVC).
We also demonstrate several optimizations to our PCD construction which greatly improve concrete efficiency
Key Exchange with Tight (Full) Forward Secrecy via Key Confirmation
Get PDFWeak forward secrecy (wFS) of authenticated key exchange (AKE) protocols is a passive variant of (full) forward secrecy (FS). A natural mechanism to upgrade from wFS to FS is the use of key confirmation messages which compute a message authentication code (MAC) over the transcript. Unfortunately, Gellert, Gjøsteen, Jacobson and Jager (GGJJ, CRYPTO 2023) show that this mechanism inherently incurs a loss proportional to the number of users, leading to an overall non-tight reduction, even if wFS was established using a tight reduction.
Inspired by GGJJ, we propose a new notion, called one-way verifiable weak forward secrecy (OW-VwFS), and prove that OW-VwFS can be transformed tightly to FS using key confirmation in the random oracle model (ROM). To implement our generic transformation, we show that several tightly wFS AKE protocols additionally satisfy our OW-VwFS notion tightly. We highlight that using the recent lattice-based protocol from Pan, Wagner, and Zeng (CRYPTO 2023) can give us the first lattice-based tightly FS AKE via key confirmation in the classical random oracle model. Besides this, we also obtain a Decisional-Diffie-Hellman-based protocol that is considerably more efficient than the previous ones.
Finally, we lift our study on FS via key confirmation to the quantum random oracle model (QROM). While our security reduction is overall non-tight, it matches the best existing bound for wFS in the QROM (Pan, Wagner, and Zeng, ASIACRYPT 2023), namely, it is square-root- and session-tight. Our analysis is in the multi-challenge setting, and it is more realistic than the single-challenge setting as in Pan et al.
ML-DSA-OSH: An Efficient, Open-Source Hardware Implementation of ML-DSA
Get PDFML-DSA is a post-quantum lattice-based digital signature algorithm (DSA) that the National Institute of Standards and Technology (NIST) recently standardized as FIPS 204. Remarkably, there are only a handful of published hardware designs and no open-source hardware implementations of complete ML-DSA.
In this work, we present an efficient open-source hardware (OSH) design of ML-DSA, based on a Dilithium implementation by Beckwith et al. (FPT 2021). We discuss the required modifications for migrating existing CRYSTALS-Dilithium implementations to match FIPS 204. In addition, we evaluate and compare the performance of our design with the prior art. Through optimized instruction scheduling in the ML-DSA rejection loop, which enables the pre-computation of critical variables, the average signing latency is improved by %. Finally, we extensively discuss potential applications and directions of research, further enabled through ML-DSA-OSH
Hyperion: Private Token Sampling with Homomorphic Encryption
Get PDFA promising direction for enabling private queries to large language models (LLMs) is with homomorphic encryption (HE). An open problem is performing token sampling under HE. In this paper, we introduce Hyperion, an efficient HE algorithm for inverse transform sampling, enabling private token sampling with 1 comparison depth, amortized comparisons, and rotations. We implement our approach and demonstrate that it samples tokens in 0.14 seconds for 32k tokens ( per token) on GPU, achieving a latency improvement over prior work
LAKE: Lattice-Code Accelerated Kyber Encapsulation
Get PDFThe standardization of CRYSTALS-Kyber (ML-KEM) by NIST represents a milestone in post-quantum security, yet its substantial communication overhead remains a critical bottleneck for resource-constrained environments. This paper introduces LAKE (Lattice-Code Accelerated Kyber Encapsulation), a novel cryptographic framework that symbiotically integrates coding theory into the Module-LWE structure. Unlike previous concatenation approaches, LAKE embeds density-optimized Construction-A lattices derived from Polar codes directly into the public matrix generation. This structural innovation yields a 15–25% reduction in ciphertext size while simultaneously improving the Decryption Failure Rate (DFR) from to , leveraging innate coding gains to suppress noise. We provide a rigorous reduction of LAKE\u27s IND-CCA2 security to the hardness of the Structured Module-LWE problem. Although LAKE introduces a modest 8–15% computational overhead, it optimizes the critical Compute-for-Bandwidth trade-off, exploiting the asymmetry between low-cost local processing and high-cost transmission. Consequently, LAKE significantly enhances deployment viability in high-latency, energy-sensitive domains such as Satellite Communications (SatCom), Narrowband-IoT (NB-IoT), and tactical edge networks, where transmission efficiency is the dominant performance metric
On the representation of self-orthogonal codes and applications to cryptography
Get PDFThe hull of a linear code is the intersection between the code and its dual.
When the hull is equal to the code (i.e., the code is contained in the dual), the code is called self-orthogonal (or weakly self-dual); if, moreover, the code is equal to its dual, then we speak of a self-dual code.
For problems such as the Permutation Equivalence Problem (PEP) and (special instances of) the Lattice Isomorphism Problem (LIP) over -ary lattices, codes with a sufficiently large hull provide hard-to-solve instances.
In this paper we describe a technique to compress the representation of a self-orthogonal code.
Namely, we propose an efficient compression (and decompression) technique that allows representing the generator matrix of a self-orthogonal code with slightly more than finite field elements.
The rationale consists in exploiting the relationships deriving from self-orthogonality to reconstruct part of the generator matrix entries from the others, thus reducing the amount of entries one needs to uniquely represent the code.
For instance, for self-dual codes, this almost halves the amount of finite field elements required to represent the code.
We first present a basic version of our algorithm and show that it runs in polynomial time and, moreover, its communication cost asymptotically approaches the lower bound set by Shannon\u27s source coding theorem.
Then, we provide an improved version which reduces both the size of the representation and the time complexity, essentially making the representation technique as costly as Gaussian elimination.
As concrete applications, we show that our technique can be used to reduce the public key size in cryptosystems based on PEP such as LESS and SPECK (achieving approximately a 50% reduction in the public key size), as well as in the Updatable Public Key Encryption Scheme recently proposed by Albrecht, Benčina and Lai, which is based on LIP