International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. 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).

2013-10-28
21:17 [Pub][ePrint] Non-Malleability from Malleability: Simulation-Sound Quasi-Adaptive NIZK Proofs and CCA2-Secure Encryption from Homomorphic Signatures, by Benoit Libert and Thomas Peters and Marc Joye and Moti Yung

  Verifiability is central to building protocols and systems with integrity. Initially, efficient methods employed the Fiat-Shamir

heuristics. Since 2008, the Groth-Sahai techniques have been the most efficient in constructing non-interactive witness indistinguishable and zero-knowledge proofs for algebraic relations. For the important task of proving membership in linear subspaces, Jutla and Roy (Asiacrypt 2013) gave significantly more efficient proofs in the quasi-adaptive setting (QA-NIZK). For membership of the row space of a $t \\times n$ matrix, their QA-NIZK proofs save $O(2t)$ group elements compared to Groth-Sahai. Here, we give QA-NIZK proofs made of a {\\it constant} number group elements -- regardless of the number of equations or the number of variables -- and additionally prove them {\\it unbounded} simulation-sound. Unlike previous unbounded simulation-sound Groth-Sahai-based proofs, our construction does not involve quadratic pairing product equations and does not rely on a chosen-ciphertext-secure encryption scheme. Instead, we build on structure-preserving signatures with homomorphic properties. We apply our methods to design new and improved CCA2-secure encryption schemes. In particular, we build the first efficient threshold CCA-secure keyed-homomorphic encryption scheme ({\\it i.e.}, where homomorphic operations can only be carried out using a dedicated evaluation key) with publicly verifiable ciphertexts.



21:17 [Pub][ePrint] Faster Compact Diffie-Hellman: Endomorphisms on the x-line, by Craig Costello and Huseyin Hisil and Benjamin Smith

  We describe an implementation of fast elliptic curve scalar multiplication, optimized for Diffie-Hellman Key Exchange at the 128-bit security level. The algorithms are compact (using only x-coordinates), run in constant time with uniform execution patterns, and do not distinguish between the curve and its quadratic twist; they thus have a built-in measure of side- channel resistance. The core of our construction is a suite of two-dimensional differential addition chains driven by efficient endomorphism decompositions, built on curves selected from a family of Q-curve reductions over F_{p^2} with p = 2^{127}-1. We include state-of-the-art experimental results for twist-secure, constant-time, x-coordinate-only scalar multiplication.



21:17 [Pub][ePrint] Secure Key Exchange and Sessions Without Credentials, by Ran Canetti and Vladimir Kolesnikov and Charles Rackoff and and Yevgeniy Vahlis

  Secure communication is a fundamental cryptographic primitive. Typically, security is achieved by relying on an existing credential infrastructure, such as a PKI or passwords, for identifying the end points to each other. But what can be obtained when no such credential infrastructure is available?

Clearly, when there is no pre-existing credential infrastructure, an adversary can mount successful ``man in the middle\'\' attacks by modifying the communication between the legitimate endpoints. Still, we show that not all is lost, as long as the adversary\'s control over the communication is not complete: We present relatively efficient key exchange and secure session protocols that provide the full guarantee of secure communication as long as the adversary fails to intercept even a single message between the legitimate endpoints.

To obtain this guarantee we strengthen the notion of key exchange to require that the keys exchanged in any two sessions are independent of each other as long as each session has at least one honest endpoint, even if both sessions has an adversarial endpoint. We call this notion credential-free key exchange. We then strengthen the existing notion of secure session protocols to provide the above guarantee given a CFKE (existing definitions and constructions are insufficient for this purpose). We provide two alternative definitions and constructions of CFKE, a game-based one with a construction in the RO model, and a UC one with a construction in the CRS model.



21:17 [Pub][ePrint] Write-Only Oblivious RAM based Privacy-Preserved Access of Outsourced Data, by Lichun Li and Anwitaman Datta

  Oblivious RAM (ORAM) has recently attracted a lot of interest since

it can be used to protect the privacy of data user\'s data access pattern from (honest but curious) outsourced storage. This is

