International Association
for Cryptologic Research

In recent years, Mixed Integer Linear Programming (MILP) has been successfully applied in searching for differential characteristics and linear approximations in block ciphers and has produced the significant results for some ciphers such as SIMON (a family of lightweight and hardware-optimized block ciphers designed by NSA) etc. However, in the literature, the MILP-based automatic search algorithm for differential characteristics and linear approximations is still infeasible for block ciphers such as ARX constructions. In this paper, we propose an MILP-based method for automatic search for differential characteristics and linear approximations in ARX ciphers. By researching the properties of differential characteristic and linear approximation of modular addition in ARX ciphers, we present a method to describe the differential characteristic and linear approximation with linear inequalities under the assumptions of independent inputs to the modular addition and independent rounds. We use this representation as an input to the publicly available MILP optimizer Gurobi to search for differential characteristics and linear approximations for ARX ciphers. As an illustration, we apply our method to Speck, a family of lightweight and software-optimized block ciphers designed by NSA, which results in the improved differential characteristics and linear approximations compared with the existing ones. Moreover, we provide the improved differential attacks on Speck48, Speck64, Speck96 and Speck128, which are the best attacks on them in terms of the number of rounds.

In the present paper, we investigate the problem of constructing MDS matrices with as few bit XOR operations as possible. The key contribution of the present paper is constructing MDS matrices with entries in the set of $m\times m$ non-singular matrices over $\mathbb{F}_2$ directly, and the linear transformations we used to construct MDS matrices are not assumed pairwise commutative. With this method, it is shown that circulant involutory MDS matrices, which have been proved do not exist over the finite field $\mathbb{F}_{2^m}$, can be constructed by using non-commutative entries. Some constructions of $4\times4$ and $5\times5$ circulant involutory MDS matrices are given when $m=4,8$. To the best of our knowledge, it is the first time that circulant involutory MDS matrices have been constructed. Furthermore, some lower bounds on XORs that required to evaluate one row of circulant and Hadamard MDS matrices of order 4 are given when $m=4,8$. Some constructions achieving the bound are also given, which have fewer XORs than previous constructions.

Statistical analysis of multiple differential attacks are considered in this paper. Following the work of Blondeau and G\'{e}rard, the most general situation of multiple differential attack where there are no restrictions on the set of differentials is studied. We obtain closed form expressions for the data complexity in terms of the success probability and the advantage of an attack. This is done under two scenarios -- one, where an independence assumption used by Blondeau and G\'{e}rard is assumed to hold and second, where no such assumption is made. The first case employs the Chernoff bounds while the second case uses the Azuma-Hoeffding bounds from the theory of martingales. In both cases, we do not make use of any approximations in our analysis. As a consequence, the results are more generally applicable compared to previous works. The analysis without the independence assumption is the first of its kind in the literature. We believe that the current work places the statistical analysis of multiple differential attack on a more rigourous foundation than what was previously known.

The log-likelihood ratio (LLR) test statistic has been proposed in the literature for performing statistical analysis of attacks on block ciphers. A limitation of the LLR test statistic is that its application requires the full knowledge of the corresponding distribution. Another test statistic which has been proposed in the literature does not possess this limitation. The statistical analysis using this test statistic requires {\em approximating} its distribution by a chi-squared distribution. Problematic issues regarding such approximations have been reported in the literature. This work proposes a new test statistic which offers the following two features. Its application does not require knowledge of the underlying distribution and it is possible to carry out an analysis using this test statistic without using any approximation. This is made possible by applying the theory of martingales to build a Doob martingale satisfying an appropriate Lipschitz condition so that the Azuma-Hoeffding inequality can be applied. Experimental comparison of the data complexity obtained using the new method is made to the data complexity obtained using the chi-squared based method for both simulated distributions and the previously reported distribution for the block cipher SERPENT. In all cases, the data complexity obtained by the new method turns out to be greater. While this may appear to be a drawback of the new method, this is a rigorous bound while the data complexity obtained using the chi-squared method is an approximation where there is little knowledge about the error in the approximation. So, if rigorous bound is desired, then one will have to be satisfied with a more conservative estimate of the data complexity.

We observe that the conventional classification of pairings into Types 1, 2, 3 and 4 is not applicable to pairings from elliptic curves with embedding degree one. We define three kinds of pairings from these elliptic curves, and discuss some subtleties with using them to implement pairing-based protocols.

