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

16:17 [Pub][ePrint] Garbled RAM Revisited, Part II, by Steve Lu and Rafail Ostrovsky

  In EUROCRYPT 2013, Lu and Ostrovsky proposed the notion of Garbled RAM (GRAM) programs. These GRAM programs are analogous to the classic result of Yao\'s garbled circuits: a large encrypted memory can first be provided to evaluator, and then a program can separately be garbled and sent to an evaluator to securely execute while learning nothing but the output of the program and its running time. The key feature of GRAM is that it harnesses the natural complexity-theoretic power that Random Access Memory (RAM) programs have over circuits, such as in binary search or randomized algorithms, where program can be executed in a garbled way without \"unrolling\" it into a circuit. The candidate Lu-Ostrovsky GRAM scheme proposed in that paper is based on the existence of one-way functions, but due to an implicit reliance on a complex \"circular\" use of Yao garbled circuits, the scheme requires an additional circularity assumptions and may not be secure otherwise.

In this paper, we show how to construct efficient GRAM without circularity and based solely on the existence of any one-way function. The novel approach that allows us to break the circularity is a modification of the Goldreich-Goldwasser-Micali (PRF) construction. More specifically, we modify the PRF to allow PRF-keys to be \"adaptively revoked\" during run-time at the additive cost of roughly log n per revocation. Then, to improve the overhead of this scheme, we apply a delicate recursion technique that bootstraps mini-GRAM schemes into larger, more powerful ones while still avoiding circularity in the hybrid arguments. This results in secure GRAM with overhead of poly($k$)(min($t; n^\\eps$)) for any constant $\\eps>0$, where $n$ is the size of memory and $t$ is the running time.

In a companion work (Part I), Gentry, Halevi, Raykova, and Wichs show an alternative approach using identity-based encryption to solve the circularity problem. Their scheme achieves overhead of poly($k$)polylog($n$) assuming the existence of IBE.

05:44 [Job][New] Security Engineer, CloudFlare Inc. (San Francisco, USA and London, UK)


