International Association for Cryptologic Research

# IACR News Central

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2012-08-13
15:17 [Pub][ePrint]

Computations of small discrete logarithms are feasible even in \"secure\" groups, and are used as subroutines in several cryptographic protocols in the literature. For example, the Boneh--Goh--Nissim degree-2-homomorphic public-key encryption system uses generic square-root discrete-logarithm methods for decryption. This paper shows how to use a small group-specific table to accelerate these subroutines. The cost of setting up the table grows with the table size, but the acceleration also grows with the table size. This paper shows experimentally that computing a discrete logarithm in an interval of order l takes only 1.93*l^{1/3} multiplications on average using a table of size l^{1/3} precomputed with 1.21*l^{2/3} multiplications, and computing a discrete logarithm in a group of order l takes only 1.77*l^{1/3} multiplications on average using a table of size l^{1/3} precomputed with 1.24*l^{2/3} multiplications.

15:17 [Pub][ePrint]

There has been much recent progress in constructing cryptosystems that maintain their security without requiring uniform randomness and perfect secrecy. These schemes are motivated by a diverse set of problems such as providing resilience to side-channel leakage, using weak physical sources of randomness as secret keys, and allowing deterministic encryption for high-entropy messages. The study of these problems has significantly deepened our understanding of how randomness is used in cryptographic constructions and proofs.

Nevertheless, despite this progress, some basic and seemingly achievable security properties have eluded our reach. For example, we are also unable to prove the security of basic tools for manipulating weak/leaky random sources, such as as pseudo-entropy generators and seed-dependent condensers. We also do not know how to prove leakage-resilient security of any cryptosystem that has a unique secret key for each public key. In the context of deterministic encryption, we do not have a standard-model constructions achieving the strongest notion of security originally proposed by Bellare, Boldyreva and O\'Neill (CRYPTO \'07), that allows for the encryption of arbitrarily correlated messages of sufficiently large individual entropy.

In this work, we provide broad black-box separation results, showing that the security of such primitives cannot be proven under virtually \\emph{any} standard cryptographic hardness assumption via a reduction that treats the adversary as a \\emph{black box}. We do so by formalizing the intuition that the only way that a reduction can simulate the correctly distributed view for an attacker is to know all the secrets, in which case it does not learn anything useful from the attack\'\'. This intuition is often misleading and subtle ways of getting around it allow us to achieve a wealth of positive results for many cryptographic primitives with imperfect randomness. However, in this work we show that this intuition can be formalized and that it indeed presents a real barrier in many special cases involving the above-mentioned examples.

15:17 [Pub][ePrint]

In this paper, we study timed-release cryptography with information-theoretic security. As fundamental cryptographic primitives with information-theoretic security, we can consider key-agreement, encryption, and authentication codes. Therefore, in this paper, we deal with information-theoretic timed-release security for all those primitives. Specifically, we propose models and formalizations of security for information-theoretic timed-release key-agreement, encryption, and authentication codes, and we present constructions of those ones. In particular, information-theoretic timed-release encryption and authentication codes can be constructed from information-theoretic timed-release key-agreement in a generic and simple way. Also, we derive tight lower bounds on sizes of secret-keys and show optimal constructions for information-theoretic timed-release key-agreement and encryption. Furthermore, we investigate a relationship of mechanisms between information-theoretic timed-release key-agreement and information-theoretic key-insulated key-agreement. It turns out that there exists a simple algorithm which converts the former into the latter, and vice versa. In the sense, we conclude that these two mechanisms are essentially close.

12:17 [Pub][ePrint]

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]

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]

Submission: 1 September 2012
From March 3 to March 6
Location: Tokyo, Japan

2012-08-11
01:26 [Event][New]

Submission: 30 September 2012
From January 11 to January 12
Location: Greater Noida, India

2012-08-09
16:00 [Job][New]

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 (http://e-voting.bfh.ch/).

15:50 [Event][New]

Submission: 7 October 2012
From December 14 to December 16
Location: Washington DC, USA

15:49 [Event][New]

Submission: 27 March 2012
From September 13 to September 13
Location: Leuven, Belgium

2012-08-08
06:17 [Pub][ePrint]

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