Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Clustering Approach for Higher-Order Deterministic Masking
Get PDFWe present a novel scheme for securely computing the AND operation, without requiring additional online randomness. Building on the work of Nikova et al., our construction extends security beyond the first order while ensuring a uniform output distribution and resilience against glitches up to a specified threshold. This result addresses a longstanding open problem in side-channel-resistant masking schemes.
Our approach is based on a new method of share clustering, inspired by finite affine geometry, enabling simultaneous consideration of both security and uniformity. Furthermore, we demonstrate how this clustering-based framework can be applied to higher-order protection of ciphers like Ascon under a fully deterministic masking regime.
By eliminating the need for online randomness within the protected circuit, our work expands the practical scope of efficient and higher-order masking schemes for resource constraint applications
A Decomposition Approach for Evaluating Security of Masking
Get PDFMasking is a commonly used countermeasure against side-channel attacks, encoding secrets into multiple shares such that each share leaks only partial information. A longstanding question is under what noise conditions masking guarantees security, and how this security scales with the number of shares. While sufficient conditions have been known for binary fields and in high-noise regimes, the borderline and low-noise cases have remained poorly understood.
In this work, we close this gap through a decomposition-based analysis. Our approach reduces leakage in extended fields to binary projections, enabling tight bounds on the adversary’s success rate and yielding an optimal reduction from the noisy leakage model to the random probing model—even in regimes where classical reductions fail. As a central theoretical result, we prove a conjecture of Dziembowski et al. (TCC 2016), showing that for any additive group with largest proper subgroup , masking strictly improves security whenever the leakage is -noisy with .
We additionally demonstrate the practical relevance of our framework for leakage certification and for determining the required masking order under realistic low-noise conditions. Our results unify and sharpen the understanding of noise requirements for masking, advancing both the theoretical foundations and the practical evaluation of side-channel countermeasures
HasteBoots: Proving FHE Bootstrapping in Seconds
Get PDFFully Homomorphic Encryption (FHE) enables computations on encrypted data, ensuring privacy for outsourced computation. However, verifying the integrity of FHE computations remains a significant challenge, especially for bootstrapping, the most computationally intensive operation in FHE. Prior approaches, including zkVM-based solutions and general-purpose SNARKs, suffer from inefficiencies, with proof generation times ranging from several hours to days. In this work, we propose HasteBoots, a succinct argument tailored for FHE operations. By designing customized polynomial interactive oracle proofs and optimized polynomial commitment schemes, HasteBoots achieves proof generation in a few seconds for FHE NAND with bootstrapping, significantly outperforming existing methods. Our approach demonstrates the potential for scalable and efficient verifiable FHE, paving the way for practical, privacy-preserving computations
Inaccessible Entropy for Watermarking Generative Agents
Get PDFIn this work, we construct distortion-free and unforgeable watermarks for language models and generative agents. The watermarked output cannot be forged by a adversary nor removed by the adversary without significantly degrading model output quality. That is, the watermarked output is distortion-free: the watermarking algorithm does not noticeably change the quality of the model output and without the public detection key, no efficient adversary can distinguish output that is watermarked from outputs which are not. The core of the watermarking schemes involve embedding a message and publicly-verifiable digital signature in the generated model output. The message and signature can be extracted during the detection phase and verified by any authorized entity that has a public key. We show that, assuming the standard cryptographic assumption of one-way functions, we can construct distortion-free and unforgeable watermark schemes. Our framework relies on analyzing the inaccessible entropy of the watermarking schemes based on computational entropy notions derived from the existence of one-way functions
ETK: External-Operations TreeKEM and the Security of MLS in RFC 9420
Get PDFThe Messaging Layer Security protocol MLS is standardized in IETF’s RFC 9420 and allows a group of parties to securely establish and evolve group keys even if the servers are malicious. Its core mechanism is based on the TreeKEM protocol, but has gained many additional features and modifications during the development of the MLS standard. Over the last years, several partial security analyses have appeared of incomplete drafts of the protocol. One of the major additions to the TreeKEM design in MLS RFC 9420 (the final version of the standard) are the external operations, i.e., external commits and proposals, which interact deeply with the core TreeKEM protocol. These operations have not been considered in any previous security analysis, leaving their impact on the protocol’s overall security unclear.
In this work, we formalize ETK: External-Operations TreeKEM that includes external commits and proposals. We develop a corresponding ideal functionality and prove that ETK indeed realizes .
Our work is the first cryptographic analysis that considers both the final changes to the standard’s version of TreeKEM as well as external proposals and external commits. Compared to previous works that considered MLS draft versions, our ETK protocol is by far the closest to the final MLS RFC 9420 standard. Our analysis implies that the core of MLS’s TreeKEM variant as defined in RFC 9420 is an ETK protocol that realizes , when used with an SUF-CMA secure signature scheme, such as the IETF variant of Ed25519. We show that contrary to previous claims, MLS does not realize [Crypto2022] when used with signature schemes that only guarantee EUF-CMA, such as ECDSA.
Moreover, we show that the security of the protocol could be further strengthened by adding a functionality to insert PSKs, allowing another form of healing, and give a corresponding construction ETK-PSK and ideal functionality
A note on the genus of the HAWK lattice
Get PDFThe cryptographic scheme and NIST candidate HAWK makes use of a particular module lattice and relies for its security on the assumption that finding module lattice isomorphisms (module LIP) is hard. To support this assumption, we compute the mass of the HAWK lattice, which gives a lower bound on the number of isometry classes of module lattices which cannot be distinguished from the HAWK lattice by an easily computed invariant called the genus. This number turns out to be so large that an attack based on the genus alone seems infeasible
Sublinear Proofs over Polynomial Rings
Get PDFWe propose a sublinear-sized proof system for rank-one constraint satisfaction over polynomial rings (Ring-R1CS), particularly for rings of the form . These rings are widely used in lattice-based constructions,
which underlie many modern post-quantum cryptographic schemes.
Constructing efficient proof systems for arithmetic over these rings is challenged by two key obstacles: (1) Under practical popular choices of and , the ring is not field-like, and thus tools like Schwartz–Zippel lemma cannot apply; (2) when is large, which is common in implementations of lattice-based cryptosystems, the ring is large, causing the proof size suboptimal.
In this paper, we address these two obstacles, enabling more efficient proofs for arithmetics over when is a `lattice-friendly\u27 modulus,
including moduli that support fast NTT computation or power-of-two moduli.
Our primary tool is a novel \emph{ring switching} technique.
The core idea of ring switching is to convert the R1CS over into another R1CS instance over Galois rings, which is field-like and small (with size independent with ).
As (zero-knowledge) proofs have many applications in cryptography, we expect that efficient proof systems for polynomial ring arithmetic could lead to more efficient constructions of advanced primitives from lattice assumptions, such as aggregate signatures, group signatures, verifiable random function, or verifiable fully holomorphic encryption
Finding a polytope: A practical fault attack against Dilithium
Get PDFIn Dilithium, the rejection sampling step is crucial for the proof of security and correctness of the scheme. However, to our knowledge, there is no attack in the literature that takes advantage of an attacker knowing rejected signatures. The aim of this paper is to create a practical black-box attack against Dilithium with a weakened rejection sampling. We succeed in showing that an adversary with enough rejected signatures can recover Dilithium\u27s secret key in less than half an hour on a desktop computer. There is one possible application for this result: by physically preventing one of the rejection sampling tests from happening, we obtain two fault attacks against Dilithium
Experimentally studying path-finding problem between conjugates in supersingular isogeny graphs: Optimizing primes and powers to speed-up cycle finding
Get PDFWe study the problem of finding a path between conjugate supersingular elliptic curves, a sub-routine of cycle finding algorithm in the graph of all supersingular elliptic curves over , connected by isogenies for primes . We prove that asymptotically the most time-efficient way of overviewing the graph to find conjugate paths is seeing steps together, a question posed in Remark 3.5 by Eisentr{\ a}ger \etal~\cite{eisentrager2020}. We see both theoretically and experimentally that selecting optimally speeds up the cycle finding
Efficient Pseudorandom Correlation Generators for Any Finite Field
Get PDFCorrelated randomness lies at the core of efficient modern secure multi-party computation (MPC) protocols. Costs of generating such correlated randomness required for the MPC online phase protocol often constitute a bottleneck in the overall protocol.
A recent paradigm of {\em pseudorandom correlation generator} (PCG) initiated by Boyle et al. (CCS\u2718, Crypto\u2719) offers an appealing solution to this issue. In sketch, each party is given a short PCG seed, which can be locally expanded into long correlated strings, satisfying the target correlation. Among various types of correlations, there is oblivious linear evaluation (OLE), a fundamental and useful primitive for typical MPC protocols on arithmetic circuits.
Towards efficient generating a great amount of OLE, and applications to MPC protocols, we establish the following results:
(i) We propose a novel {\em programmable} PCG construction for OLE over any field . For OLE correlations, we require communication and computation, where is an arbitrary integer . Previous works either have quadratic computation (Boyle et al. Crypto\u2719), or can only support fields of size larger than (Bombar et al. Crypto\u2723).
(ii) We extend the above OLE construction to provide various types of correlations for any finite field. One of the fascinating applications is an efficient PCG for two-party {\em authenticated Boolean multiplication triples}. For authenticated triples, we offer PCGs with seed size of bits. To our best knowledge, such correlation has not been realized with sublinear communication and quasi-linear computation ever before.
(iii) In addition, the \emph{programmability} admits efficient PCGs for multi-party Boolean triples, and thus the first efficient MPC protocol for Boolean circuits with {\em silent} preprocessing. In particular, we show -party Boolean multiplication triples can be generated in -bit communication, while the state-of-the-art FOLEAGE (Asiacrypt\u2724) requires a broadcast channel and takes bits communication.
(iv) Finally, we present efficient PCGs for circuit-dependent preprocessing, matrix multiplications triples, and string OTs etc. Compared to previous works, each has its own right