International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) You can also receive updates via:

To receive your credentials via mail again, please click here.

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

16:17 [Pub][ePrint] Leakage Assessment Methodology - a clear roadmap for side-channel evaluations, by Tobias Schneider and Amir Moradi

  Evoked by the increasing need to integrate side-channel countermeasures into security-enabled commercial devices, evaluation labs are seeking a standard approach that enables a fast, reliable and robust evaluation of the side-channel vulnerability of the given products. To this end, standardization bodies such as NIST intend to establish a leakage assessment methodology fulfilling these demands. One of such proposals is the Welch\'s t-test, which is being put forward by Cryptography Research Inc., and is able to relax the dependency between the evaluations and the device\'s underlying architecture. In this work, we deeply study the theoretical background of the test\'s different flavors, and present a roadmap which can be followed by the evaluation labs to efficiently and correctly conduct the tests. More precisely, we express a stable, robust and efficient way to perform the tests at higher orders. Further, we extend the test to multivariate settings, and provide details on how to efficiently and rapidly carry out such a multivariate higher-order test. Including a suggested methodology to collect the traces for these tests, we present practical case studies where different types of t-tests can exhibit the leakage of supposedly secure designs.

16:17 [Pub][ePrint] Towards Secure Distance Bounding, by Ioana Boureanu, Aikaterini Mitrokotsa and Serge Vaudenay

  Relay attacks (and, more generally, man-in-the-middle attacks) are a serious threat against many access control and payment schemes.

In this work, we present distance-bounding protocols, how these can deter relay attacks, and the security models formalizing these protocols. We show several pitfalls making existing protocols insecure (or at least, vulnerable, in some cases). Then, we introduce the SKI protocol which enjoys resistance to all popular attack-models and features provable security. As far as we know, this is the first protocol with such all-encompassing security guarantees.

16:17 [Pub][ePrint] Triathlon of Lightweight Block Ciphers for the Internet of Things, by Daniel Dinu and Yann Le Corre and Dmitry Khovratovich and Léo Perrin and Johann Großschädl and Alex Biryukov

  In this paper we introduce an open framework for the benchmarking of lightweight block ciphers on a multitude of embedded platforms. Our framework is able to evaluate execution time, RAM footprint, as well as (binary) code size, and allows a user to define a custom \"figure of merit\" according to which all evaluated candidates can be ranked. We used the framework to benchmark various implementation of 13 lightweight ciphers, namely AES, Fantomas, HIGHT, LBlock, LED, Piccolo, PRESENT, PRINCE, RC5, Robin, Simon, Speck, and TWINE, on three different platforms: 8-bit ATmega, 16-bit MSP430, and 32-bit ARM. Our results give new insights to the question of how well these ciphers are suited to secure the Internet of Things (IoT). The benchmarking framework provides cipher designers with a tool to compare new algorithms with the state-of-the-art and allows standardization bodies to conduct a fair and comprehensive evaluation of a large number of candidates.

16:17 [Pub][ePrint] Secure and Efficient Initialization and Authentication Protocols for SHIELD, by Chenglu Jin and Marten van Dijk

  With the globalization of semiconductor production, out-sourcing IC fabrication has become a trend in various aspects. This, however, introduces serious threats from the entire untrusted supply chain. To combat these threats, DARPA (Defense Advanced Research Projects Agency) proposed the SHIELD (Supply Chain Hardware Integrity for Electronics Defense) program to design a secure hardware root-of-trust, called dielet, to be inserted into the host package of legitimately produced ICs. Dielets are RF powered and communicate with the outside world through their RF antennas. They have sensors which allow them to passively (without the need for power) record malicious events which can later be read out during an authentication protocol between the dielet and server with a smartphone as intermediary.

