Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Public-Key Encryption and Injective Trapdoor Functions from LWE with Large Noise Rate
Get PDFThe hardness of the learning with errors (LWE) problem increases as its noise rate grows. However, all existing LWE-based public-key encryption schemes require the noise rate to be no greater than . Breaking through this limitation presents an intriguing challenge.
In this paper, we construct public-key encryption (PKE) schemes based on the sub-exponential hardness of decisional LWE with polynomial modulus and noise rate ranging from to . More concretely, we demonstrate the existence of CPA-secure PKE schemes as long as one of the following three assumptions holds.
(i) hardness of decisional LWE with noise rate .
(ii) -hardness of decisional LWE with noise rate for some constant .
(iii) -hardness of decisional LWE with noise rate for some constant . \end{itemize}
We also construct injective trapdoor function (iTDF) families based on the same hardness assumption as our PKE. To achieve this, we give a generalization of Babai\u27s nearest plane algorithm, which finds a ``common closest lattice point\u27\u27 for a set of vectors.
In addition, we propose a PKE based on the -hardness of constant noise learning parity with noise (LPN) problem. Our construction is simpler than the construction of Yu and Zhang [CRYPTO 2016] while achieving the same security
When Can We Incrementally Prove Computations of Arbitrary Depth?
Get PDFIncrementally Verifiable Computation (IVC) allows one to prove the correctness of a computation of potentially unbounded length (or depth) in an incremental way, while a computationally weak client can efficiently check its correctness in time sublinear in the computation\u27s length. IVC systems are of practical relevance; yet, most existing IVC schemes are only provably secure for constant-depth computations. Arguing their security for computations of polynomial depth relies on heuristic assumptions, raising both theoretical and practical concerns. More generally, it remains unclear whether these schemes are genuinely insecure at superconstant depths or whether our current proof techniques are simply insufficient.
In this work, we delve into the security foundations of incremental proof systems, while at the same time looking for new approaches to prove (or disprove) security at superconstant depths. To this end, we study the relation between the depth of the target computation and IVC security as a question in its own right. Specifically, we ask:
- **How does a proof system\u27s security degrade with depth?** More precisely, if a scheme loses negligible soundness beyond, for example, constant depth, can we at least achieve noticeable (but arbitrarily low) soundness for _some_ superconstant depth? We show that the answer is always negative.
- **Can we prove an IVC secure at depth d = ω(1) if it satisfies a “weak” security property at some larger depth D?** Yes. We uncover a surprising connection between infinitely-often soundness (guaranteed to hold only for some infinite set of parameters) and standard soundness in IVC: a scheme that is infinitely-often sound at depth D achieves standard soundness at some smaller depth d that grows more slowly than D.
- **Depth boosting: If there exists an IVC scheme secure at depth d, does there exist one secure at a greater depth?** Yes. We show a general boosting technique: given an IVC secure at depth d, we can construct one secure at depth D = d^ρ for any function ρ such that d^ρ remains polynomially bounded (ρ may even be superconstant). This allows us to systematically amplify security from modest depths to much greater ones—for example, from constant to polynomial depth—with only a logarithmic overhead.
Our results apply to both deterministic and non-deterministic computations across various soundness notions, including those for incremental functional commitments (IFC), a streaming variant of functional commitments that we introduce
BACON: An Improved Vector Commitment Construction with Applications to Signatures
Get PDFAll-but-one Vector Commitments (AVCs) allow a committed vector to be verified by randomly opening all but one of the committed values. Typically, AVCs are instantiated using Goldwasser-Goldreich-Micali (GGM) trees. Generating these trees comprises a significant computational cost for AVCs due to a large number of hash function calls. Recently, correlated GGM
(cGGM) trees were proposed to halve the number of hash calls and Batched AVCs (BAVCs) using one large GGM tree were integrated to FAEST to form the FAEST version 2 signature scheme, which improves efficiency and reduces the signature size. However, further optimizations on BAVC schemes remain possible.
Inspired by the large-GGM based BAVC and the cGGM tree, this paper proposes BACON, a BAVC with aborts scheme by leveraging a large cGGM tree. BACON executes multiple instances of AVC in a single batch and enables an abort mechanism to probabilistically reduce the commitment size. We prove that BACON is secure under the ideal cipher model and the random oracle model. We also discuss the possible application of the proposed BACON, i.e., FAEST version 2. Furthermore, because the number of hash calls in a large cGGM tree is halved compared with that used in a large GGM tree, theoretically, our BACON is more efficient than the state-of-the-art BAVC scheme
Tempo: ML-KEM to PAKE Compiler Resilient to Timing Attacks
Get PDFRecent KEM-to-PAKE compilers follow the Encrypted Key Exchange (EKE) paradigm (or a variant thereof), where the KEM public key is password-encrypted. While constant-time implementations of KEMs typically avoid secret-dependent branches and memory accesses, this requirement does not usually extend to operations involving the expansion of the public key because public keys are generally assumed to be public. A notable example is , which expands a short seed into a large matrix of polynomial coefficients using rejection sampling---a process that is variable-time but usually does not depend on any secret. However, in PAKE protocols that password-encrypt the compressed public key, this introduces the risk of timing honest parties and mounting an offline dictionary attack against the measurement. This is particularly concerning given the well-known real-world impact of such attacks on PAKE protocols.
In this paper we show two approaches which yield -based PAKEs that resist timing attacks. First, we explore constant-time alternatives to rejection sampling: one that refactors the original algorithm into constant-time style code, whilst preserving its functionality, and two that modify the matrix expansion procedure to abandon rejection sampling and rely instead on large-integer modular arithmetic. All the proposed constant-time algorithms are slower than the current rejection sampling implementations, but they are still reasonably fast in absolute terms. Our conclusion is that adopting constant-time methods will imply both performance penalties and difficulties in using off-the-shelf implementations. Alternatively, we present the first -to-PAKE compiler that mitigates this issue by design: our proposal transmits the seed in the clear, decoupling password-dependent runtime variations from the matrix expansion step. This means that vanilla implementations of can be used as a black-box. Our new protocol builds on the ideas from , which considered splitting the KEM public key, adopts the two-round Feistel approach for password encryption of the non-expandable part of the public key, and leverages the proof techniques from to show that, despite the malleability permitted by the two-round Feistel, it is sufficient for password extraction and protocol simulation in the UC framework
A Generalized Wiener-type Attack Against a Family RSA-like Cryptosystem
No full textLet be the product of two balanced prime numbers and . In 2023, Cotan and Te\c seleanu introduced a family of RSA-like cryptosystems based on the key equation , where . Note that when , we obtain the classical RSA system, while yields the variant proposed by Elkamchouchi, Elshenawy, and Shaban. In this paper, we present a novel attack that combines continued fractions with lattice-based methods for the case . This represents a natural continuation of previous research, which successfully applied similar techniques for
A Security Comment on ``A Security-Enhanced Authentication and Key Agreement Protocol in Smart Grid\u27\u27
Get PDFIn smart grid (SG), key agreement protocols (KAPs) are used as one of the most prevalent means to establish secure data transmission channels between smart meters (SMs) and service providers (SPs). Quite recently, Wu et al. have indicated the vulnerability of Hu et al.\u27s KAP to key compromise impersonation (KCI) attack and proposed a security-enhanced one for secure communications of SMs and SPs in SG. Not to undermine the noteworthy contributions of their work, this comment demonstrates that their own KAP, i.e., Wu et al.\u27s scheme is still vulnerable to KCI attack. Accordingly, we suggest a simple modification to fix the KCI attack issue. Our attack procedure gives some delicate hints to scholars to protect their schemes against the KCI attack in future researches
Optimizing Backend Verification in zk-Rollup Architectures
Get PDFZero-knowledge rollups represent a critical scaling solution for Ethereum, yet their practical deployment faces significant challenges in on-chain verification costs. This paper presents a comprehensive implementation of the Tokamak zkEVM verifier, specifically optimized for the BLS12-381 elliptic curve operations introduced by EIP-2537. We detail the complete verification architecture, from EVM compatible data formatting for pairing checks, multi-scalar multiplication (MSM), and elliptic curve
addition, to the non-interactive protocol design between prover and verifier.
Our key contribution lies in novel optimization techniques that substantially reduce on-chain verification costs. Through strategic polynomial aggregation and scalar factorization, we minimize G1 exponentiations from 40 to 31, achieving gas savings of 108,000 units per verification. Additionally, we introduce a dynamic barycentric interpolation method that replaces computationally intensive FFT operations,
resulting in 92-95% gas reduction for sparse polynomial evaluations. We further present proof aggregation strategies that minimize precompile calls while maintaining the 128-bit security guarantees of BLS12-381.
Our implementation demonstrates that careful protocol design and mathematical optimizations can make zk-rollup verification economically viable on Ethereum. The techniques presented are compatible with the upcoming Pectra upgrade and provide a blueprint for efficient on-chain verification of complex zero-knowledge proofs. Experimental results show total gas costs reduced from 857,200 to 748,450 units for complete proof verification, making our approach practical for high-throughput rollup deployments
Gluon W: A Cryptocurrency Stabilization Protocol
Get PDFThis paper introduces Gluon W, a novel stablecoin protocol inspired by nuclear physics and named after the particle responsible for the stability of matter in the universe. The key idea in Gluon W is to split (as in nuclear fission) an existing volatile asset into its stable and unstable components. These components can be merged back (as in nuclear fusion) into the original asset or transmuted into each other (as in nuclear beta decays). Various stability theorems are proven and their proofs are formally verified using the interactive proof assistant Rocq
A Framework for Witness Encryption from Linearly Verifiable SNARKs and Applications
Get PDFWitness Encryption (WE) is a powerful cryptographic primitive, enabling applications that would otherwise appear infeasible. While general-purpose WE requires strong cryptographic assumptions, and is highly inefficient, recent works have demonstrated that it is possible to design special-purpose WE schemes for targeted applications that can be built from weaker assumptions and can also be concretely efficient. Despite the plethora of constructions in the literature that (implicitly) use witness encryption schemes, there has been no systematic study of special purpose witness encryption schemes.
In this work we make progress towards this goal by designing a modular and extensible framework, which allows us to better understand existing schemes and further enables us to construct new witness encryption schemes. The framework is designed around simple but powerful building blocks that we refer to as gadgets . Gadgets can be thought of as witness encryption schemes for small targeted relations (induced by linearly verifiable arguments) but they can be composed with each other to build larger, more expressive relations that are useful in applications. To highlight the power of our framework we methodically recover past results, improve upon them and even provide new feasibility results.
The first application of our framework is a Registered Attribute-Based Encryption Scheme [Hohenberger et al. (Eurocrypt 23)] with linear sized common reference string (CRS). Numerous Registered Attribute-Based Encryption (R-ABE) constructions have introduced though a black-box R-ABE construction with a linear--in the number of users--CRS has been a persistent open problem, with the state-of-the-art concretely being N^{1.58} (Garg et al. [GLWW, CRYPTO 24]). Empowered by our Witness Encryption framework we provide the first construction of black-box R-ABE with linear-sized CRS. Our construction is based on a novel realization of encryption for DNF formulas that leverages encryption for set membership.
Our second application is a feasibility result for Registered Threshold Encryption (RTE) with succinct ciphertexts. RTE (Branco et al. [ASIACRYPT 2024] is an analogue of the recently introduced Silent Threshold Encryption (Garg et al. [GKPW, CRYPTO 24]) in the Registered Setting. We revisit Registered Threshold Encryption and provide an efficient construction, with constant-sized encryption key and ciphertexts, that makes use of our WE framework
Universally Composable Adaptor Signatures
Get PDFAdaptor signatures extend the functionality of digital signatures by enabling the computation of pre-signatures on messages relative to statements in NP relations.
Pre-signatures are publicly verifiable objects that simultaneously hide and commit to a standard signature on the same message.
Anyone possessing a valid witness for the statement can adapt the pre-signature into a full signature under the underlying signature scheme.
Since adaptor signatures are commonly used as building blocks in larger systems—such as blockchain protocols—it is natural to seek a security definition within the Universal Composability (UC) framework.
A recent attempt by Tairi et al. (CCS\u2723) introduced the first UC functionality for adaptor signatures.
This paper makes both negative and positive contributions. On the negative side, we show that the functionality proposed by Tairi et al. suffers from critical limitations:
- The functionality fails to guarantee extractability and adaptability—the core security properties of adaptor signatures—to higher-level protocols.
- No adaptor signature scheme can realize the functionality.
On the positive side, we propose a new UC functionality that faithfully captures the latest security guarantees of adaptor signatures as formalized via game-based notions by Gerhart et al. (EUROCRYPT\u2724).
- Our functionality guarantees extractability, unique extractability, and pre-signature adaptability in a way that is composable and meaningful for higher-level protocols.
- We show that it is realizable by an enhanced Schnorr-based adaptor signature scheme that we construct. Our construction maintains compatibility with existing infrastructure and is efficient enough for practical deployment, particularly in Bitcoin-like environments