International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. 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).

2013-02-20
10:17 [Pub][ePrint] Related-key Attacks Against Full Hummingbird-2, by Markku-Juhani O. Saarinen

  We present attacks on full Hummingbird-2 which are able to recover

the 128-bit secret keys of two black box cipher instances that have a certain type of low-weight XOR difference in their keys. We call these

highly correlated keys as they produce the same ciphertext with a

significant probability. The complexity of our main chosen-IV

key-recovery attack is $2^{64}$. The first 64 bits of the key can be independently recovered with only $2^{36}$ effort. This is the first sub-exhaustive attack on the full cipher under two related keys. Our attacks use some novel tricks and techniques which are made possible by Hummingbird-2\'s unique word-based structure. We have verified the correctness and complexity of our attacks by fully implementing them.

We also discuss enabling factors of these attacks and describe an alternative design for the WD16 nonlinear keyed function which is resistant to attacks of this type. The new experimental function replaces S-boxes with simple $\\chi$ functions.



10:17 [Pub][ePrint] Relation collection for the Function Field Sieve, by Jérémie Detrey and Pierrick Gaudry and Marion Videau

  In this paper, we focus on the relation collection step of the Function Field Sieve (FFS), which is to date the best algorithm known for computing discrete logarithms in small-characteristic finite fields of cryptographic sizes. Denoting such a finite field by GF(p^n), where p is much smaller than n, the main idea behind this step is to find polynomials of the form a(t)-b(t)x in GF(p)[t][x] which, when considered as principal ideals in carefully selected function fields, can be factored into products of low-degree prime ideals. Such polynomials are called \"relations\", and current record-sized discrete-logarithm computations need billions of those.

Collecting relations is therefore a crucial and extremely expensive step in FFS, and a practical implementation thereof requires heavy use of cache-aware sieving algorithms, along with efficient polynomial arithmetic over GF(p)[t]. This paper presents the algorithmic and arithmetic techniques which were put together as part of a new public implementation of FFS, aimed at medium- to record-sized computations.



10:17 [Pub][ePrint] The UC approach: an application view, by István Vajda

  What kind of guidelines can the UC approach provide for traditional designs and applications? The aim of this report is to bring this theoretically rooted, computer scientist technology closer to the community of practitioners in the field of protocol designs.



10:17 [Pub][ePrint] Zero-Knowledge Using Garbled Circuits: How To Prove Non-Algebraic Statements Efficiently, by Marek Jawurek and Florian Kerschbaum and Claudio Orlandi

  Zero-knowledge protocols are one of the fundamental concepts in modern cryptography and have countless applications. However, after more than 30 years from their introduction, there are only very few languages (essentially those with a group structure) for which we can construct zero-knowledge protocols that are efficient enough to be used in practice.

In this paper we address the problem of how to construct efficient zero-knowledge protocols for generic languages and we propose a protocol based on Yao\'s garbled circuit technique.

The motivation for our work is that in many cryptographic applications it is useful to be able to prove efficiently statements of the form e.g., ``I know x s.t. y=SHA-256(x)\'\' for a

