IACR Communications in Cryptology
Not a member yet
283 research outputs found
Sort by
HiSE: Hierarchical (Threshold) Symmetric-key Encryption
Full text link Threshold symmetric encryption (TSE) [DiSE, CCS 2018], provides a practical decentralized solution for symmetric encryption by distributing the secret-key at all times, thus avoiding a single point of attack or failure. TSE was further enhanced [ATSE, CCS 2021] by an amortization which enables a “more privileged” client to encrypt bulk records by interacting only once with the key servers, while decryption must be performed individually for each record, potentially by a “less privileged” client. However, a typical enterprise generates data once and queries it several times for various data analysis; i.e., enterprise workloads are often decryption heavy! ATSE does not meet the bar for this setting because of linear interaction / computation (in the number of records to be decrypted) – our experiments show that ATSE provides a sub-par throughput of a few hundred records/sec.Our work starts with an observation that a large and useful class of analytics queries access some time-windowed sequence of database records (e.g. log entries or user transactions). Can we offer faster decryption for such access patterns, without compromising the benefits of prior schemes?To that end, we build a new TSE scheme that allows for both encryption and decryption with flexible granularity, in that a client\u27s interactions with the key servers is at most logarithmic in the number of records. Our idea is to employ a binary-tree structure, where one interaction is needed to decrypt all ciphertexts in a sub-tree, and thus only log-many for any arbitrary sub-sequence. Our scheme incorporates ideas from binary-tree encryption by Canetti et al. [Eurocrypt 2003] and carefully combines that with Merkle-tree commitments. We show that our scheme satisfies all essential TSE properties, such as correctness, privacy and authenticity for our notion, formalized as hierarchical threshold symmetric-key encryption (HiSE). Our analysis relies on a well-known XDH assumption and a new assumption, that we call -masked BDDH, over asymmetric bilinear pairing in the programmable random oracle model. We also show that our new assumption holds in the generic group model.Our extensive implementation shows 10-65 improvement in latency and throughput over ATSE. HiSE can decrypt over 6K records/sec on server-grade hardware, but the logarithmic overhead in encryption (not decryption) only lets us encrypt up to 3K records/sec ( 4.5 slowdown) and incurs roughly 500 bytes of ciphertext expansion per record – while reducing this penalty is an important future work, we believe HiSE offers an acceptable practical trade-off in practice. </p
OverModRaise: Reducing Modulus Consumption of CKKS Bootstrapping
Full text linkThe Cheon-Kim-Kim-Song (CKKS) homomorphic encryption scheme is widely adopted for securely evaluating circuits over real numbers, such as those arising in privacy-preserving machine learning (PPML), because it efficiently supports approximate floating-point arithmetic of messages. A CKKS ciphertext has a finite level, which corresponds to the budget for how many multiplicative operations can be applied. Once these levels are consumed, the ciphertext must be refreshed through a bootstrapping procedure to restore its capacity for further computation. The CKKS bootstrapping procedure consists of four main steps: 1) ModRaise, which raises the ciphertext coefficient modulus; 2) C2S, which homomorphically evaluates the inverse-DFT (iDFT) to enable further operations on the ciphertext coefficients; 3) EvalMod, which homomorphically removes the unintended coefficients introduced by ModRaise and shifted to the message side by C2S; and 4) S2C, which homomorphically evaluates the DFT to map the ciphertext back from the iDFT domain. However, these bootstrapping procedures also consume a significant number of levels, leaving fewer levels after each bootstrapping.In this work, we introduce three techniques—OverModRaise1, OverModRaise2, and Tuple-C2S/S2C—that target reductions in the modulus consumption of C2S/S2C among the CKKS bootstrapping procedures, without introducing substantial overhead or compromising security. By combining these techniques, our implementation demonstrates at most 41% throughput improvement compared to the state-of-the-art bootstrapping. </p
A Note on Output Length of One-Way State Generators and EFIs
Full text linkWe study the output length of one-way state generators (OWSGs), their weaker variants, and EFIs.Standard OWSGs: Recently, Cavalar et al. (Quantum 9, 1679 (2025)) give OWSGs with m-qubit outputs for any m = ω(log λ), where λ is the security parameter, and conjecture that there do not exist OWSGs with O(log log λ)-qubit outputs. We prove their conjecture in a stronger manner by showing that there do not exist OWSGs with O(log λ)-qubit outputs. This means that their construction is optimal in terms of output length.Inverse-polynomial-advantage OWSGs: Let ε-OWSGs be a parameterized variant of OWSGs where a quantum polynomial-time adversary\u27s advantage is at most ε. For any constant c ∈ N, we construct λ^(-c)-OWSGs with ((c+1) log λ + O(1))-qubit outputs assuming the existence of OWFs. We show that this is almost tight by proving that there do not exist λ^(-c)-OWSGs with at most (c log λ – 2)-qubit outputs.Constant-advantage OWSGs: For any constant ε > 0, we construct ε-OWSGs with O(log log λ)-qubit outputs assuming the existence of subexponentially secure OWFs. We show that this is almost tight by proving that there do not exist Θ(1)-OWSGs with ((log log λ)/2 + O(1))-qubit outputs.Weak OWSGs: We refer to (1 – 1/poly(λ))-OWSGs as weak OWSGs. We construct weak OWSGs with m-qubit outputs for any m = ω(1) assuming the existence of exponentially secure OWFs with linear expansion. We show that this is tight by proving that there do not exist weak OWSGs with O(1)-qubit outputs.EFIs: We show that there do not exist O(log λ)-qubit EFIs. We show that this is tight by proving that there exist m(λ)-qubit EFIs for any m(λ) = ω(log λ) assuming the existence of exponentially secure pseudorandom generators. </p
zkMaP: Zero-Knowledge Succinct Non-Interactive Matrix Multiplication Proofs
Full text linkWe introduce zkMaP (Zero-Knowledge Succinct Non-Interactive Matrix Multiplication Proofs), a novel non-interactive zero-knowledge proof system for verifying matrix multiplication with significant improvements in efficiency and scalability. Our protocol leverages KZG polynomial commitments and an innovative inner-product reduction technique to reduce the verification of n x n matrix multiplication to a single pairing equation, thereby enabling constant-time verification independent of the matrix size. In particular, zkMaP requires only two pairing operations and produces proofs as small as 320 bytes, yielding a 96 percent reduction in proof size compared to prior schemes. Furthermore, the prover\u27s computational complexity follows the state-of-the-art at O(n^2), with experimental results demonstrating that proofs for 1024 x 1024 matrices can be generated in approximately 12.21 seconds, offering a 16.14x speedup over previous methods. Our implementation also exhibits better memory efficiency, using only 24.58 MB of prover-side RAM for 1024 x 1024 matrices, and supports scalable batch processing, achieving per-proof generation times of 46.79 milliseconds for 1024 instances while maintaining a constant verification time of 3.6 ms. </p
Leaky LWE: Learning with Errors with Semi-Adaptive Secret- and Error-Leakage
Full text link The Learning with Errors (LWE) problem asks to distinguish noisy samples s^T A + e^T mod q from uniformly random values given the random matrix A. In this work, we show that a variant called Leaky LWE, where the distinguisher receives additionally noisy leakages (s^T, e^T) L + f^T of the LWE secret s and error e for low-norm matrix L chosen adaptively by the distinguisher after seeing A, is not easier than the standard LWE of the same dimensions up to polynomial losses in the noise level and the modulus. More generally, we show that the Leaky LWE problem is hard even if the public matrix A is structured and/or hinted and if the non-leaky parts of the secret and error do not follow Gaussian distributions, as long as the corresponding LWE problem without leakage is hard. Our reduction from LWE to Leaky LWE unifies and extends prior results on the Error-Leakage LWE problem [Döttling-Kolonelos-Lai-Lin-Malavolta-Rahimi, EUROCRYPT\u2723], where L only acts on the error e and the Hint-MLWE problem [Kim-Lee-Seo-Song, CRYPTO\u2723], where L is restricted to concatenations of random Gaussian scalar matrices not controlled by the distinguisher. Previously, the Hint-MLWE and Error-Leakage LWE assumptions were used as computational replacements of the statistical noise flooding technique in security proofs which led to improved parameters in lattice-based cryptographic constructions such as zero-knowledge proofs, threshold signatures and registration-based encryption. We provide lemmas which abstract out such computational arguments based on Leaky LWE. </p
Keyed-Verification Anonymous Credentials with Highly Efficient Partial Disclosure
Full text link An anonymous credential (AC) system with partial disclosure allows users to prove possession of a credential issued by an issuer while selectively disclosing a subset of their attributes to a verifier in a privacy-preserving manner. In keyed-verification AC (KVAC) systems, the issuer and verifier share a secret key. Existing KVAC schemes rely on computationally expensive zero-knowledge proofs during credential presentation, with the presentation size growing linearly with the number of attributes. In this work, we propose two highly efficient KVAC constructions that eliminate the need for zero-knowledge proofs during the credential presentation and achieve constant-size presentations. Our first construction adapts the approach of Fuchsbauer, Hanser and Slamanig (JoC\u2719), which achieved constant-size credential presentation in a publicly verifiable setting using their proposed structure-preserving signatures on equivalence classes (SPS-EQ) and set commitment schemes, to the KVAC setting. We introduce structure-preserving message authentication codes on equivalence classes (SP-MAC-EQ) and designated-verifier set commitments (DVSC), resulting in a KVAC system with constant-size credentials (2 group elements) and presentations (5 group elements). To avoid the bilinear groups and pairing operations required by SP-MAC-EQ, our second construction uses a homomorphic MAC with a simplified DVSC. While this sacrifices constant-size credentials (n+2 group elements, where n is the number of attributes), it retains constant-size presentations (2 group elements) in a pairingless setting. We formally prove the security of both constructions and provide open-source implementation results demonstrating their practicality. We extensively benchmarked our KVAC protocols and, additionally, bechmarked the efficiency of our SP-MAC-EQ scheme against the original SPS-EQ scheme, showcasing significant performance improvements. </p
Revisiting Discrete Logarithm Reductions
Full text link A reduction showing that the hardness of the discrete logarithm (DL) assumption implies the hardness of the computational Diffie-Hellman (CDH) assumption, given a suitable auxiliary input as advice, was first presented by den Boer [Crypto, 88]. We consider groups of prime order p, where p-1 is somewhat smooth (say, every prime q that divides p-1 is less than ). Several practically relevant groups satisfy this condition. We present a concretely efficient version of den Boer\u27s reduction for such groups. In particular, among practically relevant groups, we obtain the most efficient and tightest reduction in the literature for BLS12-381, showing that DL = CDH. By generalizing den Boer\u27s reduction, we show that in these groups the n-Power DL (n-PDL) assumption implies n-Diffie-Hellman Exponent (n-DHE) assumption, where n is polynomial in the security parameter. On the negative side, we show there is no generic reduction, which could demonstrate that n-PDL implies the n-Generalized Diffie-Hellman Exponent (n-GDHE) assumption. This is in stark contrast with the algebraic group model, where this implication holds. </p
HAWK: Having Automorphisms Weakens Key
Full text link The search rank-2 module Lattice Isomorphism Problem (smLIP), over a cyclotomic ring of degree a power of two, can be reduced to an instance of the Lattice Isomorphism Problem (LIP) of at most half the rank if an adversary knows a nontrivial automorphism of the underlying integer lattice. Knowledge of such a nontrivial automorphism speeds up the key recovery attack on HAWK at least quadratically, which would halve the number of security bits. Luo et al. (ASIACRYPT 2024) recently found an automorphism that breaks omSVP, the initial underlying hardness assumption of HAWK. The team of HAWK amended the definition of omSVP to include this so-called symplectic automorphism in their submission to the second round of NIST\u27s standardization of additional signatures. This work provides confidence in the soundness of this updated definition, assuming smLIP is hard, since there are plausibly no more trivial automorphisms that allow winning the omSVP game easily. Although this work does not affect the security of HAWK, it opens up a new attack avenue involving the automorphism group that may be theoretically interesting on its own. </p
Practical Batch Proofs of Exponentiation
Full text linkA Proof of Exponentiation (PoE) allows a prover to efficiently convince a verifier that in some group of unknown order. PoEs are the basis for practical constructions of Verifiable Delay Functions (VDFs), which, in turn, are important for various higher-level protocols in distributed computing. In applications such as distributed consensus, many PoEs are generated regularly, motivating protocols for secure aggregation of batches of statements into a few statements to improve the efficiency for both parties. Rotem (TCC 2021) recently presented two such generic batch PoEs.In this work, we introduce two batch PoEs that outperform both proposals of Rotem and we evaluate their practicality. First, we show that the two batch PoEs of Rotem can be combined to improve the overall efficiency by at least a factor of two. Second, we revisit the work of Bellare, Garay and Rabin (EUROCRYPT 1998) on batch verification of digital signatures and show that, under the low order assumption, their bucket test can be securely adapted to the setting of groups of unknown order. The resulting batch PoE quickly outperforms the state of the art in the expected number of group multiplications with the growing number of instances, and it decreases the cost of batching by an order of magnitude already for hundreds of thousands of instances. Importantly, it is the first batch PoE that significantly decreases both the proof size and complexity of verification.Our experimental evaluations show that even a non-optimized implementation achieves such improvements, which would match the demands of real-life systems requiring large-scale PoE processing. Our proof techniques are conceptually similar to Rotem. However, we give an improved analysis of the application of the low order assumption towards secure batching of PoE instances, resulting in a tight reduction, which is important when setting the security parameter in practice.Finally, we discuss a new application of batch PoEs towards efficient remote attestation of parallel computational power. We show that, under a natural generalization of the hardness of iterated squaring in groups of unknown order, any batch PoE can be used to construct a secure protocol for testing the parallelism of the prover with optimal communication complexity independent of the claimed number of available processors. </p
Efficient Weak Key Recovery for QC-MDPC Codes like BIKE
Full text linkCode-based cryptography, originally proposed nearly 50 years ago, has been highly successful in the NIST standardization process for post-quantum key encapsulation mechanisms. With HQC and BIKE, two of the considered candidates are based on the hardness of quasi-cyclic codes. One important attack first presented by Guo et al. at ASIACRYPT 2016 that targets moderately dense codes is the distance spectrum recovery attack. The attack makes use of the correlation between the error patterns causing a decryption failure and the sparse private key. However, for random keys, decoding failures are highly unlikely and the attack thus only succeeds with negligible probability. Another line of cryptanalysis on quasi-cyclic code-based cryptosystems has focused on weak keys with higher DFR, which invalidate the provable security guarantees. However, so far the distance spectrum of such weak keys have never been analyzed, leaving a gap in the cryptanalysis research of modern code-based cryptosystems. In this work, we show that Type I weak keys feature a new distance spectrum not analyzed before that cannot be attacked with known key recovery techniques proposed by Guo et al. Instead, we introduce a new key recovery algorithm that, considering the reaction attacker setting, exceeds the state-of-the-art recovery methods by exploiting the distance spectrum of the new weak keys with high probability. When considering a natural side-channel occurring in real-world implementations of the decoding phase, our attack can be enhanced even further. </p