International Association
for Cryptologic Research

Holenstein et al. (STOC 2011) have shown that the Feistel construction with fourteen rounds and public random round functions is indifferentiable from a random permutation. In the same paper, they pointed out that a previous proof for the 10-round Feistel construction by Seurin (PhD thesis) was flawed. However, they left open the question of whether the proof could be patched (leaving hope that the simulator described by Seurin could still be used to prove indifferentiability of the 10-round Feistel construction). In this note, we show that the proof cannot be patched (and hence that the simulator described by Seurin cannot be used to prove the indifferentiability of the 10-round Feistel construction) by describing a distinguishing attack that succeeds with probability close to one against this simulator. We stress that this does not imply that the 10-round Feistel construction is not indifferentiable from a random permutation (since our attack does not exclude the existence of a different simulator that would work).

The paper presented an identity based encryption (IBE) under selective opening attack (SOA) whose security is almost-tightly related to a set of computational assumptions. Our result is a combination of Bellare, Waters, and Yilek\'s method [TCC, 2011] for constructing (not tightly) SOA secure IBE and Hofheinz, Koch, and Striecks\' technique [PKC, 2015] on building almost-tightly secure IBE in the multi-ciphertext setting. In particular, we first tuned Bellare \\textit{et al.}\'s generic construction for SOA secure IBE to show that a one-bit IBE achieving ciphertext indistinguishability under chosen plaintext attack in the \\emph{multi-ciphertext} setting (with one-sided publicly openability) \\emph{tightly} implies a multi-bit IBE secure under selective opening attack. Next, we almost-tightly reduced such a one-bit IBE to static assumptions in the composite-order bilinear groups employing the technique of Hofheinz \\textit{et al.} This yielded the \\emph{first} SOA secure IBE with almost-tight reduction.

Modern Intel processors use an undisclosed hash function to map memory lines into last-level cache slices. In this work we develop a technique for reverse-engineering the hash function. We apply the technique to a 6-core Intel processor and demonstrate that knowledge of this hash function can facilitate cache-based side channel attacks, reducing the amount of work required for profiling the cache by three orders of magnitude. We also show how using the hash function we can double the number of colours used for page-colouring techniques.

Designing block ciphers targeting resource constrained 8-bit

CPUs is a challenging problem. There are many recent lightweight ciphers designed for better performance in hardware. On the other hand, most software efficient lightweight ciphers either lack a security proof or have a low security margin. To fill the gap, we present RoadRunneR which is an efficient block cipher in 8-bit software, and its security is provable against differential and linear attacks. RoadRunneR has lowest code size in Atmel\'s ATtiny45, except NSA\'s design SPECK, which has no security proof. Moreover, we propose a new metric for the fair comparison of block ciphers. This metric, called ST/A, is the first metric to

use key length as a parameter to rank ciphers of different key length in a fair way. By using ST/A and other metrics in the literature, we show that RoadRunneR is competitive among existing ciphers on ATtiny45.

The mission of theoretical cryptography is to define and construct provably secure cryptographic protocols and schemes. Without proofs of security, cryptographic constructs offer no guarantees whatsoever and no basis for evaluation and comparison. As most security proofs necessarily come in the form of a reduction between the security claim and an intractability assumption, such proofs are ultimately only as good as the assumptions they are based on. Thus, the complexity implications of every assumption

we utilize should be of significant substance, and serve as the yard stick for the value of our proposals.

Lately, the field of cryptography has seen a sharp increase in the number of new assumptions that are often complex to define and difficult to interpret. At times, these assumptions are hard to untangle from the constructions which utilize them.

We believe that the lack of standards of what is accepted as a reasonable cryptographic assumption can be harmful to the credibility of our field. Therefore, there is a great need for measures according to which we classify and compare assumptions, as to which are safe and which are not. In this paper, we propose such a classification and review recently suggested assumptions in this light. This follows the footsteps of Naor (Crypto 2003).

The application of the concept of linear cryptanalysis to the domain of key-less primitives is largely an open problem. In this paper we, for the first time, propose a model in which its application is meaningful for distinguishing block ciphers.

Combining our model with ideas from message modification and rebound-like approaches, we initiate a study of cryptographic primitives with respect to this new attack vector and choose the lightweight block cipher PRESENT as an example target. This leads to known-key distinguishers over up to 27 rounds, whereas the best previous result is up to 18 rounds in the chosen-key model.

Hash functions are often constructed based on permutations or blockciphers, and security proofs are typically done in the ideal permutation or cipher model. However, once these random primitives are instantiated, vulnerabilities of these instantiations may nullify the security. At ASIACRYPT 2007, Knudsen and Rijmen introduced known-key security of blockciphers, which gave rise to many distinguishing attacks on existing blockcipher constructions. In this work, we analyze the impact of such attacks on primitive-based hash functions. We present and formalize the weak cipher model, which captures the case a blockcipher has a certain weakness but is perfectly random otherwise. A specific instance of this model, considering the existence of sets of B queries whose XOR equals 0 at bit-positions C, where C is an index set, covers a wide range of known-key attacks in literature. We apply this instance to the PGV compression functions, as well as to the Groestl (based on two permutations) and Shrimpton-Stam (based on three permutations) compression functions, and show that these designs do not seriously succumb to any differential known-key attack known to date.

