Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Lookup-Table Evaluation over Key-Homomorphic Encodings and KP-ABE for Nonlinear Operations
Get PDFLattice-based key-homomorphic encodings introduced by Boneh et al.~(Eurocrypt\u2714)---known as BGG+ encodings---underpin many primitives, including key-policy attribute-based encryption (KP-ABE). Many applications beyond KP-ABE require simulating the homomorphic evaluation of FHE ciphertexts over BGG+ encodings, which involves nonlinear operations on integers of magnitude up to the ciphertext modulus . However, due to noise growth incurred by multiplication, the encodable integers must be kept small, typically bits, thereby forcing nonlinear operations to be simulated by Boolean circuits and incurring a circuit-size blow-up polynomial in . Apart from resorting to costly bootstrapping for BGG+ encodings, no method is known to beat this baseline.
We propose a method to evaluate lookup tables~(LUTs) over BGG+ encodings that operates directly on base- digit representations for , with noise growth independent of the magnitudes of the encoded integers. Consequently, this replaces the factor in the circuit-size blow-up with , yielding a reduction in evaluation time by a factor polynomial in . We obtain: (i) small-integer arithmetic with base- outputs in constant size; (ii) modulo- multiplication with circuit size quadratic in ; and (iii) homomorphic ciphertext multiplication in the Gentry--Sahai--Waters FHE scheme~(Crypto\u2713) with circuit size approximately cubic in . As an application, we build a KP-ABE scheme that is selectively secure under the Ring-LWE assumption and compatible with our LUT evaluation method. This reduces decryption cost by a factor polynomial in at the expense of a polynomial-in- increase in decryption-key generation cost and decryption-key size, which is an attractive trade-off because decryption is invoked far more frequently than key generation in ABE applications
Just How Secure is SRP, Really?
Get PDFAn asymmetric Password-Authenticated Key Exchange (aPAKE) protocol allows a client and a server to agree upon a cryptographic key, with the only information shared in advance being a low-entropy password (memorized by the client) and a corresponding password file (stored in the server). The standard security definition for aPAKE is in the Universally Composable (UC) framework. Since aPAKE does not rely on a PKI, such protocols have received much attention in recent years due to their potential of replacing the traditional “password-over-TLS” approach for client-server authentication on the Internet.
One of the only two aPAKE protocols currently deployed in practice is Secure Remote Password (SRP) (Wu, NDSS 1998), which is used by millions of users on the Internet. A formal security analysis of SRP has long been elusive; the only security proof to date is the one by Dayanikli and Lehmann (CSF 2024) which is in a (somewhat non-standard) variant of UC called UC with angels. This framework allows the simulator access to an additional oracle that solves certain hard cryptographic problems.
In this work, we present a comprehensive new analysis of SRP, and clarify a number of ambiguities about its security:
1. We formally prove that the SRP is UC-secure if and only if one computational problem in the field is hard and one decisional problem is easy. As the decisional problem is likely hard in the field, this strongly suggests that SRP is not UC-secure and hence justifies the usage of UC with angels in the security analysis;
2. On the other hand, we show that the “angel” given to the simulator in the Dayanikli–Lehmann analysis is stronger than necessary, and can be replaced by a weaker oracle;
3. Finally, we prove that UC-with-angels-security is still stronger than the game-based security for aPAKE, i.e., SRP is still game-based secure under some reasonable assumptions.
Overall, we pinpoint the exact conditions under which SRP can be proven secure, reducing its security to a number of underlying hardness problems. Along the way we also identify and bridge multiple gaps in the Dayanikli–Lehmann analysis — most notably, the concrete security bound — and apply novel proof techniques that might find application in other contexts
Succinct Line-Point Zero-Knowledge Arguments from Homomorphic Secret Sharing
Get PDFDittmer, Ishai and Ostrovsky (ITC\u2721) proposed {\em line-point zero-knowledge proof} (LPZK), a simple ``commit-and-prove\u27\u27 system, motivated by practical protocols for compressing correlated pseudorandomness used in secure multiparty computation (MPC). Typically, LPZK admits concretely efficient ZK protocols with a streaming, linear time prover, {\em but a linear size proof}. A natural question raised in the context is how far can we go in minimizing the proof size, while maintaining the prover efficiency. Though a recent work by Lin, Xing and Yao (ASIACRYPT\u2724) gives an interactive LPZK with a sublinear proof size , it is still far from being {\em succinct}, where are referred to as input size, circuit depth, and circuit size, respectively.
In this work, we beat the proof size barrier and propose {\em succinct LPZK arguments}, by distilling techniques from orthogonal studies on homomorphic secret sharing and succinct garbling.
Specifically, under variants of group/lattice-based assumptions, we show the followings:
i) There exist succinct LPZK arguments with common reference string (CRS) size , proof size , prover time , verification time , and negligible soundness error, where both the prover and the verifier executions and be run in a streaming fashion.
ii) The above proof size can be further optimized to , at the cost of a larger CRS size , and prover time increased to .
In general, our succinct LPZK arguments pave a new way for building designated-verifier zero-knowledge succinct non-interactive arguments of knowledge (dv-zkSNARKs), and new interesting features (e.g., streaming, constant sized proof with CRS size not proportional to the circuit size) are obtained for the first time along the way
Credential Revocation Assisted by a Covertly Corrupted Server
Get PDFEuropean Digital Identity (EUDI) Wallet aims to provide end users with a way to get attested credentials from issuers, and present them to different relying parties. An important property mentioned in the regulatory frameworks is the possibility to revoke a previously issued credential. While it is possible to issue a short-lived credential, in some cases it may be inconvenient, and a separate revocation service which allows to revoke a credential at any time may be necessary.
In this work, we propose a full end-to-end description of a generic credential revocation system, which technically relies on a single server and secure transmission channels between parties. We prove security of the proposed revocation functionality in the universal composability model, and estimate its efficiency based on a proof-of-concept implementation
Lattice-Based zk-SNARKs with Hybrid Verification Technique
Get PDFZero-knowledge succinct arguments of knowledge (zkSNARK) provide short privacy-preserving proofs for general NP problems. Public verifiability of zkSNARK protocols is a desirable property, where the proof can be verified by anyone once generated. Designated-verifier zero-knowledge is useful when it is necessary that only one or a few individuals should have access to the verification result. All zkSNARK schemes are either fully publicly verifiable or can be verified by a designated verifier with a secret verification key.
In this work, we propose a new notion of a hybrid verification mechanism. Here, the prover generates a proof that can be verified by a designated verifier. For this proof, the designated verifier can generate auxiliary information with its secret key. The combination of this proof and the auxiliary information allows any public verifier to verify the proof without any other information. We also introduce necessary security notions and mechanisms to identify a cheating designated verifier or the prover. Our hybrid verification zkSNARK construction is based on module lattices and adapts the zkSNARK construction by Ishai et al. (CCS 2021). In this construction, the designated verifier is required only once after proof generation to create the publicly verifiable proof. Our construction achieves a small constant-size proof and fast verification time, which is linear in the statement size
Ajax: Fast Threshold Fully Homomorphic Encryption without Noise Flooding
Get PDFThreshold fully homomorphic encryption (ThFHE) enables multiple parties to perform arbitrary computation over encrypted data, while the secret key is distributed across the parties. The main task of designing ThFHE is to construct threshold key-generation and decryption protocols for FHE schemes. Among existing FHE schemes, FHEW-like cryptosystems enjoy the advantage of fast bootstrapping and small parameters.
However, known ThFHE solutions use the ``noise-flooding\u27\u27 technique to realize threshold decryption, which requires either large parameters or switching to a scheme with large parameters via bootstrapping, leading to a slow decryption process. Besides, for key generation, existing ThFHE schemes either assume a generic MPC or a trusted setup, or incur noise growth that is linear in the number of parties.
In this paper, we propose a fast ThFHE scheme Ajax, by designing threshold key-generation and decryption protocols for FHEW-like cryptosystems. In particular, for threshold decryption, we eliminate the need for noise flooding, and instead present a new technique called ``mask-then-open\u27\u27 based on random double sharings over different rings, while keeping the advantage of small parameters.
For threshold key generation, we show a simple approach to reduce the noise growth from times to times in the honest-majority setting, where at most t=\floor{(n-1)/2} parties are corrupted. Our end-to-end implementation reports the running time 17.6 and 0.9 (resp., 91.9 and 4.4 ) of generating a set of keys and decrypting a single ciphertext respectively, for (resp., ) parties under the network of 1 Gbps bandwidth and 1 ping time. Compared to the state-of-the-art implementation, our protocol improves the end-to-end performance of the threshold decryption protocol by a factor of at least across different network latencies from to . Our approaches can also be applied in other types of FHE schemes like BGV, BFV, and CKKS.
In addition, we show how to strengthen our protocols in order to guarantee the security against malicious adversaries
Proofs of No Intrusion
Get PDFA central challenge in data security is not just preventing theft, but detecting whether it has occurred. Classically, this is impossible because a perfect copy leaves no evidence. Quantum mechanics, on the other hand, forbids general duplication, opening up new possibilities.
We introduce Proofs of No Intrusion, which enable a classical client to remotely test whether a quantum server has been hacked and the client\u27s data stolen. Crucially, the test does not destroy the data being tested, avoiding the need to store a backup elsewhere. We define and construct proofs of no intrusion for ciphertexts assuming fully homomorphic encryption. Additionally, we show how to equip several constructions of unclonable primitives with proofs of non-intrusion, such as unclonable decryption keys and signature tokens. Conceptually, proofs of non-intrusion can be defined for essentially any unclonable primitive.
At the heart of our techniques is a new method for non-destructively testing coset states with classical communication. It can be viewed as a non-destructive proof of knowledge of a measurement result of the coset state
Solving one-sided linear systems over symmetrized and supertropical semirings
Get PDFOne-sided linear systems of the form ``\u27\u27 are well-known and extensively studied over the tropical (max-plus) semiring and wide classes of related idempotent semirings. The usual approach is to first find the greatest solution to such system in polynomial time and then to solve a much harder problem of finding all minimal solutions. We develop an extension of this approach to the same systems over two well-known extensions of the tropical semiring: symmetrized and supertropical, and discuss the implications of our findings for the tropical cryptography
DDH-based schemes for multi-party Function Secret Sharing
Get PDFFunction Secret Sharing (FSS) schemes enable sharing efficiently secret functions. Schemes dedicated to point functions, referred to as Distributed Point Functions (DPFs), are the center of FSS literature thanks to their numerous applications including private information retrieval, anonymous communications, and machine learning. While two-party DPFs benefit from schemes with logarithmic key sizes, multi-party DPFs have seen limited advancements: key sizes (with , the function domain size) and/or exponential factors in the key size.
We propose a DDH-based technique reducing the key size of existing multi-party schemes. In particular, we build an honest-majority DPF with key size. Our benchmark highlights key sizes up to smaller (on realistic problem sizes) than state-of-the-art schemes. Finally, we extend our technique to schemes supporting comparison functions
Quantum Circuit Implementation and Resource Analysis of AIM2
Get PDFIn this paper, we propose a quantum circuit implementation of AIM2. We apply optimization to reduce the circuit depth and introduce a method to reuse qubits by performing inverse operations in parallel.
For all AIM2 variants (AIM2-I, AIM2-III, AIM2-V), we design quantum circuits for , the linear layer, , and feed-forward. We confirm that the operation dominates the overall cost.
Compared to the previous version of AIM, AIM2 requires significantly more quantum resources since it introduces before the linear layer.
Based on the proposed circuits, we estimate the cost of Grover\u27s algorithm for key search and compare it with the NIST estimates for AES. As a result, AIM2-I, AIM2-III, and AIM2-V achieve the post-quantum security levels of Level-1, Level-3, and Level-5, respectively