achieved by simulating each original data read or write operation with some read and write operations on some real and dummy data items. This paper proposes two single-server write-only ORAM schemes and one multi-server write-only ORAM scheme, which simulate only the write operations and protect only the write pattern. The reduction of functions however allows to build much simpler and efficient (in terms of communication cost and storage usage) write-only ORAMs. Write-only ORAM can be used in conjunction with Private Information Retrieval (PIR), which is a technique to protect data user\'s read patterns, in order to protect both write and read patterns. Write-only ORAM may be used alone too, when only write patterns need protection. We study two usage scenarios: (i) data publishing/sharing: where a data owner shares the data with others, who only consume the published information. Data consumers should not have write access to the outsourced data, and thus cannot use ORAM to protect their read patterns in this scenario. To hide access patterns from the outsourced storage, the data owner can use ORAM to write data, and data consumers use PIR to read data. Alternatively, for some applications, a data consumer can trivially download all data once or regularly, and neither the data owner nor data consumers mind that the outsourced storage learns such read pattern. Compared with using traditional ORAM, using the simpler write-only ORAM here produces much less communication cost and/or client-side storage usage. Our single-server write-only ORAM scheme produces lower (typically one order lower) communication cost with the same client-side storage usage, or requires much less (typically at least one order less) client-side storage to achieve the same level of communication cost than the best known single-server full functional ORAM schemes do. Compared with the

best known multi-server ORAM scheme, our write-only ORAM schemes have lower (typically one order lower) communication cost, or achieve the same communication cost with the same client-side storage usage in single-server setting. (ii) the data owner\'s personal use: Our write-only ORAM schemes combined with PIR can be used as building blocks for some existing full functional ORAM schemes. This leads to the reduction of the communication costs for two full-functional ORAM schemes by the factors of $O(\\log N)$ and $O(\\sqrt{\\log N}\\times \\log\\log N)$, where $N$ is the maximum data item count. One of these resulting schemes has a communication cost of $O(l)$, where $l$ is data item length. This is typically one order lower than the previous best known ORAM scheme\'s cost, which is $O(\\log N \\times l)$. The other resulting scheme also achieves $O(\\log N \\times l)$ communication cost, but its client-side storage usage is several orders lower than the best known single-server ORAM\'s.



21:17 [Pub][ePrint] AEGIS: A Fast Authenticated Encryption Algorithm, by Hongjun Wu and Bart Preneel

  This paper introduces a dedicated authenticated encryption algorithm AEGIS; AEGIS allows for the protection of associated data which makes it very suitable for protecting network packets. AEGIS-128L uses eight AES round functions to process a 32-byte message block (one step). AEGIS-128 uses five AES round functions to process a 16-byte message block (one step); AES-256 uses six AES round functions. The security analysis shows that these algorithms offer a high level of security. On the Intel Sandy Bridge Core i5 processor, the speed of AEGIS-128L, AEGIS-128 and AEGIS-256 is around 0.48, 0.66 and 0.7 clock cycles/byte (cpb) for 4096-byte messages, respectively. This is substantially faster than the AES CCM, GCM and OCB modes.



21:17 [Pub][ePrint] Examination of a New Defense Mechanism: Honeywords, by Ziya Genc, S├╝leyman Kardas, and Mehmet Sabir Kiraz

  It has become much easier to crack a password

hash with the advancements in the graphicalprocessing

unit (GPU) technology. An adversary can

recover a user\'s password using brute-force attack on

password hash. Once the password has been recovered

no server can detect any illegitimate user authentication

(if there is no extra mechanism used).

In this context, recently, Juels and Rivest published a

paper for improving the security of hashed passwords.

Roughly speaking, they propose an approach for user

authentication, in which some false passwords, i.e., \"honeywords\"

are added into a password file, in order to

detect impersonation. Their solution includes an auxiliary

secure server called \"honeychecker\" which can distinguish

a user\'s real password among her honeywords and immediately

sets off an alarm whenever a honeyword is used.

In this paper, we analyze the security of the proposal and

provide some possible improvements which are easy to

implement



