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

00:17 [Pub][JoC] A Note on Constant-Round Zero-Knowledge Proofs of Knowledge


Abstract  In this note, we show the existence of constant-round computational zero-knowledge proofs of knowledge for all . The existence of constant-round zero-knowledge proofs was proven by Goldreich and Kahan (Journal of Cryptology, 1996), and the existence of constant-round zero-knowledge arguments of knowledge was proven by Feige and Shamir (CRYPTO, 1989). However, the existence of constant-round zero-knowledge proofs of knowledge for all is folklore, to the best of our knowledge, since no proof of this fact has been published.

  • Content Type Journal Article
  • Pages 1-17
  • DOI 10.1007/s00145-012-9132-7
  • Authors

    • Yehuda Lindell, Department of Computer Science, Bar-Ilan University, Ramat Gan, Israel

    • Journal Journal of Cryptology
    • Online ISSN 1432-1378
    • Print ISSN 0933-2790

From: Mon, 15 Oct 2012 16:40:04 GMT

18:17 [Pub][ePrint] Symbolic computation in block cipher with application to PRESENT, by Changyong Peng and Chuangying zhu and Yuefei Zhu and Fei Kang

  In this paper,we give an example of how symbolic computation are used to analyze the block cipher

PRESENT,an ultra-lightweight block cipher proposed by Bogdanov et al. at CHES\'07.The

block size is 64 bits and the key size can be 80 bit or 128 bit.Using Mathematica 7.0,this paper

obtains the unexpanded polynomial expressions of the output of round 1-6 of PRESENT-80(80-

bit key variant).The time complexity of getting these expressions is 4 minutes on a PC with a

2.6GHz CPU and 8G RAM.Then we expand the expressions of the output of round 1-2 and the

LSB(least significant bit) of the output of round 3 and obtain the ANFs(Algebraic Normal Form)

of these 129(=2*64+1) expressions. The time complexity of getting these ANFs is 22 minutes.It

it known that the time complexity of the classical method of computing the ANF of an n-ary

Boolean function from its truth table is O(n*2^n),with total time complexity of obtaining these 129

ANFs O(129*144*2^144) = O(2^158)(each of the 129 ANFs can be viewed as a 144-ary Boolean

function,where 144=64+80,the sum of the block size and the key size).As an application,we give

a side channel attack on PRESENT-80 under the single bit leakage model proposed by Dinur and

Shamir.If the LSB bit of the output of the 3rd round can be obtained without error,then with 200

known plaintexts,we can set up an equation system in terms of the master key bits and can recover

43 bits key by the Gr¨obner Basis method.Compared with the previous side channel attack

on PRESENT,such as Yang et al. in CANS 2009,Abdul-Latip et al. in ASIACCS 2011 and Zhao

et al. in 2011,each of which needs at least 2^13 chosen plaintexts,the data complexity of our attack

is the best.

15:17 [Pub][ePrint] Nanoelectronic Solutions for Hardware Security, by Jeyavijayan Rajendran, Ramesh Karri, James B. Wendt, Miodrag Potkonjak, Nathan McDonald, Garrett S. Rose, and Bryant Wysocki

  Information security has emerged as an important system and application metric. Classical security solutions use algorithmic mechanisms that address a small subset of emerging security requirements, often at high energy and performance overhead. Further, emerging side channel and physical attacks can compromise classical

security solutions. Hardware based security solutions overcome many of the limitations of classical security while consuming less energy and improving performance. Nanoelectronics based hardware security preserves all of these advantages while enabling conceptually new security mechanisms and security applications. This paper highlights

nanoelectronics based security capabilities and challenges. The paper describes nanoelectronics based hardware security primitives for device identification, digital forensics, and tamper detection. These primitives can be developed using the unique characteristics of emerging nanoelectronic devices such as complex device and system models, bidirectional operation, and temporal drift of the state variable. We conclude by identifying important desiderata and outstanding challenges in nanoelectronics based security.

15:17 [Pub][ePrint] Concurrent Signatures without Random Oracles, by Xiao Tan and Qiong Huang and Duncan S. Wong

  Concurrent signatures provide a way to exchange digital signature among parties in an efficient and fair manner. To the best of our knowledge, all the existing solutions are all proven secure in the random oracle model, which is only heuristic. How to build an efficient concurrent signature scheme in the standard model has been remaining an open problem since the introduction in EUROCRYPT 2004. In this paper we answer the problem affirmatively and propose a novel construction of concurrent signature, the security of which does not rely on the random oracle assumption. The ambiguity of our scheme is slightly different from the existing schemes, requiring that any one can produce indistinguishable ambiguous signatures using merely public information. Security of the new scheme is based on Computational Diffie-Hellman (CDH) assumption in the standard model, which is a rather standard and well-studied assumption in cryptography.

15:17 [Pub][ePrint] A Framework for Unique Ring Signatures, by Matthew Franklin and Haibin Zhang

  We propose a simple, general, and unified framework for constructing unique ring signatures that simplify and capture the spirit of linkable ring signatures. The framework, which can be efficiently instantiated in the random oracle and the standard model, is obtained by generalizing the Bellare-Goldwasser ``PRF made public\" paradigm. Security of the first instantiation can be tightly related to the DDH problem. The scheme leads to the most efficient linkable/unique ring signature in the random oracle model, for a given level of provable security. The second one based on stronger assumptions partly simplifies and slightly improves sublinear size traceable ring signature of Fujisaki. Both of the improvements would be difficult without the general framework in hand.

