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] Protecting obfuscation against arithmetic attacks, by Eric Miles and Amit Sahai and Mor Weiss

  Recently, the work of Garg et al. (FOCS 2013) gave the first candidate general-purpose obfuscator. This construction is built upon multilinear maps, also called a graded encoding scheme. Several subsequent works have shown that variants of this obfuscator achieves the highest notion of security (VBB security) against \"purely algebraic\" attacks, namely attacks that respect the restrictions of the graded encoding scheme. While important, the scope of these works is somewhat limited due to the strong restrictions imposed on the adversary.

We propose and analyze another variant of the Garg et al. obfuscator in a setting that imposes fewer restrictions on the adversary that we call the arithmetic setting. This setting captures a broader class of algebraic attacks than considered in previous works. Most notably, it allows for unlimited additions across different \"levels\" of the encoding. In this setting, we present two results:

- First, in the arithmetic setting where the adversary is limited to creating only multilinear polynomials, we obtain an unconditional proof of VBB security.

- Second, in the arithmetic setting where the adversary can create polynomials of arbitrary degree, we prove VBB security under an assumption that is closely related to the Bounded Speedup Hypothesis of Brakerski and Rothblum (TCC 2014). We also give evidence that any unconditional proof of VBB security in this model would entail proving the algebraic analog of P \\neq NP.

21:17 [Pub][ePrint] Watch your Constants: Malicious Streebog, by Riham AlTawy and Amr M. Youssef

  In August 2012, the Streebog hash function was selected as the new Russian cryptographic hash standard (GOST R 34.11-2012). In this paper, we investigate the new standard in the context of malicious hashing and present a practical collision for a malicious version of the full hash function. In particular, we apply the rebound attack to find three solutions for three different differential paths for four rounds, and using the freedom of the round constants we connect them to obtain a collision for the twelve rounds of the compression function. Additionally, and due to the simple processing of the counter, we bypass the barrier of the checksum finalization step and transfer the compression function collision to the hash function output with no additional cost. The presented attack has a practical complexity and is verified by an example. While the results of this paper may not have a direct impact on the security of the current Streebog hash function, it presents an urge for the designers to publish the origin of the used parameters and the rational behind their choices in order for this function to gain enough confidence and wide spread adoption by the security community.

21:17 [Pub][ePrint] Sieving for Shortest Vectors in Ideal Lattices: a Practical Perspective, by Joppe W. Bos and Michael Naehrig and Joop van de Pol

  Lattice-based cryptography is a promising candidate for providing cryptographic functions that remain secure in a post-quantum era. The security of lattice-based schemes relies on the hardness of lattice problems such as the problem of finding short vectors in integral lattices. In this work, we propose a new variant of the parallel Gauss sieve algorithm which can compute such short vectors. Our algorithm combines favorable properties of previous approaches: all vectors in the global list remain pairwise Gauss reduced (reducing the list size and runtime) while this list is split up between the participating nodes (lowering the memory requirements per node). To demonstrate the benefits of this variant, we present an optimized implementation of our parallel algorithm, using commonly available vector instruction set extensions. We conducted experiments with lattices of dimensions 80, 88, and 96, and the results show that the new approach outperforms the previous parallel Gauss sieve algorithms. The implementation will be made available, and we hope that it will serve as a basis for additional experiments.

Almost all recent implementations of lattice-based cryptographic schemes use ideal lattices, and it is known that sieving algorithms can benefit from their additional algebraic structure. Namely, the list size can be reduced by considering vectors along with all their rotations. We show that ideal lattices allow more optimizations, which enhance the performance of sieving algorithms even further. We use the fast Fourier transform (FFT) to speed up the computation of inner products between a vector and the rotations of another. On a conventional, academic computer cluster, our algorithm solved an SVP ideal lattice challenge in a negacyclic ideal lattice of dimension 128 in less than nine days using 1024 cores. This is more than twice as fast as the recent computation by Ishiguro et al. that solved the same challenge on a cluster with the same computer architecture, but without using large shared memory. This indicates that the FFT version can lead to a practical performance increase compared to a naive version using only rotations. Our results shed additional light on the security of schemes which rely on the hardness of computing short vectors in this special setting.

21:17 [Pub][ePrint] Overview of the Candidates for the Password Hashing Competition -- And their Resistance against Garbage-Collector Attacks, by Stefan Lucks and Jakob Wenzel

  In this work we provide an overview of the candidates of the Password Hashing Competition (PHC) regarding to their functionality, e.g., client-independent update and server relief, their security, e.g., memory-hardness and side-channel resistance, and its general properties, e.g., memory usage and underlying primitives. Furthermore, we introduce two kinds of attacks, called Garbage-Collector and Weak Garbage-Collector Attack, exploiting the memory handling of a candidate. The following overview considers all candidates which are not yet withdrawn from the competition.

21:17 [Pub][ePrint] Obfuscation of Probabilistic Circuits and Applications, by Ran Canetti and Huijia Lin and Stefano Tessaro and Vinod Vaikuntanathan

  This paper studies the question of how to define, construct, and use obfuscators for probabilistic programs. Such obfuscators compile a possibly randomized program into a deterministic one, which achieves computationally indistinguishable behavior from the original program as long as it is run on each input at most once. For obfuscation, we propose a notion that extends indistinguishability obfuscation to probabilistic circuits: It should be hard to distinguish between the obfuscations of any two circuits whose output distributions at each input are computationally indistinguishable, possibly in presence of some auxiliary input. We call the resulting notion probabilistic indistinguishability obfuscation (pIO).

