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

19:17 [Pub][ePrint] Round-Efficient Concurrently Composable Secure Computation via a Robust Extraction Lemma, by Vipul Goyal and Omkant Pandey and Amit Sahai

  We consider the problem of constructing protocols for secure computation that achieve strong concurrent and composable notions of security in the plain model. Unfortunately UC-secure secure computation protocols are impossible in this setting, but the Angel-Based Composable Security notion offers a promising alternative. Until now, however, under standard (polynomial-time) assumptions, only protocols with polynomially many rounds were known to exist.

In this work, we give the first $\\tilde{O}(\\log n)$-round secure computation protocol in the plain model that achieves angel-based composable security in the concurrent setting, under standard assumptions. We do so by constructing the first $\\tilde{O}(\\log n)$-round CCA-secure commitment protocol. Our CCA-secure commitment protocol is secure based on the minimal assumption that one-way functions exist.

A central tool in obtaining our result is a new \\emph{robust concurrent extraction lemma} that we introduce and prove, based on the minimal assumptions that one-way functions exist. This robust concurrent extraction lemma shows how to build concurrent extraction procedures that work even in the context of an ``external\'\' protocol that cannot be rewound by the extractor. We believe this lemma can be used to simplify many existing works on concurrent security, and is of independent interest. In fact, our lemma when used in conjunction with the concurrent-simulation schedule of Pass and Venkitasubramaniam (TCC\'08), also yields a constant round construction based additionally on the existence of quasi-polynomial time (\\pqt) secure one-way functions.

19:17 [Pub][ePrint] How powerful are the DDH hard groups?, by Periklis A. Papakonstantinou and Charles W. Rackoff and Yevgeniy Vahlis

  The question whether Identity-Based Encryption (IBE) can be based on the Decisional Diffie-Hellman (DDH) assumption is one of the most prominent questions in Cryptography related to DDH. We study limitations on the use of the DDH assumption in cryptographic constructions, and show that it is impossible to construct a secure Identity-Based Encryption system using, in a black box way, only the DDH (or similar) assumption about a group. Our impossibility result is set in the generic groups model, where we describe an attack on any IBE construction that relies on oracle access to the group operation of randomly labelled group elements -- a model that formalizes naturally DDH hardness.

The vast majority of existing separation results typically give separation from general primitives, whereas we separate a primitive from a class of number theoretic hardness assumptions. Accordingly, we face challenges in creating an attack algorithm that will work against constructions which leverage the underlying algebraic structure of the group. In fact, we know that this algebraic structure is powerful enough to provide generic constructions for several powerful primitives including oblivious transfer and chosen ciphertext secure public-key cryptosystems (note that an IBE generalizes such systems). Technically, we explore statistical properties of the group algebra associated with a DDH oracle, which can be of independent interest.

19:17 [Pub][ePrint] Refine the Concept of Public Key Encryption with Delegated Search, by Qiang Tang and Yuanjie Zhao and Xiaofeng Chen and Hua Ma

  We revisit the concept of public key encryption with delegated keyword search (PKEDS), a concept proposed by Ibraimi et al. A PKEDS scheme allows a receiver to authorize third-party server(s) to search in two ways: either according to a message chosen by the server itself or according to a trapdoor sent by the receiver. We show that the existing formulation has some defects and the proposed scheme is unnecessarily inefficient. Based on our analysis, we present a refined formulation of the primitive with a new security model. We then propose a new PKEDS scheme, which is proven secure and much more efficient than the original scheme by Ibraimi et al.

19:17 [Pub][ePrint] Privacy Preserving Revocable Predicate Encryption Revisited, by Kwangsu Lee and Intae Kim and Seong Oun Hwang

  Predicate encryption (PE) that provides both the access control of ciphertexts and the privacy of ciphertexts is a new paradigm of public-key encryption. An important application of predicate encryption is a searchable encryption system in a cloud storage, where it enables a client to securely outsource its data to an untrusted cloud server and to search over it even without revealing a keyword itself. One practical issue of predicate encryption is to devise an efficient revocation method to revoke a user when the secret key of the user is compromised. Privacy preserving revocable predicate encryption (RPE) can provide not only revocation, but also the privacy of revoked users.