In this paper, based on the FV scheme, we construct a first fully homomorphic encryption scheme FHE4FX that can homomorphically compute addition and/or multiplication of encrypted fixed point numbers without knowing the secret key. Then, we show that in the FHE4FX scheme one can efficiently and homomorphically compare magnitude of two encrypted numbers. That is, one can compute an encryption of the greater-than bit that represents whether or not $x > x'$ given two ciphertexts $c$ and $c'$ (of $x$ and $x'$, respectively) without knowing the secret key. Finally we show that these properties of the FHE4FX scheme enables us to construct a fully homomorphic encryption scheme FHE4FL that can homomorphically compute addition and/or multiplication of encrypted floating point numbers.

Affine-padding {\sc rsa} signatures consist in signing $\omega\cdot m+\alpha$ instead of the message $m$ for some fixed constants $\omega,\alpha$. A thread of publications progressively reduced the size of $m$ for which affine signatures can be forged in polynomial time. The current bound is $\log m \sim \frac{N}{3}$ where $N$ is the {\sc rsa} modulus' bit-size. Improving this bound to $\frac{N}{4}$ has been an elusive open problem for the past decade.\smallskip

In this invited talk we consider a slightly different problem: instead of minimizing $m$'s size we try to minimize its {\sl entropy}. We show that affine-padding signatures on $\frac{N}{4}$ entropy-bit messages can be forged in polynomial time. This problem has no direct cryptographic impact but allows to better understand how malleable the {\sc rsa} function is. In addition, the techniques presented in this talk might constitute some progress towards a solution to the longstanding $\frac{N}{4}$ forgery open problem.\smallskip\smallskip

We also exhibit a sub-exponential time technique (faster than factoring) for creating affine modular relations between strings containing three messages of size $\frac{N}{4}$ and a fourth message of size $\frac{3N}{8}$.\smallskip

Finally, we show than $\frac{N}{4}$-relations can be obtained in specific scenarios, {\sl e.g.} when one can pad messages with two independent patterns or when the modulus' most significant bits can be chosen by the opponent.\smallskip

At Asiacrypt 2015, Barbulescu et al. performed a thorough analysis of the tower number field sieve (TNFS) variant of the number field sieve algorithm. More recently, Kim and Barbulescu combined the TNFS variant with several polynomial selection methods including the Generalised Joux-Lercier method and the Conjugation method proposed by Barbulescu et al. at Eurocrypt 2015. Sarkar and Singh (Eurocrypt 2016) proposed a polynomial selection method which subsumes both the GJL and the Conjugation methods. This study was done in the context of the NFS and the multiple NFS (MNFS). The purpose of the present note is to show that the polynomial selection method of Sarkar and Singh subsumes the GJL and the Conjugation methods also in the context of the TNFS and the multiple TNFS variants. This was not clear from the recent work by Kim and Barbulescu. Applying the new polynomial selection method to the TNFS variants results in new asymptotic complexities for certain ranges of primes.

We provide an overview of some of the security issues involved in securely implementing Lalley and Weyl's ``Quadratic Voting'', and suggest some possible implementation architectures. Our proposals blend ``end-to-end verifiable'' voting methods with anonymous payments. We also consider new refund rules for quadratic voting, such as a ``lottery'' method.

Discrete-logarithm authentication protocols are known to present two interesting features: The first is that the prover's commitment, $x=g^r$, claims most of the prover's computational effort. The second is that $x$ does not depend on the challenge and can hence be computed in advance. Provers exploit this feature by pre-loading (or pre-computing) ready to use commitment pairs $r_i,x_i$. The $r_i$ can be derived from a common seed but storing each $x_i$ still requires 160 to 256 bits when implementing DSA or Schnorr.

This paper proposes a new concept called {\it slow motion zero-knowledge} (SM-ZK). SM-ZK allows the prover to slash commitment size (by a factor of 4 to 6) by combining classical zero-knowledge and a timing side-channel. We pay the conceptual price of requiring the ability to measure time but, in exchange, obtain communication-efficient protocols.

We introduce the high-degree indicator matrix (HDIM), an object closely related with both the linear approximation table and the algebraic normal form (ANF) of a permutation. We show that the HDIM of a Feistel Network contains very specific patterns depending on the degree of the Feistel functions, the number of rounds and whether the Feistel functions are 1-to-1 or not. We exploit these patterns to distinguish Feistel Networks, even if the Feistel Network is whitened using unknown affine layers.

We also present a new type of structural attack exploiting monomials that cannot be present at round $r-1$ to recover the ANF of the last Feistel function of a $r$-round Feistel Network. Finally, we discuss the relations between our findings, integral attacks, cube attacks, Todo's division property and the congruence modulo 4 of the Linear Approximation Table.

Non-malleable codes were introduced by Dziembowski et al. (ICS 2010) as coding schemes that protect a message against tampering attacks. Roughly speaking, a code is non-malleable if decoding an adversarially tampered encoding of a message m produces the original message m or a value m' (eventually $\perp$) completely unrelated with m. Moreover, the probability of which one of these two events happens is also independent of m. It is known that non-malleability is possible only for restricted classes of tampering functions. Since their introduction, a long line of works has established feasibility results of non-malleable codes against different families of tampering functions. However, for many interesting families the challenge of finding “good” non-malleable codes remains open. In particular, we would like to have explicit constructions of non-malleable codes with high-rate and efficient encoding/decoding algorithms (i.e. low computational complexity). In this work we present two explicit constructions: the first one is a natural generalization of the seminal work of Dziembowski et al. and gives rise to the first constant-rate non-malleable code with linear-time complexity (in a model including bit-wise independent tampering). The second construction is inspired by the recent works about non-malleable codes of Agrawal et al. (TCC 2015) and of Cheraghchi and Guruswami (TCC 2014) and improves the previous result in the bit-wise tampering model: it builds the first non-malleable codes with linear-time complexity and optimal-rate (i.e. rate 1 − o(1)).

In this note, we describe attacks on the recently proposed Haraka hash functions. First, for the two hash functions Haraka-256/256 and Haraka-512/256 in the family, we show how two colliding messages can be constructed in about $2^{16}$ function evaluations. Second, we invalidate the preimage security claim for Haraka-512/256 with an attack finding one preimage in about $2^{192}$ function evaluations. These attacks are possible thanks to symmetries in the internal state that are preserved over several rounds.

Block-cipher-based authenticated encryption has obtained considerable attention from the ongoing CAESAR competition. While the focus of CAESAR resides primarily on nonce-based authenticated encryption, Deterministic Authenticated Encryption (DAE) is used in domains such as key wrap, where the available message entropy motivates to omit the overhead for nonces. Since the highest possible security is desirable when protecting keys, beyond-birthday-bound (BBB) security is a valuable goal for DAE. In the past, significant efforts had to be invested into designing BBB-secure AE schemes from conventional block ciphers, with the consequences of losing efficiency and sophisticating security proofs.

This work proposes Deterministic Counter in Tweak (DCT), a BBB-secure DAE scheme inspired by the Counter-in-Tweak encryption scheme by Peyrin and Seurin. Our design combines a fast $\epsilon$-almost-XOR-universal family of hash functions, for $\epsilon$ close to $2^{-2n}$, with a single call to a $2n$-bit SPRP, and a BBB-secure encryption scheme. First, we describe our construction generically with three independent keys, one for each component. Next, we present an efficient instantiation which (1) requires only a single key, (2) provides software efficiency by encrypting at less than two cycles per byte on current x64 processors, and (3) produces only the minimal $\tau$-bit stretch for $\tau$ bit authenticity. We leave open two minor aspects for future work: our current generic construction is defined for messages of at least $2n-\tau$ bits, and the verification algorithm requires the inverse of the used $2n$-bit SPRP and the encryption scheme.

We reconsider the formalization of known-key attacks against ideal primitive-based block ciphers. This was previously tackled by Andreeva, Bogdanov, and Mennink (FSE 2013), who introduced the notion of known-key indifferentiability. Our starting point is the observation, previously made by Cogliati and Seurin (EUROCRYPT 2015), that this notion, which considers only a single known key available to the attacker, is too weak in some settings to fully capture what one might expect from a block cipher informally deemed resistant to known-key attacks. Hence, we introduce a stronger variant of known-key indifferentiability, where the adversary is given multiple known keys to ``play'' with, the informal goal being that the block cipher construction must behave as an independent random permutation for each of these known keys. Our main result is that the 9-round iterated Even-Mansour construction (with the trivial key-schedule, i.e., the same round key xored between permutations) achieves our new ``multiple'' known-keys indifferentiability notion, which contrasts with the previous result of Andreeva et al. that one single round is sufficient when only a single known key is considered. We also show that the 3-round iterated Even-Mansour construction achieves the weaker notion of multiple known-keys sequential indifferentiability, which implies in particular that it is correlation intractable with respect to relations involving any (polynomial) number of known keys.

We consider the adjacency graphs of linear feedback shift registers (LFSRs) with reducible characteristic polynomials. Let l(x) be a characteristic polynomial, and l(x)=l_1(x)l_2(x)\cdots l_r(x) be a decomposition of l(x) into co-prime factors. Firstly, we show a connection between the adjacency graph of FSR(l(x)) and the association graphs of FSR(l_i(x)), 1\leq i\leq r. By this connection, the problem of determining the adjacency graph of FSR(l(x)) is decomposed to the problem of determining the association graphs of FSR(l_i(x)), 1\leq i\leq r, which is much easier to handle. Then, we study the association graph of LFSRs with irreducible characteristic polynomials and give a relationship between these association graphs and the cyclotomic numbers over finite fields. At last, some applications are suggested.

The PKC 2017 call for papers is now online. PKC will be held March 28-31, in Amsterdam. Submission deadline is October 6.

Event date: 23 May to 27 May 2016
Submission deadline: 15 May 2016

Event date: 29 June to 9 July 2016

Event date: 28 October 2016
Submission deadline: 27 July 2016
Notification: 5 September 2016