We define several variants of pIO, using different approaches to formalizing the above security requirement, and study non-trivial relations among them. Moreover, we give a construction of one of our pIO variants from sub-exponentially hard indistinguishability obfuscation (for deterministic circuits) and one-way functions, and conjecture this construction to be a good candidate for other pIO variants.

We then move on to show a number of applications of pIO:

* We give a general and natural methodology to achieve leveled homomorphic encryption (LHE) from variants of semantically secure encryption schemes and of pIO. In particular, we propose instantiations from lossy and re-randomizable encryption schemes, assuming the two weakest notions of pIO.

* We enhance the above constructions to obtain a full-fledged (i.e., non-leveled) FHE scheme under the same (or slightly stronger) assumptions. In particular, this constitutes the first construction of full-fledged FHE that does not rely on encryption with circular security.

* Finally, we show that assuming sub-exponentially secure puncturable PRFs computable in NC1, sub-exponentially-secure indistinguishability obfuscation for (deterministic) NC1 circuits can be bootstrapped to obtain indistinguishability obfuscation for arbitrary (deterministic) poly-size circuits.

21:17 [Pub][ePrint] Faulty Clock Detection for Crypto Circuits Against Differential Faulty Analysis Attack, by Pei Luo and Yunsi Fei

  Clock glitch based Differential Fault Analysis (DFA) attack is a serious threat to cryptographic devices. Previous error detection schemes for cryptographic devices target improving the circuit reliability and cannot resist such DFA attacks. In this paper, we propose a novel faulty clock detection method which can be easily implemented either in FPGAs or integrated circuits to detect the glitches in system clock. Results show that the proposed method can detect glitches efficiently while needs very few system resource. It is also highly reconfigurable to tolerant clock inherent jitters, and will not involve complex design work for different processing technologies.

18:17 [Pub][ePrint] UCE+LTDFs: Efficient, Subversion-Resistant PKE in the Standard Model, by Mihir Bellare and Viet Tung Hoang

  This paper provides the first efficient, standard-model, fully-secure schemes for some related and challenging forms of public-key encryption (PKE), namely deterministic and hedged PKE. These forms of PKE defend against subversion of random number generators, an end given new urgency by recent revelations on the nature and extent of such subversion. We resolve the (recognized) technical challenges in reaching these goals via a new paradigm that combines UCEs (universal computational extractors) with LTDFs (lossy trapdoor functions). Crucially, we rely only on a weak form of UCE, namely security for statistically (rather than computationally) unpredictable sources. We then define and achieve unique-ciphertext PKE as a way to defend against implementation subversion via algorithm-substitution attacks.

18:17 [Pub][ePrint] CM55: special prime-field elliptic curves almost optimizing den Boer\'s reduction between Diffie-Hellman and discrete logs, by Daniel R. L. Brown

  Using the Pohlig--Hellman algorithm, den Boer reduced the discrete logarithm problem to the Diffie--Hellman problem in groups of an order whose prime factors were each one plus a smooth number. This report reviews some related general conjectural lower bounds on the Diffie-Hellman problem in elliptic curve groups that relax the smoothness condition into a more commonly true condition.

This report focuses on some elliptic curve parameters defined over a prime field size of size 9+55(2^288), whose special form may provide some efficiency advantages over random fields of similar sizes. The curve has a point of Proth prime order 1+55(2^286), which helps to nearly optimize the den Boer reduction. This curve is constructed using the CM method. It has cofactor 4, trace 6, and fundamental discriminant -55.

This report also tries to consolidate the variety of ways of deciding between elliptic curves (or other algorithms) given the efficiency and security of each.

16:08 [Event][New] DBSec 2015: 29th IFIP WG11.3 Working Conf. on Data and Applications Security & Privacy

  Submission: 21 February 2015
Notification: 20 April 2015
From July 13 to July 15
Location: Fairfax, Virginia, USA
More Information:

16:02 [Job][New] Senior Cryptographic/Software Obfuscation Engineer, DARPA-i_SW Corp, Arlington, VA

  i_SW is looking for a Staff Scientist with a background in mathematics and cryptography to support a DARPA program focused on program obfuscation to protect DoD assets. Candidate will provide Scientific, Engineering and Technical Assistance (SETA) support to assist in the management and evaluation of the research underlying this effort. Candidate should have experience planning and developing technical projects of a research and development (R&D) nature, concerned with unique or controversial problems which have an important effect on major Department of Defense programs.

This work will be collaborative with DARPA and i_SW corporation located in Arlington, VA

Required Skills

• Demonstrated skill in successfully performing technical assignments including conducting research in problem areas of considerable scope and complexity requiring unconventional or novel approaches and sophisticated research techniques, risk analysis and resolution, tracking technical milestones, and report preparations

• Research focus on the theoretical sides of cryptography

• Demonstrated skill in conceiving, planning, and conducting research in problem areas of considerable scope and complexity requiring unconventional or novel approaches and sophisticated research techniques.

• Demonstrated the ability to independently conduct the appropriate analyses to offer recommendations, solutions, and alternatives to resolve R&D issues, concerns, problems, or methods.

Applicants must be US Citizens in order to obtain security clearances.


BS/MS Math or Computer Science

Some post-graduate work in mathematics and cryptography preferred.

03:55 [News] Video of IACR Distinguished Lecture

  The video of Mihir Bellare's IACR distinguished lecture at Crypto is now online.