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:17 [Pub][ePrint] EPiC: Efficient Privacy-Preserving Counting for MapReduce, by Erik-Oliver Blass and Guevara Noubir and Triet Vo Huu

  In the face of an untrusted cloud infrastructure, outsourced data

needs to be protected. Fully homomorphic encryption is one solution

that also allows performing operations on outsourced data. However,

the involved high overhead of today\'s fully homomorphic encryption

techniques outweigh cloud cost saving advantages, rendering it

impractical. We present EPiC, a practical, efficient protocol for

the privacy-preserving evaluation of a fundamental operation on data

sets: frequency counting. In an IND-CPA encrypted outsourced data

set, a cloud user can specify a pattern, and the cloud will count

the number of occurrences of this pattern in a completely oblivious

manner. EPiC\'s main idea is, first, to reduce the problem of

counting to polynomial evaluation. Second, to efficiently evaluate

polynomials in a privacy-preserving manner, we extend previous work

on the Hidden Modular Group Order assumption and design a new

\\emph{somewhat homomorphic} encryption scheme. This scheme is highly

efficient in our particular counting scenario with a relatively

small number of possible patterns. Besides a formal analysis where

we prove EPiC\'s privacy, we also present implementation and

evaluation results. We specifically target Google\'s prominent

MapReduce paradigm as offered by major cloud providers. Our

evaluation performed both locally and in Amazon\'s public cloud with

data sets sizes of up to 1 TByte shows only modest overhead compared

to non-private counting, attesting to EPiC\'s efficiency.

12:17 [Pub][ePrint] New Leakage Resilient CCA-Secure Public Key Encryption, by Kaoru Kurosawa and Ryo Nojima and Le Trieu Phong

  This paper shows a generic method of constructing CCA-secure public key encryption schemes with leakage resilience on the secret key. It is based on a new kind of universal$_2$ hash proof system which accepts an auxiliary parameter. Specifically, two schemes are presented, basing on the DCR assumption and DLIN assumption respectively.

07:37 [Event][New] TCC2013: The Tenth Theory of Cryptography Conference

  Submission: 1 September 2012
Notification: 1 December 2012
From March 3 to March 6
Location: Tokyo, Japan
More Information:

01:26 [Event][New] Qshine-2013: Heterogeneous Networking for Quality, Reliability, Security and Robustness

  Submission: 30 September 2012
Notification: 15 November 2012
From January 11 to January 12
Location: Greater Noida, India
More Information:

16:00 [Job][New] Research Associate in Verifiable Internet Voting (M/F), University of Luxembourg

  The APSIA Group (APplied Security and Information Assurance), led by Prof P Y A Ryan, along with the University of Applied Science in Berne, has recently been awarded a joint INTER project (funded by the FNR in Luxembourg and the SNF in Switzerland), to study verifiable, secure internet voting. The APSIA Group is seeking a highly qualified post-doctoral researcher for this project.

