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

08:59 [Job][Update] Post-Doc, University of Athens, Greece

  We are looking for a Post-Doc in cryptography. Contact us if you have (or about to receive) a Ph.D. in cryptography (or very related subject), an excellent publication record that includes IACR conferences and you want to work in a fun environment in Athens - Greece.

Funding is through the European Research Council project CODAMODA. More information about the Crypto.Sec group at the National and Kapodistrian University of Athens can be found here

Applications will be considered immediately. The position is for 1 year with the possibility of renewal. Salary is competitive.

21:17 [Pub][ePrint] On secret sharing with nonlinear product reconstruction, by Ignacio Cascudo and Ronald Cramer and Diego Mirandola and Carles Padro and Chaoping Xing

  Multiplicative linear secret sharing is a fundamental notion in the area of secure multi-party computation (MPC) and,

since recently, in the area of two-party cryptography as well. In a nutshell, this notion guarantees that

``the product of two secrets is obtained as a linear function of the vector consisting of the

coordinate-wise product of two respective share-vectors\'\'. This paper focuses on the following foundational question, which is novel to the best of our knowledge. Suppose we {\\em abandon the latter linearity condition} and instead require that this product is obtained by {\\em some},

not-necessarily-linear ``product reconstruction function\'\'. {\\em Is the resulting notion equivalent to

multiplicative linear secret sharing?} We show the (perhaps somewhat counter-intuitive) result that this relaxed notion is strictly {\\em more general}.

Concretely, fix a finite field $\\FF_q$ as the base field $\\FF_q$ over which linear secret sharing is considered.

Then we show there exists an (exotic) linear secret sharing scheme with an unbounded number of players $n$

such that it has $t$-privacy with $t\\approx \\sqrt{n}$

and such that it does admit a product reconstruction function, yet this function is {\\em necessarily} nonlinear. Our proof is based on

combinatorial arguments involving bilinear forms. It extends to similar separation results for important variations,

such as strongly multiplicative secret sharing.

21:17 [Pub][ePrint] A Comparison of Double Point Multiplication Algorithms and their Implementation over Binary Elliptic Curves, by Reza Azarderakhsh and Koray Karabina

  Efficient implementation of double point multiplication is crucial for elliptic curve cryptographic systems. We revisit three recently proposed simultaneous double point multiplication algorithms. We propose hardware architectures for these algorithms, and provide a comparative analysis of their performance. We implement the proposed architectures on Xilinx Virtex-4 FPGA, and report on the area and time results . Our results indicate that differential addition chain based algorithms are better suited to compute double point multiplication over binary elliptic curves for both high performance and resource constrained applications.

21:17 [Pub][ePrint] Improvement of One Anonymous Identity-Based Encryption, by Zhengjun Cao and Lihua Liu

  In 2009, Seo et al. proposed an anonymous hierarchical identity-based

encryption (IBE). The ciphertext consists of $(C_1, C_2, C_3, C_4)$, where $C_1$ is the blinded message, $C_4$ is the blinded identity,

both $C_2$ and $C_3$ are used as decrypting helpers. To prove its security, the authors defined five games and introduced a strong simulator who is able to select different Setups for those games.

In this paper, we optimize the IBE scheme by removing one decrypting helper and the strong simulator. We show its security under the $\\ell$-computational Diffie-Hellman assumption with a normal simulator who only requires a unique Setup.

21:17 [Pub][ePrint] A Formal Proof of Countermeasures against Fault Injection Attacks on CRT-RSA, by Pablo Rauzy and Sylvain Guilley

  In this article, we describe a methodology that aims at either breaking or proving the security of CRT-RSA algorithms against fault injection attacks. In the specific case-study of BellCoRe attacks, our work bridges a gap between formal proofs and implementation-level attacks. We apply our results to three versions of CRT-RSA, namely the naive one, that of Shamir, and that of Aumüller et al. Our findings are that many attacks are possible on both the naive and the Shamir implementations, while the implementation of Aumüller et al. is resistant to all fault attacks with one fault. However, we show that the countermeasure is not minimal, since two tests out of seven are redundant and can simply be removed.

21:17 [Pub][ePrint] SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge, by Eli Ben-Sasson and Alessandro Chiesa and Daniel Genkin and Eran Tromer and Madars Virza

  An argument system for NP is a proof system that allows efficient verification of NP statements, given proofs produced by an untrusted yet computationally-bounded prover. Such a system is non-interactive and publicly-verifiable if, after a trusted party publishes a proving key and a verification key, anyone can use the proving key to generate non-interactive proofs for adaptively-chosen NP statements, and proofs can be verified by anyone by using the verification key.

We present an implementation of a publicly-verifiable non-interactive argument system for NP. The system, moreover, is a zero-knowledge proof-of-knowledge. It directly proves correct executions of programs on TinyRAM, a random-access machine tailored for efficient verification of nondeterministic computations. Given a program $P$ and time bound T, the system allows for proving correct execution of $P$, on any input $x$, for up to T steps, after a one-time setup requiring $\\tilde{O}(|P| T)$ cryptographic operations. An honest prover requires $\\tilde{O}(|P| \\cdot T)$ cryptographic operations to generate such a proof, while proof verification can be performed with only $O(|x|)$ cryptographic operations. This system can be used to prove the correct execution of C programs, using our TinyRAM port of the GCC compiler.

