International Association
for Cryptologic Research

This paper explores ways of performing commutative tasks by $N$ parties. Tasks are defined as {\\sl commutative} if the order at which parties perform tasks can be freely changed without affecting the final result. It is easy to see that arbitrary $N$-party commutative tasks cannot be completed in less than $N-1$ basic time units.

We conjecture that arbitrary $N$-party commutative tasks cannot be performed in $N-1$ time units by exchanging less than $4N-6$ messages and provide computational evidence in favor this conjecture. We also explore the most equitable commutative task protocols.

We propose to relax the assumption that decryption failures are indistinguishable in security models for symmetric encryption. Our main purpose is to build models that better reflect the reality of cryptographic implementations, and to surface the security issues that arise from doing so. We systematically explore the consequences of this relaxation, with some surprising consequences for our understanding of this basic cryptographic primitive. Our results should be useful to practitioners who wish to build accurate models of their implementations and then analyse them. They should also be of value to more theoretical cryptographers proposing new encryption schemes, who, in an ideal world, would be compelled by this work to consider the possibility that their schemes might leak more than simple decryption failures.

In this work, we explore building constructions with full domain hash structure, but with standard model proofs that do not employ the random oracle heuristic. The launching point for our results will be the utilization of a ``leveled\'\' multilinear map setting for which Garg, Gentry, and Halevi (GGH) recently gave an approximate candidate. Our first step is the creation of a standard model signature scheme that exhibits the structure of the Boneh, Lynn and Shacham signatures. In particular, this gives us a signature that admits unrestricted aggregation.

We build on this result to offer the first *identity-based* aggregate signature scheme that admits unrestricted aggregation. In our construction, an arbitrary-sized set of signatures on identity/message pairs can be aggregated into a single group element, which authenticates the entire set. The identity-based setting has important advantages over regular aggregate signatures in that it eliminates the considerable burden of having to store, retrieve or verify a set of verification keys, and minimizes the total cryptographic overhead that must be attached to a set of signer/message pairs. While identity-based signatures are trivial to achieve, their aggregate counterparts are not. To the best of our knowledge, no prior candidate for realizing unrestricted identity-based aggregate signatures exists in either the standard or random oracle models.

A key technical idea underlying these results is the realization of a hash function with a Naor-Reingold-type structure that is publicly computable using repeated application of the multilinear map. We present our results in a generic ``leveled\'\' multilinear map setting and then show how they can be translated to the GGH graded algebras analogue of multilinear maps.

Goldwasser and Micali (1984) highlighted the importance of randomizing the plaintext for public-key encryption and introduced the notion of semantic security. They also realized a cryptosystem meeting this security notion under the standard complexity assumption of deciding quadratic residuosity modulo a composite number. The Goldwasser-Micali cryptosystem is simple and elegant but is quite wasteful in bandwidth when encrypting large messages. A number of works followed to address this issue and proposed various modifications. This paper revisits the original Goldwasser-Micali cryptosystem using 2^k-th power residue symbols. The so-obtained cryptosystems appear as a very natural generalization for k >= 2 (the case k = 1 corresponds exactly to the Goldwasser-Micali cryptosystem). Advantageously, they are efficient in both bandwidth and speed; in particular,they allow for fast decryption. Further, the cryptosystems described in this paper inherit the useful features of the original cryptosystem (like its homomorphic property) and are shown to be secure under a similar complexity assumption. As a prominent application, this paper describes an efficient lossy trapdoor function based thereon.

MISTY1 is a block cipher designed by Matsui in 1997. It is widely deployed in Japan where it is an e-government standard, and is recognized internationally as a NESSIE-recommended cipher as well as

an ISO standard and an RFC. Moreover, MISTY1 was selected to be the blueprint on top of which KASUMI, the GSM/3G block cipher, was based. Since its introduction, and especially in recent years, MISTY1 was subjected to extensive cryptanalytic efforts, which resulted in numerous attacks on its reduced variants. Most of these attacks aimed at maximizing the number of attacked rounds, and as a result, their complexities are highly impractical.

In this paper we pursue another direction, by focusing on attacks with a practical time complexity. The best previously-known attacks with practical complexity against MISTY1 could break either 4 rounds (out of 8), or 5 rounds in a modified variant in which some of the FL functions are removed. We present an attack on 5-round MISTY1 with all the FL functions present whose time complexity is 2^38 encryptions. When the FL functions are removed, we present a devastating (and experimentally verified) related-key attack on the full 8-round variant, requiring only 2^18 data and time.

While our attacks clearly do not compromise the security of the full

MISTY1, they expose several weaknesses in MISTY1\'s components, and

improve our understanding of its security. Moreover, future designs which rely on MISTY1 as their base, should take these issues into close consideration.

The Deutsche Telekom Chair of Mobile Business & Multilateral Security at Goethe University Frankfurt offers a position of a Scientific Assistant (m/f, E13 TV-G-U). To strengthen our team we are looking for a committed, creative and flexible PhD candidate (male/female) with advanced professional knowledge in Information Technology and interest in the current development in business informatics.

We are looking for people with advanced knowledge and special skills in at least three of the following areas:

- Network and System Security

- Privacy-Enhancing Technologies and data protection

- Identity Management

- Mobile Platforms, Smartcards and Trusted Computing

- Mobile Application Development (e.g. in Android, etc.)

- Cryptography

- Programming languages and experiences in software projects

- Administration skills in different platforms (e.g. UNIX, Linux, Windows)

- Web technologies and development

- Project management

The position is available immediately and has a fixed-term of 3 years with an extension option.

Deadline for applications: 2013-07-31

Contact for applications: Prof. Dr. Kai Rannenberg, bewerbungen(at)m-chair(dot)net

Documents recommended to be submitted: personal statement of purpose, current resume, official references, list of publications, official test scores

More Information: http://www.m-chair.net/wps/wse/home/rannenberg/career/

Submission: 22 July 2013
Notification: 23 August 2013
From October 14 to October 14
Location: Atlanta, United States
More Information: http://www.vizsec.org/

Submission: 1 September 2013
Notification: 15 September 2013
From October 23 to October 25
Location: Dubai, United Arab Emirates
More Information: http://sdiwc.net/conferences/2013/dipecc2013/

We are seeking for candidates for four funded theses.

The candidates will work on the following topics:

Thesis 1 - Faut and side-channel attacks.

Thesis 2 - Formal proofs of hardware and software implementations.

Thesis 3 - Lightweight cryptography (theory and practice).

Thesis 4 - Embedded equipment securit.

Due to employment visa constraints, the candidates must be of EU citizenship or Swiss.

The candidate will be based in the Paris area with access to very advanced laboratory equipment.

In this paper, we first prove beyond-birthyday-bound security for the Misty structure. Specifically, we show that an $r$-round Misty structure is secure against CCA attacks up to $O(2^{\\frac{rn}{r+7}})$ query complexity, where $n$ is the size of each round permutation. So for any $\\epsilon>0$, a sufficient number of rounds would guarantee the security of the Misty structure up to $2^{n(1-\\epsilon)}$ query complexity.

The Centre for Telematics and Information Technology (CTIT) at the University of Twente invites applications for a Post-Doc position in system security with a strong focus on security of industrial control and SCADA systems.

