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

09:17 [Pub][ePrint] Folding Alternant and Goppa Codes with Non-Trivial Automorphism Groups, by Jean-Charles Faugère and Ayoub Otmani and Ludovic Perret and Frédéric de Portzamparc and Jean-Pierre Tillich

  The main practical limitation of the McEliece public-key encryption scheme is probably the size of its key. A famous trend to overcome this issue is to focus on subclasses of alternant/Goppa codes with a non trivial automorphism group. Such codes display then symmetries allowing compact parity-check or generator matrices. For

instance, a key-reduction is obtained by taking quasi-cyclic (QC) or quasi-dyadic (QD) alternant/Goppa codes.

We show that the use of such symmetric alternant/Goppa codes in cryptography introduces a fundamental weakness. It is indeed possible to reduce the key-recovery on the original symmetric public-code to the key-recovery on a (much) smaller code that has not anymore symmetries. This result is obtained thanks to a new operation on codes called folding that exploits the knowledge of the automorphism group. This operation consists in adding the coordinates of codewords which belong to the same orbit under the action of the automorphism group. The advantage is twofold:

the reduction factor can be as large as the size of the orbits, and it preserves a fundamental property: folding the dual of an alternant (resp. Goppa) code provides the dual of an alternant (resp. Goppa) code. A key point is to show that all the existing constructions of alternant/Goppa codes with symmetries follow a common principal of taking codes whose support is globally invariant under the action of affine transformations (by building upon prior works of T. Berger and A. D¨ur). This enables not only to present a unified view but also to generalize the construction of QC, QD and even quasi-monoidic (QM) Goppa codes. All in all, our results can be harnessed to boost up any key-recovery attack on McEliece systems based on symmetric alternant or Goppa codes, and in particular algebraic attacks.

09:17 [Pub][ePrint] Optimizing Information Set Decoding Algorithms to Attack Cyclosymmetric MDPC Codes, by Ray Perlner

  The most important drawback to code-based cryptography has historically been its large key sizes. Recently, several promising approaches have been proposed to reduce keysizes. In particular, significant keysize reduction has been achieved by using structured, but non-algebraic codes, such as quasi-cyclic (QC) Moderate Density Parity Check (MDPC) codes. Biasi et al. propose further reducing the keysizes of code-based schemes using cyclosymmetric (CS) codes. Biasi et al analyze the complexity of attacking their scheme against standard information-set-decoding attacks. However, the research presented here shows that information set decoding algorithms can be modified, by choosing the columns of the information set in a way that takes advantage of the added symmetry. The result is an attack that significantly reduces the security of the proposed CS-MDPC schemes to the point that they no longer offer an advantage in keysize over QC-MDPC schemes of the same security level.

09:17 [Pub][ePrint] Graph-theoretic design and analysis of key predistribution schemes, by Michelle Kendall and Keith M. Martin

  Key predistribution schemes for resource-constrained networks are methods for allocating symmetric keys to devices in such a way as to provide an efficient trade-off between key storage, connectivity and resilience. While there have been many suggested constructions for key predistribution schemes, a general understanding of the design principles on which to base such constructions is somewhat lacking. Indeed even the tools from which to develop such an understanding are currently limited, which results in many relatively ad hoc proposals in the research literature.

It has been suggested that a large edge-expansion coefficient in the key graph is desirable for efficient key predistribution schemes. However, attempts to create key predistribution schemes from known expander graph constructions have only provided an extreme in the trade-off between connectivity and resilience: namely, they provide perfect resilience at the expense of substantially lower connectivity than can be achieved with the same key storage.

Our contribution is two-fold. First, we prove that many existing key predistribution schemes produce key graphs with good expansion.

This provides further support and justification for their use, and confirms the validity of expansion as a sound design principle. Second, we propose the use of incidence graphs and concurrence graphs as tools to represent, design and analyse key predistribution schemes. We show that these tools can lead to helpful insights and new constructions.