This yields a zero-knowledge Succinct Non-interactive ARgument of Knowledge (zk-SNARK) for program executions in the preprocessing model -- a powerful solution for delegating NP computations, with several features not achieved by previously-implemented primitives.

Our approach builds on recent theoretical progress in the area. We present efficiency improvements and implementations of two main ingredients:

* Given a C program, we produce a circuit whose satisfiability encodes the correctness of execution of the program. Leveraging nondeterminism, the generated circuit\'s size is merely quasilinear in the size of the computation. In particular, we efficiently handle arbitrary and data-dependent loops, control flow, and memory accesses. This is in contrast with existing ``circuit generators\'\', which in the general case produce circuits of quadratic size.

* Given a linear PCP for verifying satisfiability of circuits, we produce a corresponding SNARK. We construct such a linear PCP (which, moreover, is zero-knowledge and very efficient) by building on and improving on recent work on quadratic arithmetic programs.

21:17 [Pub][ePrint] Multi-Key Searchable Encryption, by Raluca Ada Popa and Nickolai Zeldovich

  We construct a searchable encryption scheme that enables keyword search over data encrypted with {\\em different} keys. The scheme is practical and was designed to be included in a new system for protecting data confidentiality in client-server applications against attacks on the server.

21:17 [Pub][ePrint] Replacing a Random Oracle: Full Domain Hash From Indistinguishability Obfuscation, by Susan Hohenberger and Amit Sahai and Brent Waters

  Our main result gives a way to instantiate the

random oracle with a concrete hash function in

\"full domain hash\" applications.

The term full domain hash was first proposed by Bellare and

Rogaway and referred to a signature scheme from any

trapdoor permutation that was part of their seminal work introducing

the random oracle heuristic. Over time the term full domain hash has

informally encompassed a broader range of notable cryptographic

schemes including the Boneh-Franklin IBE scheme and

Boneh-Lynn-Shacham (BLS) signatures.

All of the above described schemes required a hash function that had

to be modeled as a random oracle to prove security. Our work utilizes

recent advances in indistinguishability obfuscation to construct

specific hash functions for use in these schemes. We then prove

security of the original cryptosystems when instantiated with

our specific hash function.

Of particular interest, our work evades the impossibility result of

Dodis, Oliveira, and Pietrzak, who showed that there can

be no black-box construction of hash functions that allow Full-Domain

Hash Signatures to be based on trapdoor permutations. This indicates

that our techniques applying indistinguishability obfuscation may be

useful in the future for circumventing other such black-box

impossibility proofs.

21:17 [Pub][ePrint] Discrete Ziggurat: A Time-Memory Trade-off for Sampling from a Gaussian Distribution over the Integers, by Johannes Buchmann and Daniel Cabarcas and Florian Göpfert and Andreas Hülsing and Patrick W

  Several lattice-based cryptosystems require to sample from a discrete Gaussian distribution over the integers. Existing methods to sample from such a distribution either need large amounts of memory or they are very slow. In this paper we explore a different method that allows for a flexible time-memory trade-off, offering developers freedom in choosing how much space they can spare to store precomputed values. We prove that the generated distribution is close enough to a discrete Gaussian to be used in lattice-based cryptography. Moreover, we report on an implementation of the method and compare its performance to existing methods from the literature. We show that for large standard deviations, the Ziggurat algorithm outperforms all existing methods.

21:17 [Pub][ePrint] Low Data Complexity Biclique Cryptanalysis of Block Ciphers with Application to Piccolo and HIGHT, by Siavash Ahmadi, Zahra Ahmadian, Javad Mohajeri, and Mohammad Reza Aref

  In this paper, we present a framework for biclique cryptanalysis of block ciphers with an extremely low data complexity. To that end, we enjoy a new representation of biclique attack. Then an algorithm for choosing two dierential characteristics is also presented to simultaneously minimize the data complexity and control the computational complexity.

Then we characterize those block ciphers that are vulnerable to this technique and among them, we apply this attack on lightweight block ciphers Piccolo-80, Piccolo-128 and HIGHT. The data complexities of these attacks are considerably less than the existing results. For full-round Piccolo-80 and 128, the data complexity of the attacks are only 16

plaintext-ciphertext pairs and for full-round HIGHT our attack requires

256 pairs. In all attacks the computational complexity remains the same

as the previous ones or even it is slightly improved.

21:17 [Pub][ePrint] Rounding LLL: Finding Faster Small Roots of Univariate Polynomial Congruences , by Jingguo Bi and Phong Q. Nguyen

  In a seminal work at EUROCRYPT \'96, Coppersmith showed how to find all small roots of a univariate polynomial congruence in polynomial time:

this has found many applications in public-key cryptanalysis and in a few security proofs.

However, the running time of the algorithm is a high-degree polynomial,

which limits experiments:

the bottleneck is an LLL reduction of a high-dimensional matrix with extra-large coefficients.

We present in this paper a polynomial speedup over Coppersmith\'s algorithm.

Our improvement is based on a special property of the matrices used by Coppersmith\'s algorithm,

which allows us to speed up the LLL reduction by rounding.

The exact speedup depends on the LLL algorithm used: for instance, the speedup is quadratic

in the bit-size of the small-root bound if one uses the Nguyen-Stehl\\\'e L^2 algorithm.