International Association
for Cryptologic Research

We describe an algorithm to solve the approximate Shortest Vector Problem for lattices corresponding to ideals of the ring of integers of an arbitrary number field $K$. This algorithm has a pre-processing phase, whose run-time is exponential in $\log |\Delta|$ with $\Delta$ the discriminant of $K$. Importantly, this pre-processing phase depends only on $K$. The pre-processing phase outputs an advice, whose bit-size is no more than the run-time of the query phase. Given this advice, the query phase of the algorithm takes as input any ideal $I$ of the ring of integers, and outputs an element of $I$ which is at most $\exp(\widetilde O((\log |\Delta|)^{\alpha+1}/n))$ times longer than a shortest non-zero element of $I$ (with respect to the Euclidean norm of its canonical embedding). This query phase runs in time and space $\exp(\widetilde O( (\log |\Delta|)^{\max(2/3, 1-2\alpha)}))$ in the classical setting, and $\exp(\widetilde O((\log |\Delta|)^{1-2\alpha}))$ in the quantum setting. The parameter $\alpha$ can be chosen arbitrarily in $[0,1/2]$. Both correctness and cost analyses rely on heuristic assumptions, whose validity is consistent with experiments.

The algorithm builds upon the algorithms from Cramer al. [EUROCRYPT 2016] and Cramer et al. [EUROCRYPT 2017]. It relies on the framework from Buchmann [Séminaire de théorie des nombres 1990], which allows to merge them and to extend their applicability from prime-power cyclotomic fields to all number fields. The cost improvements are obtained by allowing precomputations that depend on the field only.

In this work we continue the study on the round complexity of secure multi-party computation with black-box simulation in the simultaneous broadcast model where all the parties get the output.

In Eurocrypt 2016 Garg at al. show that four rounds are necessary to obtain a secure multi-party computation protocol for any function in the plain model. Many different works have tried to show that, relying on standard assumptions, four rounds are also sufficient for MPC. In Crypto 2017 Ananth et al. and in TCC 2017 Brakerski at al. propose a four-round protocol based on quasi-polynomial time number theoretic assumptions. In Crypto 2018 the two independent works of Badrinarayanan et al. and Halevi at al. show how reach the four-round barrier relying on number theoretic polynomial-time assumptions.

In this work we propose a compiler that takes as input a three-round oblivious transfer protocol, and outputs a four-round MPC protocol. Our compiler is also based on two-round witness indistinguishable proof (zap). We also show how to obtain three-round OT assuming sub-exponentially secure trapdoor permutations and zap. As a corollary we obtain the first four-round MPC protocol that relies on general assumptions. Moreover, given the three-round OT from claw-free trapdoor permutation proposed by Hazay at el. in SCN 2016, we obtain the first four-round MPC protocol that is based on general polynomial-time assumptions.

We construct deterministic public key encryption secure for any constant number of arbitrarily correlated computationally unpredictable messages. Prior works required either random oracles or non-standard knowledge assumptions. In contrast, our constructions are based on the exponential hardness of DDH, which is plausible in elliptic curve groups. Our central tool is a new trapdoored extremely lossy function, which modifies extremely lossy functions by adding a trapdoor.

The Winternitz one-time signature (WOTS) scheme, which can be described using a certain number of so-called ``function chains", plays an important role in the design of both stateless and stateful many-time signature schemes. This work introduces WOTS^GES, a new WOTS type signature scheme in which the need for computing all of the intermediate values of the chains is eliminated. This significantly reduces the number of required operations needed to calculate the algorithms of WOTS^GES. To achieve this results, we have used the concept of ``leveled" multilinear maps which is also referred to as graded encoding schemes. In the context of provable security, we reduce the hardness of graded discrete-logarithm (GDL) problem to the EU-CMA security of WOTS^GES in the standard model.