In this paper, we first define two new security models of privacy preserving RPE: the strongly full-hiding security and the weakly full-hiding security. The strongly full-hiding security provides the full privacy of ciphertexts against outside and inside adversaries, but the weakly full-hiding security only provides the full privacy of ciphertexts against an outside adversary who cannot decrypt the challenge ciphertext. Next, we propose two general RPE constructions from any inner product encryption (IPE) schemes, and prove their security. This first RPE scheme provides the strongly full-hiding security, but the size of ciphertexts is proportional to the number of users in the system. The second RPE scheme improves the efficiency of the first RPE scheme such that the size of ciphertexts is sublinear and the decryption algorithm is efficient, but it provides the weakly full-hiding security.

19:17 [Pub][ePrint] Security Evaluation of Rakaposhi Stream Cipher, by Mohammad Ali Orumiehchiha and Josef Pieprzyk and Elham Shakour and Ron Steinfeld

  Rakaposhi is a synchronous stream cipher, which uses three main components a non-linear

feedback shift register (NLFSR), a dynamic linear feedback shift register (DLFSR) and a

non-linear filtering function ($NLF$). NLFSR consists of 128 bits and is initialised

by the secret key $K$. DLFSR holds 192 bits and is initialised by an initial vector ($IV$).

$NLF$ takes 8-bit inputs and returns a single output bit.

The work identifies weaknesses and properties of the cipher. The main observation

is that the initialisation procedure has the so-called sliding property.

The property can be used to launch distinguishing and key recovery attacks.

The distinguisher needs four observations of the related $(K,IV)$ pairs. The key recovery algorithm allows to discover the secret key $K$ after observing

$2^{9}$ pairs of $(K,IV)$. In the proposed related-key attack, the number of related $(K,IV)$ pairs is $2^{(128+192)/4}$ pairs.

The key recovery algorithm allows to discover the secret key $K$ after observing

$2^9$ related $(K,IV)$ pairs.

Further the cipher is studied when the registers enter short cycles.

When NLFSR is set to all ones, then the cipher degenerates to a linear feedback

shift register with a non-linear filter.

Consequently, the initial state (and Secret Key and $IV$) can be recovered with complexity


If DLFSR is set to all zeros, then $NLF$ reduces to a low non-linearity filter

function. As the result, the cipher is insecure allowing the adversary

to distinguish it from a random cipher after $2^{17}$ observations of

keystream bits. There is also the key recovery algorithm that allows to

find the secret key with complexity $2^{54}$.

16:17 [Pub][ePrint] Galindo-Garcia Identity-Based Signature Revisited, by Sanjit Chatterjee and Chethan Kamath and Vikas Kumar

  In Africacrypt 2009, Galindo-Garcia [11] proposed a lightweight identity-based signature (IBS) scheme based on the Schnorr signature. The construction is simple and claimed to be the most efficient IBS till date. The security is based on the discrete-log assumption and the security argument consists of two reductions: B1 and B2, both of which use the multiple-forking lemma [4] to solve the discrete-log problem (DLP).

In this work, we revisit the security argument given in [11]. Our contributions are two fold: (i) we identify several problems in the original argument and (ii) we provide a detailed new security argument which allows significantly tighter reductions. In particular, we show that the reduction B1 in [11] fails in the standard security model for IBS [1], while the reduction B2 is incomplete. To remedy these problems, we adopt a two-pronged approach. First, we sketch ways to fill the gaps by making minimal changes to the structure of the original security argument; then, we provide a new security argument. The new argument consists of three reductions: R1, R2 and R3 and in each of them, solving the DLP is reduced to breaking the IBS. R1 uses the general forking lemma [2] together with the programming of the random oracles and Coron\'s technique [7]. Reductions R2 and R3, on the other hand, use the multiple-forking lemma along with the programming of the random oracles. We show that the reductions R1 and R2 are significantly tighter than their original counterparts.