A sequence of recent works have constructed constant-size quasi-adaptive (QA) NIZK argu- ments of membership in linear subspaces of $G^m$, where $G$ is a group equipped with a bilinear map $e : G × H \\to T$. Although applicable to any bilinear group, these techniques are less useful in the asymmetric case. For example, Jutla and Roy (Crypto 2014) show how to do QA aggregation of Groth-Sahai proofs, but the types of equations which can be aggregated are more restricted in the asymmetric setting. Furthermore, there are natural statements which cannot be expressed as membership in linear subspaces, for example the satisfiability of quadratic equations.

In this paper we develop specific techniques for asymmetric groups. We introduce a new computational assumption, under which we can recover all the aggregation results of Groth- Sahai proofs known in the symmetric setting. We adapt the arguments of membership in linear spaces of $G^m$ to linear subspaces of $G^m \\times H^n . In particular, we give a constant-size argument that two sets of Groth-Sahai commitments, defined over different groups $G$, $H$, open to the same scalars in $Z_q$, a useful tool to prove satisfiability of quadratic equations in $Z_q$. We then use one of the arguments for subspaces in $G^m \\times H^n$ and develop new techniques to give constant-size QA-NIZK proofs that a commitment opens to a bit-string. To the best of our knowledge, these are the first constant-size proofs for quadratic equations in $Z_q$ under standard and falsifiable assumptions. As a result, we obtain improved threshold Groth-Sahai proofs for pairing product equations, ring signatures, proofs of membership in a list, and various types of signature schemes.

Submission: 30 September 2015
Notification: 30 September 2015
From September 28 to September 30
Location: Hyderabad, India
More Information: https://docs.google.com/forms/d/1KiT3ZU_qYucqM1-F_xAx-5VwatXyBfqAGIFsNlEO9Hw/viewform?c=0&w=1

Submission: 21 December 2015
Notification: 15 February 2016
From March 30 to March 30
Location: Xi'an, China
More Information: http://www2.nict.go.jp/nsri/fund/asiapkc2016/

It has been six years since Ristenpart et al. demonstrated the viability of co-location and provided the first concrete evidence for sensitive information leakage on a commercial cloud. We show that co-location can be achieved and detected by monitoring the last level cache in public clouds. More significantly, we present a full-fledged attack that exploits subtle leakages to recover RSA decryption keys from a co-located instance. We target a recently patched Libgcrypt RSA implementation by mounting Cross-VM Prime and Probe cache attacks in combination with other tests to detect co-location in Amazon EC2. In a preparatory step, we reverse engineer the unpublished nonlinear slice selection function for the 10 core Intel Xeon processor which significantly accelerates our attack (this chipset is used in Amazon EC2). After co-location is detected and verified, we perform the Prime and Probe attack to recover noisy keys from a carefully monitored Amazon EC2 VM running the aforementioned vulnerable libgcrypt library. We subsequently process the noisy data and obtain the complete 2048-bit RSA key used during encryption. This work reaffirms the privacy concerns and underlines the need for deploying stronger isolation techniques in public clouds.

Attribute Based Encryption (ABE) is a promising public-key

cryptographic primitive that can be used for cryptographically enforced access control in untrusted storage. Storing data on untrusted storage not only requires data security for data owners but also poses data protection from untrusted storage server. To address this important requirement, Anonymous Attribute Based Encryption (AABE) is a suitable primitive that provides users to access data from untrusted storage without revealing their identities. At the same time user data can be stored in untrusted storage in an encrypted form. While storing data in an encrypted

form, keyword-based query search (and data retrieval) is a challenging research problem. In this paper we present an anonymous attribute based searchable encryption (A2SBE) scheme which facilitates user to retrieve only a subset of documents pertaining to his chosen keyword(s). User can upload documents in public cloud in an encrypted form, search documents based on keyword(s) and retrieve documents without revealing his identity. The scheme is proven secure under the selective ciphertext-

policy and chosen plaintext attack (IND-sCP-CPA) model and selective ciphertext-policy and chosen keyword attack (IND-sCP-CKA) model. The scheme requires small storage for user\'s decryption key and reduced computation for decryption in comparison to other schemes.

This paper surveys the results obtained so far in designing identity-based encryption (IBE) schemes based on the quadratic residuosity assumption (QRA). We begin by describing the r-st such scheme due to Cocks, and then we advance to the novel idea of Boneh, Gentry and Hamburg. Major improvements of the Boneh-Gentry-Hamburg scheme are then recalled. The recently revealed algebraic torus structures of the Cocks scheme allows for a better understanding of this scheme, as well as for new applications of it such as homomorphic and anonymous variants of it.