In this paper we present a new 2-party protocol for secure computation over rings of the form $\mathbb{Z}_{2^k}$. As many recent efficient MPC protocols supporting dishonest majority, our protocol consists of a heavier (input-independent) pre-processing phase and a very efficient online stage. Our offline phase is similar to BeDOZa (Bendlin et al. Eurocrypt 2011) but employs Joye-Libert (JL, Eurocrypt 2013) as underlying homomorphic cryptosystem. JL turns out to be particularly well suited for the ring setting as it naturally supports $\mathbb{Z}_{2^k}$ as underlying message space. Moreover, it enjoys several additional properties (such has valid ciphertext-verifiability and efficiency) that make it a very good fit for MPC in general. As a main technical contribution we show how to take advantage of all these properties (and of more properties that we introduce in this work, such as a ZK proof of correct multiplication) in order to design a two-party protocol that is efficient, fast and easy to implement in practice. Our solution is particularly well suited for relatively large choices of k (e.g. k = 128), but compares favorably with the state of the art solution of SPDZ2k (Cramer et al. Crypto 2018) already for the practically very relevant case of $\mathbb{Z}_{2^{64}}$ .

Traditionally, countermeasures against physical attacks are integrated into the implementation of cryptographic primitives after the algorithms have been designed for achieving a certain level of cryptanalytic security. This picture has been changed by the introduction of PICARO, ZORRO, and FIDES, where efficient protection against Side-Channel Analysis (SCA) attacks has been considered in their design. In this work we present the tweakable block cipher CRAFT: the efficient protection of its implementations against Differential Fault Analysis (DFA) attacks has been one of the main design criteria, while we provide strong bounds for its security in the related-tweak model. Considering the area footprint of round-based hardware implementations, CRAFT outperforms the other lightweight ciphers with the same state and key size. This holds not only for unprotected implementations but also when fault-detection facilities, side-channel protection, and their combination are integrated into the implementation. In addition to supporting a 64-bit tweak, CRAFT has the additional property that the circuit realizing the encryption can support the decryption functionality as well with very little area overhead.

In this paper, a platform named PEIGEN is presented to evaluate security, find efficient software/hardware implementations, and generate cryptographic S-boxes. Continuously developed for decades, S-boxes are constantly evolving in terms of the design criteria for both security requirements and software/hardware performances. PEIGEN is aimed to be a platform covering a comprehensive check-list of design criteria of S-boxes appearing in the literature. To do so, the security requirements are first intensively surveyed, existing tools of S-boxes are then comprehensively compared, and finally our platform PEIGEN is presented. The survey part is aimed to be a systematic reference for the theoretical study of S-boxes. The platform is aimed to be an assistant tool for the experimental study and practical use of S-boxes. PEIGEN not only integrates most of the features in existing tools, but also equips with functionalities to evaluate new security-related properties, improves the efficiency of the search algorithms for optimized implementations in several aspects. With the help of this powerful platform, many interesting observations are made in-between the security notations, as well as on the S-boxes used in the existing symmetric-key cryptographic primitives. PEIGEN will become an open platform and welcomes contributions from all parties to help the community to facilitate the research and use of S-boxes.

Statistical saturation attack takes advantage of a set of plaintext with some bits fixed while the others vary randomly, and then track the evolution of a non-uniform plaintext distribution through the cipher. Previous statistical saturation attacks are all implemented under single-key setting, and there is no public attack models under related-key/tweak setting. In this paper, we propose a new cryptanalytic method which can be seen as related-key/tweak statistical saturation attack by revealing the link between the related-key/tweak statistical saturation distinguishers and KDIB (Key Difference Invariant Bias) / TDIB (Tweak Difference Invariant Bias) ones. KDIB cryptanalysis was proposed by Bogdanov \emph{et al.} at ASIACRYPT'13 and utilizes the property that there can exist linear trails such that their biases are deterministically invariant under key difference. And this method can be easily extended to TDIB distinguishers if the tweak is also alternated. The link between them provides a new and more efficient way to find related-key/tweak statistical saturation distinguishers in ciphers. Thereafter, an automatic searching algorithm for KDIB/TDIB distinguishers is also given in this paper, which can be implemented to find word-level KDIB distinguishers for S-box based key-alternating ciphers. We apply this algorithm to \texttt{QARMA}-64 and give related-tweak statistical saturation attack for 10-round \texttt{QARMA}-64 with outer whitening key. Besides, an 11-round attack on \texttt{QARMA}-128 is also given based on the TDIB technique. Compared with previous public attacks on \texttt{QARMA} including outer whitening key, all attacks presented in this paper are the best ones in terms of the number of rounds.

