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).

21:17 [Pub][ePrint] An algorithm for MD5 single-block collision attack using high-performance computing cluster, by Anton A. Kuznetsov

  The parallel algorithm and its implementation for performing a single-block collision attack on MD5 are described. The algorithm is implemented as MPI program based upon the source code of Dr Marc Stevens\' collision search sequential program. In this paper we present a parallel single-block MD5 collision searching algorithm itself and details of its implementation. We also disclose a pair of new single-block messages colliding under MD5 that were found using our algorithm on the high-performance computing cluster.

21:17 [Pub][ePrint] Recent Results in Scalable Multi-Party Computation, by Jared Saia and Mahdi Zamani

  Secure multi-party computation (MPC) allows multiple parties to compute a known function over inputs held by each party, without any party having to reveal its private input. Unfortunately, traditional MPC algorithms do not scale well to large numbers of parties. In this paper, we describe several recent MPC algorithms that are designed to handle large networks. All of these algorithms rely on recent techniques from the Byzantine agreement literature on forming and using quorums. Informally, a quorum is a small set of parties, most of which are trustworthy. We describe the advantages and disadvantages of these scalable algorithms, and we propose new ideas for improving practicality of current techniques. Finally, we conduct simulations to measure bandwidth cost for several current MPC algorithms.

21:17 [Pub][ePrint] Bootstrapping for HElib, by Shai Halevi and Victor Shoup

  Gentry\'s bootstrapping technique is still the only known method of obtaining fully homomorphic encryption where the system\'s parameters do not depend on the complexity of the evaluated functions. Bootstrapping involves a recryption procedure where the scheme decryption is evaluated homomorphically. So far, there have been precious few implementations of recryption, and none that could handle

\"packed ciphertexts\" that encrypt vectors of elements.

In the current work we implemented recryption of fully-packed ciphertexts using the HElib library for somewhat-homomorphic encryption. This required extending the recryption algorithms from the literature, as well as many aspects of the HElib library.

Our implementation supports bootstrapping of packed ciphertexts over

many extension fields/rings. One example that we tested involves

ciphertexts that encrypt vectors of 1024 elements from GF(2^{16}). In that setting, the recryption procedure takes under 5.5 minutes (at security-level ~ 76) on a single core, and allows a depth-9

computation before the next recryption is needed.

20:56 [Job][New] PhD student, Chalmers University of Technology, Sweden

  PhD position in Secure and Private Machine Learning and Decision Making

at the Department of Computer Science and Engineering, Chalmers University of Technology

Application deadline: November 21, 2014

Expected starting date: January 2015

Job description

