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

21:17 [Pub][ePrint] Improved Broadcast Encryption Scheme with Constant-Size Ciphertext, by Renaud Dubois and Aurore Guillevic and Marine Sengelin Le Breton

  The Boneh-Gentry-Waters (BGW) scheme is one of the most efficient broadcast encryption scheme regarding the overhead size. This performance relies on the use of a pairing. Hence this protocol can benefit from public key improvements. The ciphertext is of constant size, whatever the proportion of revoked users is. The main lasting constraint is the computation time at receiver end as it depends on the number of revoked users. In this paper we describe two modifications to improve the BGW bandwidth and time complexity. First we rewrite the protocol and its security proof with an asymmetric pairing over the Barreto-Naehrig (BN) curves instead of a symmetric one over supersingular curves. This modification leads to a practical gain of 60 % in speed and 84 % in bandwidth. The second tweaks allows to reduce the computation time from $O(n-r)$ to $\\min(O(r),O(n-r))$ for the worst case (and better for the average case). We give performance measures of our implementation for a 128-bit security level of the modified protocol on a smartphone.

21:17 [Pub][ePrint] Simultaneous hashing of multiple messages , by Shay Gueron and Vlad Krasnov

  We describe a method for efficiently hashing multiple messages of different lengths. Such computations occur in various scenarios, and one of them is when an operating system checks the integrity of its components during boot time. These tasks can gain performance by parallelizing the computations and using SIMD architectures. For such scenarios, we compare the performance of a new 4-buffers SHA-256 S-HASH implementation, to that of the standard serial hashing. Our results are measured on the 2nd Generation IntelĀ® Core(TM) Processor, and demonstrate SHA-256 processing at effectively ~5.2 Cycles per Byte, when hashing from any of the three cache levels, or from the system memory. This represents speedup by a factor of 3.42x compared to OpenSSL (1.0.1), and by 2.25x compared to the recent and faster n-SMS method. For hashing from a disk, we show an effective rate of ~6.73 Cycles/Byte, which is almost 3 times faster than OpenSSL (1.0.1) under the same conditions. These results indicate that for some usage models, SHA-256 is significantly faster than commonly perceived.

21:17 [Pub][ePrint] New Preimage Attacks on Hash Modes of AES-256, by Deukjo Hong and Dong-Chan Kim and Daesung Kwon

  We study the slow diffusion of the AES key schedule for 256-bit keys and find weakness which can be used in the preimage attack on Davis-Meyer mode. Our preimage attack works for 8 rounds of AES- 256 with the computational complexity of $2^{124.9}$, while the best previous attack works for 7 rounds of AES-256. It is also extended to the preimage attack on some well-known double-block-length hash modes assuming the underlying block cipher is 8-round AES-256, whose computational complexity is $2^{252.9}$.

21:17 [Pub][ePrint] Optimal Lower Bound for Differentially Private Multi-Party Aggregation, by T-H. Hubert Chan and Elaine Shi and Dawn Song

  We consider distributed private data analysis,

where $n$ parties each holding some sensitive data wish

to compute some aggregate statistics over all parties\' data.

We prove a tight lower bound for the private distributed summation

problem. Our lower bound is strictly stronger than

the prior lower-bound result by Beimel, Nissim, and Omri

published in CRYPTO 2008.

In particular, we show that any $n$-party protocol

computing the sum with sparse communication graph

must incur an additive error

of $\\Omega(\\sqrt{n})$

with constant probability, in order

to defend against potential coalitions of compromised users.

Furthermore, we show that in the client-server communication model,

where all users communicate solely with an untrusted server,

the additive error must be $\\Omega(\\sqrt{n})$, regardless of

the number of messages or rounds.

Both of our lower-bounds, for the general setting and the


communication model, are strictly stronger than those of

Beimel, Nissim and Omri, since we remove the assumption

on the number of rounds (and

also the number of messages in the client-to-server

communication model).

Our lower bounds generalize to the

$(\\epsilon, \\delta)$ differential

privacy notion, for reasonably small values of $\\delta$.

21:17 [Pub][ePrint] Infiltrate the Vault: Security Analysis and Decryption of Lion Full Disk Encryption, by Omar Choudary and Felix Grobert and Joachim Metz

  With the launch of Mac OS X 10.7 (Lion), Apple has introduced a volume

