International Association
for Cryptologic Research

Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties so that any qualified subset of parties can reconstruct the secret, while every unqualified subset of parties learns nothing about the secret. The collection of qualified subsets is called an access structure. The best known access structure is the k-threshold one, where any subset of size k or more is qualified and all smaller subsets are not qualified. A major issue is the size of the shares needed to assure this property. For the threshold access structure, when k=2 and there are n parties it is known that the share size must be log(n) even for secrets of 1 bit.

In this work we consider the case where the set of parties is not known in advanced and could potentially be infinite. We would still like to give the t-th party arriving a small share as possible as a function of t. We show that for any access structure it is possible to do so by giving shares of size 2^{t-1}. Our main result is a scheme for k-threshold access structure with shares of size (k-1)*log(t)+poly(k)*o(log t) bits. Finally, we prove that no secret sharing scheme for the 2-threshold access structure with share size at most log(t)+loglog(t)+O(1) exists.

We explore further the hardness of the RLWE problem for various number rings, construct a new family of vulnerable Galois number fields, give improved attacks for certain rings satisfying some additional assumptions, and apply some number theoretic results on Gauss sums to deduce the likely failure of these attacks for cyclotomic rings and unramified moduli.

The list of papers accepted to Eurocrypt 2016 is now available at http://ist.ac.at/eurocrypt2016/accepted.html. 62 papers were accepted, a new high for Eurocrypt. The conference will be held May 8-12 in Vienna.

Goldreich and Izsak (Theory of Computing, 2012) initiated the research on understanding the role of negations in circuits implementing cryptographic primitives, notably, considering one-way functions and pseudo-random generators. More recently, Guo, Malkin, Oliveira and Rosen (TCC, 2014) determined tight bounds on the minimum number of negations gates (i.e., negation complexity) of a wide variety of cryptographic primitives including pseudo-random functions, error-correcting codes, hardcore-predicates and randomness extractors.

We continue this line of work to establish the following results: 1. First, we determine tight lower bounds on the negation complexity of collision-resistant and target collision-resistant hash-function families. 2. Next, we examine the role of injectivity and surjectivity on the negation complexity of one-way functions. Here we show that, a) Assuming the existence of one-way injections, there exists a monotone one-way injection. Furthermore, we complement our result by showing that, even in the worst-case, there cannot exist a monotone one-way injection with constant stretch. b) Assuming the existence of one-way permutations, there exists a monotone one-way surjection. 3. Finally, we show that there exists list-decodable codes with monotone decoders.

In addition, we observe some interesting corollaries to our results.

We perform a concrete security treatment of digital signature schemes obtained from canonical identification schemes via the Fiat-Shamir transform. If the identification scheme is rerandomizable and satisfies the weakest possible security notion (key-recoverability), then the implied signature scheme is unforgeability against chosen-message attacks in the multi-user setting in the random oracle model. The reduction loses a factor of roughly Qh, the number of hash queries. Previous security reductions incorporated an additional multiplicative loss of N, the number of users in the system. As an important application of our framework, we obtain a concrete security treatment for Schnorr signatures.

Our analysis is done in small steps via intermediate security notions, and all our implications have relatively simple proofs. Furthermore, for each step we show the optimality of the given reduction via a meta-reduction.

Lightweight cryptography strives to protect communication in constrained environments without sacrificing security. However, security often conflicts with efficiency, shown by the fact that many new lightweight block cipher designs have block sizes as low as 64 or 32 bits. Due to the birthday bound, such low block sizes lead to impractical limits on how much data a mode of operation can process per key. MAC (message authentication code) modes of operation frequently have bounds which degrade with both the number of messages queried and the message length. We present a MAC mode of operation, LightMAC, where the message length has no effect on the security bound, allowing an order of magnitude more data to be processed per key. Furthermore, LightMAC is incredibly simple, has almost no overhead over the block cipher, and is parallelizable. As a result, LightMAC not only offers compact authentication for resource-constrained platforms, but also allows high-performance parallel implementations. We highlight this in a comprehensive implementation study, instantiating LightMAC with PRESENT and the AES. Moreover, LightMAC allows flexible trade-offs between rate and maximum message length. Unlike PMAC and its many derivatives, LightMAC is not covered by patents. Altogether, this makes it a promising authentication primitive for a wide range of platforms and use cases.