16:17 [Pub][ePrint] A Measure of Security for Ideal Functions, by Daniel Smith-Tone and Cristina Tone

  In this work we present a modification of a well-established measure of dependence appropriate for the analysis of stopping times for adversarial processes on cryptographic primitives. We apply this measure to construct generic criteria for the ideal behavior of fixed functions in both the random oracle and ideal permutation setting. More significantly, we provide a nontrivial extension of the notion of hash function indifferentiability, transporting the theory from the status of providing security arguments for protocols utilizing ideal primitives into the more realistic setting of protocol assurance with fixed functions. The methodology this measure introduces to indifferentiability analysis connects the security of a hash function with an indifferentiable mode to the security of the underlying compression function in a quantitative way; thus, we prove that dependence results on cryptographic primitives provide a direct means of determining the practical resistance or vulnerability of protocols employing such primitives.

16:17 [Pub][ePrint] Search in Encrypted Data: Theoretical Models and Practical Applications, by Qiang Tang

  Recently, the concept of Search in Encrypted Data (SED) has become a highlight in cryptography. A SED scheme enables a client to have third-party server(s) to perform certain search functionalities on his encrypted data. In this book chapter, we aim at conducting a systematic study on SED schemes. Firstly, we describe three application scenarios and identify the desirable security requirements. Secondly, we provide two orthogonal categorizations and review the related security models for each category of SED schemes. Thirdly, we analyze the practical issues related to SED schemes and identify some future research directions.

16:17 [Pub][ePrint] A Robust and Plaintext-Aware Variant of Signed ElGamal Encryption , by Yannick Seurin and Joana Treger

  Adding a Schnorr signature to ElGamal encryption is a popular proposal aiming at thwarting chosen-ciphertext attacks by rendering the scheme plaintext-aware. However, there is no known security proof for the resulting scheme, at least not in a weaker model than the one obtained by combining the Random Oracle Model (ROM) and the Generic Group Model (Schnorr and Jakobsson, ASIACRYPT 2000). In this paper, we propose a very simple modification to Schnorr-Signed ElGamal encryption that leaves keys and ciphertexts size unchanged, for which the resulting scheme is semantically secure under adaptive chosen-ciphertext attacks (IND-CCA2-secure) in the ROM under the Decisional Diffie-Hellman assumption. In fact, we even prove that our new scheme is plaintext-aware in the ROM as defined by Bellare et al. (CRYPTO\'98). Interestingly, we also observe that Schnorr-Signed ElGamal is not plaintext-aware (again, for the definition of Bellare et al.) under the Computational Diffie-Hellman assumption. We show that our new scheme additionally achieves anonymity as well as robustness, a notion formalized by Abdalla et al. (TCC 2010) which captures the fact that it is hard to create a ciphertext that is valid under two different public keys. Finally, we study the hybrid variant of our new proposal, and show that it is IND-CCA2-secure in the ROM under the Computational Diffie-Hellman assumption when used with a symmetric encryption scheme satisfying the weakest security notion, namely ciphertext indistinguishability under one-time attacks (IND-OT-security).

15:41 [Event][New] RCD-2013: Romanian Cryptology Days, RCD-2013

  Submission: 1 May 2013
Notification: 1 July 2013
From September 16 to September 17
Location: Bucharest, Romania
More Information:

10:28 [Event][New] DBSec: 27th IFIP WG 11.3 Working Conference on Data and Application and Privacy

  Submission: 15 February 2013
Notification: 19 April 2013
From July 15 to July 17
Location: Newark, NJ, USA
More Information: