IACR Communications in Cryptology
Not a member yet
283 research outputs found
Sort by
Efficient Methods for Simultaneous Homomorphic Inversion
Get PDF Efficient implementation of some privacy-preserving algorithms and applications rely on efficient implementation of homomorphic inversion. For example, a recently proposed homomorphic image filtering algorithm and the privacy-preserving body mass index (BMI) calculations repetitively use homomorphic inversion. In this paper, inspired by Montgomery\u27s trick to perform simultaneous plaintext inversion, we tackle the simultaneous homomorphic inversion problem to compute s inverses simultaneously over ciphertexts. The advantage of Montgomery\u27s trick for plaintext arithmetic is well-known. We first observe that the advantage can quickly vanish when homomorphic encryption is employed because of the increased depth of the circuits. Therefore, we propose three algorithms (Montgomery\u27s trick and two other variants) that reduce the number of homomorphic inversions from s to 1 and that offer different levels of trade-offs between the number of multiplications and the circuit depth. We provide a theoretical complexity analysis of our algorithms and implement them using the CKKS scheme in the OpenFHE library. Our experiments show that, for some cases, the run time of homomorphic s-inversion can be improved up to 35 percent while in some other cases, regular inversion seems to outperform Montgomery-based inversion algorithms. </p
Tighter Concrete Security for the Simplest OT
Get PDFThe Chou-Orlandi batch oblivious transfer (OT) protocol is a particularly attractive OT protocol that bridges the gap between practical efficiency and strong security guarantees and is especially notable due to its simplicity. The security analysis provided by Chou and Orlandi bases the security of their protocol on the hardness of the computational Diffie-Hellman (CDH) problem in prime-order groups. Concretely, in groups in which no better-than-generic algorithms are known for the CDH problem, their security analysis yields that an attacker running in time and issuing random-oracle queries breaks the security of their protocol with probability at most , where is the bit-length of the group\u27s order. This concrete bound, however, is somewhat insufficient for 256-bit groups (e.g., for , it does not provide any guarantee already for and ).In this work, we establish a tighter concrete security bound for the Chou-Orlandi protocol. First, we introduce the list square Diffie-Hellman problem and present a tight reduction from the security of the protocol to the hardness of solving the list square Diffie-Hellman problem. That is, we completely shift the task of analyzing the concrete security of the protocol to that of analyzing the concrete hardness of the list square Diffie-Hellman problem. Second, we reduce the hardness of the list square Diffie-Hellman problem to that of the decisional Diffie-Hellman (DDH) problem without incurring a multiplicative loss. Our key observation is that although CDH and DDH have the same assumed concrete hardness, relying on the hardness of DDH enables our reduction to efficiently test the correctness of the solutions it produces.Concretely, in groups in which no better-than-generic algorithms are known for the DDH problem, our analysis yields that an attacker running in time and issuing random-oracle queries breaks the security of the Chou-Orlandi protocol with probability at most (i.e., we eliminate the above multiplicative term). We prove our results within the standard real-vs-ideal framework considering static corruptions by malicious adversaries, and provide a concrete security treatment by accounting for the statistical distance between a real-model execution and an ideal-model execution. </p
Type-2 Generalized Feistel Structures Based on Tweakable Block Ciphers, Reconsidered
Get PDFGeneralized Feistel structures (GFSs) generalize a Feistel structure to have more flexible input length. Among them, Zheng et al. originally introduced type-2 GFS (CRYPTO \u2789) from pseudorandom functions (PRFs). This can be naturally instantiated with tweakable block ciphers (TBCs), which was analyzed by Nakaya and Iwata (ToSC 2022/FSE 2023). For a -line TBC-based construction, they gave a security proof to show that a -round construction is birthday-bound secure against chosen ciphertext attacks (CCAs). In this paper, we first show a counterexample to their proof by presenting a distinguishing attack against the -round construction with queries. The attack implies that the proof by Nakaya and Iwata is incorrect, making the provable security of the construction open. We next show that the -line construction with rounds is provably secure against chosen plaintext attacks (CPAs) up to the birthday bound. The proof is first given for the case , and we then extend this recursively to cover arbitrary values of . Based on the result against CPAs, we also show that the construction is provably secure against CCAs with rounds.</p
Adaptive TDF from any TDF via Pseudorandom-Ciphertext PKE
Get PDFAdaptive trapdoor function (TDF) is TDF that remains secure even if an adversary can get access to the inversion oracle. We present a generic construction of adaptive TDF from the combination of any TDF and pseudorandom-ciphertext public-key encryption (PKE) scheme. As a direct corollary, we can obtain adaptive TDF from any trapdoor permutation (TDP) whose domain is both recognizable and sufficiently dense. In our construction, we can prove that the function\u27s output is indistinguishable from uniform even when an adversary has access to the inversion oracle. </p
Towards Post-Quantum Bitcoin Blockchain using Dilithium Signature
Get PDFBitcoin is one of the famous cryptocurrencies in the world. It is a permissionless blockchain, and all transactions are stored in a public decentralized ledger. In its security design, Bitcoin utilizes various cryptographic primitives, such as hash functions and signature schemes. In the current version of Bitcoin, the Elliptic Curve Digital Signature Algorithm (ECDSA) is employed, which is not considered post-quantum secure due to the Shor\u27s algorithm. Since December 2016, the National Institute of Standards and Technology (NIST) initiated a process to standardize certain post-quantum cryptographic primitives, including key encapsulation mechanisms (KEMs), public key encryption (PKE), and digital signature schemes. Dilithium, a lattice-based digital signature scheme, emerged as one of the winners of this competition and is recently standardized as ML-DSA (FIPS 204). In this work, we analyze the potential replacement of the ECDSA signature, the current signature in Bitcoin, with Dilithium, which is a post-quantum digital signature. This replacement will have a significant impact on many protocols within the Bitcoin ecosystem. The ECDSA algorithms are not only utilized for transaction signing and verification but also in wallet management. Bitcoin operates on a pseudonymous system rather than complete anonymity. To enhance privacy protection, the Bitcoin community has adopted a special type of (hierarchical) deterministic wallet as outlined in Bitcoin Improvement Proposal 32 (BIP32). We have constructed deterministic wallets by first designing DilithiumRK, a signature scheme with rerandomizable keys from Dilithium. Subsequently, we conducted a thorough security analysis and successful implementation of DilithiumRK. </p
Blind zkSNARKs for Private Proof Delegation and Verifiable Computation over Encrypted Data
Get PDFIn this paper, we show for the first time it is practical to privately delegate proof generation of zkSNARKs to a single server for computations of up to 2^20 R1CS constraints. We achieve this by computing zkSNARK proof generation over homomorphic ciphertexts, an approach we call blind zkSNARKs. We formalize the concept of blind proofs, analyze their cryptographic properties and show that the resulting blind zkSNARKs remain sound when compiled using BCS compilation. Our work follows the framework proposed by Garg et al. (Crypto\u2724) and improves the instantiation presented by Aranha et al. (Asiacrypt\u2724), which implements only the FRI subprotocol. By delegating proof generation, we are able to reduce client computation time from 10 minutes to mere seconds, while server computation time remains limited to 20 minutes. We also propose a practical construction for vCOED supporting constraint sizes four orders of magnitude larger than the current state-of-the-art verifiable FHE-based approaches. These results are achieved by optimizing Fractal for the GBFV homomorphic encryption scheme, including a novel method for making homomorphic NTT evaluation packing-friendly by computing it in two dimensions. Furthermore, we make the proofs publicly verifiable by appending a zero-knowledge Proof of Decryption (PoD). We propose a new construction for PoDs optimized for low proof generation time, exploiting modulus and ring switching in GBFV and using the Schwartz-Zippel lemma for proof batching; these techniques might be of independent interest. Finally, we implement the latter protocol in C and report on execution time and proof sizes. </p
FLIP-and-Prove R1CS
Get PDFWe present the first folding framework that achieves sub-linear verification and communication when a single prover must convince a verifier of independent R1CS instances. FLIP (Fold-Inner-Product) folds the instance–witness pairs in only rounds. Built on the homomorphic two-tier commitment of Abe et al. (CRYPTO 2010), FLIP transmits group elements. r-Groth is a commit-and-prove variant of Groth16 that natively handles relaxed R1CS. It retains Groth16’s three-element proof and two pairing checks, requires only a slightly modified (instance-independent) trusted setup, and does not rely on elliptic-curve cycles or foreign-field arithmetic. Combined, FLIP+rGroth replace the extra Groth16 proofs demanded by aggregation schemes and avoid the heavy verifier-in-circuit logic of recursive systems. The total prover work is essentially one Groth16 run plus light folding, while the verifier processes group elements and two pairings.This design is immediately applicable to roll-ups, Proof-of-Space, and other “proving-as-a-service” scenarios where all witnesses reside on a single machine. </p
Towards Practical Multi-Party Hash Chains using Arithmetization-Oriented Primitives With Applications to Threshold Hash-Based Signatures
Get PDFHash chains constitute a fundamental cryptographic primitive with widespread applications in authentication protocols and post-quantum cryptography. Despite their simplicity and quantum-resistant security properties, the deployment of hash chains in distributed settings through secure multi-party computation (MPC) has been demonstrated to be impractical when employing traditional hash functions (i.e., SHA2/SHA3) due to their high number of non-linear gates which lead to heavy computational costs. In this work, we present a comprehensive evaluation of hash chain computations over MPC using arithmetization-oriented (AO) primitives, specifically focusing on the Poseidon2 family of hash functions. We systematically analyze the MPC-friendliness of various Poseidon2 instantiations across different prime fields and parameter choices to minimize both multiplicative depth and preprocessing requirements. We conduct extensive benchmarks using the MP-SPDZ framework across three state-of-the-art MPC protocols under varying network conditions and adversarial models. We further explore practical applications to threshold cryptography, presenting optimized implementations of threshold hash-based signatures that achieve signing times less than 1 second in a 3-party setting for practical parameter sets. Specifically, we demonstrate how structural parallelism in hash-based signatures can be exploited to batch independent hash chains within a single MPC execution, and introduce a time-memory trade-off that enables non-interactive online signature generation through systematic precomputation of all chain intermediates. Our work suggests the practical viability of moderate length AO-based hash chains for MPC applications. </p
Why cut-and-choose quantum state verification cannot be both efficient and secure
Get PDFQuantum state verification plays a vital role in many quantum cryptographic protocols, as it allows using quantum states from an untrusted source. While some progress has been made in this direction, the question of whether the most prevalent type of quantum state verification, namely cut-and-choose verification, can be efficient and secure, is still not answered in full generality. In this work, we show a fundamental limit for quantum state verification for all cut-and-choose approaches used to verify arbitrary quantum states. We provide a no-go result showing that the cut-and-choose techniques cannot lead to quantum state verification protocols that are both efficient and secure. We show this trade-off for stand-alone and composable security, where the scaling of the lower bound for the security parameters renders cut-and-choose quantum state verification effectively unusable. </p
Poseidon(2)b Binary Field Versions of Poseidon/Poseidon2
Get PDFWe present Poseidonb and Poseidon2b, natural variants of Poseidon and Poseidon2, respectively, defined over binary extension fields with a target security level of 128 bits. They are specifically designed to inherit many of the circuit-friendly properties of their prime field version, and to be used together with binary extension field proving systems such as Binius. Benchmarking demonstrates the merits in proof size, proving time, and especially verification time, in comparison to traditional hash functions and other binary circuit-friendly hash functions such as Vision-32b and Anemoi.Due to the close similarity to their prime field counterparts, many existing cryptanalytic results directly carry over to Poseidonb and Poseidon2b. Nevertheless, we revisit the security analysis to incorporate recent advances in cryptanalysis and to account for attack vectors that do not arise in the prime field setting. In particular, we focus on algebraic cryptanalysis and subspace trails, techniques that resulted in attacks on initial versions of Poseidon defined over binary extension fields. Our complexity estimates are based on the ideal degree, now increasingly adopted as a standard measure in algebraic cryptanalysis</p