SPDZ, TinyOT and MiniMAC are a family of MPC protocols based on secret sharing with MACs, where a preprocessing stage

produces multiplication triples in a finite field. This work describes new protocols for generating multiplication triples in fields of characteristic two using OT extensions. Before this work, TinyOT, which works on binary circuits, was the only protocol in this family using OT extensions.

Previous SPDZ protocols for triples in large finite fields require somewhat homomorphic encryption, which leads to very inefficient runtimes in practice, while no dedicated preprocessing protocol for MiniMAC (which operates on vectors of small field elements) was previously known. Since actively secure OT extensions can be performed very efficiently using only symmetric primitives, it is highly desirable to base MPC protocols on these rather than expensive public key primitives. We analyze the practical efficiency of our protocols, showing that they should all perform favorably compared with previous works; we estimate our protocol for SPDZ triples in $\\mathbb{F}_{2^{40}}$ will perform around 2 orders of magnitude faster

than the best known previous protocol.

Submission: 25 January 2016
Notification: 2 May 2016
From August 9 to August 12
Location: Tacoma, USA
More Information: http://www.icits2016.com

In this paper, we propose a new multivariate signature scheme named MI-T-HFE as a competitor of QUARTZ. The core map of MI-T-HFE is of an HFEv type but more importantly has a specially designed trapdoor. This special trapdoor makes MI-T-HFE have several attractive advantages over QUARTZ. First of all, the core map and the public map of MI-T-HFE are both surjective. This surjectivity property is important for signature schemes because any message should always have valid signatures; otherwise it may be troublesome to exclude those messages without valid signatures. However this property is missing for a few major signature schemes, including QUARTZ. A practical parameter set is proposed for MI-T-HFE with the same length of message and same level of security as QUARTZ, but it has smaller public key size, and is more efficient than (the underlying HFEv- of) QUARTZ with the only cost that its signature length is twice that of QUARTZ.

Attribute-based encryption (ABE) is an extension of traditional public key encryption in which the encryption and decryption phases are based on user\'s attributes. More precisely, we focus on cipher-text-policy ABE (CP-ABE) where the secret-key is associated to a set of attributes and the ciphertext is generated with an access policy. It then becomes feasible to decrypt a ciphertext only if one\'s attributes satisfy the used access policy.

In this paper, we give the first private CP-ABE constructions with a constant-size ciphertext, supporting CNF (Conjunctive Normal Form) access policy, with the simple restriction that each attribute can only appear $k_{max}$ times in the access formula. Our two constructions are based on the BGW scheme at Crypto\'05. The first scheme is basic selective secure (in the standard model) while our second one reaches the selective CCA security (in the random oracle model).

This paper revisits related randomness attacks against public key encryption schemes as introduced by Paterson, Schuldt and Sibborn (PKC 2014). We present a general transform achieving security for public key encryption in the related randomness setting using as input any secure public key encryption scheme in combination with an auxiliary-input reconstructive extractor. Specifically, we achieve security in the function-vector model introduced by Paterson et al., obtaining the first constructions providing CCA security in this setting. We consider instantiations of our transform using the Goldreich-Levin extractor; these outperform the previous constructions in terms of public-key size and reduction tightness, as well as enjoying CCA security. Finally, we also point out that our approach leads to an elegant construction for Correlation Input Secure hash functions, which have proven to be a versatile tool in diverse areas of cryptography.

Robust authenticated encryption (RAE) is a primitive for symmetric encryption that allows to flexibly specify the ciphertext expansion, i.e., how much longer the ciphertext is compared to the plaintext. For every ciphertext expansion, RAE aims at providing the best-possible authenticity and confidentiality. To investigate whether this is actually achieved, we characterize exactly the guarantees symmetric cryptography can provide for any given ciphertext expansion. Our characterization reveals not only that RAE reaches the claimed goal, but also, contrary to prior belief, that one cannot achieve full confidentiality without ciphertext expansion. This provides new insights into the limits of symmetric cryptography.

Moreover, we provide a rigorous treatment of two previously only informally stated additional features of RAE; namely, we show how redundancy in the message space can be exploited to improve the security and we analyze the exact security loss if multiple messages are encrypted with the same nonce.

We generalise the cube attack of Dinur and Shamir (and the similar AIDA attack of Vielhaber) to a more general higher order differentiation attack, by summing over an arbitrary subspace of the space of initialisation vectors. The Moebius transform can be used for efficiently examining all the subspaces of a big space, similar to the method used by Fouque and Vannet for the usual cube attack. Secondly we propose replacing the Generalised Linearity Test proposed by Dinur and Shamir with a test based on higher order differentiation/ Moebius transform. We show that the proposed test provides all the information provided by the Generalised Linearity Test, at the same computational cost. In addition, for functions that do not pass the linearity test it also provides, at no extra cost, an estimate of the degree of the function. This is useful for guiding the heuristics for the cube/AIDA attacks. Finally we implement our ideas and test them on the stream cipher Trivium.