International Association
for Cryptologic Research

The Universal Thresholdizer (CRYPTO'18) is a cryptographic scheme that facilitates the transformation of any cryptosystem into a threshold cryptosystem, making it a versatile tool for threshold cryptography. For instance, this primitive enables the black-box construction of a one-round threshold signature scheme based on the Learning with Error problem, as well as a one-round threshold chosen ciphertext attack-secure public key encryption, by being combined with non-threshold schemes.

The compiler is constructed in a modular fashion and includes a compact threshold fully homomorphic encryption, a non-interactive zero-knowledge proof with preprocessing, and a non-interactive commitment. An instantiation of the Universal Thresholdizer can be achieved through the construction of a compact threshold fully homomorphic encryption. Currently, there are two threshold fully homomorphic encryptions based on linear secret sharing, with one using Shamir's secret sharing and the other using the $\{0,1\}$-linear secret sharing scheme ($\{0,1\}$-LSSS). The former fails to achieve compactness as the size of its ciphertext is $O(N\log N)$, where $N$ is the number of participants in the distributed system. Meanwhile, the latter provides compactness, with a ciphertext size of $O(\log N)$, but requires $O(N^{4.3})$ share keys on each party, leading to high communication costs.

In this paper, we propose a communication-efficient Universal Thresholdizer by revisiting the threshold fully homomorphic encryption. Our scheme reduces the number of share keys required on each party to $O(N^{2+o(1)})$ while preserving the ciphertext size of $O(\log N)$. To achieve this, we introduce a new linear secret sharing scheme called TreeSSS, which requires a smaller number of shared keys and satisfies compactness. As a result, the Threshold Fully Homomorphic Encryption underlying our linear secret sharing scheme has fewer shared keys during the setup algorithm and reduced communication costs during the partial decryption algorithm. Moreover, the construction of a Universal Thresholdizer can be achieved through the use of TreeSSS, as it reduces the number of shared keys compared to previous constructions. Additionally, TreeSSS may be of independent interest, as it improves the efficiency in terms of communication costs when used to replace $\{0,1\}$-LSSS.

Fully Homomorphic Encryption enables the evaluation of an arbitrary computable function over encrypted data. Among all such functions, particular interest goes for integer arithmetics. In this paper, we present a bundle of methods for fast arithmetic operations over encrypted data: addition/subtraction, multiplication, and some of their special cases. On top of that, we propose techniques for signum, maximum, and rounding. All methods are specifically tailored for computations with data encrypted with the TFHE scheme (Chillotti et al., Asiacrypt '16) and we mainly focus on parallelization of non-linear homomorphic operations, which are the most expensive ones. This way, evaluation times can be reduced significantly, provided that sufficient parallel resources are available. We implement all presented methods in the Parmesan Library and we provide an experimental evaluation. Compared to integer arithmetics of the Concrete Library, we achieve considerable speedups for all comparable operations. Major speedups are achieved for the multiplication of an encrypted integer by a cleartext one, where we employ special addition-subtraction chains, which save a vast amount of homomorphic operations.

Two fundamental properties of quantum states that quantum information theory explores are pseudorandomness and provability of destruction. We introduce the notion of quantum pseudorandom states with proofs of destruction (PRSPD) that combines both these properties. Like standard pseudorandom states (PRS), these are efficiently generated quantum states that are indistinguishable from random, but they can also be measured to create a classical string. This string is verifiable (given the secret key) and certifies that the state has been destructed.

We show that, similarly to PRS, PRSPD can be constructed from any post-quantum one-way function. As far as the authors are aware, this is the first construction of a family of states that satisfies both pseudorandomness and provability of destruction. We show that many cryptographic applications that were shown based on PRS variants using quantum communication can be based on (variants of) PRSPD using only classical communication. This includes symmetric encryption, message authentication, one-time signatures, commitments, and classically verifiable private quantum coins.

In this paper we introduce a multistep generalization of the guess-and-determine or hybrid strategy for solving a system of multivariate polynomial equations over a finite field. In particular, we propose performing the exhaustive evaluation of a subset of variables stepwise, that is, by incrementing the size of such subset each time that an evaluation leads to a polynomial system which is possibly unfeasible to solve. The decision about which evaluation to extend is based on a preprocessing consisting in computing an incomplete Grobner basis after the current evaluation, which possibly generates linear polynomials that are used to eliminate further variables. If the number of remaining variables in the system is deemed still too high, the evaluation is extended and the preprocessing is iterated. Otherwise, we solve the system by a Grobner basis computation.

Having in mind cryptanalytic applications, we present an implementation of this strategy in an algorithm called MultiSolve which is designed for polynomial systems having at most one solution. We prove explicit formulas for its complexity which are based on probability distributions that can be easily estimated by performing the proposed preprocessing on a testset of evaluations for different subsets of variables. We prove that an optimal complexity of MultiSolve is achieved by using a full multistep strategy with a maximum number of steps and in turn the classical guess-and-determine strategy, which essentially is a strategy consisting of a single step, is the worst choice. Finally, we extensively study the behaviour of MultiSolve when performing an algebraic attack on the well-known stream cipher Trivium.

This paper explores the design space of vector-optimized polynomial multiplications in the lattice-based key-encapsulation mechanisms NTRU and NTRU Prime. Since NTRU and NTRU Prime do not support straightforward applications of number– theoretic transforms, the state-of-the-art vector code either resorted to Toom–Cook, or introduced various techniques for coefficient ring extensions. All these techniques lead to a large number of small-degree polynomial multiplications, which is the bottleneck in our experiments. For NTRU Prime, we show how to reduce the number of small-degree polynomial multiplications to nearly 1/4 times compared to the previous vectorized code with the same functionality. Our transformations are based on careful choices of FFTs, including Good–Thomas, Rader’s, Schönhage’s, and Bruun’s FFTs. For NTRU, we show how to deploy Toom-5 with 3-bit losses. Furthermore, we show that the Toeplitz matrix–vector product naturally translates into efficient implementations with vector-by-scalar multiplication instructions which do not appear in all prior vector-optimized implementations. We choose the ARM Cortex-A72 CPU which implements the Armv8-A architecture for experiments, because of its wide uses in smartphones, and also the Neon vector instruction set implementing vector-by-scalar multiplications that do not appear in most other vector instruction sets like Intel’s AVX2. Even for platforms without vector-by-scalar multiplications, we expect significant improvements compared to the state of the art, since our transformations reduce the number of multiplication instructions by a large margin. Compared to the state-of-the-art optimized implementations, we achieve 2.18× and 6.7× faster polynomial multiplications for NTRU and NTRU Prime, respectively. For full schemes, we additionally vectorize the polynomial inversions, sorting network, and encoding/decoding subroutines in NTRU and NTRU Prime. For ntruhps2048677, we achieve 7.67×, 2.48×, and 1.77× faster key generation, encapsulation, and de- capsulation, respectively. For ntrulpr761, we achieve 3×, 2.87×, and 3.25× faster key generation, encapsulation, and decapsulation, respectively. For sntrup761, there are no previously optimized implementations and we significantly outperform the reference implementation.

We present an optimized constant-time implementation of the MAYO signature scheme on ARMv7-M. MAYO is a novel multivariate proposal based on the trapdoor function of the Unbalanced Oil and Vinegar scheme. Our implementation builds on existing techniques for UOV-based schemes and introduces a new approach for evaluating the polar forms of quadratic maps. We modify MAYO's original parameters to achieve greater benefits from the proposed optimizations, resulting in slightly larger keys and shorter signatures for the same level of security. We evaluate the optimized implementation with the new parameters on the STM32H753ZIT6 microcontroller and measure its performance for the signing and verification procedures. At NIST security level I, signing requires approximately 43M cycles, and verification requires approximately 6M cycles. Both are 2.6 times faster than the results obtained from the original parameters.

Assume that we have a group $G$ of known order $q$, in which we want to solve discrete logarithms (dlogs). In 1994, Maurer showed how to compute dlogs in $G$ in poly time given a Diffie-Hellman (DH) oracle in $G$, and an auxiliary elliptic curve $\hat E(\mathbb{F}_q)$ of smooth order. The problem of Maurer's reduction of solving dlogs via DH oracles is that no efficient algorithm for constructing such a smooth auxiliary curve is known. Thus, the implications of Maurer's approach to real-world applications remained widely unclear.

In this work, we explicitly construct smooth auxiliary curves for a dozen of mostly used, standardized elliptic curves of bit-sizes in the range $[204,256]$, including e.g., NIST P-256, Curve25519, SM2 and GOST R34.10. For all these curves we construct a corresponding cyclic auxiliary curve $\hat E(\mathbb{F}_q)$, whose order is $39$-bit smooth, i.e., its largest factor is of bit-length at most $39$ bits.

This in turn allows us to compute for all divisors of the order of $\hat E(\mathbb{F}_q)$ exhaustively a codebook for all discrete logarithms. As a consequence, dlogs on $\hat E(\mathbb{F}_q)$ can efficiently be computed in a matter of seconds. Our resulting codebook sizes are less than 29 TByte, and fit on our hard disk.

We also construct auxiliary curves for NIST P-384 and NIST P-521 with a $65$-bit and $110$-bit smooth order.

Further, we provide an efficient implementation of Maurer's reduction from the dlog computation in $G$ with order $q$ to the dlog computation on its auxiliary curve $\hat E(\mathbb{F}_q)$. Let us provide a flavor of our results, e.g., when $G$ is the NIST P-256 group, the results for other curves are similar. With the help of our codebook for the auxiliary curve $\hat E(\mathbb{F}_q)$, and less than 24,000 calls to a DH oracle in $G$ (that we simulate), we can solve discrete logarithms on NIST P-256 in around 30 secs.

From a security perspective, our results show that for current elliptic curve standards the difficulty of solving DH is practically tightly related to the difficulty of computing dlogs. Namely, unless dlogs are easy to compute on these curves $G$, we provide a very concrete security guarantee that DH in $G$ must also be hard.

From a cryptanalytic perspective, our results show a way to efficiently solve discrete logarithms in the presence of a DH oracle. Thus, if practical implementations unintentionally provide a DH oracle, dlog computations actually become surprisingly easy.

We present a general compiler to add the publicly verifiable deletion property for various cryptographic primitives including public key encryption, attribute-based encryption, and quantum fully homomorphic encryption. Our compiler only uses one-way functions, or more generally hard quantum planted problems for NP, which are implied by one-way functions. It relies on minimal assumptions and enables us to add the publicly verifiable deletion property with no additional assumption for the above primitives. Previously, such a compiler needs additional assumptions such as injective trapdoor one-way functions or pseudorandom group actions [Bartusek-Khurana-Poremba, ePrint:2023/370]. Technically, we upgrade an existing compiler for privately verifiable deletion [Bartusek-Khurana, ePrint:2022/1178] to achieve publicly verifiable deletion by using digital signatures.

POSEIDON is a hash function proposed by Grassi et al. in the USENIX Security ’21 conference. Due to its impressive efficiency and low arithmetic complexity it has garnered the attention of designers of integrity-proof systems such as SNARKS, STARKS, and Bulletproofs. In this work, we show some caveats in Poseidon’s security argument. Most notably, we extend on previous work by Sauer and quantify the rate at which the degree of regularity increases as a function of full and partial rounds. We observe that this degree grows slower than originally assumed, suggesting that there are cases where the recommended number of rounds is insufficient to meet claimed security. The findings presented in this paper are asymptotic in nature and do not affect all parameter sets equally. As a proof of concept, we present a full attack for an instance at the 1024-bit security level. We present two more parameter sets at the 512- and 384-bit security levels where the original security argument does not hold, but for which we were not able to demonstrate a full attack due to other aspects of the design. We were not able to find parameter sets in the 128- and 256-bit levels that are vulnerable

We are proud to announce the winners of the 2023 IACR Test-of-Time Award for Eurocrypt. The IACR Test-of-Time Award honors papers published at the 3 IACR flagship conferences 15 years ago which have had a lasting impact on the field. This year, we will be announcing the winners for each conference separately.

The Test-of-Time award for Eurocrypt 2008 is awarded to the following two papers:

Efficient Non-interactive Proof Systems for Bilinear Groups, by Jens Groth and Amit Sahai, for providing efficient Groth-Sahai proofs that have given rise to many applications including succinct non-interactive arguments.

On the Indifferentiability of the Sponge Construction, by Guido Bertoni, Joan Daemen, Michael Peeters and Gilles Van Assche, for introducing the Sponge construction that is deployed in world-wide standards such as SHA-3 and ASCON.

For more information, see https://www.iacr.org/testoftime.

Congratulations to all winners!

We present new protocols for *Asynchronous Verifiable Secret Sharing* for Shamir (i.e., threshold $t

Gadget decomposition is widely used in lattice based cryptography, especially homomorphic encryption (HE) to keep the noise growth slow. If it is randomized following a subgaussian distribution, it is called subgaussian (gadget) decomposition which guarantees that we can bound the noise contained in ciphertexts by its variance. This gives tighter and cleaner noise bound in average case, instead of the use of its norm. Even though there are few attempts to build efficient such algorithms, most of them are still not practical enough to be applied to homomorphic encryption schemes due to somewhat high overhead compared to the deterministic decomposition. Furthermore, there has been no detailed analysis of existing works. Therefore, HE schemes use the deterministic decomposition algorithm and rely on a Heuristic assumption that every output element follows a subgaussian distribution independently.

In this work, we introduce a new practical subgaussian gadget decomposition algorithm which has the least overhead (less than 14\%) among existing works for certain parameter sets, by combining two previous works. In other words, we bring an existing technique based on an uniform distribution to a simpler and faster design (PKC' 22) to exploit parallel computation, which allows to skip expensive parts due to pre-computation, resulting in even simpler and faster algorithm. When the modulus is large (over 100-bit), our algorithm is not always faster than the other similar work. Therefore, we give a detailed comparison, even for large modulus, with all the competitive algorithms for applications to choose the best algorithm for their choice of parameters.

Anonymous message delivery, as in private communication and privacy-preserving blockchain applications, ought to protect recipient metadata: a message should not be inadvertently linkable to its destination. But in this case, how can messages be delivered to each recipient, without every recipient scanning all the messages? Recent work constructed Oblivious Message Retrieval (OMR) protocols that outsource this job to untrusted servers in a privacy-preserving manner.

We consider the case of group messaging, where each message may have multiple recipients (e.g., in a group chat or blockchain transaction). A direct use of prior OMR protocols in the group setting increases the servers' work linearly in the group size, rendering it prohibitively costly for large groups.

We thus devise new protocols where the servers' cost grows very slowly with the group size, while recipients' cost is low and independent of the group size. Our approach uses Fully Homomorphic Encryption and other lattice-based techniques, building on and improving on prior work. The efficient handling of groups is attained by encoding multiple recipient-specific clues into a single polynomial or multilinear function that can be efficiently evaluated under FHE, and via preprocessing and amortization techniques.

We formally study several variants of Group Oblivious Message Retrieval (GOMR), and describe corresponding GOMR protocols.

Our implementation and benchmarks show, for parameters of interest, cost reductions of orders of magnitude compared to prior schemes. For example, the servers' cost is $3.36 per million messages scanned, where each message may address up to 15 recipients.

Recent work on dynamic structured and searchable symmetric encryption has focused on achieving the notion of forward-privacy. This is mainly motivated by the claim that forward-privacy protects against adaptive file injection attacks (Zhang, Katz, Papamanthou, Usenix Security, 2016). In this work, we revisit the notion of forward-privacy in several respects. First, we observe that forward-privacy does not necessarily guarantee security against adaptive file injection attacks if a scheme reveals other leakage patterns like the query equality. We then propose a notion of security called correlation security which generalizes forward privacy. We then show how correlation security can be used to formally define security against different kinds of injection attacks. We then propose the first injection-secure multi-map encryption encryption scheme and use it as a building block to design the first injection-secure searchable symmetric encryption (SSE) scheme; which solves one of the biggest open problems in the field. Towards achieving this, we also propose a new fully-dynamic volume-hiding multi-map encryption scheme which may be of independent interest.

Implementation of Fully Homomorphic Encryption (FHE) is challenging. Especially when considering hardware acceleration, the major performance bottleneck is data transfer. Here we propose an algebraic framework called Heterogenous Lattice Graph (HLG) to build and process computing graphs in Residue Number System (RNS), which is the basis of high performance implementation of mainstream FHE algorithms.

There are three main design goals for HLG framework: • Design a dedicated IR (HLG IR) for RNS system, here splitting and combination of data placeholders has practical implications in an algebraic sense. Existing IRs cannot efficiently support these operations. • Lower the technical barriers for both crypto researchers and hardware engineers by decoupling front-end cryptographic algorithms from the back-end hardware platforms. The algorithms and solutions built on HLG framework can be written once and run everywhere. Researchers and engineers don’t need to understand each other. • Try to reduce the cost of data transfer between CPU and GPU/FPGA/dedicated hardware, by providing the intermediate representation (IR) of the computing graph for hardware compute engine, which allows task scheduling without help from CPU.

We have implemented CKKS algorithm based on HLG framework, together with a compute engine for multiple CPU cores. Experiment shows that we can outperform SEAL v3 Library in several use cases in multi-threading scenarios.

The early registration period of PKC 2023 has been extended until April 19th, with the reservation deadline for the hotel room block extended until April 17th.

More information here: https://pkc.iacr.org/2023/

This report addresses the development of a pseudo random bit generator (PRBG) for constraint silicon devices. NIST.SP800-22 "Statistical test suite for Pseudo Random Generators" suggests a suite of tests that can confirm or deny the randomness of a given bit sequence. However, although providing a “pass / fail” criteria for the property of randomness of an arbitrary sequence, it is hard to get from the NIST suite the sense for the “level of randomness” for a given sequence, a measure that is sometimes required for the development process of PRBG. This post suggests a tool that can measure randomness, and therefore allows gradual changes in the PRBG algorithm, that helps trading power / time / area constraints versus quantifiable measure of the resulting randomness.

Keywords: Binomial distribution, commutative distribution function (CDF), PRBG, Bernoulli density

Garbled circuits are a fundamental cryptographic primitive that allows two or more parties to securely evaluate an arbitrary Boolean circuit without revealing any information beyond the output using a constant number of communication rounds. Garbled circuits have been introduced by Yao (FOCS’86) and generalized to the multi-party setting by Beaver, Micali and Rogaway (STOC’90). Since then, several works have improved their efficiency by providing different garbling schemes and several implementations exist. Starting with the seminal Fairplay compiler (USENIX Security’04), several implementation frameworks decoupled the task of compiling the function to be evaluated into a Boolean circuit from the engine that securely evaluates that circuit, e.g., using a secure two-party computation protocol based on garbled circuits. In this paper, we show that this decoupling of circuit generation and evaluation allows a subtle attack on several prominent garbling schemes. It occurs when violating the implicit assumption on the circuit that gates have different input wires which is most often not explicitly specified in the respective papers. The affected garbling schemes use separate calls to a deterministic encryption function for the left and right input wire of a gate to derive pseudo-random encryption pads that are XORed together. When a circuit contains a gate where the left and right input wire are the same, these two per-wire encryption pads cancel out and we demonstrate that this can result in a complete break of privacy. We show how the vulnerable garbling schemes can be fixed easily.

In this paper, we explore the feasibility of reliable and private communication in dynamic networks, where in each round the adversary can choose which direct peer-to-peer links are available in the network graph, under the sole condition that the graph is k-connected at each round (for some k).

We show that reliable communication is possible in such a dynamic network if and only if k > 2t. We also show that if k = cn > 2t for a constant c, we can achieve reliable communication with polynomial round and communication complexity.

For unconditionally private communication, we show that for a passive adversary, k > t is sufficient (and clearly necessary). For an active adversary, we show that k > 2t is sufficient for statistical security (and clearly necessary), while k > 3t is sufficient for perfect security. We conjecture that, in contrast to the static case, k > 2t is not enough for perfect security, and we give evidence that the conjecture is true.

Once we have reliable and private communication between each pair of parties, we can emulate a complete network with secure channels, and we can use known protocols to do secure computation.

It is a long-standing open problem whether the Minimum Circuit Size Problem ($\mathrm{MCSP}$) and related meta-complexity problems are NP-complete. Even for the rare cases where the NP-hardness of meta-complexity problems are known, we only know very weak hardness of approximation.

In this work, we prove NP-hardness of approximating meta-complexity with nearly-optimal approximation gaps. Our key idea is to use *cryptographic constructions* in our reductions, where the security of the cryptographic construction implies the correctness of the reduction. We present both conditional and unconditional hardness of approximation results as follows.

$\bullet$ Assuming subexponentially-secure witness encryption exists, we prove essentially optimal NP-hardness of approximating conditional time-bounded Kolmogorov complexity ($\mathrm{K}^t(x \mid y)$) in the regime where $t \gg |y|$. Previously, the best hardness of approximation known was a $|x|^{1/ \mathrm{poly}(\log \log |x|)}$ factor and only in the sublinear regime ($t \ll |y|$). $\bullet$ Unconditionally, we show near-optimal NP-hardness of approximation for the Minimum Oracle Circuit Size Problem (MOCSP), where Yes instances have circuit complexity at most $2^{\varepsilon n}$, and No instances are essentially as hard as random truth tables. Our reduction builds on a witness encryption construction proposed by Garg, Gentry, Sahai, and Waters (STOC'13). Previously, it was unknown whether it is NP-hard to distinguish between oracle circuit complexity $s$ versus $10s\log N$. $\bullet$ Finally, we define a "multi-valued" version of $\mathrm{MCSP}$, called $\mathrm{mvMCSP}$, and show that w.p. $1$ over a random oracle $O$, $\mathrm{mvMCSP}^O$ is NP-hard to approximate under quasi-polynomial-time reductions with $O$ oracle access. Intriguingly, this result follows almost directly from the security of Micali's CS proofs (Micali, SICOMP'00).

In conclusion, we give three results convincingly demonstrating the power of cryptographic techniques in proving NP-hardness of approximating meta-complexity.