The VIVO project, a joint project with Prof Rolf Haenni of the University of Applied Sciences in Berne, will develop and evaluate novel approaches to ensuring the security (verifiability, coercion-resistance etc.) of internet voting. You will be working with Prof Ryan and members of the APSIA team as well as collaborating with Prof Haenni and members of the Berne e-voting group (

15:50 [Event][New] RISE'12: Workshop on Redefining and Integrating Security Engineering

  Submission: 7 October 2012
Notification: 5 November 2012
From December 14 to December 16
Location: Washington DC, USA
More Information:

15:49 [Event][New] PROOFS: Workshop on Security Proofs for Embedded Systems

  Submission: 27 March 2012
Notification: 7 July 2012
From September 13 to September 13
Location: Leuven, Belgium
More Information:

06:17 [Pub][ePrint] Stam\'s Conjecture and Threshold Phenomena in Collision Resistance, by John Steinberger, Xiaoming Sun, Zhe Yang

  At CRYPTO 2008 Stam conjectured that if an $(m\\!+\\!s)$-bit

to $s$-bit compression function $F$ makes $r$ calls to a primitive $f$

of $n$-bit input, then a collision for $F$ can be obtained (with high

probability) using $r2^{(nr-m)/(r+1)}$ queries to $f$, which is sometimes

less than the birthday bound. Steinberger (Eurocrypt 2010) proved Stam\'s

conjecture up to a constant multiplicative factor for most cases in

which $r = 1$ and for certain other cases that reduce to the case

$r = 1$. In this paper we prove the general case of Stam\'s conjecture

(also up to a constant multiplicative factor). Our result is

qualitatively different from Steinberger\'s, moreover, as we show the

following novel threshold phenomenon: that exponentially many (more

exactly, $2^{s-2(m-n)/(r+1)}$) collisions are obtained with high

probability after $O(1)r2^{(nr-m)/(r+1)}$ queries. This in particular

shows that threshold phenomena observed in practical compression

functions such as JH are, in fact, unavoidable for compression

functions with those parameters. (This is the full version of the

same-titled article that appeared at CRYPTO 2012.)

21:17 [Pub][ePrint] On the Impossibility of Constructing Efficient Key Encapsulation and Programmable Hash Functions in Prime Order Groups, by Goichiro Hanaoka and Takahiro Matsuda and Jacob C.N. Schuldt

  In this paper, we focus on the problem of minimizing ciphertext overhead, and discuss the (im)possibility of constructing key encapsulation mechanisms (KEMs) with low ciphertext overhead. More specifically, we rule out the existence of algebraic black-box reductions from the (bounded) CCA security of a natural class of KEMs to any non-interactive problem. The class of KEMs captures the structure of the currently most efficient KEMs defined in standard prime order groups, but restricts an encapsulation to consist of a single group element and a string. This result suggests that we cannot rely on existing techniques to construct a CCA secure KEM in standard prime order groups with a ciphertext overhead lower than two group elements. Furthermore, we show how the properties of an (algebraic) programmable hash function can be exploited to construct a simple, efficient and CCA secure KEM based on the hardness of the decisional Diffie-Hellman problem with the ciphertext overhead of just a single group element. Since this KEM construction is covered by the above mentioned impossibility result, this enables us to derive a lower bound on the hash key size of an algebraic programmable hash function, and rule out the existence of algebraic $({\\sf poly},n)$-programmable hash functions in prime order groups for any integer $n$. The latter result answers an open question posed by Hofheinz and Kiltz (CRYPTO\'08) in the case of algebraic programmable hash functions in prime order groups.

21:17 [Pub][ePrint] Long Term Confidentiality: a Survey, by Johannes Braun, Johannes Buchmann, Ciaran Mullan, and Alex Wiesmaier

  Sensitive electronic data may be required to remain confidential for long periods of time. Yet encryption under a computationally secure cryptosystem cannot provide a guarantee of long term confidentiality, due to potential advances in computing power or cryptanalysis. Long term confidentiality is ensured by information theoretically secure ciphers, but at the expense of impractical key agreement and key management.

We overview known methods to alleviate these problems, whilst retaining some form of information theoretic security relevant for long term confidentiality.

21:17 [Pub][ePrint] Tweakable Blockciphers with Beyond Birthday-Bound Security, by Will Landecker and Thomas Shrimpton and R. Seth Terashima

  Liskov, Rivest and Wagner formalized the tweakable blockcipher (TBC) primitive at CRYPTO\'02. The typical recipe for instantiating a TBC is to start with a blockcipher, and then build up a construction that admits a tweak. Almost all such constructions enjoy provable security only to the birthday bound, and the one that does achieve security beyond the birthday bound (due to Minematsu) severely restricts the tweak size and requires per-invocation blockcipher rekeying.

This paper gives the first TBC construction that simultaneously allows for arbitrarily \"wide\" tweaks, does not rekey, and delivers provable security beyond the birthday bound. Our construction is built from a blockcipher and an $\\eAXU$ hash function.

As an application of the TBC primitive, LRW suggest the TBC-MAC construction (similar to CBC-MAC but chaining through the tweak), but leave open the question of its security. We close this question, both for TBC-MAC as a PRF and a MAC. Along the way, we find a nonce-based variant of TBC-MAC that has a tight reduction to the security of the underlying TBC, and also displays graceful security degradation when nonces are misused. This result is interesting on its own, but it also serves as an application of our new TBC construction, ultimately giving a variable input-length PRF with beyond birthday-bound security.