21:17 [Pub][ePrint] A More Efficient AES Threshold Implementation, by Begul Bilgin and Benedikt Gierlichs and Svetla Nikova and Ventzislav Nikov and Vincent Rijmen

  Threshold Implementations provide provable security against first-order power analysis attacks for hardware and software implementations. Like masking, the approach relies on secret sharing but it differs in the implementation of logic functions. At \\textsc{Eurocrypt} 2011 Moradi et al. published the to date most compact Threshold Implementation of AES-128 encryption. Their work shows that the number of required random bits may be an additional evaluation criterion, next to area and speed. We present a new Threshold Implementation of AES-128 encryption that is 18\\% smaller, 7.5\\% faster and that requires 8\\% less random bits than the implementation from \\textsc{Eurocrypt} 2011. In addition, we provide results of a practical security evaluation based on real power traces in adversary-friendly conditions. They confirm the first-order attack resistance of our implementation and show good resistance against higher-order attacks.



21:17 [Pub][ePrint] Cryptanalysis and improvement of a dynamic and secure key management model for hierarchical heterogeneous sensor networks, by Xi-Jun Lin and Lin Sun

  In 2012, Alagheband and Aref presented a dynamic and secure key manage

ment model for hierarchical heterogeneous sensor networks. They proposed a signcryption algorithm which is the main building block in their key management model. They proved the algorithm is as strong as the elliptical curve discrete logarithm problem. In this work,

we study the security of their signcryption algorithm. It is regretful that we found their algorithm is insecure. The adversary can impersonate the base station by sending forged messages to the cluster leaders after capturing the signcrypted messages. Hence, the key management model proposed by them is insecure. Then, we propose an improved signcryption algorithm to fix this weakness.



21:17 [Pub][ePrint] Bootstrapping Obfuscators via Fast Pseudorandom Functions, by Benny Applebaum

  We show that it is possible to upgrade an obfuscator for a weak complexity class $\\weak$ into an obfuscator for arbitrary polynomial size circuits, assuming that the class $\\weak$ can compute pseudorandom functions. Specifically, under standard intractability assumptions (e.g., hardness of factoring, Decisional Diffie--Hellman, or Learning with Errors), the existence of obfuscators for $\\NC^1$ or even $\\TC^0$ implies the existence of general-purpose obfuscators for $\\classP$. Previously, such a bootstrapping procedure was known to exist under the assumption that there exists a fully-homomorphic encryption whose decryption algorithm can be computed in $\\weak$. Our reduction works with respect to virtual black-box obfuscators and relativizes to ideal models.



21:17 [Pub][ePrint] Higher Order Masking of Look-up Tables, by Jean-Sebastien Coron

  We describe a new algorithm for masking look-up tables of block-ciphers at any order, as a countermeasure against side-channel attacks. Our technique is a generalization of the classical randomized table countermeasure against first-order attacks. We prove the security of our new algorithm against t-th order attacks in the usual Ishai-Sahai-Wagner model from Crypto 2003; we also improve the bound on the number of shares from n>=4t+1 to n>= 2t+1 for an adversary who can adaptively move its probes between successive executions.

Our algorithm has the same time complexity O(n^2) as the Rivain-Prouff algorithm for AES, and its extension by Carlet et al. to any look-up table. In practice for AES our algorithm is less efficient than Rivain-Prouff, which can take advantage of the special algebraic structure

of the AES Sbox; however for DES our algorithm performs slightly better.



21:17 [Pub][ePrint] More on the Impossibility of Virtual-Black-Box Obfuscation with Auxiliary Input, by Nir Bitansky and Ran Canetti and Omer Paneth and Alon Rosen

  We show that if there exist indistinguishability obfuscators for a certain class C of circuits then there do not exist independent-auxiliary-input virtual-black-box (VBB) obfuscators for any family of circuits that compute a pseudo-entropic function. A function f_k is pseudo-entropic if it is hard, given oracle access to f_k but without asking explicitly on a value x, to distinguish f_k(x) from a random variable with some real entropy.

This strengthens the bound of Goldwasser and Kalai [FOCS `05, ePrint `13] that rules out dependent-auxiliary-input VBB obfuscation for the same set of circuit families, assuming inditinguishability obfuscators for another class, C\', of circuits. That is, while they only rule out the case where the adversary and the simulator obtain auxiliary information that depends on the actual (secret) obfuscated function, we rule out even the case where the auxiliary input depends only

on the (public) family of programs.