encryption mechanism known as FileVault 2. Apple only disclosed marketing aspects of the closed-source software, e.g. its use of the AES-XTS tweakable encryption, but a publicly available security evaluation and detailed description was unavailable until now.

We have performed an extensive analysis of FileVault 2 and we have been able to find all the algorithms and parameters needed to successfully read an encrypted volume. This allows us to perform forensic investigations on encrypted volumes using our own tools.

In this paper we present the architecture of FileVault 2, giving details of the key derivation, encryption process and metadata structures needed to perform the volume decryption. Besides the analysis of the system, we have also built a library that can mount a volume encrypted with FileVault 2. As a contribution to the research and forensic communities we have made this library open source.

Additionally, we present an informal security evaluation of the system and comment on some of the design and implementation features. Among others we analyze the random number generator used to create the recovery password. We have also analyzed the entropy of each 512-byte block in the encrypted volume and discovered that part of the user data was left unencrypted.

21:17 [Pub][ePrint] How to Store some Secrets, by Reto E. Koenig and Rolf Haenni

  This paper introduces a special type of symmetric cryptosystem called multi-encryption scheme. It allows users to encrypt multiple plaintexts into a single ciphertext. Each plaintext is protected with its own secret key, meaning that they can be decrypted individually by applying the decryption function with the corresponding key to the ciphertext. Compared to encrypting the ciphertexts one-by-one using a standard symmetric cryptosystem, the main advantage of using a multi-encryption scheme is the no-search property, which guarantees that knowing the key is sufficient for decrypting a single plaintext. We show how to construct a multi-encryption scheme based on polynomials over finite fields. A possible application area is coercion-resistant electronic voting. To ensure a strong form of privacy, voters are equipped with multiple fake credentials, which are indistinguishable from the proper one. While theoretically sound, this requires a voter to perfectly recall multiple lengthy random numbers, and to know which of them is the proper one. To ensure 100\\% recall, users need to manage these numbers and keep them secret. A multi-encryption scheme is an elegant solution for this problem.

21:17 [Pub][ePrint] Combinatorial Solutions Providing Improved Security for the Generalized Russian Cards Problem, by Colleen M. Swanson and Douglas R. Stinson

  We present the first formal mathematical presentation of the generalized Russian cards problem, and provide rigorous security definitions that capture both basic and extended versions of weak and perfect security notions. In the generalized Russian cards problem, three players, Alice, Bob, and Cathy, are dealt a deck of $n$ cards, each given $a$, $b$, and $c$ cards, respectively. The goal is for Alice and Bob to learn each other\'s hands via public communication, without Cathy learning the fate of any particular card. The basic idea is that Alice announces a set of possible hands she might hold, and Bob, using knowledge of his own hand, should be able to learn Alice\'s cards from this announcement, but Cathy should not. Using a combinatorial approach, we are able to give a nice characterization of informative strategies (i.e., strategies allowing Bob to learn Alice\'s hand), having optimal communication complexity, namely the set of possible hands Alice announces must be equivalent to a large set of $t-(n, a, 1)$-designs, where $t=a-c$. We also provide some interesting necessary conditions for certain types of deals to be simultaneously informative and secure. That is, for deals satisfying $c = a-d$ for some $d \\geq 2$, where $b \\geq d-1$ and the strategy is assumed to satisfy a strong version of security (namely perfect $(d-1)$-security), we show that $a = d+1$ and hence $c=1$. We also give a precise characterization of informative and perfectly $(d-1)$-secure deals of the form $(d+1, b, 1)$ satisfying $b \\geq d-1$ involving $d-(n, d+1, 1)$-designs.

21:17 [Pub][ePrint] Distributed Key Generation in the Wild, by Aniket Kate and Yizhou Huang and Ian Goldberg

  Distributed key generation (DKG) has been studied extensively in the cryptographic literature. However, it has never been examined outside of the synchronous setting, and the known DKG protocols cannot guarantee safety or liveness over the Internet.