There are two main ways of performing computation on private data: one method uses linear secret-sharing, in which additions require no communication and multiplications require two secrets to be broadcast; the other method is known as circuit garbling, in which a circuit is somehow randomised by one set of parties and then evaluated by another. There are different advantages and disadvantages to each method in terms of communication and computation complexity. The main disadvantage of secret-sharing-based computation is that many non-linear operations require many rounds of communication. On the other hand, garbled circuit (GC) solutions require only constant rounds. Mixed protocols aim to leverage the advantages of both methods by switching between the two dynamically.

In this work we present the first mixed protocol secure in the presence of a dishonest majority for any number of parties and an active adversary. We call the resulting mixed arithmetic/Boolean circuit a marbled circuit 3 . Our implementation showed that mixing protocols in this way allows us to evaluate a linear Support Vector Machine with 400 times fewer AND gates than a solution using GC alone albeit with twice the preprocessing required using only SPDZ (Damgaard et al., CRYPTO ’12). When evaluating over a WAN network, our online phase is 10 times faster than the plain SPDZ protocol.

Lattice-based cryptography is one of the leading candidates for NIST's post-quantum standardisation effort, providing efficient key encapsulation and signature schemes. Most of these schemes base their hardness on variants of LWE, and thus rely heavily on error samplers to provide necessary uncertainty by obfuscating computations on secret information. Because of this it is a clear and obvious target for side-channel analysis, with numerous types of attacks targeting this component to gain secret-key information. In order to bring potential lattice-based cryptographic standards to practical realisation, it is important to protect these modules from past and future fault and side-channel attacks. This paper proposes countermeasures that exploit the distributions expected from these error samples, that is either Gaussian or binomial, by using statistical tests to verify the samplers are operating properly. The novel countermeasures are designed to protect against all previous fault attacks on error samplers. We optimize hardware implementation of the proposed tests to avoid division and square root calculations, however, the countermeasure we propose is sufficiently generic to be suitable also for software. We measure the impact of these countermeasures on performance and area consumption on a Xilinx Artix-7 FPGA. Our countermeasure achieve promising performance while resulting in a minimal overhead.

Using the idea behind the recently proposed isogeny- and paring-based verifiable delay function (VDF) by De Feo, Masson, Petit and Sanso, we construct an isogeny-based VDF without the use of pairings. Our scheme is a hybrid of time-lock puzzles and (trapdoor) verifiable delay functions. We explain how to realise the proposed VDF on elliptic curves with commutative endomorphism ring, however this construction is not quantum secure. The more interesting, and potentially quantum-secure, non-commutative case is left open.

We study the computational hardness of recovering single bits of the private key in the supersingular isogeny Diffie--Hellman (SIDH) key exchange and similar schemes. Our objective is to give a polynomial-time reduction between the problem of computing the private key in SIDH to the problem of computing any of its bits. The parties in the SIDH protocol work over elliptic curve torsion groups of different order $N$. Our results depend on the parity of $N$. Our main result shows that if $N$ is odd, then each of the top and lower $O(\log\log N)$ bits of the private key is as hard to compute, with any noticeable advantage, as the entire key. A similar, but conditional, result holds for each of the middle bits. This condition can be checked, and heuristically holds almost always. The case of even $N$ is a bit more challenging. We give several results, one of which is similar to the result for an odd $N$, under the assumption that one always succeeds to recover the designated bit. To achieve these results we extend the solution to the chosen-multiplier hidden number problem, for domains of a prime-power order, by studying the Fourier coefficients of single-bit functions over these domains.

In this work, we revisit multi-authority attribute based signatures (MA-ABS), and elaborate on the limitations of the current MA-ABS schemes to provide a hard to achieve (yet very useful) combination of features, i.e., decentralization, periodic usage limitation, dynamic revocation of users and attributes, reliable threshold traceability, and authority hiding. In contrast to previous work, we disallow even the authorities to de-anonymize an ABS, and only allow joint tracing by threshold-many tracing authorities. Moreover, in our solution, the authorities cannot sign on behalf of users. In this context, first we define a useful and practical attribute based signature scheme (versatile ABS or VABS) along with the necessary operations and security games to accomplish our targeted functionalities. Second, we provide the first VABS scheme in a modular design such that any application can utilize a subset of the features endowed by our VABS, while omitting the computation and communication overhead of the features that are not needed. Third, we prove the security of our VABS scheme based on standard assumptions, i.e., Strong RSA, DDH, and SDDHI, in the random oracle model. Fourth, we implement our signature generation and verification algorithms, and show that they are practical (for a VABS with 20 attributes, Sign and Verify times are below 1.2 seconds, and the generated signature size is below 0.5 MB).