15:17 [Pub][ePrint] Security Evaluations Beyond Computing Power: How to Analyze Side-Channel Attacks you Cannot Mount? , by Nicolas Veyrat-Charvillon and Benoît Gérard and François-Xavier Standaert

  Present key sizes for symmetric cryptography are usually required to be at least 80-bit long for short-term protection, and 128-bit long for long-term protection. However, current tools for security evaluations against side-channel attacks do not provide a precise estimation of the remaining key strength after some leakage has been observed, e.g. in terms of number of candidates to test. This leads to an uncomfortable situation, where the security of an implementation can be anywhere between enumerable values (i.e. $2^{40}$ -- $2^{50}$ key candidates to test) and the full key size (i.e. $2^{80}$ -- $2^{128}$ key candidates to test). In this paper, we mitigate this important issue, and describe a key rank estimation algorithm that provides tight bounds for the security level of leaking cryptographic devices. As a result and for the first time, we are able to analyze the full complexity of \"standard\" (i.e. divide-and-conquer) side-channel attacks, in terms of their tradeoff between time, data and memory complexity.

15:17 [Pub][ePrint] Defending Against the Unknown Enemy: Applying FlipIt to System Security, by Kevin D. Bowers and Marten van Dijk and Robert Griffin and Ari Juels and Alina Oprea and Ronald L. Rivest and Nikos Triandop

  Most cryptographic systems carry the basic assumption that entities

are able to preserve the secrecy of their keys. With attacks today showing ever increasing sophistication, however, this tenet is eroding. \"Advanced Persistent Threats\" (APTs), for instance, leverage zero-day exploits and extensive system knowledge to achieve full compromise of cryptographic keys and other secrets.Such compromise is often silent, with defenders failing to detect the loss of private

keys critical to protection of their systems. The growing virulence of today\'s threats clearly calls for new models of defenders\' goals and abilities.

In this paper, we explore applications of FlipIt, a novel game-theoretic model of system defense introduced recently. In FlipIt, an attacker periodically gains complete control of a system, with the unique feature that system compromises are stealthy, i.e., not immediately detected by the system owner, called the defender. We distill out several lessons from our study of FlipIt and demonstrate

their application to several real-world problems, including password reset policies, key rotation, VM refresh and cloud auditing.

15:17 [Pub][ePrint] Cryptanalysis of the OKH Authenticated Encryption Scheme, by Peng Wang and Wenling Wu and Liting Zhang

  Alomair proposed a new authenticated encryption scheme OKH at ACNS 2012, and proved the security, i.e. authenticity and privacy, of OKH. Our research shows that it is not the case. We only need one query to break the authenticity of OKH with success probability of $1$, and two queries to break the privacy of OKH with success probability of $1-1/2^n$, where $n$ is the block-length of underlying blockcipher.

15:17 [Pub][ePrint] On the security of two smart-card-based remote user authentication schemes for WSN, by Ding Wang and Chun-guang Ma

  Understanding security failures of cryptographic protocols is the key to both patching existing protocols and designing future schemes. The design of secure and efficient remote user authentication schemes for real-time data access in wireless sensor networks (WSN) is still an open and quite challenging problem, though many schemes have been proposed lately. In this study, we analyze two recent proposals in this research domain. Firstly, Das et al.\'s scheme is scrutinized, demonstrating its vulnerabilities to smart card security breach attack and privileged insider attack, which are among the security objectives pursued in their protocol specification. Then, we investigate a temporal-credential-based password authentication scheme introduced by Xue et al. in 2012. This protocol only involves hash and XOR operations and thus is suitable for the resource-constrained WSN environments where an external user wants to obtain real-time data from the sensor nodes inside WSN. However, notwithstanding their security arguments, we point out that Xue et al.\'s protocol is still vulnerable to smart card security breach attack and privileged insider attack, and fails to provide identity protection. The proposed cryptanalysis discourages any use of the two schemes under investigation in practice and reveals some subtleties and challenges in designing this type of schemes. Besides reporting the security flaws, we put forward a principle that is vital for designing more robust two-factor authentication schemes for WSN.

15:17 [Pub][ePrint] Using Randomizers for Batch Verification of ECDSA Signatures, by Sabyasachi Karati and Abhijit Das and Dipanwita Roychowdhury

  Randomizers are popularly used to prevent various types of attacks on batch-verification schemes. Recently, several algorithms based upon symbolic computation are proposed for the batch verification of ECDSA signatures. In this article, we demonstrate that the concept of randomizers can be easily embedded in these symbolic-computation algorithms. The performance degradation caused by randomizers is comparable with that associated with ECDSA*.

15:17 [Pub][ePrint] New Constructions and Proof Methods for Large Universe Attribute-Based Encryption, by Yannis Rouselakis and Brent Waters

  We propose two large universe Attribute-Based Encryption constructions. In a large universe ABE construction any string can be used as an attribute and attributes need not be enumerated at system setup. Our first construction establishes a novel large universe Ciphertext-Policy ABE scheme on prime order bilinear groups, while the second achieves

a significant efficiency improvement over the large universe Key-Policy ABE systems of Lewko-Waters and Lewko. Both schemes are selectively secure in the standard model under two \"q-type\" assumptions similar to ones used in prior works. Our work brings back \"program and cancel\" techniques to this problem.

We provide implementations and benchmarks of our constructions

in Charm; a programming environment for rapid prototyping of cryptographic primitives.