In this work, we present the first realistic DKG protocol for use over the Internet. We propose a practical system model for the Internet and define an efficient verifiable secret sharing (VSS) scheme in it. We observe the necessity of Byzantine agreement for asynchronous DKG and analyze the difficulty of using a randomized protocol for it. Using our VSS scheme and a leader-based agreement protocol, we then design a provably secure DKG protocol. We also consider and achieve cryptographic properties such as uniform randomness of the shared secret and compare static versus adaptive adversary models. Finally, we implement our DKG protocol, and establish its efficiency and reliability by extensively testing it on the PlanetLab platform. Counter to a general non-scalability perception about asynchronous systems, our experiments demonstrate that our asynchronous DKG protocol scales well with the system size and it is suitable for realizing multiparty computation and threshold cryptography over the Internet.

21:17 [Pub][ePrint] Multiparty Proximity Testing with Dishonest Majority from Equality Testing, by Ran Gelles and Rafail Ostrovsky and Kina Winoto

  Motivated by the recent widespread emergence of location-based services (LBS) over mobile devices, we explore efficient protocols for proximity-testing. Such protocols allow a group of friends to discover if they are all close to each other in some physical location, without revealing their individual locations to each other. We focus on hand-held devices and aim at protocols with very small communication complexity and a small number of rounds.

The proximity-testing problem can be reduced to the private equality testing (PET) problem, in which parties find out whether or not they hold the same input (drawn from a low-entropy distribution) without revealing any other information about their inputs to each other. While previous works analyze the 2-party PET special case (and its LBS application), in this work we consider highly-efficient schemes for the multiparty case with no honest majority. We provide schemes for both a direct-communication setting and a setting with a honest-but-curious mediating server that does not learn the users\' inputs. Our most efficient scheme takes 2 rounds, where in each round each user sends only a couple of ElGamal ciphertexts.

21:17 [Pub][ePrint] A Framework for Efficient Fully-Equipped UC Commitments, by Eiichiro Fujisaki

  We present a general framework for constructing non-interactive universally composable (UC) commitment schemes that are secure against adaptive adversaries in the erasure-free setting under a single re-usable common reference string.

Previously, such fully-equipped UC commitment schemes are

only known in \\cite{CF01,CLOS02}, with an unavoidable overhead of $O(\\spar)$; meaning that to commit $\\lambda$ bit, the communication and computational costs are $O(\\lambda\\spar)$. Efficient construction of a fully-equipped UC commitment scheme was a long-standing open problem. We introduce a new cryptographic primitive, called all-but-many encryptions (ABMEs), and prove that it is a translation of fully-equipped UC commitment in the algorithmic level. We implement ABMEs from two primitives, called probabilistic pseudo random functions

and extractable sigma protocols, where the former is a probabilistic version of pseudo random function and the latter is a special kind of sigma (i.e., canonical 3-round public-coin HVSZK) protocols with some extractability.

Interestingly, ABEs are not chosen-ciphertext secure, but still suffice to construct UC commitments without an additional zero-knowledge protocol.

We provide efficient fully-equipped UC commitment schemes

from ABMEs under DDH and DCR-based assumptions. The former is at least as efficient as the arguably most efficient UC commitment scheme~\\cite{Lin11:UCCom} (which is interactive and not erasure-free) in reasonable security parameters.

The latter is the first fully-equipped UC commitment scheme

with optimal expansion factor $O(1)$.

We also construct a fully-equipped UC commitment scheme from

a general assumption (that trap-door permutations exist), converted from a weak ABME in an non-black-box manner, which is far more efficient than the previous general construction~\\cite{CLOS02}, because it does not require any non-interactive zero knowledge protocol.

21:17 [Pub][ePrint] Several Weak Bit-Commitments Using Seal-Once Tamper-Evident Devices, by Ioana Boureanu and Serge Vaudenay

  Following both theoretical and practical arguments, we construct UC-secure bit-commitment protocols that place their strength on the sender\'s side and are built using tamper-evident devices, e.g., a type of distinguishable, sealed envelopes.

We show that by using a second formalisation of tamper-evident distinguishable envelopes we can attain better security guarantees, i.e., EUC-security.

We show the relations between several flavours of weak bit-commitments, bit-commitments and distinguishable tamper-evident envelopes.

We focus, at all points, on the lightweight nature of the underlying mechanisms and on the end-to-end human verifiability.