09:17 [Pub][ePrint] Fully Key-Homomorphic Encryption, Arithmetic Circuit ABE, and Compact Garbled Circuits, by Dan Boneh and Craig Gentry and Sergey Gorbunov and Shai Halevi and Valeria Nikolaenko and Gil Segev and Vinod

  We construct the first (key-policy) attribute-based encryption (ABE) system with short secret keys: the size of keys in our system depends only on the depth of the policy circuit, not its size. Our constructions extend naturally to arithmetic circuits with arbitrary fan-in gates thereby further reducing the circuit depth. Building on this ABE system we obtain the first reusable circuit garbling scheme that produces garbled circuits whose size is the same as the original circuit {\\em plus} an additive $\\mathsf{poly}(\\secp,d)$ bits, where $\\secp$ is the security parameter and $d$ is the circuit depth. Save the additive $\\mathsf{poly}(\\secp,d)$ factor, this is the best one could hope for. All previous constructions incurred a {\\em multiplicative} $\\mathsf{poly}(\\secp)$ blowup. As another application, we obtain (single key secure) functional encryption with short secret keys.

We construct our attribute-based system using a mechanism we call {\\em fully key-homomorphic encryption} which is a public-key system that lets anyone translate a ciphertext encrypted under a public-key~$\\vx$ into a ciphertext encrypted under the public-key~$(f(\\vx),f)$ of the same plaintext, for any efficiently computable~$f$. We show that this mechanism gives an ABE with short keys. Security is based on the subexponential hardness of the learning with errors problem.

We also present a second (key-policy) ABE, using multilinear maps, with short ciphertexts: an encryption to an attribute vector~$\\vx$ is the size of $\\vx$ plus $\\mathsf{poly}(\\secp,d)$ additional bits. This gives a reusable circuit garbling scheme where the size of the garbled input is short, namely the same as that of the original input, {\\em plus} a $\\mathsf{poly}(\\secp,d)$ factor.