We search for a candidate with a strong background in practical system level security. The candidate is expected to support supervision of PhD students, contribute to our on-going projects, and also contribute to future project proposals to strengthen our research profile. Our group is member of multiple national and European research projects with strong links to industry. One example is the currently ongoing CRISALIS FP7 project (http://www.crisalisproject.eu/).

Successful candidates must hold a PhD degree in computer science or a closely related discipline and have demonstrated their excellence by top-class publications.

Please submit your application via the link provided below including:

• motivation letter specifically addressing our position,

• full curriculum vitae including a list of all courses and marks,

• publication list incl. a one-page summary of your PhD thesis,

• two recommendation letters (or alternatively the names and email addresses of two references).

The position will be closed as soon as a suitable candidate is found.

Submission: 15 November 2013
From February 20 to February 21
Location: Redmond, USA
More Information: http://research.microsoft.com/en-us/events/mpcworkshop/

Name: Alexander Meurer
Topic: A Coding-Theoretic Approach to Cryptanalysis
Category: foundations

Description: In this thesis we study the applicability of coding-theoretic algorithms to cryptanalysis and provide new insights into the practical security of different cryptographic primitives. We introduce a new generalised framework for the class of \"Information Set Decoding\" (ISD) algorithms. By applying the so-called representation technique, we design a new ISD algorithm which asymptotically achieves an exponential improvement over all known methods. Within the generalised ISD framework we provide a rigorous formal proof of superiority of the new algorithm for arbitrary code rates 0[...]

Besides Karatsuba algorithm, optimal Toeplitz matrix-vector product (TMVP) formulae is another approach to design GF(2^n) subquadratic multipliers. However, when GF(2^n) elements are represented using a shifted polynomial basis, this approach is currently appliable only to GF(2^n)s generated by all irreducible trinomials and a special type of irreducible pentanomials, not all general irreducible pentanomials. The reason is that no transformation matrix, which transforms the Mastrovito matrix into a Toeplitz matrix, has been found. In this article, we propose such a transformation matrix and its inverse matrix for an arbitrary irreducible pentanomial. Because there is no known value of n for which either an irreducible trinomial or an irreducible pentanomial does not exist, this transformation matrix makes the TMVP approach a universal tool, i.e., it is applicable to all practical GF(2^n)s.

The 3GPP Task Force recently supplemented mobile LTE network security with an additional set of confidentiality and integrity algorithms, namely 128-EEA3 and 128-EIA3 built on top of ZUC, a new keystream generator. We propose two novel techniques to improve the software performance of these algorithms. We show how delayed modular reduction increases the efficiency of the LFSR feedback function, yielding performance gains for ZUC and thus both 128-EEA3 and 128-EIA3. We also show how to leverage carryless multiplication to evaluate the universal hash function making up the core of 128-EIA3. Our software implementation results on Qualcomm\'s Hexagon DSP architecture indicate significant performance gains when employing these techniques: up to roughly a 2-fold and 2.5-fold throughput improvement for 128-EEA3 and 128-EIA3, respectively.

Cloud storage service providers such as Dropbox, Mozy, and others perform deduplication to save space by only storing one copy of each file uploaded. Should clients conventionally encrypt their files, however, savings are lost. Message-locked encryption (the most prominent manifestation of which is convergent encryption) resolves this tension. However it is inherently subject to brute-force attacks that can recover files falling into a known set. We propose an architecture that provides secure deduplicated storage resisting brute-force attacks, and realize it in a system called DupLESS. In DupLESS, clients encrypt under message-based keys obtained from a key-server via an oblivious PRF protocol. It enables clients to store encrypted data with an existing service, have the service perform deduplication on their behalf, and yet achieves strong confidentiality guarantees. We show that encryption for deduplicated storage can achieve performance and space savings close to that of using the storage service with plaintext data.

We develop secure \\emph{threshold} protocols for two important

operations in lattice cryptography, namely, generating a hard lattice

$\\Lambda$ together with a ``strong\'\' trapdoor, and sampling from a

discrete Gaussian distribution over a desired coset of $\\Lambda$ using

the trapdoor. These are the central operations of many cryptographic

schemes: for example, they are exactly the key-generation and signing

operations (respectively) for the GPV signature scheme, and they are

the public parameter generation and private key extraction operations

(respectively) for the GPV IBE. We also provide a protocol for

trapdoor delegation, which is used in lattice-based hierarchical IBE

schemes. Our work therefore directly transfers all these systems to

the threshold setting.

Our protocols provide information-theoretic (i.e., statistical)

security against adaptive corruptions in the UC framework, and they

are private and robust against an

optimal number of semi-honest or malicious parties. Our Gaussian

sampling protocol is both noninteractive and efficient, assuming

either a trusted setup phase (e.g., performed as part of key

generation) or a sufficient amount of interactive but offline

precomputation, which can be performed before the inputs to the

sampling phase are known.

We study collusion-resistant traitor tracing in the simple decoder approach, i.e. assignment of scores for each user separately.

We introduce a new score function for non-binary bias-based traitor tracing. It has three special properties that have long been sought after:

(i) The expected score of an innocent user is zero in each content position.

(ii) The variance of an innocent user\'s score is~1 in each content position.

(iii) The expectation of the coalition\'s score does not depend on the

collusion strategy.

We also find a continuous bias distribution that optimizes the asymptotic (large coalition) performance.

In the case of a binary alphabet our scheme reduces exactly to the

symmetrized Tardos traitor tracing system.

Unfortunately, the asymptotic fingerprinting rate

of our new scheme decreases with growing alphabet size.

We regret to inform you that this grail has holes.

In [12], the authors present a new light-weight cryptographic primitive which supports an associated RFID-based authentication protocol. The primitive has some structural similarities to AES, but is presented as a keyed one-way function using a 128-bit key. Although a security analysis is included, this is at a high-level only. To provide a more concrete idea as to the security of this primitive, we therefore make three contributions: first, a structural attack requiring $O(2^{5})$ plaintext/ciphertext pairs (and hence effort online) plus $O(2^{21})$ effort offline, second an algebraic attack on round reduced versions of the primitive which requires only a single plaintext/ciphertext pair, and, third debunk the claimed attack of [36] on the same primitive as wishful thinking. Our structural attack completely breaks the primitive and the algebraic attack highlights a crucial weakness of the primitive: we conclude that although one can consider countermeasures against these specific attacks, the design in general is questionable and should therefore be avoided.

In a private database query system, a client issues queries to a database and obtains the results without learning anything else about the database and without the server learning the query. While previous work has yielded systems that can efficiently support disjunction queries, performing conjunction queries privately remains an open problem. In this work, we show that using a polynomial encoding of the database enables efficient implementations of conjunction queries using somewhat homomorphic encryption. We describe a three-party protocol that supports efficient evaluation of conjunction queries. Then, we present two implementations of our protocol using Paillier\'s

additively homomorphic system as well as Brakerski\'s somewhat homomorphic cryptosystem. Finally, we show that the additional homomorphic properties of the Brakerski cryptosystem allow us to handle queries involving several thousand elements over a million-record database in just a few minutes, far outperforming the implementation using the additively homomorphic system.