CloudFlare is looking for a talented security engineer to join our team. We are working on a number of ambitious projects to secure the web and protect our customers from threats of all sorts. The role of security engineer at CloudFlare is more that of a builder than a breaker. You will have to approach problems with creativity and flexibility and be able to identify and use the best tools for the job or build better ones from scratch. At CloudFlare, we are serious about protecting our customers and advancing the state of the art in computer security.


  • Strong systems-level programming skills
  • Deep understanding of networking protocols (TCP/IP, SSL/TLS, DNS)

  • Experience with cryptographic libraries and APIs

  • Expert in C/C++ and performance analysis

  • Proficiency in Go and/or Lua or willingness to learn

  • Strong understanding of security concepts (key management, access control, authentication)

  • Understanding of Linux internals

  • Interest in advancements in security and cryptography

    Bonus Points:

  • Contributions to the open source community

  • Experience implementing production-grade cryptographic algorithms

  • Knowledge or expertise in White-box cryptography

  • Experience with DNSSEC

  • Familiarity with compilers or code generation tools (e.g.

  • Experience with cryptographic hardware (TPM, HSM, etc.)

  • Healthy sense of paranoia

  • 2014-02-04
    19:17 [Pub][ePrint] Efficient Privacy-Preserving Big Data Processing through Proxy-Assisted ORAM, by Nikolaos P. Karvelas and Andreas Peter and Stefan Katzenbeisser and Sebastian Biedermann

      We present a novel mechanism that allows a client

    to securely outsource his private data to the cloud while at the same

    time to delegate to a third party the right to run

    certain algorithms on his data. The mechanism is

    privacy-preserving, meaning that the third party only learns the result

    of his algorithm on the client\'s data, while at the same time the access

    pattern on the client\'s data is hidden from the cloud. To achieve this we

    combine recent advances in the field of Oblivious RAM and Secure Two-Party

    Computation: We develop an Oblivious RAM which is ran between the cloud and a

    proxy server, and which does not need the data to be decrypted at any

    point. The evaluation on the data is done by employing Yao\'s garbled

    circuit solution for Secure Two-Party Computation.

    19:17 [Pub][ePrint] Anonymous Authentication with Shared Secrets, by Joel Alwen and Martin Hirt and Ueli Maurer and Arpita Patra and Pavel Raykov

      Anonymity and authenticity are both important yet often conflicting security goals in a wide range of applications. On the one hand for many applications (say for access control) it is crucial to be able to verify the identity of a given legitimate party (a.k.a. entity authentication). Alternatively an application might require that no one but a party can communicate on its behalf (a.k.a. message authentication). Yet, on the other hand privacy concerns also dictate that anonymity of a legitimate party should be preserved; that is no information concerning the identity of parties should be leaked to an outside entity eavesdropping on the communication. This conflict becomes even more acute when considering anonymity with respect to an active entity that may attempt to impersonate other parties in the system.

    In this work we resolve this conflict in two steps. First we formalize what it means for a system to provide both authenticity and anonymity even in the presence of an active man-in-the-middle adversary for various specific applications such as message and entity authentication using the constructive cryptography framework of~\\cite{Mau11}. Our approach inherits the composability statement of constructive cryptography and can therefore be directly used in any higher-level context. Next we demonstrate several simple protocols for realizing these systems, at times relying on a new type of (probabilistic) Message Authentication Code (MAC) called \\emph{key indistinguishable} (KI) MACs. Similar to the key hiding encryption schemes of~\\cite{BellareBDP01} they guarantee that tags leak no discernible information about the keys used to generate them.

    19:17 [Pub][ePrint] New and Improved Key-Homomorphic Pseudorandom Functions, by Abhishek Banerjee and Chris Peikert

      A \\emph{key-homomorphic} pseudorandom function (PRF) family

    $\\set{F_{s} \\colon D \\to R}$ allows one to efficiently compute the

    value $F_{s+t}(x)$ given $F_{s}(x)$ and $F_{t}(x)$. Such functions

    have many applications, such as distributing the operation of a

    key-distribution center and updatable symmetric encryption. The only

    known construction of key-homomorphic PRFs without random oracles, due

    to Boneh \\etal (CRYPTO~2013), is based on the learning with errors

    (\\lwe) problem and hence on worst-case lattice problems. However, the

    security proof relies on a very strong \\lwe assumption (i.e., very

    large approximation factors), and hence has quite inefficient

    parameter sizes and runtimes.

    In this work we give new constructions of key-homomorphic PRFs that

    are based on much weaker \\lwe assumptions, are much more efficient in

    time and space, and are still highly parallel. More specifically, we

    improve the \\lwe approximation factor from exponential in the input

    length to exponential in its \\emph{logarithm} (or less). For input

    length~$\\lambda$ and~$2^{\\lambda}$ security against known lattice

    algorithms, we improve the key size from~$\\lambda^{3}$ to~$\\lambda$

    bits, the public parameters from~$\\lambda^{6}$ to~$\\lambda^{2}$ bits,

    and the runtime from~$\\lambda^{7}$ to~$\\lambda^{\\omega+1}$ bit

    operations (ignoring polylogarithmic factors in~$\\lambda$), where

    $\\omega \\in [2,2.373]$ is the exponent of matrix multiplication. In

    addition, we give even more efficient ring-\\lwe-based constructions

    whose key sizes, public parameters, and \\emph{incremental} runtimes on

    consecutive inputs are all \\emph{quasi-linear}~$\\Otil(\\lambda)$, which

    is optimal up to polylogarithmic factors. To our knowledge, these are

    the first \\emph{low-depth} PRFs (whether key homomorphic or not)

    enjoying any of these efficiency measures together with nontrivial

    proofs of~$2^{\\lambda}$ security under any conventional assumption.

    19:17 [Pub][ePrint] Publicly Auditable Secure Multi-Party Computation, by Carsten Baum and Claudio Orlandi and Ivan Damgård

      In the last few years the efficiency of secure multi-party computation (MPC) increased in several orders of magnitudes. However, this alone might not be enough if we want MPC protocols to be used in practice.

    A crucial property that is needed in many applications is that everyone can check that a given (secure) computation was performed correctly -- even in the extreme case where all the parties involved in the computation are corrupted, and even if the party who wants to verify the result was not involved. An obvious example of this is electronic voting, but also in many types of auctions one may want independent verification of the result. Traditionally, this is achieved by using non-interactive zero-knowledge proofs.

    A recent trend in MPC protocols is to have a more expensive preprocessing phase followed by a very efficient online phase, e.g., the recent so-called SPDZ protocol by Damgård et al. Applications such as voting and some auctions are perfect applications for these protocols, as the parties usually know well in advance when the computation will take place, and using those protocols allows us to use only cheap information theoretic primitives in the actual computation. Unfortunately no protocol of the SPDZ type supports an audit phase.

    In this paper we formalize the concept of publicly auditable secure computation and provide an enhanced version of the SPDZ protocol where, even if all the servers are corrupted, anyone with access to the transcript of the protocol can check that the output is indeed correct. Most importantly, we do so without compromising the performance of SPDZ i.e., the cost of our online phase is the same as that of SPDZ, up to a small constant factor of about two.

    19:17 [Pub][ePrint] Certified Bitcoins, by Giuseppe Ateniese and Antonio Faonio and Bernardo Magri and Breno de Medeiros

      Bitcoin is a peer-to-peer (p2p) electronic cash system that

    uses a distributed timestamp service to record transactions in a public ledger (called the Blockchain). A critical component of Bitcoin\'s success is the decentralized nature of its architecture, which does not require or even support the establishment of trusted authorities. Yet the absence of certification creates obstacles to its wider acceptance in e-commerce and official uses. We propose a certification system for Bitcoin that offers: a) an opt-in guarantee to send and receive bitcoins only to/ from certified users; b) control of creation of bitcoins addresses (certified users) by trusted authorities.

    Our proposal may encourage the adoption of Bitcoin in different scenarios that require an officially recognized currency, such

    as tax payments--often an integral part of e-commerce transactions.

    19:17 [Pub][ePrint] Mixcoin: Anonymity for Bitcoin with accountable mixes, by Joseph Bonneau and Arvind Narayanan and Andrew Miller and Jeremy Clark and Joshua A. Kroll and Edward W. Felten

      We propose Mixcoin, a protocol to facilitate anonymous payments using the Bitcoin currency system. We build on the emergent phenomenon of currency mixes, adding an accountability mechanism to expose theft. Unlike other proposals to improve anonymity in Bitcoin, our scheme can be deployed immediately with no changes to Bitcoin itself. We demonstrate that incentives of mixes and clients can be aligned to ensure that rational mixes will not steal from clients. We contrast mixing for financial anonymity with better-studied communication mixes, demonstrating important and subtle new attacks.

    19:17 [Pub][ePrint] Implementation and Comparison of Lattice-based Identification Protocols on Smart Cards and Microcontrollers, by Ahmad Boorghany and Rasool Jalili

      Most lattice-based cryptographic schemes which enjoy a security proof suffer from huge key sizes and heavy computations. This is also true for the simpler case of identification protocols. Recent progress on ideal lattices has significantly improved the efficiency, and made it possible to implement practical lattice-based cryptography on constrained devices like FPGAs and smart phones. However, to the best of our knowledge, no previous attempts were made to implement lattice-based schemes on smart cards. In this paper, we report the results of our implementation of several state-of-the-art and highly-secure lattice-based identification protocols on smart cards and microcontrollers. Our results show that only a few of such protocols fit into the limitations of these devices. We also discuss the implementation challenges and techniques to perform lattice-based cryptography on constrained devices, which may be of independent interest.

    19:17 [Pub][ePrint] Unifying Leakage Models: from Probing Attacks to Noisy Leakage, by Alexandre Duc and Stefan Dziembowski and Sebastian Faust

      A recent trend in cryptography is to formally show the leakage resilience of cryptographic implementations in a given leakage model. One of the most prominent leakage models -- the so-called bounded leakage model -- assumes that the amount of leakage is a-priori bounded. Unfortunately, it has been pointed out that the assumption of bounded leakages is hard to verify in practice. A more realistic assumption is to assume that leakages are sufficiently noisy, following the engineering observation that real-world physical leakages are inherently noisy. While the noisy leakage assumption has first been studied in the seminal work of Chari et al. (CRYPTO 99), the recent work of Prouff and Rivain (Eurocrypt 2013) provides the first analysis of a full masking scheme under a physically motivated noise model. In particular, the authors show that a block-cipher implementation that uses an additive masking scheme is secure against noisy leakages. Unfortunately, the security analysis of Prouff and Rivain has three important shortcomings: (1) it requires leak-free gates, (2) it considers a restricted adversarial model (random message attacks), and (3) the security proof has limited application for cryptographic settings. In this work, we provide an alternative security proof in the same noisy model that overcomes these three challenges. We achieve this goal by a new reduction from noisy leakage to the important theoretical model of probing adversaries (Ishai et al~ -- CRYPTO 2003). Our work can be viewed as a next step of closing the gap between theory and practice in leakage resilient cryptography: while our security proofs heavily rely on concepts of theoretical cryptography, we solve problems in practically motivated leakage models.

    16:17 [Pub][ePrint] One-Pass Authenticated Key Establishment Protocol on Bilinear Pairings for Wireless Sensor Networks, by Manoj Ranjan Mishra, Jayaprakash Kar and Banshidhar Majhi

      The article proposes one-pass authenticated key establishment protocol

    in random oracles for Wireless Sensor Networks. Security of the protocol relies on Computational Diffie-Hellman Problem on Bilinear Pairings. In one-pass key establishment protocol, the initiator computes a session key and a related message. The key token is to be sent to the intended receiver using receiver\'s public key and sender

    secret key. From the received key token the receiver compute the session key, which is the same as the one computed by the sender, using sender public key and receiver\'s secret key. Because of low communication overhead, the scheme is better suited for Wireless Sensor Networks(WSNs) than the traditional key establishment protocol to establish the session key between two adjacent nodes.