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] New Identity Based Encryption And Its Proxy Re-encryption, by Xu An Wang and Xiaoyuan Yang

  Identity based encryption (IBE) has received great attention since Boneh and Franklin\'s breakthrough work on bilinear group based IBE [4]. Till now, many IBE schemes relying on bilinear groups with dierent properties have been proposed [5, 25, 29, 14]. However, one part of the user\'s private key in all these IBE schemes is constructed as y = f(msk), where msk is the master key and y is an element in the underlying bilinear group G. In this paper, we propose a new IBE: one part of the private key is y = f(msk), where msk is the master key and y is an element in Zp . Here p is the underlying bilinear group\'s prime order. By using some novel techniques, we prove this new IBE is semantic secure under the selective identity chosen plaintext attacks (IND-sID-CPA) in the standard model. Based on this IBE scheme, we construct

an IND-ID-CCA secure identity based proxy re-encryption (IBPRE) scheme

which is master secret secure and ecient for the proxy compared with

other IND-ID-CCA (IBPRE) schemes.

15:50 [Event][Update] SCC2012: Third international conference on Symbolic Computation and Cryptography

  Submission: 12 May 2012
Notification: 18 May 2012
From July 11 to July 13
Location: Castro Urdiales(Cantabria), Spain
More Information:

18:17 [Pub][ePrint] A secret sharing scheme of prime numbers based on hardness of factorization, by Kai-Yuen Cheong

  Secret sharing schemes usually have perfect information theoretic security. This implies that each share must be as large as the secret. In this work we propose a scheme where the shares are smaller, while the security becomes computational. The computational security assumption is hardness of factorization, which is a simple and rather standard assumption in cryptography. In our scheme, the shared secret can only be a set of prime numbers.