There is surprisingly little consensus on the precise role of the generator g in group-based assumptions such as DDH. Some works consider g to be a fixed part of the group description, while others take it to be random. We study this subtle distinction from a number of angles.

- In the generic group model, we demonstrate the plausibility of groups in which random-generator DDH (resp. CDH) is hard but fixed-generator DDH (resp. CDH) is easy. We observe that such groups have interesting cryptographic applications.

- We find that seemingly tight generic lower bounds for the Discrete-Log and CDH problems with preprocessing (Corrigan-Gibbs and Kogan, Eurocrypt 2018) are not tight in the sub-constant success probability regime if the generator is random. We resolve this by proving tight lower bounds for the random generator variants; our results formalize the intuition that using a random generator will reduce the effectiveness of preprocessing attacks.

- We observe that DDH-like assumptions in which exponents are drawn from low-entropy distributions are particularly sensitive to the fixed- vs. random-generator distinction. Most notably, we discover that the Strong Power DDH assumption of Komargodski and Yogev (Komargodski and Yogev, Eurocrypt 2018) used for non-malleable point obfuscation is in fact false precisely because it requires a fixed generator. In response, we formulate an alternative fixed-generator assumption that suffices for a new construction of non-malleable point obfuscation, and we prove the assumption holds in the generic group model. We also give a generic group proof for the security of fixed-generator, low-entropy DDH (Canetti, Crypto 1997).

We define a new UC functionality (DL-extractable commitment scheme) that allows committer to open a commitment to a group element $g^x$; however, the simulator will be able to extract its discrete logarithm $x$. Such functionality is useful in situations where the secrecy of $x$ is important since the knowledge of $x$ enables to break privacy while the simulator needs to know $x$ to be able to simulate the corrupted committer. Based on Fujisaki's UC-secure commitment scheme and the Damgård-Fujisaki integer commitment scheme, we propose an efficient commitment scheme that realizes the new functionality. As another novelty, we construct the new scheme in the weaker RPK (registered public key) model instead of the CRS model used by Fujisaki.

We show, via a non-interactive reduction, that the existence of a secure multi-party computation (MPC) protocol for degree-$2$ functions implies the existence of a protocol with the same round complexity for general functions. Thus showing that when considering the round complexity of MPC, it is sufficient to consider very simple functions.

Our completeness theorem applies in various settings: information theoretic and computational, fully malicious and malicious with various types of aborts. In fact, we give a master theorem from which all individual settings follow as direct corollaries. Our basic transformation does not require any additional assumptions and incurs communication and computation blow-up which is polynomial in the number of players and in $S,2^D$, where $S,D$ are the circuit size and depth of the function to be computed. Using one-way functions as an additional assumption, the exponential dependence on the depth can be removed.

As a consequence, we are able to push the envelope on the state of the art in various settings of MPC, including the following cases.

* $3$-round perfectly-secure protocol (with guaranteed output delivery) against an active adversary that corrupts less than a quarter of the parties.

* $2$-round statistically-secure protocol that achieves security with ``selective abort'' against an active adversary that corrupts less than half of the parties.

* Assuming one-way functions, $2$-round computationally-secure protocol that achieves security with (standard) abort against an active adversary that corrupts less than half of the parties. This gives a new and conceptually simpler proof to the recent result of Ananth et al. (Crypto 2018).

Technically, our non-interactive reduction draws from the encoding method of Applebaum, Brakerski and Tsabary (TCC 2018). We extend these methods to ones that can be meaningfully analyzed even in the presence of malicious adversaries.

We introduce password-authenticated public-key encryption (PAPKE), a new cryptographic primitive. PAPKE enables secure end-to-end encryption between two entities without relying on a trusted third party or other out-of-band mechanisms for authentication. Instead, resistance to man-in-the-middle attacks is ensured in a human-friendly way by authenticating the public key with a shared password, while preventing offline dictionary attacks given the authenticated public key and/or the ciphertexts produced using this key.

