IACR Communications in Cryptology
Not a member yet
283 research outputs found
Sort by
Cycles of supersingular elliptic curves for pairing-based proof systems
Full text link We give new constructions of cycles of pairing-friendly elliptic curves with a view towards unbounded recursive pairing-based proof systems. Unlike the only known prior cycle of elliptic curves - the ordinary MNT cycle - our construction uses elliptic curves that are supersingular. The drawback of our approach is that the supersingular cycles are defined over extension fields (quadratic extensions in the optimal case), which makes elements and computations in less compact and efficient than those in the MNT cycle. On the other hand, the supersingular cycles in this paper offer a key advantage over their MNT counterpart: every instance of our infinite family of supersingular curves can be efficiently constructed via Bröker\u27s algorithm, whereas it is only feasible to construct a relatively small, bounded number of MNT instances via the CM method. In other words, while both constructions give infinite families of pairing-friendly curves in theory, only the supersingular construction gives rise to infinite numbers of cycles that can be realised in practice. Supersingular cycles offer benefits that are relevant in the context of recursive pairing-based proof systems. They afford flexibility in the choices of underlying finite fields; one can choose primes for which the underlying field arithmetic is efficient and for which is divisible by a large power of 2. Or, as we study in detail, using supersingular cycles unlocks the possibility of connecting the cycle with other pairing-friendly elliptic curves that are defined over much smaller finite fields, where proof system arithmetic is much more efficient. Indeed, constructing these so-called lollipops of pairing-friendly curves was the motivating problem (posed by researchers back in 2019) that inspired the present work.</p
Side-Channel Attacks on VOLEitH Signature Schemes Breaking Masked FAEST
Full text link The ongoing transition to post-quantum cryptography has highlighted the need for digital signature schemes offering diverse performance and security trade-offs. Among the candidates in NIST’s ongoing post-quantum signature standardisation process is FAEST, a scheme built upon the Vector Oblivious Linear Evaluation in-the-Head (VOLEitH) paradigm introduced in 2023. VOLEitH enables efficient zero-knowledge proofs with competitive signature sizes under conservative assumptions, allowing FAEST to rely primarily on the one-wayness of the Advanced Encryption Standard (AES). Despite their promising efficiency, VOLEitH-based signature schemes have remained relatively unexplored from a physical security perspective. In this paper, we present the first side-channel security evaluation. Specifically, we demonstrate two single-trace, deep learning-assisted power analysis attacks on the masked implementation of FAEST by Aranha, Degn, Eilath, Nielsen, and Scholl. These attacks exploit leakage from witness bits and VOLE tag computations, recovering the full secret key with success probability above 0.99 from a single signature on an ARM Cortex-M4 processor. We further analyse how the VOLEitH construction enables profiling of VOLE tags without knowledge of the secret key and how even partial leakage of these tags compromises security. Finally, we discuss practical countermeasures to mitigate such leakages and strengthen the physical resilience of VOLEitH-based signature implementations. </p
A Note on Obfuscation-Based Attacks on Private-Coin Evasive LWE
Full text linkThe evasive learning with errors (evasive LWE) assumption is a new assumption recently introduced by Wee [Wee22] and Tsabary [Tsa22] independently, as a significant strengthening of the standard LWE assumption. While the assumption is known to imply various strong primitives including witness encryption [Tsa22, VWW22], the assumption in the most general case (i.e., the private coin variant) is considered quite implausible due to the obfuscation based attack mentioned in [Wee22]. This obfuscation based attack is then later formalized by Vaikuntanathan, Wee, and Wichs [VWW22]. In this note, we revisit their attack and show that the attack actually does not work by showing a concrete counterexample. While various attacks against private-coin evasive LWE are now known, the attack of [VWW22] is the only one that applies in the setting where the sampler is oblivious to the LWE secret, which we call the S-oblivious regime. Therefore, our refutation closes the only known avenue for attacking the assumption in the S-oblivious regime. To complement the above refutation of this attack, we also present a variant of the counterexample assuming the existence of instance-hiding witness encryption. However, our sampler is not S-oblivious, and thus we do not fully recover the attack considered in [VWW22]. Taken together, these results indicate that the security of private-coin evasive LWE in the S-oblivious regime remains open. </p
KLaPoTi
Full text link We construct and implement an efficient post-quantum commutative cryptographic group action based on combining the SCALLOP framework for group actions from isogenies of oriented elliptic curves on one hand with the recent Clapoti method for polynomial-time evaluation of the CM group action on elliptic curves on the other. We take advantage of the very attractive performance of (2^e,2^e)-isogenies between products of elliptic curves in the theta coordinate system. To successfully apply Clapoti in dimension 2, it is required to resolve a particular quadratic diophantine norm equation, for which we employ a slight variant of the KLPT algorithm. Our work marks the first practical instantiation of the CM group action for which both the setup and the online phase can be computed in (heuristic) polynomial time. We also point out that the order of the acting group - equivalently, the size of the set being acted on - is known, and can be chosen (within constraints) during parameter generation, in our construction.</p
Exploring SHA Instructions and Its Application to AES-based Schemes
Full text linkIn this paper, we explore the potential of improving AES-based schemes by integrating SHA instructions alongside AES instructions, starting from the key observation that SHA instructions can be executed in parallel with AES instructions on modern processors. We investigate conditions for parallel execution, the invocation ratio, and overhead of type conversions, and then provide guidelines for efficient SHA instruction usage with AES instructions. Applying these guidelines, we integrate SHA round functions into the AES-based short-input hash functions of Simpira and Areion, resulting in approximately 50% faster performance by achieving security with fewer iterations. Besides, we apply integration of SHA instructions to AES-based AEAD schemes of AEGIS-128L, which supports a 256-bit tag but has recently been shown to fall short of providing full 256-bit forgery security. We demonstrate that hybrid schemes can achieve 256-bit forgery security for AEGIS-128L while preserving performance. </p
An Asymmetric Diffie-Hellman Protocol with Enhanced Efficiency through Parallelization
Full text linkTo ensure secure communication between two parties (Alice and Bob), Public Key Agreement (PKA) algorithms play a crucial role. The Diffie-Hellman (D-H) algorithm, introduced by W. Diffie and M. Hellman in 1976, is the most well-known PKA algorithm, based on exponentiation over a finite field. Over time, various PKA algorithms have been developed based on this original idea—these are referred to as D-H realizations or D-H algorithms. A common issue with D-H realizations is their computational inefficiency, particularly in environments with resource-constrained devices. This inefficiency arises from the high computational complexity of generating public and secret shared keys (SSKs), often resulting in communication delays.In this paper, we propose a modified D-H protocol designed to reduce the computational time required by one party, thereby decreasing the total time needed to establish the SSK in asymmetric environments where Alice and Bob have different computational capabilities. The core of this approach leverages the group homomorphism property of the underlying function to enable parallelization and reduce the complexity of Alice’s computations, together with an asymmetric key agreement structure in which both parties may follow distinct computational rules for public key and SSK generation.We demonstrate that the proposed protocol retains the security properties of the original D-H realizations, preserving the hardness of the discrete logarithm (DL), computational Diffie-Hellman (CDH), and decisional Diffie-Hellman (DDH) problems under an asymmetric setting. We also discuss its applicability to other cryptographic protocols. Experimental results show that the modified protocol significantly improves computational efficiency, particularly by reducing Alice\u27s computational burden through parallel processing. </p
Sequential Indifferentiability of STH and EDM
Full text linkThe notion of indifferentiability was proposed by Maurer et al. to bound the distinguishing advantage of a construction built on a public primitive, from a public random function. In Indocrypt\u2710, Mandal et al. have shown that the sum of two independent permutations is indifferentiable from a public random function up to queries. Later in ACNS\u2715, Mennink and Preneel identified an analytical flaw of Mandal et al\u27s result and revised the security bound to . In Eurocrypt\u2718, Bhattacharya and Nandi have improved their indifferentiable bound to queries, which was again identified as incorrect in the analysis by Gunsing et al. In this paper, we study the indifferentiability of a few other PRF constructions, namely STH and EDM constructions. We will show that neither STH nor STH2 is indifferentiable, which led us to propose a generalized version called gSTH. We have shown that gSTH achieves a tight -bit security bound, where denotes the size of the constants in terms of bits used in the construction. While we show that EDM achieves a tight -bit indifferentiable bound with respect to our proposed simulator, single-keyed EDM is not indifferentiable from a public random function. We would like to mention that all the proofs and the attacks have been done in the sequential indifferentiability model. </p
Modular Reduction in CKKS
Full text linkThe Cheon–Kim–Kim–Song (CKKS) scheme is renowned for its efficiency in encrypted computing over real numbers. However, it lacks an important functionality that most exact schemes have, an efficient modular reduction. This derives from the fundamental difference in encoding structure. The CKKS scheme encodes messages to the least significant bits, while the other schemes encode to the most significant bits (or in an equivalent manner). As a result, CKKS could enjoy an efficient rescaling but lost the ability to modular reduce inherently.Instead of homomorphically approximating the modular reduction function, we suggest to use the inherent modular reduction over . We construct a novel homomorphic modular reduction algorithm using the discrete bootstrapping from Bae et al. [Asiacrypt\u2724] and a new discretization algorithm from modulus switching. One of the key advantages of our modular reduction is that its computational complexity grows sublinearly () as we increase the input range , which is asymptotically better than the state-of-the-art with .We checked our algorithms with concrete experiments. Notably, our modulo 1 function for input range takes only 44.9 seconds with 13.3 bits of (mean) precision, in a single-threaded CPU. Recall that modular reduction over such a large range was almost infeasible in the previous works, as they need to evaluate a polynomial of degree > 2^{20} (or equivalent). As an application of our method, we compared a bit decomposition based on our framework with the state-of-the-art method from Drucker et al. [J.Cryptol\u2724]. Our method is faster while reducing the failure probability by more than two orders of magnitude. </p
Data Matching in Unequal Worlds and Applications to Smart Contracts
Full text link SNARKs enable compact proofs that an NP statement is true and that the prover knows a valid witness. They have become a key building block in modern smart contract applications, including rollups and privacy-focused cryptocurrencies. In the widely used Groth16 framework, however, long statements incur high costs. A common workaround is to pass the statement’s hash to the SNARK and move the statement into the witness. The smart contract then hashes the statement first, and the circuit that is proven additionally checks consistency of the hash and the statement. Unfortunately, virtually any hash function is expensive to call either in a smart contract (in terms of gas) or in the proven circuit (in terms of prover time).We demonstrate a novel solution to this dilemma, which we call hybrid compression. Our method allows us to use two different hash functions—one optimized for the proof circuit, and another optimized for on-chain verification—thereby combining the efficiency advantages of both. We define a clean and simple security property of the two hash functions to which our security reduces in the standard model, namely, joint UHF hardness. We then show the plausibility of this assumption in the random oracle model. Our benchmarks show that it achieves near-optimal performance in both gas usage and prover time. As an example, compressing an 8 KB statement with our approach results in a 10-second prover time and a smart contract spending 270K gas, whereas the existing approaches either need a much longer proof generation (290 seconds for SHA-256 hashing) or a much more expensive contract (5M gas for Poseidon hashing). Along the way, we develop a two-party protocol of independent interest in communication complexity: an efficient deterministic method for checking input equality when the two parties do not share the same hash function. </p
FRIttata: A FRI-based Polynomial Commitment Scheme for Distributed Proof Generation
Full text linkWe present the first horizontally scalable polynomial commitment scheme (PCS) that is both transparent and plausibly post-quantum (PQ) secure. This PCS can be combined with the distributed polynomial interactive oracle proof (PIOP) introduced in Pianist (IEEE S& P 2024), which achieves linear scalability by encoding witnesses using bivariate polynomials. While Pianist and other scalable SNARK systems offer strong performance profiles, they rely on trusted setup ceremonies and cryptographic assumptions that are not PQ secure, e.g., pairing-based primitives. In contrast, we present a bivariate PCS based on FRI, which, when used to compile the Pianist PIOP, achieves a transparent and plausibly PQ alternative. Distributed FRI has a high communication cost. Therefore, we introduce Fold-and-Batch, a customizable technique that applies partial folding locally before performing batched FRI centrally. We formally prove the security of our constructions and provide an implementation for three variants of distributed FRI, accompanied by thorough performance evaluations. Our results show that Fold-and-Batch reduces communication overhead compared to existing distributed FRI approaches, while preserving scalability and maintaining moderate proof sizes. To our knowledge, this is the first horizontally scalable PCS that simultaneously achieves transparency, plausible PQ security, and a tunable tradeoff between efficiency, verifier cost, and communication. </p