In this paper, we propose to use AES counter mode encryption (as opposed to DARPA\'s suggested plain AES encryption) as a basis for the authentication process. We show that this leads to several advantages: (1) resistance to a ``try-and-check\'\' attack which in case of DARPA\'s authentication protocol nullifies the effectiveness of one of SHIELD\'s main goals (that of being able to detect and trace adversarial activities with significant probability), (2) immunity against differential power analysis and differential fault analysis for free, (3) a 2$\\times$ speed up of the authentication phase by halving the the number of communication rounds with the server, and (4) a significant reduction of the power consumption of the dielet by halving the number of needed AES encryptions and by a 4$\\times$ reduction of the number of transmitted bits.

Each dielet needs to go through an initialization phase during which the manufacturer sets a serial ID and cryptographic key.

%Fusing this information one dielet at a time (while they are still on the wafer) takes a significant amount of time ($\\approx$7 minutes).

In this paper we propose the first efficient and secure initialization protocol where dielets generate their own serial ID and key by using a true random number generator (TRNG). Finally, the area overhead of our authentication and initialization protocols is only 64-bit NVM, one 8-bit counter and a TRNG based on a single SRAM-cell together with corresponding control logic.

16:17 [Pub][ePrint] Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing, by Thijs Laarhoven and Benne de Weger

  Recently, it was shown that angular locality-sensitive hashing (LSH) can be used to significantly speed up lattice sieving, leading to heuristic time and space complexities for solving the shortest vector problem (SVP) of $2^{0.3366n + o(n)}$. We study the possibility of applying other LSH methods to sieving, and show that with the recent spherical LSH method of Andoni et al.\\ we can heuristically solve SVP in time and space $2^{0.2972n + o(n)}$. We further show that a practical variant of the resulting SphereSieve is very similar to Wang et al.\'s two-level sieve, with the key difference that we impose an order on the outer list of centers.

16:17 [Pub][ePrint] Analyzing Permutations for AES-like Ciphers: Understanding ShiftRows, by Christof Beierle and Philipp Jovanovic and Martin M. Lauridsen and Gregor Leander and Christian Rechberger

  Designing block ciphers and hash functions in a manner that resemble the AES in many aspects has been very popular since Rijndael was adopted as the Advanced Encryption Standard. However, in sharp contrast to the MixColumns operation, the security implications of the way the state is permuted by the operation resembling ShiftRows has never been studied in depth.

Here, we provide the first structured study of the influence of ShiftRows-like operations, or more generally, word-wise permutations, in AES-like ciphers with respect to diffusion properties and resistance towards differential- and linear attacks. After formalizing the concept of guaranteed trail weights, we show a range of equivalence results for permutation layers in this context. We prove that the trail weight analysis when using arbitrary word-wise permutations, with rotations as a special case, reduces to a consideration of a specific normal form. Using a mixed-integer linear programming approach, we obtain optimal parameters for a wide range of AES-like ciphers, and show improvements on parameters for Rijndael-192, Rijndael-256, PRIMATEs-80 and Prøst-128. As a separate result, we show for specific cases of the state geometry that a seemingly optimal bound on the trail weight can be obtained using cyclic rotations only for the permutation layer, i.e. in a very implementation friendly way.

16:17 [Pub][ePrint] Attribute-Based Versions of Schnorr and ElGamal, by Javier Herranz

  We design in this paper the first attribute-based cryptosystems that work in the classical Discrete Logarithm, pairing-free, setting. The attribute-based signature scheme can be seen as an extension of Schnorr signatures, with adaptive security relying on the Discrete Logarithm Assumption, in the random oracle model. The attribute-based encryption schemes can be seen as extensions of ElGamal cryptosystem, with adaptive security relying on the Decisional Diffie-Hellman Assumption, in the standard model.

The proposed schemes are secure only in a bounded model: the systems admit $L$ secret keys, at most, for a bound $L$ that must be fixed in the setup of the systems. The efficiency of the cryptosystems, later, depends on this bound $L$. Although this is an important drawback that can limit the applicability of the proposed schemes in some real-life applications, it turns out that the bounded security of our key-policy attribute-based encryption scheme (in particular, with $L=1$) is enough to implement the generic transformation of Parno, Raykova and Vaikuntanathan at TCC\'2012. As a direct result, we obtain a protocol for the verifiable delegation of computation of boolean functions, which does not employ pairings or lattices, and whose adaptive security relies on the Decisional Diffie-Hellman Assumption.

19:17 [Pub][ePrint] Key-Homomorphic Constrained Pseudorandom Functions, by Abhishek Banerjee and Georg Fuchsbauer and Chris Peikert and Krzysztof Pietrzak and Sophie Stevens

  A pseudorandom function (PRF) is a keyed function $F \\colon {\\cal

K}\\times{\\cal X}\\rightarrow {\\cal Y}$ where, for a random key

$k\\in{\\cal K}$, the function $F(k,\\cdot)$ is indistinguishable from a

uniformly random function, given black-box access. A

\\emph{key-homomorphic} PRF has the additional feature that for any

keys $k,k\'$ and any input $x$, we have $F(k + k\', x)= F(k,x) \\oplus

F(k\',x)$ for some group operations $+, \\oplus$ on $\\cal{K}$ and

$\\cal{Y}$, respectively. A \\emph{constrained} PRF for a family of

sets ${\\cal S} \\subseteq \\cal{P}({\\cal X})$ has the property that,

given any key $k$ and set $S \\in \\cal{S}$, one can efficiently compute

a ``constrained\'\' key $k_S$ that enables evaluation of $F(k,x)$ on all

inputs $x\\in S$, while the values $F(k,x)$ for $x \\notin S$ remain

pseudorandom even given $k_{S}$.

In this paper we construct PRFs that are simultaneously constrained

\\emph{and} key homomorphic, where the homomorphic property holds even

for constrained keys. We first show that the multilinear map-based

bit-fixing and circuit-constrained PRFs of Boneh and Waters (Asiacrypt

2013) can be modified to also be \\emph{key-homomorphic}. We then show

that the LWE-based key-homomorphic PRFs of Banerjee and Peikert

(Crypto 2014) are essentially already \\emph{prefix-constrained} PRFs,

using a (non-obvious) definition of constrained keys and associated

group operation. Moreover, the constrained keys themselves are

pseudorandom, and the constraining and evaluation functions can all be

computed in low depth.

As an application of key-homomorphic constrained PRFs, we construct a

proxy re-encryption scheme with fine-grained access control. This

scheme allows storing encrypted data on an untrusted server, where

each file can be encrypted relative to some attributes, so that only

parties whose constrained keys match the attributes can decrypt.

Moreover, the server can re-key (arbitrary subsets of) the ciphertexts

without learning anything about the plaintexts, thus permitting

efficient and fine-grained revocation.

19:17 [Pub][ePrint] Links among Impossible Differential, Integral and Zero Correlation Linear Cryptanalysis, by Bing Sun and Zhiqiang Liu and Vincent Rijmen and Ruilin Li and Lei Cheng and Qingju Wang and Hoda Alkhzaimi

  As two important cryptanalytic methods, impossible differential cryptanalysis and integral cryptanalysis have attracted much attention in recent years. Although relations among other important cryptanalytic approaches have been investigated, the link between these two methods has been missing. The motivation in this paper is to fix this gap and establish links between impossible differential cryptanalysis and integral cryptanalysis.

Firstly, by introducing the concept of structure and dual structure, we prove that $a\\rightarrow b$ is an impossible differential of a structure $\\mathcal E$ if and only if it is a zero correlation linear hull of the dual structure $\\mathcal E^\\bot$. More specifically, constructing a zero correlation linear hull of a Feistel structure with $SP$-type round function where $P$ is invertible, is equivalent to constructing an impossible differential of the same structure with $P^T$ instead of $P$. Constructing a zero correlation linear hull of an SPN structure is equivalent to constructing an impossible differential of the same structure with $(P^{-1})^T$ instead of $P$. Meanwhile, our proof shows that the automatic search tool presented by Wu and Wang could find all impossible differentials of both Feistel structures with $SP$-type round functions and SPN structures, which is useful in provable security of block ciphers against impossible differential cryptanalysis.

Secondly, by establishing some boolean equations, we show that a zero correlation linear hull always indicates the existence of an integral distinguisher while a special integral implies the existence of a zero correlation linear hull. With this observation we improve the integral distinguishers of Feistel structures by $1$ round, build a $24$-round integral distinguisher of CAST-$256$ based on which we propose the best known key recovery attack on reduced round CAST-$256$ in the non-weak key model, present a $12$-round integral distinguisher of SMS4 and an $8$-round integral distinguisher of Camellia without $FL/FL^{-1}$. Moreover, this result provides a novel way for establishing integral distinguishers and converting known plaintext attacks to chosen plaintext attacks.

Finally, we conclude that an $r$-round impossible differential of $\\mathcal E$ always leads to an $r$-round integral distinguisher of the dual structure $\\mathcal E^\\bot$. In the case that $\\mathcal E$ and $\\mathcal E^\\bot$ are linearly equivalent, we derive a direct link between impossible differentials and integral distinguishers of $\\mathcal E$. Specifically, we obtain that an $r$-round impossible differential of an SPN structure, which adopts a bit permutation as its linear layer, always indicates the existence of an $r$-round integral distinguisher. Based on this newly established link, we deduce that impossible differentials of SNAKE(2), PRESENT, PRINCE and ARIA, which are independent of the choices of the $S$-boxes, always imply the existence of integral distinguishers.

Our results could help to classify different cryptanalytic tools. Furthermore, when designing a block cipher, the designers need to demonstrate that the cipher has sufficient security margins against important cryptanalytic approaches, which is a very tough task since there have been so many cryptanalytic tools up to now. Our results certainly facilitate this security evaluation process.

19:17 [Pub][ePrint] Tweakable Blockciphers with Asymptotically Optimal Security, by Rodolphe Lampe and Yannick Seurin

  We consider tweakable blockciphers with beyond the birthday bound security. Landecker, Shrimpton, and Terashima (CRYPTO 2012) gave the first construction with security up to $\\mathcal{O}(2^{2n/3})$ adversarial queries ($n$ denotes the block size in bits of the underlying blockcipher), and for which changing the tweak does not require changing the keys for blockcipher calls. In this paper, we extend this construction, which consists of two rounds of a previous proposal by Liskov, Rivest, and Wagner (CRYPTO 2002), by considering larger numbers of rounds $r>2$. We show that asymptotically, as $r$ increases, the resulting tweakable blockcipher approaches security up to the information bound, namely $\\mathcal{O}(2^n)$ queries. Our analysis makes use of a coupling argument, and carries some similarities with the analysis of the iterated Even-Mansour cipher by

Lampe, Patarin, and Seurin (ASIACRYPT 2012).

19:17 [Pub][ePrint] New Links Between Differential and Linear Cryptanalysis, by Céline Blondeau and Kaisa Nyberg

  Recently, a number of relations have been established among previously known statistical attacks on block ciphers. Leander showed in 2011 that statistical saturation distinguishers are on average equivalent to multidimensional linear distinguishers. Further relations between these two types of distinguishers and the integral and zero-correlation distinguishers were established by Bogdanov et al.. Knowledge about

such relations is useful for classification of statistical attacks in order to determine those that give essentially complementary information about the security of block ciphers. The purpose of the work presented in this paper is to explore relations between differential and linear attacks. The mathematical link between linear and differential attacks was discovered by Chabaud and Vaudenay already in 1994, but it has never been used in practice. We will show how to use it for computing accurate estimatesof truncated differential probabilities from accurate estimates of correlations of linear approximations. We demonstrate this method in practice and give the first instantiation of multiple differential cryptanalysis using the LLR statistical test on PRESENT. On a more theoretical side,we establish equivalence between a multidimensional linear distinguisher and a truncated differential distinguisher, and show that certain zero-correlation linear distinguishers exist if and only if certain impossible differentials exist.