We offer efficient and practical solutions of Yao's millionaires' problem without using any one-way functions. Some of the solutions involve physical principles, while others are purely mathematical. One of our solutions (based on physical principles) yields a public-key encryption protocol secure against a computationally unbounded adversary. In that protocol, the legitimate parties are not assumed to be computationally unbounded.

In 2015, Todo introduced a property of multisets of a finite field called the division property. It is then used by Todo in an attack against the S7 S-box of the MISTY1 cipher. This paper provides a complete mathematical analysis of the division property. The tool we use is the discrete Fourier transform. We relate the division property to the natural concept of the degree of a subset of a finite field. This indeed provides a characterization of multisets satisfying the division property. In 2015, Sun et al. gave some properties related to the division property. In this paper we give a complete characterization and reprove many of their results. We show that the division property is actually the dual of the degree of $t$-products of the inverse S-box and show these two characteristics are affine invariants. We then propose a very efficient way to check vulnerability of a given S-box against attacks of this type. We also reprove some recent interesting results using the method based on the discrete Fourier transform. We finally check whether the S-boxes of the candidate ciphers in the CAESAR competition are vulnerable against attacks based on the division property.

We study secure multiparty computation (MPC) in the dishonest majority setting providing security with identifiable abort, where if the protocol aborts, the honest parties can agree upon the identity of a corrupt party. All known constructions that achieve this notion require expensive zero-knowledge techniques to obtain active security, so are not practical.

In this work, we present the first efficient MPC protocol with identifiable abort. Our protocol has an information-theoretic online phase, with roughly the same performance as the SPDZ protocol (Damgård et al., Crypto 2012), requiring O(n) messages to be broadcast for each secure multiplication. A key component of our protocol is a linearly homomorphic information-theoretic signature scheme, for which we provide the first definitions and construction based on a previous non-homomorphic scheme. We then show how to implement the preprocessing for our protocol using somewhat homomorphic encryption, similarly to the SPDZ protocol and other recent works with applicable efficiency improvements.

In this article, we analyze the circulant structure of generalized circulant matrices to reduce the search space for finding lightweight MDS matrices. We first show that the implementation of circulant matrices can be serialized and can achieve similar area requirement and clock cycle performance as a serial-based implementation. By proving many new properties and equivalence classes for circulant matrices, we greatly reduce the search space for finding lightweight maximum distance separable (MDS) circulant matrices. We also generalize the circulant structure and propose a new class of matrices, called \textit{cyclic matrices}, which preserve the benefits of circulant matrices and, in addition, have the potential of being self-invertible. In this new class of matrices, we obtain not only the MDS matrices with the least XOR gates requirement for dimensions from $3 \times 3$ to $8 \times 8$ in $\gf(2^4)$ and $\gf(2^8)$, but also involutory MDS matrices which was proven to be non-existence in the class of circulant matrices. To the best of our knowledge, the latter matrices are the first of its kind, which have a similar matrix structure as circulant matrices and are involutory and MDS simultaneously. Compared to the existing best known lightweight matrices, our new candidates either outperform or match them in terms of XOR gates required for a hardware implementation. Notably, our work is generic and independent of the metric for lightweight. Hence, our work is applicable for improving the search for efficient circulant matrices under other metrics besides XOR gates.