Our contributions are three-fold. First, we provide property-based and universally composable (UC) denitions for PAPKE, with the resulting primitive combining CCA security of public-key encryption (PKE) with password authentication. Second, we show that PAPKE implies Password-Authenticated Key Exchange (PAKE), but the reverse implication does not hold, indicating that PAPKE is a strictly stronger primitive than PAKE. Indeed, PAPKE implies a two-flow PAKE which remains secure if either party re-uses its state in multiple sessions, e.g. due to communication errors, thus strengthening existing notions of PAKE security. Third, we show two highly practical UC PAPKE schemes: a generic construction built from CCA-secure and anonymous PKE and an ideal cipher, and a direct construction based on the Decisional Diffie-Hellman assumption in the random oracle model.

Finally, applying our PAPKE-to-PAKE compiler to the above PAPKE schemes we exhibit the first 2-round UC PAKE's with efficiency comparable to (unauthenticated) Diffie-Hellman Key Exchange.

The need for high-quality randomness in cryptography makes random-number generation one of its most fundamental tasks. A recent important line of work (initiated by Dodis et al., CCS ’13) focuses on the notion of *robustness* for *pseudorandom number generators (PRNGs) with inputs*—these are primitives that use various sources to accumulate sufficient entropy into a state, from which pseudorandom bits are extracted. Robustness ensures that PRNGs remain secure even under state compromise and adversarial control of entropy sources. However, the achievability of robustness inherently depends on a seed, or, alternatively, on an ideal primitive (e.g., a random oracle), independent of the source of entropy. Both assumptions are problematic: seed generation requires randomness to start with, and it is arguable whether the seed or the ideal primitive can be kept independent of the source. This paper resolves this dilemma by putting forward new notions of robustness which enable both (1) *seedless* PRNGs and (2) *primitive-dependent* adversarial sources of entropy. To bypass obvious impossibility results, we make a realistic compromise by requiring that the source produce sufficient entropy even given its evaluations of the underlying primitive. We also provide natural, practical, and provably secure constructions based on hash-function designs from compression functions, block ciphers, and permutations. Our constructions can be instantiated with minimal changes to industry-standard hash functions SHA-2 and SHA-3, or HMAC (as used for the key derivation function HKDF), and can be downgraded to *(online) seedless randomness extractors*, which are of independent interest. On the way we consider both a *computational* variant of robustness, where attackers only make a bounded number of queries to the ideal primitive, as well as a new *information-theoretic* variant, which dispenses with this assumption to a certain extent, at the price of requiring a high rate of injected weak randomness (as it is, e.g., plausible on Intel’s on-chip RNG). The latter notion enables applications such as everlasting security. Finally, we show that the CBC extractor, used by Intel’s on-chip RNG, is provably insecure in our model.

We present the first treatment of non-interactive publicly-verifiable timestamping schemes in the Universal Composability framework. Similar to a simple construction by Mahmoody et al., we use non-parallelizable computational work that relates to elapsed time to avoid previous impossibility results on non-interactive timestamping. We extend these ideas to the UC-framework and show how to model verifiable delay functions (VDF) related to a global clock, and non-interactive timestamping, in the UC-framework. Furthermore, we present new constructions that are substantial improvements over Mahmoody et al.’s construction, such that any forged timestamps by the adversary are now limited to within a certain time-window that depends only on its ratio to compute VDFs more quickly and the time-window of corruption. Finally, we discuss natural applications for our construction in decentralized protocols.

Ring signatures allow for creating signatures on behalf of an ad hoc group of signers, hiding the true identity of the signer among the group. A natural goal is to construct a ring signature scheme for which the signature size is short in the number of ring members. Moreover, such a construction should not rely on a trusted setup and be proven secure under falsifiable standard assumptions. Despite many years of research this question is still open.

In this paper, we present the first construction of size-optimal ring signatures which do not rely on a trusted setup or the random oracle heuristic. Specifically, our scheme can be instantiated from standard assumptions and the size of signatures grows only logarithmically in the number of ring members.

We also extend our techniques to the setting of linkable ring signatures, where signatures created using the same signing key can be linked.