We are looking for an excellent, motivated, self-driven doctoral student to work in the area of machine learning and decision theory with a focus on security and privacy. The position is for five years at the Department of Computer Science and Engineering, within the division of Computing Science and the group of Algorithms, Learning and Computational Biology (, who are doing research on fields ranging from machine learning, statistics, algorithms, optimisation, reinforcement learning to computational biology, text and massive data analysis.

The student will be expected to develop and analyse state-of-the-art algorithms for distributed machine learning and decision making that provide users with strong privacy guarantees. In particular, the research will be focused on machine learning and differential privacy for distributed systems, but some aspects of the work will involve recent advances in cryptography. The student will be supervised by Dr. Christos Dimitrakakis (Machine learning, decision theory and differential privacy - see ) and co-supervised by Dr. Katerina Mitrokotsa (Cryptography and security - see ).

Employment will be in the scope of the Swiss Sense Synergy project, whose aim is to develop intelligent location-based networking protocols and crowdsourcing applications, in collaboration with three Swiss universities. Further info about the Swiss Sense Synergy project can be found here

Details about Employment

PhD student positions are limited to five years and no

18:17 [Pub][ePrint] BRUTUS: Identifying Cryptanalytic Weaknesses in CAESAR First Round Candidates, by Markku-Juhani O. Saarinen

  This ``half-year\'\' report summarizes our results from security

analysis covering all 57 CAESAR first round candidates. We have manually

identified security issues with three candidates, two of which are

more serious, and these ciphers been withdrawn from the competition.

We have developed a testing

framework, BRUTUS, to facilitate automatic detection of simple security

lapses and susceptible statistical structures across all ciphers.

From this testing we have security usage notes on four submissions and

statistical notes on a further four. We highlight that some of the CAESAR

algorithms pose an elevated risk if employed in real-life protocols due

to a class of adaptive chosen plaintext attacks. Although AEADs are often

defined (and are best used) as discrete primitives that authenticate and

transmit only complete messages, in practice these algorithms are

easily implemented in a fashion that outputs observable ciphertext data

when the algorithm has not received all of the (attacker-controlled)

plaintext. For an implementor, this strategy

appears to offer seemingly harmless and compliant storage and latency

advantages. If the algorithm uses the same state for secret

keying information, encryption, and integrity protection, and the

internal mixing permutation is not cryptographically strong, an attacker

can exploit the ciphertext-plaintext feedback loop to to reveal secret

state information or even keying material. We conclude that

the main advantages of exhaustive, automated cryptanalysis is that it

acts as a very necessary sanity check for implementations and gives the

cryptanalyst insights that can be used to focus more specific attack

methods on given candidates.

18:17 [Pub][ePrint] Near Optimal Rate Homomorphic Encryption for Branching Programs, by Aggelos Kiayias and Nikos Leonardos and Helger Lipmaa and Kateryna Pavlyk and Qiang Tang

  We initiate the study of good rate homomorphic encryption schemes.

Based on previous work on securely evaluating (binary I/O) branching programs, we propose a leveled homomorphic encryption scheme

for {\\em large-output} polynomial-size branching programs (which we call $\\mathbf{L/poly}$) that possesses near optimal-rate. The rate analysis of the new scheme is intricate: the best rate is achieved if a certain parameter $s$ is set equal to the only positive root of a degree-$m$ polynomial, where $m$ is the length of the branching program. We employ the Newton-Puiseux algorithm to find a Puiseux series for this parameter, and based on this, propose a $\\Theta (\\log m)$-time algorithm to find an integer approximation to $s$.

We also describe a rate-optimal 1-out-of-$n$ CPIR based on rate-optimal homomorphic encryption. In concrete terms, when applied to say, a movie database with $n = 2^{16}$ elements of $\\ell = 3.8 \\cdot 10^{9}$-bits, the client can privately download a movie with a communication rate of almost $0.99$, hence sacrificing only about $1\\%$ of bandwidth for privacy.

We also analyze the optimality of the rate efficiency of our scheme in a novel model that may be of independent interest. Our $1$-out-of-$n$ CPIR has rate $ 1- 1.72 \\sqrt{k / \\ell} \\cdot \\log_{2} n + O_\\ell(\\ell^{-1})$, while we show that no black-box construction surpasses $1 - \\sqrt{k / \\ell} (\\log n/ \\log \\log n) + O_\\ell(\\ell^{-1})$ in terms of rate, where $\\ell$ is the length of the database elements and $k$ the security parameter.

18:17 [Pub][ePrint] Faster ECC over $\\mathbb{F}_{2^{521}-1}$, by Robert Granger and Michael Scott

  In this paper we present a new multiplication algorithm for residues modulo the Mersenne prime $2^{521} - 1$.

Using this approach, on an Intel Haswell Core i7-4770, constant-time variable-base scalar multiplication on NIST\'s (and SECG\'s) curve P-521 requires $989,000$ cycles, while on the recently proposed Edwards curve E-521 it requires just $779,000$ cycles. As a comparison, on the same architecture openSSL\'s ECDH speed test for curve P-521 requires $1,319,000$ cycles.

Furthermore, our code was written entirely in C with no non-compiler optimisations and so is robust across different platforms.

The basic observation behind these speedups is that the form of the modulus allows

one to multiply residues with as few word-by-word multiplications as is needed for squaring, while incurring very

little overhead from extra additions, in contrast to the usual Karatsuba methods.

18:17 [Pub][ePrint] Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation, by David Cash and Joseph Jaeger and Stanislaw Jarecki and Charanjit Jutla and Hugo Krawczyk and Marcel-Cătă

  We design and implement dynamic symmetric searchable encryption schemes that efficiently and privately search server-held encrypted databases with tens of billions of record-keyword pairs. Our basic theoretical construction supports single-keyword searches and offers asymptotically optimal server index size, fully parallel searching, and minimal leakage. Our implementation effort brought to the fore several factors ignored by earlier coarse-grained theoretical performance analyses, including low-level space utilization, I/O parallelism and goodput. We accordingly introduce several optimizations to our theoretically optimal construction that model the prototype\'s characteristics designed to overcome these factors. All of our schemes and optimizations are proven secure and the information leaked to the untrusted server is precisely quantified. We evaluate the performance of our prototype using two very large datasets: a synthesized census database with 100 million records and hundreds of keywords per record and a multi-million webpage collection that includes Wikipedia as a subset. Moreover, we report on an implementation that uses the dynamic SSE schemes developed here as the basis for supporting recent SSE advances, including complex search queries (e.g., Boolean queries) and richer operational settings (e.g., query delegation), in the above terabyte-scale databases.

18:17 [Pub][ePrint] Power Analysis Attack on Hardware Implementation of MAC-Keccak on FPGAs, by Pei Luo, Yunsi Fei, Xin Fang, A. Adam Ding, Miriam Leeser, and David R. Kaeli

  Keccak is the hash function selected by NIST as the new SHA-3 standard. Keccak is built on Sponge construction and it provides a new MAC function called MAC-Keccak. These new algorithms have raised questions with regards to side-channel leakage and analysis attacks of MAC-Keccak. So far there exists prior work on attacks of software implementations of MAC-Keccak, but there has been no comprehensive side-channel vulnerability assessment of its hardware implementation. In this paper we describe an attack on the $\\theta$ step of the first round of MAC-Keccak implemented on an FPGA. We construct several different side-channel leakage models and implement attacks based on them. Our work shows that an unmasked hardware implementation of SHA-3 is vulnerable to power-based side-channel attacks.

18:17 [Pub][ePrint] Relating Undisturbed Bits to Other Properties of Substitution Boxes, by Rusydi H. Makarim and Cihangir Tezcan

  Recently it was observed that for a particular nonzero input difference to an S-Box, some bits in all the corresponding output differences may remain invariant. These specific invariant bits are called undisturbed bits. Undisturbed bits can also be seen as truncated differentials with probability 1 for an S-Box. The existence of undisturbed bits was found in the S-Box of PRESENT and its inverse. A 13-round improbable differential attack on PRESENT was provided by Tezcan and without using the undisturbed bits in the S-Box an attack of this type can only reach 7 rounds. Although the observation and the cryptanalytic application of undisturbed bits are given, their relation with other properties of an S-Box remain unknown. This paper presents some results on mathematical properties of S-Boxes having undisturbed bits. We show that an S-Box has undisturbed bits if any of its coordinate functions has a nontrivial linear structure. The relation of undisturbed bits with other cryptanalytic tools such as difference distribution table (DDT) and linear approximation table (LAT) are also given. We show that autocorrelation table is proven to be a more useful tool, compared to DDT, to obtain all nonzero input differences that yield undisturbed bits. Autocorrelation table can then be viewed as a counterpart of DDT for truncated differential cryptanalysis. Given an nxm balanced S-Box, we state that the S-Box has undisturbed bits whenever the degree of any of its coordinate function is quadratic.

15:17 [Pub][ePrint] Reflections on Slide with a Twist Attacks, by Itai Dinur and Orr Dunkelman and Nathan Keller and Adi Shamir

  Slide attacks use pairs of encryption operations which are slid against each other. Slide with a twist attacks are more sophisticated

variants of slide attacks which slide an encryption operation against a decryption operation, and were used in 2000 to attack several cryptosystems, including DESX, the Even-Mansour construction, and Feistel structures with four-round self-similarity. They were further extended in 2012 to the mirror slidex framework, which was used to attack 20-round GOST and several additional variants of the Even-Mansour construction. In this paper, we revisit all the previously published applications of these techniques and show that in almost all cases, the same or better results can be achieved

by a simpler attack which is based on the seemingly unrelated idea of exploiting their internal fixed points. The observation that such fixed points can be useful in cryptanalysis had already been pointed out in 2007 by Kara, but all the examples he gave for his reflection attack were based on particular constructions such as Feistel structures or GOST key schedules in which it was easy to explicitly

list and count their fixed points.

In this paper, we generalize Kara\'s reflection attack by using the combinatorial result that random involutions on 2^n values are expected to have a surprisingly large number of O(2^{n/2}) fixed points (whereas random permutations are expected to have only O(1) fixed points). This makes it possible to reduce the complexity of the best known attack on additional cryptographic schemes in which it is difficult to explicitly characterize and count their internal fixed points.