Many MAC (Message Authentication Code) algorithms have security bounds which degrade linearly with the message length. Often there are attacks that confirm the linear dependence on the message length, yet PMAC has remained without attacks. Our results show that PMAC's message length dependence in security bounds is non-trivial. We start by studying a generalization of PMAC in order to focus on PMAC's basic structure. By abstracting away details, we are able to show that there are two possibilities: either there are infinitely many instantiations of generic PMAC with security bounds independent of the message length, or finding an attack against generic PMAC which establishes message length dependence is computationally hard. The latter statement relies on a conjecture on the difficulty of finding subsets of a finite field summing to zero or satisfying a binary quadratic form. Using the insights gained from studying PMAC's basic structure, we then shift our attention to the original instantiation of PMAC, namely, with Gray codes. Despite the initial results on generic PMAC, we show that PMAC with Gray codes is one of the more insecure instantiations of PMAC, by illustrating an attack which roughly establishes a linear dependence on the message length.

Secure two-party computation based on cut-and-choose has made great strides in recent years, with a significant reduction in the total number of garbled circuits required. Nevertheless, the overhead of cut-and-choose can still be significant for large circuits (i.e., a factor of $\rho$ in both communication and computation for statistical security $2^{-\rho}$).

We show that for a particular class of computation it is possible to do better. Namely, consider the case where a function on the parties' inputs is computed only if each party's input satisfies some publicly checkable predicate (e.g., is signed by a third party, or lies in some desired domain). Using existing cut-and-choose-based protocols, both the predicate checks and the function would need to be garbled $\rho$ times. Here we show a protocol in which only the underlying function is garbled $\rho$ times, and the predicate checks are each garbled only \emph{once}. For certain natural examples (e.g., signature verification followed by evaluation of a million-gate circuit), this can lead to huge savings in communication (up to 80$\times$) and computation (up to 56$\times$). We provide detailed estimates using realistic examples to validate our claims.

Side-channel attacks are an important concern for the security of cryptographic algorithms. To counteract it, a recent line of research has investigated the use of software encoding functions such as dual-rail rather than the well known masking countermeasure. The core idea consists in encoding the sensitive data with a fixed Hamming weight value and perform all operations following this fashion. This new set of countermeasures applies to all devices that leak a function of the Hamming weight of the internal variables. However when the leakage model deviates from this idealized model, the claimed security guarantee vanishes. In this work, we introduce a framework that aims at building customized encoding functions according to the precise leakage model based on stochastic profiling. We specifically investigate how to take advantage of adversary's knowledge of the physical leakage to select the corresponding optimal encoding. Our solution has been evaluated within several security metrics, proving its efficiency against side-channel attacks in realistic scenarios. A concrete experimentation of our proposal to protect the PRESENT Sbox confirms its practicability. In a realistic scenario, our new custom encoding achieves a hundredfold reduction in leakage compared to the dual-rail, although using the same code length.

Besides security against classical cryptanalysis, its important for cryptographic implementations to have sucient robustness against side-channel attacks. Many countermeasures have been proposed to thwart side channel attacks, especially power trace measurement based side channel attacks. Additionally, researchers have proposed several evaluation metrics to evaluate side channel security of crypto-system. However, evaluation of any crypto-system is done during the testing phase and is not part of the actual hardware. In our approach, we propose to implement such evaluation metrics on-chip for run-time side channel vulnerability estimation of a cryptosystem. The objective is to create a watchdog on the hardware which will monitor the side channel leakage of the device, and will alert the user if that leakage crosses a pre-determined threshold, beyond which the system might be considered vulnerable. Once such alert signal is activated, proactive countermeasures can be activated either at the device level or at the protocol level, to prevent the impending side channel attack. A FPGA based prototype designed by us show low hardware overhead, and is an eective option that avoids the use of bulky and inconvenient on-eld measurement setup.

The operation of modular addition modulo a power of two is one of the most applied operations in symmetric cryptography. For example, modular addition is used in RC6, MARS and Twofish block ciphers and RC4, Bluetooth and Rabbit stream ciphers. In this paper, we study statistical and algebraic properties of modular addition modulo a power of two. We obtain probability distribution of modular addition carry bits along with conditional probability distribution of these carry bits. Using these probability distributions and Markovity of modular addition carry bits, we compute the joint probability distribution of arbitrary number of modular addition carry bits. Then, we examine algebraic properties of modular addition with a constant and obtain the number of terms as well as algebraic degrees of component Boolean functions of modular addition with a constant. Finally, we present another formula for the ANF of the component Boolean functions of modular addition modulo a power of two. This formula contains more information than representations which are presented in cryptographic literature, up to now.