09:17 [Pub][ePrint] Making and Breaking Leakage Simulators, by Jake Longo Galea and Daniel Martin and Elisabeth Oswald and Daniel Page and Martijn Stam

  Recently, Standaert et al. (Crypto\'13) advocated the notion of simulatable leakage

as a means to connect theoretical leakage resilience to practice.

They argued that using simulators based on actual physical devices, the

assumptions underlying their proofs of side channel resistance

become empirically `verifiable\' as evaluation labs can scrutinise the indistinguishability

of the simulator by actually `playing\' the games that involve real versus simulated leakage.

Standaert \\emph{et al.} proposed a concrete, block cipher based instantiation of a leakage

resilient pseudorandom generator. They provided a high level definition of a simulator based

on splicing two partial traces, and included detailed reasoning why their simulator (for AES-128) would resist state-of-the-art side channel attacks.

We exhibit a distinguisher against their simulator, thereby falsifying their hypothesis.

We demonstrate the efficacy of our distinguishing technique by experimental validation

using concrete implementations of the Standaert \\emph{et al.} simulator on several different platforms.

Our successful analysis is based on `tracking\' consistency (and likewise spotting simulator

inconsistencies) in leakage traces by means of cross correlation.

By taking the cross correlation between trace points, we can estimate real-or-simulated based either on a single key that is used multiple times, or based on multiple runs of

Standaert\'s \\emph{et al.} security game with varying keys each used only once.

Since the game hybridizes (in the number of keys used), the latter implies that theoretically

our distinguisher already wins when a single key is used with a single trace of side channel leakage!

Finally, we propose several alternative simulators, based on splitting traces at points of low intrinsic cross-correlation, which are more promising w.r.t.~the cross-correlation distinguisher. Unfortunately, these new simulators come with significant caveats, and we conclude that the most natural way of producing simulated leakage is by using the underlying construction `as is\' (but with a random key).

Provided the actual implementation has a low signal-to-noise ratio, we believe it practically infeasible to distinguish between real and simulated traces: when only a few very noisy leakages are made available to an attacker, signal processing techniques that rely on having sufficient observations are not applicable.

10:16 [Job][New] Lecturer (Assistant/Associate Professor equivalent), University of Bristol, United Kingdom of Greater Britan and Norther Ireland, EU

  Four positions in Computer Science

  • Two in any area of CS

  • One in theory and algorithms

  • One in HCI

You will have demonstrated that you are on track to become an outstanding researcher, carrying out innovative research to complement that currently being pursued in the Department. You will have already achieved international recognition and have a significant number of high quality publications in top venues. Our strategy is to grow our research portfolio and you will be expected to take a major role in achieving that goal.

In addition, you will be expected to take an active role in providing high quality and innovative teaching in areas of Computer Science according to your experience. We are looking to enhance our teaching in core computer science; both theoretical aspects (such as formal methods, complexity, information theory, theory of programming languages, automated theorem proving/protocol analysis), as well as engineering aspects (such as programming languages, operating systems, distributed computing and software engineering). Interest in developing innovative ways of integrating teaching and research, and linking our teaching with the general computing industry, is particularly welcomed. The Department operates a reduced teaching load policy for new staff to enable their research activities to be established.

Please include in your CV and covering letter two one page statements; One on your research plans and how they will impact on the research profile of the Department and one on the contributions that you can make to teaching in the Department, especially in respect of innovation in delivery and content.

09:17 [Pub][ePrint] Secret and Verifiable Delegated Voting for Wide Representation, by Yefim Leifman

  This paper combines cryptographic voting and web page ranking and proves that it is possible to hold elections so as not to limit a voter by a list of candidates, to benefit from voter\'s personal experience in dealing with people, to make wide and proportional representation, and to achieve secrecy, including incoercibility, and verifiability of cryptographic voting systems.

09:17 [Pub][ePrint] Multi-Vendor PayWord with Payment Approval, by Andrea Huszti

  One of the most well known micropayment scheme is the PayWord scheme. It is designed to be onevendor, so if we apply it for multiple vendors, it does not protect against double spending. We extended the PayWord scheme, it supports shopping at multiple vendors without an on-line broker or an on-line secure database. The proposed credit-based system uses one hash chain, hence besides the secret signature key only the seed and a random value should be securely stored. Our scheme is analyzed in applied pi calculus, we prove that it fulfills payment approval, secure payment authorization, secrecy of payment information and unreusability.

18:17 [Pub][ePrint] Proposing Individualization of the design of cryptographic hardware accelerators as countermeasure against structure and side channel analysis, by Zoya Dyka, Thomas Basmer, Christian Wittke and Peter

  Side channel and fault attacks take advantage from the fact that the behavior of crypto implementations can be observed and provide hints that simplify revealing keys. These attacks are normally prepared by analyzing devices that are identical to the real target. Here we propose to individualize the design of cryptographic devices in order to prevent attacks that use identical devices. We implemented three different designs that provide exactly the same cryptographic function, i.e. an ECC kP multiplication. The synthesis and power simulation results show clear differences in the area consumed as well as in the power traces. We envision that this type of protection mechanism is relevant e.g. for wireless sensor networks from which devices can easily be stolen for further analysis in the lab.

18:17 [Pub][ePrint] New Results on Solving Linear Equations Modulo Unknown Divisors and its Applications, by Yao Lu and Rui Zhang and Dongdai Lin

  We revisit the problem of finding small solutions to a collection of linear equations modulo an unknown divisor $p$ for a known composite integer $N$. In Asiacrypt\'08, Herrmann and May introduced a heuristic algorithm for this problem, and their algorithm has many interesting applications, such as factoring with known bits problem, fault attacks on RSA signatures, etc. In this paper, we consider two variants of Herrmann-May\'s equations, and propose some new techniques to solve them. Applying our algorithms, we obtain a few by far the best analytical/experimental results for RSA and its variants. Specifically,


\\item We improve May\'s results (PKC\'04) on small secret exponent attack on RSA variant with moduli $N = p^rq$ ($r\\geq 2$).

\\item We extend Nitaj\'s result (Africacrypt\'12) on weak encryption exponents of RSA and CRT-RSA.


18:17 [Pub][ePrint] Toward Robust Hidden Volumes using Write-Only Oblivious RAM, by Erik-Oliver Blass and Travis Mayberry and Guevara Noubir and Kaan Onarlioglu

  With sensitive data being increasingly stored on mobile devices and

laptops, hard disk encryption is more important than ever. In

particular, being able to plausibly deny that a hard disk contains

certain information is a very useful and interesting research

goal. However, it has been known for some time that existing

``hidden volume\'\' solutions, like TrueCrypt, fail in the face of an

adversary who is able to observe the contents of a disk on multiple,

separate occasions. In this work, we explore more robust

constructions for hidden volumes and present HIVE, which is

resistant to more powerful adversaries with multiple-snapshot

capabilities. In pursuit of this, we propose the first security

definitions for hidden volumes, and prove HIVE secure under these

definitions. At the core of HIVE, we design a new write-only

Oblivious RAM. We show that, when only hiding writes, it is

possible to achieve ORAM with optimal O(1) communication complexity

and only poly-logarithmic user memory. This is a significant

improvement over existing work and an independently interesting

result. We go on to show that our write-only ORAM is specially

equipped to provide hidden volume functionality with low overhead

and significantly increased security. Finally, we implement HIVE as

a Linux kernel block device to show both its practicality and

usefulness on existing platforms.