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 get this service 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).

12:20 [Pub][JoC] A Single-Key Attack on the Full GOST Block Cipher


Abstract  The GOST block cipher is the Russian encryption standard published in 1989. In spite of considerable cryptanalytic efforts

over the past 20 years, a key recovery attack on the full GOST block cipher without any key conditions (e.g., weak keys and

related keys) has not been published yet. In this paper, we show the first single-key attack, which works for all key classes,

on the full GOST block cipher. To begin, we develop a new attack framework called Reflection-Meet-in-the-Middle Attack. This approach combines techniques of the reflection attack and the meet-in-the-middle (MITM) attack. Then we apply it to

the GOST block cipher employing bijective S-boxes. In order to construct the full-round attack, we use additional novel techniques

which are the effective MITM techniques using equivalent keys on a small number of rounds. As a result, a key can be recovered

with a time complexity of 2225 encryptions and 232 known plaintexts. Moreover, we show that our attack is applicable to the full GOST block cipher using any S-boxes, including

non-bijective S-boxes.

  • Content Type Journal Article
  • Pages 1-18
  • DOI 10.1007/s00145-012-9118-5
  • Authors

    • Takanori Isobe, Sony Corporation, 1-7-1 Konan, Minato-ku, Tokyo, 108-0075 Japan

    • Journal Journal of Cryptology
    • Online ISSN 1432-1378
    • Print ISSN 0933-2790

From: Wed, 01 Feb 2012 17:14:25 GMT

12:20 [Pub][JoC] On the Analysis of Cryptographic Assumptions in the Generic Ring Model


Abstract  The generic ring model considers algorithms that operate on elements of an algebraic ring by performing only the ring operations

and without exploiting properties of a given representation of ring elements. It is used to analyze the hardness of computational

problems defined over rings. For instance, it is known that breaking RSA is equivalent to factoring in the generic ring model

(Aggarwal and Maurer, Eurocrypt 2009). Do hardness results in the generic ring model support the conjecture that solving the considered problem is also hard in

the standard model, where elements of ℤ


are represented by integers modulo n?

We prove in the generic ring model that computing the Jacobi symbol of an integer modulo n is equivalent to factoring. Since there are simple and efficient non-generic algorithms which compute the Jacobi symbol,

this provides an example of a natural computational problem which is hard in the generic ring model, but easy to solve if

elements of ℤ


are given in their standard representation as integers. Thus, a proof in the generic ring model is unfortunately not a very

strong indicator for the hardness of a computational problem in the standard model.

Despite this negative result, generic hardness results still provide a lower complexity bound for a large class of algorithms,

namely all algorithms solving a computational problem independent of a given representation of ring elements. From this point

of view, results in the generic ring model are still interesting. Motivated by this fact, we also show that solving the quadratic

residuosity problem generically is equivalent to factoring.

  • Content Type Journal Article
  • Pages 1-21
  • DOI 10.1007/s00145-012-9120-y
  • Authors

    • Tibor Jager, Institut für Kryptographie und Sicherheit, Karlsruhe Institute of Technology, Karlsruhe, Germany
    • Jörg Schwenk, Horst Görtz Institute for IT Security, Ruhr-University Bochum, Bochum, Germany

    • Journal Journal of Cryptology
    • Online ISSN 1432-1378
    • Print ISSN 0933-2790

From: Thu, 08 Mar 2012 06:51:31 GMT

12:20 [Pub][JoC] A Note on the Bivariate Coppersmith Theorem


Abstract  In 1997, Coppersmith proved a famous theorem for finding small roots of bivariate polynomials over ℤ, with important applications

to cryptography.

While it seems to have been overlooked until now, we found the proof of the most commonly cited version of this theorem to

be incomplete. Filling in the gap requires technical manipulations which we carry out in this paper.

  • Content Type Journal Article
  • Pages 1-5
  • DOI 10.1007/s00145-012-9121-x
  • Authors

    • Jean-Sébastien Coron, Université du Luxembourg, 6, rue Richard Coudenhove-Kalergi, 1359 Luxembourg, Luxembourg
    • Alexey Kirichenko, F-Secure Corporation, Tammasaarenkatu 7, PL 24, 00181 Helsinki, Finland
    • Mehdi Tibouchi, NTT Information Sharing Platform Laboratories, 3-9-1 Midori-cho, Musashino-shi, Tokyo, 180-8585 Japan

    • Journal Journal of Cryptology
    • Online ISSN 1432-1378
    • Print ISSN 0933-2790

From: Tue, 20 Mar 2012 16:51:58 GMT

12:20 [Pub][JoC] Mercurial Commitments with Applications to Zero-Knowledge Sets


Abstract  We introduce a new flavor of commitment schemes, which we call mercurial commitments. Informally, mercurial commitments are standard commitments that have been extended to allow for soft decommitment. Soft decommitments, on the one hand, are not binding but, on the other hand, cannot be in conflict with true


We then demonstrate that a particular instantiation of mercurial commitments has been implicitly used by Micali, Rabin and

Kilian to construct zero-knowledge sets. (A zero-knowledge set scheme allows a Prover to (1) commit to a set S in a way that reveals nothing about S and (2) prove to a Verifier, in zero-knowledge, statements of the form xS and xS.) The rather complicated construction of Micali et al. becomes easy to understand when viewed as a more general construction

with mercurial commitments as an underlying building block.

By providing mercurial commitments based on various assumptions, we obtain several different new zero-knowledge set constructions.

  • Content Type Journal Article
  • Pages 1-29
  • DOI 10.1007/s00145-012-9122-9
  • Authors

    • Melissa Chase, Microsoft Research, Redmond, WA 98052, USA
    • Alexander Healy, Division of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138, USA
    • Anna Lysyanskaya, Department of Computer Science, Brown University, Providence, RI 02912, USA
    • Tal Malkin, Department of Computer Science, Columbia University, New York, NY 10027, USA
    • Leonid Reyzin, Department of Computer Science, Boston University, Boston, MA 02215, USA

    • Journal Journal of Cryptology
    • Online ISSN 1432-1378
    • Print ISSN 0933-2790

From: Wed, 28 Mar 2012 05:59:34 GMT