Event date: 1 December to 31 December 2017
Submission deadline: 31 January 2017
Notification: 31 March 2017

In a selective-opening (SO) attack on an encryption scheme, an adversary A gets a number of ciphertexts (with possibly related plain- texts), and can then adaptively select a subset of those ciphertexts. The selected ciphertexts are then opened for A (which means that A gets to see the plaintexts and the corresponding encryption random coins), and A tries to break the security of the unopened ciphertexts.

Two main flavors of SO security notions exist: indistinguishability-based (IND-SO) and simulation-based (SIM-SO) ones. Whereas IND-SO security allows for simple and efficient instantiations, its usefulness in larger constructions is somewhat limited, since it is restricted to special types of plaintext distributions. On the other hand, SIM-SO security does not suffer from this restriction, but turns out to be significantly harder to achieve. In fact, all known SIM-SO secure encryption schemes either re-quire O(|m|) group elements in the ciphertext to encrypt |m|-bit plaintexts, or use specific algebraic properties available in the DCR setting.

In this work, we present the first SIM-SO secure PKE schemes in the discrete-log setting with compact ciphertexts (whose size is O(1) group elements plus plaintext size). The SIM-SO security of our constructions can be based on, e.g., the k-linear assumption for any k.

Technically, our schemes extend previous IND-SO secure schemes by the property that simulated ciphertexts can be efficiently opened to arbitrary plaintexts. We do so by encrypting the plaintext in a bitwise fashion, but such that each encrypted bit leads only to a single ciphertext bit (plus O(1) group elements that can be shared across many bit encryptions). Our approach leads to rather large public keys (of O(|m|^2) group elements), but we also show how this public key size can be reduced (to O(|m|) group elements) in pairing-friendly groups.

We outline an algorithm to compute $\theta(z,\tau)$ in genus 2 in quasi-optimal time, borrowing ideas from the algorithm for theta constants and the one for $\theta(z,\tau)$ in genus 1. Our implementation shows a large speedup for precisions as low as a few thousand decimal digits. We also lay out a strategy to generalize this algorithm to genus $g$.

Integral attacks form a powerful class of cryptanalytic techniques that have been widely used in the security analysis of block ciphers. The integral distinguishers are based on balanced properties holding with probability one. To obtain a distinguisher covering more rounds, an attacker will normally increase the data complexity by iterating through more plaintexts with a given structure under the strict limitation of the full codebook. On the other hand, an integral property can only be deterministically verified if the plaintexts cover all possible values of a bit selection. These circumstances have somehow restrained the applications of integral cryptanalysis.

In this paper, we aim to address these limitations and propose a novel \emph{statistical integral distinguisher} where only a part of value sets for these input bit selections are taken into consideration instead of all possible values. This enables us to achieve significantly lower data complexities for our statistical integral distinguisher as compared to those of traditional integral distinguisher. As an illustration, we successfully attack the full-round Skipjack-BABABABA for the first time, which is the variant of NSA's Skipjack block cipher.

NTRU is a public-key cryptosystem introduced at ANTS-III. The two most used techniques in attacking the NTRU private key are meet-in-the-middle attacks and lattice-basis reduction attacks. In the 2007 CRYPTO paper ``A Hybrid Lattice-Reduction and Meet-in-the-Middle Attack Against NTRU'' both techniques are combined and it is pointed out that the largest obstacle to attacks is the memory capacity that is required for the meet-in-the-middle phase.

In this paper an algorithm is presented that applies low-memory techniques to find `golden' collisions to Odlyzko's meet-in-the-middle attack against the NTRU private key. Several aspects of NTRU secret keys and the algorithm are analysed. The running time of the algorithm with a maximum storage capacity of $w$ is estimated and experimentally verified. Experiments indicate that decreasing the storage capacity by a factor $c$ increases the running time by a factor $\sqrt{c}$.