International Association for Cryptologic Research

# IACR News Central

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2012-07-06
21:17 [Pub][ePrint]

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]

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

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

client-to-server

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]

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]

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]

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 (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]

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]

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]

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.

15:03 [Job][New]

Job description

The main task of the candidate will be to do research in applied cryptography. He/she will also be responsible for the daily supervision of a number of PhD students. The candidate will be offered the opportunity to gain some teaching experience, related to his/her background and interests.

Requirements

We are looking for an excellent and independent researcher who has (1) a PhD degree in Applied Cryptography or a related discipline, (2) a good publication record, and (3) good communication skills.

Conditions of employment

The Post-Doc will be appointed as a Researcher for a period of two years, with the possibility of an extension for a further three years. The monthly salary of the Researcher will amount to, depending on the experience, maximum 3755 euro gross per month according to salary scale 10 of the Dutch Universities Labour Agreement.

09:43 [Job][New]

Coding and Cryptograph Research Group (http://www1.spms.ntu.edu.sg/~ccrg/index.html) at Nanyang Technological University (NTU), Singapore, is seeking candidates for 1 or 2 research fellow positions (from fresh post-docs to senior research fellows) and a few Ph.D. student positions in the areas of symmetric key cryptography and lightweight cryptography. The future research team will be funded by the 5-year National Research Foundation (NRF) Fellowship grant from Singapore (started in April 2012).

Salaries are very competitive and are determined according to the successful applicants accomplishments, experience and qualifications. The duration of the contracts are very flexible. Interested applicants are encouraged to send their detailed CVs, cover letter and references.

Review of applications starts immediately and will continue until positions are filled.