18:17 [Pub][ePrint] A Generalization of the Rainbow Band Separation Attack and its Applications to Multivariate Schemes, by Enrico Thomae

  The Rainbow Signature Scheme is a non-trivial generalization of the well known Unbalanced Oil and Vinegar (UOV) signature scheme (Eurocrypt \'99) minimizing the length of the signatures. By now the Rainbow Band Separation attack is the best key recovery attack known. For some sets of parameters it is even faster than a direct attack on the public key. Unfortunately the available description of the attack is very ad hoc and does not provide deep insights.

In this article we provide another view on the Rainbow Band Separation attack using the theory of equivalent keys and a new generalization called good keys. Thereby we generalize the attack into a framework that also includes Reconciliation attacks. We further formally prove the correctness of the attack and show that it does not only perform well on Rainbow, but on all multivariate quadratic (MQ) schemes that suffer from missing cross-terms. We apply our attack and break the Enhanced STS signature scheme and all its variants, as well as the MFE encryption scheme and its variant based on Diophantine equations. In the case of Rainbow and Enhanced TTS we show that parameters have to be chosen carefully and that the remaining efficiency gain over UOV is small. As there is still some room to improve the Band Separation attack, it is not clear whether layer-based MQ-schemes will eventually become superfluous or not.

18:17 [Pub][ePrint] Shorter IBE and Signatures via Asymmetric Pairings, by Jie Chen and Hoon Wei Lim and San Ling and Huaxiong Wang and Hoeteck Wee

  We present efficient Identity-Based Encryption (IBE) and signature schemes

under the Symmetric External Diffie-Hellman (SXDH) assumption in bilinear

groups. In both the IBE and the signature schemes,

all parameters have constant numbers of group elements,

and are shorter than those of previous constructions

based on Decisional Linear (DLIN) assumption. Our constructions use both

dual system encryption (Waters, Crypto \'09) and dual pairing vector spaces

(Okamoto and Takashima, Pairing \'08, Asiacrypt \'09). Specifically, we show

how to adapt the recent DLIN-based instantiations of Lewko (Eurocrypt \'12)

to the SXDH assumption. To our knowledge, this is the first work to instantiate

either dual system encryption or dual pairing vector spaces under the SXDH assumption.

18:17 [Pub][ePrint] When Homomorphism Becomes a Liability, by Zvika Brakerski

  We show that an encryption scheme cannot have a simple decryption circuit and be homomorphic at the same time. Specifically, if a scheme can homomorphically evaluate the majority function, then its decryption circuit cannot be a linear function of the secret key (or even a succinct polynomial), even if decryption error is allowed.

An immediate corollary is that known schemes that are based on the hardness of decoding in the presence of noise with low hamming weight cannot be fully homomorphic. This applies to known schemes such as LPN-based symmetric or public key encryption.

An additional corollary is that the recent candidate fully homomorphic encryption, suggested by Bogdanov and Lee (ePrint \'11, henceforth BL), is insecure. In fact, we show two attacks on the BL scheme: One by applying the aforementioned general statement, and another by directly attacking one of the components of the scheme.

18:17 [Pub][ePrint] ZKPDL: A Language-Based System for Efficient Zero-Knowledge Proofs and Electronic Cash, by Sarah Meiklejohn and C. Chris Erway and Alptekin Küpçü and Theodora Hinkle and Anna Lysyanskaya

  In recent years, many advances have been made in cryptography, as well as in the performance of communication networks and processors. As a result, many advanced cryptographic protocols are now efficient enough to be considered practical, yet research in the area remains largely theoretical and little work has been done to use these protocols in practice, despite a wealth of potential applications.

This paper introduces a simple description language, ZKPDL, and an interpreter for this language. ZKPDL implements non-interactive zero-knowledge proofs of knowledge, a primitive which has received much attention in recent years. Using our language, a single program may specify the computation required by both the prover and verifier of a zero-knowledge protocol, while our interpreter performs a number of optimizations to lower both computational and space overhead.

Our motivating application for ZKPDL has been the efficient implementation of electronic cash. As such, we have used our language to develop a cryptographic library, Cashlib, that provides an interface for using ecash and fair exchange protocols without requiring expert knowledge from the programmer.

18:17 [Pub][ePrint] Secure password-based remote user authentication scheme with non-tamper resistant smart cards, by Ding Wang and Chun-guang Ma and Peng Wu

  It is a challenge for password authentication protocols using non-tamper resistant smart cards to achieve user anonymity, forward secrecy, immunity to various attacks and high performance at the same time. In DBSec\'11, Li et al. showed that Kim and Chung\'s password-based remote user authentication scheme is vulnerable to various attacks if the smart card is non-tamper resistant. Consequently, an improved version was proposed and claimed that it is secure against smart card security breach attacks. In this paper, however, we will show that Li et al.\'s scheme still cannot withstand offline password guessing attack under the non-tamper resistance assumption of the smart card. In addition, their scheme is also vulnerable to denial of service attack and fails to provide user anonymity and forward secrecy. As our main contribution, a robust scheme is presented to cope with the aforementioned defects, while keeping the merits of different password authentication schemes using smart cards. The analysis demonstrates that our scheme meets all the proposed criteria and eliminates several hard security threats that are difficult to be tackled at the same time in previous scholarship.

18:17 [Pub][ePrint] Physical Unclonable Functions in Cryptographic Protocols: Security Proofs and Impossibility Results, by Marten van Dijk and Ulrich Rührmair

  We investigate the power of physical unclonable functions (PUFs) as a new primitive in cryptographic protocols. Our contributions split into three parts. Firstly, we focus on the realizability of PUF-protocols in a special type of stand-alone setting (the \"stand-alone, good PUF setting\") under minimal assumptions. We provide new PUF definitions that require only weak average security properties of the PUF, and prove that these definitions suffice to realize secure PUF-based oblivious transfer (OT), bit commitment (BC) and key exchange (KE) in said setting. Our protocols for OT, BC and KE are partly new, and have certain practicality and security advantages compared to existing schemes.

In the second part of the paper, we formally prove that there are very sharp limits on the usability of PUFs for OT and KE {\\em beyond} the above stand-alone, good PUF scenario. We introduce two new and realistic attack models, the so-called posterior access model (PAM) and the bad PUF model, and prove several impossibility results in

these models. First, OT and KE protocols whose security is solely based on PUFs are generally impossible in the PAM. More precisely, one-time access of an adversary to the PUF after the end of a single protocol (sub-)session makes all previous (sub-)sessions provably insecure. Second, OT whose security is solely based on PUFs is

impossible in the bad PUF model, even if only a stand alone execution of the protocol is considered (i.e., even if no adversarial PUF access after the protocol is allowed). Our impossibility proofs do not only hold for the weak PUF definition of the first part of the paper, but even apply if ideal randomness and unpredictability is assumed in the PUF, i.e., if the PUF is modeled as a random permutation oracle.

In the third part, we investigate the feasibility of PUF-based bit commitment beyond the stand-alone, good PUF setting. For a number of reasons, this case is more complicated than OT and KE. We first prove that BC is impossible in the bad PUF model if players have got access to the PUF between the commit and the reveal phase. Again, this result holds even if the PUF is \"ideal\" and modeled as a random permutation oracle. Secondly, we sketch (without proof) two new BC-protocols, which can deal with bad PUFs or with adversarial access between the commit and reveal phase, but not with both.

We hope that our results can contribute to a clarification of the usability of PUFs in cryptographic protocols. They show that new hardware properties such as offline certifiability and the erasure of PUF responses would be required in order to make PUFs a broadly applicable cryptographic tool. These features have not yet been realized in practical PUF-implementations and generally seem hard to achieve at low costs. Our findings also show that the question how PUFs can be modeled comprehensively in a UC-setting must be considered at least partly open.

18:17 [Pub][ePrint] Languages with Efficient Zero-Knowledge PCP\'s are in SZK, by Mohammad Mahmoody and David Xiao

  A \\emph{Zero-Knowledge PCP} (ZK-PCP) is a randomized PCP such that

the view of any (perhaps cheating) efficient verifier can be

efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC \'97)

constructed ZK-PCPs for all languages in $\\NEXP$. Ishai, Mahmoody,

and Sahai (TCC \'12), motivated by cryptographic applications,

revisited the possibility of \\emph{efficient} ZK-PCPs for all $L \\in

\\NP$ where the PCP is encoded as a polynomial-size circuit that

given a query $i$ returns the $i\\th$ symbol of the PCP.

Ishai \\etal showed that there is no efficient ZK-PCP for $\\NP$ with

a \\emph{non-adaptive} verifier, who prepares all of its PCP queries

before seeing any answers, unless $\\NP \\se \\coAM$ and

polynomial-time hierarchy collapses. The question of whether

\\emph{adaptive} verification can lead to efficient ZK-PCPs for $\\NP$

remained open.

In this work, we resolve this question and show that any language or

promise problem with efficient ZK-PCPs must be in $\\SZK$ (the class

of promise problems with a statistical zero-knowledge \\emph{single

prover} proof system). Therefore, no $\\NP$-complete problem can

have an efficient ZK-PCP unless $\\NP \\se \\SZK$ (which also implies

$\\NP \\se \\coAM$ and the polynomial-time hierarchy collapses).

We prove our result by reducing any promise problem with an efficient

ZK-PCP to two instances of the $\\CEA$ problem defined and studied by

Vadhan (FOCS\'04) which is known to be complete for the class $\\SZK$.

18:17 [Pub][ePrint] On Ideal Lattices and Learning with Errors Over Rings, by Vadim Lyubashevsky and Chris Peikert and Oded Regev

  The ``learning with errors\'\' (LWE) problem is to distinguish random

linear equations, which have been perturbed by a small amount of

noise, from truly uniform ones. The problem has been shown to be as

hard as worst-case lattice problems, and in recent years it has served

as the foundation for a plethora of cryptographic applications.

Unfortunately, these applications are rather inefficient due to an

inherent quadratic overhead in the use of LWE. A main open question

was whether LWE and its applications could be made truly efficient by

exploiting extra algebraic structure, as was done for lattice-based

hash functions (and related primitives).

We resolve this question in the affirmative by introducing an

algebraic variant of LWE called \\emph{ring-LWE}, and proving that it

too enjoys very strong hardness guarantees. Specifically, we show

that the ring-LWE distribution is pseudorandom, assuming that

worst-case problems on ideal lattices are hard for polynomial-time

quantum algorithms. Applications include the first truly practical

lattice-based public-key cryptosystem with an efficient security

reduction; moreover, many of the other applications of LWE can be made

much more efficient through the use of ring-LWE.