common input y (or other ``unstructured\'\' languages), but no efficient protocols for this task are currently known.

It is clear that zero-knowledge is a subset of secure two-party computation (i.e., any protocol for generic secure computation can be used to do zero-knowledge). The main contribution of this paper is to construct an efficient protocol for the special case of secure two-party computation where only one party has input (like in the zero-knowledge case).

The protocol achieves active security and is essentially only twice as slow as Yao\'s garbled circuit protocol. This is a great improvement with respect to the cut-n-choose technique to make Yao\'s protocol actively secure, where the complexity grows linearly with the security parameter.



10:17 [Pub][ePrint] On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in $\\F_{2^{1971}}$, by Faruk Gologlu and Robert Granger and Gary McGuire and Jens Zumb

  In this paper we propose a binary field variant of the Joux-Lercier medium-sized Function Field Sieve, which results not only in complexities as low as $L_{q^n}(1/3,2/3)$ for computing arbitrary logarithms, but also in an heuristic {\\em polynomial time} algorithm

for finding the discrete logarithms of degree one elements. To illustrate the efficiency of the method, we have successfully solved the DLP in the finite field with $2^{1971}$ elements.



10:17 [Pub][ePrint] Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme, by Joppe W. Bos and Kristin Lauter and Jake Loftus and Michael Naehrig

  In 1996, Hoffstein, Pipher and Silverman introduced an efficient lattice based encryption scheme dubbed NTRUEncrypt. Unfortunately, this scheme lacks a proof of security. However, in 2011, Stehle and Steinfeld showed how to modify NTRUEncrypt to reduce security to standard problems in ideal lattices. At STOC 2012, Lopez-Alt, Tromer and Vaikuntanathan proposed a fully homomorphic scheme based on this modified system. However, to allow homomorphic operations and prove security, a non-standard assumption is required in their scheme. In this paper, we show how to remove this non-standard assumption via techniques introduced by Brakerski at CRYPTO 2012 and construct a new fully homomorphic encryption scheme from the Stehle and Steinfeld version based on standard lattice assumptions and a circular security assumption. The scheme is scale-invariant and therefore avoids modulus switching, it eliminates ciphertext expansion in homomorphic multiplication, and the size of ciphertexts is one ring element. Moreover, we present a practical variant of our scheme, which is secure under stronger assumptions, along with parameter recommendations and promising implementation results. Finally, we present a novel approach for encrypting larger input sizes by applying a CRT approach on the input space.



10:17 [Pub][ePrint] Design Space Exploration and Optimization of Path Oblivious RAM in Secure Processors, by Ling Ren and Xiangyao Yu and Christopher Fletcher and Marten van Dijk and Srinivas Devadas

  Keeping user data private is a huge problem both in cloud computing and computation outsourcing. One paradigm to achieve data privacy in these settings is to use tamper-resistant processors. Users\' private data is decrypted and computed upon in a secure compartment from which that data will not be revealed to an untrusted party. Since program working sets seldom fit within the on-chip storage of today\'s processor solutions, a secure and efficient way of transporting and storing data off-chip is required. A simple solution to this problem is to encrypt all data that leaves the chip. However, the address sequence that goes off-chip may still leak information. ORAM (Oblivious RAM) has been previously proposed to hide the address leakage of the program. However, ORAM has mainly been explored in server/file settings which assume a vastly different computation model than secure processors (e.g., accesses are for files not processor cache blocks). Not surprisingly, naively applying ORAM to a secure processor setting incurs large performance overheads.

In this paper, we demonstrate techniques to make ORAM practical in a secure processor setting. A particular ORAM proposed recently, called Path ORAM, is studied. For the first time, we thoroughly explore the design space of Path ORAM, and introduce a novel throughput-driven design space exploration approach based on ORAM background eviction schemes and super blocks. With our ORAM optimizations, ORAM latency drops by 45%, and SPEC benchmark execution time improves by 39% in relation to a baseline configuration. We also propose an efficient integrity verification scheme for Path ORAM.

Our work can be used to improve the security level of previous secure processors.



10:17 [Pub][ePrint] UC-Secure Multi-Session OT Using Tamper-Proof Hardware , by Kaoru Kurosawa and Ro Nojima and Le Trieu Phong

  In this paper, we show the first UC-secure multi-session OT protocol using tamper-proof hardware tokens. The sender and the receiver exchange tokens only at the beginning. Then these tokens are reused in arbitrarily many sessions of OT. An instantiation of the proposed scheme is UC-secure against static adversaries under the DDH assumption and the RSA assumption in the random oracle model.



10:17 [Pub][ePrint] Broadcast Steganography, by Nelly Fazio and Antonio R. Nicolosi and Irippuge Milinda Perera

  We initiate the study of broadcast steganography (BS), an extension of steganography to the multi-recipient setting. BS enables a sender to communicate covertly with a dynamically designated set of receivers, so that the recipients recover the original content, while unauthorized users and outsiders remain \\emph{unaware} of the covert communication. One of our main technical contributions is the introduction of a new variant of anonymous broadcast steganography that we term \\emph{anonymous identity-based encryption with pseudorandom ciphertexts} (oABE$). Our oABE$ construction achieves sublinear ciphertext size and is secure in the standard model. Besides being of interest in its own right, oABE$ enables an efficient construction of BS secure in the standard model against adaptive adversaries that also features sublinear ciphertexts.



10:17 [Pub][ePrint] Fast Cut-and-Choose Based Protocols for Malicious and Covert Adversaries, by Yehuda Lindell

  In the setting of secure two-party computation, two parties wish to securely compute a joint function of their private inputs, while revealing only the output. One of the primary techniques for achieving efficient secure two-party computation is that of Yao\'s garbled circuits (FOCS 1986). In the semi-honest model, where just one garbled circuit is constructed and evaluated, Yao\'s protocol has proven itself to be very efficient. However, a malicious adversary who constructs the garbled circuit may construct a garbling of a different circuit computing a different function, and this cannot be detected (due to the garbling). In order to solve this problem, many circuits are sent and some of them are opened to check that they are correct while the others are evaluated. This methodology, called \\emph{cut-and-choose}, introduces significant overhead, both in computation and in communication, and is mainly due to the number of circuits that must be used in order to prevent cheating.

In this paper, we present a cut-and-choose protocol for secure computation based on garbled circuits, with security in the presence of malicious adversaries, that vastly improves on all previous protocols of this type. Concretely, for a cheating probability of at most $2^{-40}$, the best previous works send between 125 and 128 circuits. In contrast, in our protocol 40 circuits alone suffice (with some additional overhead). Asymptotically, we achieve a cheating probability of $2^{-s}$ where $s$ is the number of garbled circuits, in contrast to the previous best of $2^{-0.32s}$. We achieve this by introducing a new cut-and-choose methodology with the property that in order to cheat, \\emph{all} of the evaluated circuits must be incorrect, and not just the \\emph{majority} as in previous works.



10:17 [Pub][ePrint] An efficient attack of a McEliece cryptosystem variant based on convolutional codes, by Grégory Landais and Jean-Pierre Tillich

  L\\\"ondahl and Johansson proposed last year a variant of the McEliece cryptosystem which

replaces Goppa codes by convolutional codes. This modification is supposed to make

structural attacks more difficult since the public generator matrix of this scheme contains

large parts which are generated completely at random. They proposed two schemes of this

kind, one of them consists in taking a Goppa code and extending it by adding a generator matrix of

a time varying convolutional code. We show here that this scheme can be successfully attacked by looking

for low-weight codewords in the public code of this scheme and using it to unravel the convolutional part.

It remains to break the Goppa part of this scheme which can be done in less than a day of computation in

the case at hand.