International Association
for Cryptologic Research

In (key-policy) attribute based encryption (ABE), messages are encrypted respective to attributes $x$, and keys are generated respective to policy functions $f$. The ciphertext is decryptable by a key only if $f(x)=0$. Adding homomorphic capabilities to ABE is a long standing open problem, with current techniques only allowing compact homomorphic evaluation on ciphertext respective to the same $x$. Recent advances in the study of multi-key FHE also allow cross-attribute homomorphism with ciphertext size growing (quadratically) with the number of input ciphertexts.

We present an ABE scheme where homomorphic operations can be performed compactly across attributes. Of course, decrypting the resulting ciphertext needs to be done with a key respective to a policy $f$ with $f(x_i)=0$ for all attributes involved in the computation. In our scheme, the target policy $f$ needs to be known to the evaluator, we call this targeted homomorphism. Our scheme is secure under the polynomial hardness of learning with errors (LWE) with sub-exponential modulus-to-noise ratio.

We present a second scheme where there needs not be a single target policy. Instead, the decryptor only needs a set of keys representing policies $f_j$ s.t.\ for any attribute $x_i$ there exists $f_j$ with $f_j(x_i)=0$. In this scheme, the ciphertext size grows (quadratically) with the size of the set of policies (and is still independent of the number of inputs or attributes). Again, the target set of policies needs to be known at evaluation time. This latter scheme is secure in the random oracle model under the polynomial hardness of LWE with sub-exponential noise ratio.

Protocols for secure electronic voting are of increasing societal importance. Proving rigorously their security is more challenging than many other protocols, which aim at authentication or key exchange. One of the reasons is that they need to be secure for an arbitrary number of malicious voters. In this paper we identify a class of voting protocols for which only a small number of agents needs to be considered: if there is an attack on vote privacy then there is also an attack that involves at most 3 voters (2 honest voters and 1 dishonest voter). In the case where the protocol allows a voter to cast several votes and counts, e.g., only the last one, we also reduce the number of ballots required for an attack to 10, and under some additional hypotheses, 7 ballots. Our results are formalised and proven in a symbolic model based on the applied pi calculus. We illustrate the applicability of our results on several case studies, including different versions of Helios and Prêt-à-Voter, as well as the JCJ protocol. For some of these protocols we can use the ProVerif tool to provide the first formal proofs of privacy for an unbounded number of voters

Impossible differential cryptanalysis and zero-correlation linear cryptanalysis are two of the most useful cryptanalysis methods in the field of symmetric ciphers. Until now, there are several automatic search tools for impossible differentials such as $\mathcal{U}$-method and UID-method, which are all independent of the non-linear S-boxes. Since the differential and linear properties may contribute to the search of impossible differentials and zero-correlation linear approximations respectively, it is meaningful to study the search with considering the properties of non-linear components. In this paper, we propose an automatic search tool for impossible differentials and zero-correlation linear approximations in both ARX ciphers and ciphers with S-box, which is the first widely applicable one that considers the influence of non-linear operations, especially in ARX ciphers. What's more, this tool can be used to proof whether there are impossible differentials (zero-correlation linear approximations) in certain rounds of a target cipher, particularly for certain subset of input and output differences (masks) patterns. As applications, we use the proposed automatic tool on HIGHT and PRESENT ciphers. As a result, we find total 4 impossible differentials and 4 zero-correlation linear approximations for 17-round HIGHT which are the longest ones until now. In addition, we find 5050 impossible differentials for 6-round PRESENT cipher, which extend two more rounds than those searched by previous widely applicable automatic search tools.

To date, all constructions in the standard model (i.e., without random oracles) of Bounded Key-Dependent Message (KDM) secure (or even just circularly-secure) encryption schemes rely on specific assumptions (LWE, DDH, QR or DCR); all of these assumptions are known to imply the existence of collision-resistant hash functions. In this work, we demonstrate the existence of bounded KDM secure encryption assuming indistinguishability obfsucation for $P/poly$ and just one-way functions. Relying on the recent result of Asharov and Segev (STOC'15), this yields the first construction of a Bounded KDM secure (or even circularly secure) encryption scheme from an assumption that provably does not imply collision-resistant hash functions w.r.t. black-box constructions. Combining this with prior constructions, we show how to augment this Bounded KDM scheme into a Bounded CCA2-KDM scheme.

Designing an efficient cipher was always a delicate balance between linear and non-linear operations. This goes back to the design of DES, and in fact all the way back to the seminal work of Shannon.

Here we focus, for the first time, on an extreme corner of the design space and initiate a study of symmetric-key primitives that minimize the multiplicative size and depth of their descriptions. This is motivated by recent progress in practical instantiations of secure multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge proofs (ZK) where linear computations are, compared to non-linear operations, essentially ``free''.

We focus on the case of a block cipher, and propose the family of block ciphers ``LowMC'', beating all existing proposals with respect to these metrics. As examples, we give concrete instatiations for 80-bit, 128-bit, and 256-bit security. We sketch several applications for such ciphers and give implementation comparisons suggesting that when encrypting larger amounts of data the new design strategy translates into improvements in computation and communication complexity by up to a factor of 5 compared to AES-128, which incidentally is one of the most competitive classical designs. Furthermore, we identify cases where ``free XORs'' can no longer be regarded as such but represent a bottleneck, hence refuting this commonly held belief with a practical example.

MDS matrices are important parts for block ciphers. We searched the $4\times 4$ MDS matrices over GL(4, $\mathbb{F}_2$), and found the lightest MDS matrices only have 10 XOR operations. Besides, all these lightest MDS matrices can be classified to 3 classes.

Given a set S = {C_1,...,C_k } of Boolean circuits, we show how to construct a universal for S circuit C_0, which is much smaller than Valiant’s universal circuit or a circuit incorporating all C_1,...,C_k. Namely, given C_1,...,C_k and viewing them as directed acyclic graphs (DAGs) D_1,...,D_k, we embed them in a new graph D_0. The embedding is such that a GC garbling of any of C_1,...,C_k could be implemented by a corresponding garbling of a circuit corresponding to D_0.

We show how to improve Garbled Circuit (GC) and GMW-based secure function evaluation (SFE) of circuits with if/switch clauses using such S-universal circuit.

The most interesting case here is the application to the GMW approach. We provide a novel observation that in GMW the cost of processing a gate is almost the same for 5 (or more) Boolean inputs, as it is for the usual case of 2 Boolean inputs. While we expect this observation to greatly improve general GMW-based computation, in our context this means that GMW gates can be programmed almost for free, based on the secret-shared programming of the clause.

Our approach naturally and cheaply supports nested clauses. Our algorithm is a heuristic; we show that solving the circuit embedding problem is NP-hard. Our algorithms are in the semi-honest model and are compatible with Free-XOR.

We report on experimental evaluations and discuss achieved performance in detail. For 32 diverse circuits in our experiment, our construction results 6.1x smaller circuit than prior techniques.

Computing discrete logarithms in finite fields is a main concern in cryptography. The best algorithms known are the Number Field Sieve and its variants in large and medium characteristic fields (e.g. $\mathrm{GF}(p^2)$, $\mathrm{GF}(p^{12})$); the Function Field Sieve and the Quasi Polynomial-time Algorithm in small characteristic finite fields (e.g. $\mathrm{GF}(3^{6 \cdot 509})$). The last step of the NFS and FFS algorithms is the individual logarithm computation. It computes a smooth decomposition of a given target in two phases: an initial splitting then a descent tree. While new improvements have been made to reduce the complexity of the dominating relation collection and linear algebra steps of NFS and FFS, resulting in a smaller factor basis (database of known logarithms of small elements), the last step remains of same difficulty. Indeed, we have to find a smooth decomposition of a typically large element in the finite field.

The method we propose improves the initial splitting phase and applies to any finite field of composite extension degree. It exploits the available subfields with a cheap (polynomial-time) linear algebra step, resulting in a much more smooth decomposition of the target. This leads to a new trade-off in the asymptotic complexity of the initial splitting step: for instance it is improved by a factor 2 in the exponent for FFS and $2^{1/3}$ in the exponent for NFS, for any finite field of even extension degree, and with a much smaller smoothness bound. In medium and large characteristic, it can be combined with Pomerance's Early Abort strategy. In small characteristic, it replaces the Waterloo algorithm of Blake, Fuji-Hara, Mullin and Vanstone. Moreover it reduces the width and the height of the subsequent descent tree.

A sparse Merkle tree is an authenticated data structure based on a perfect Merkle tree of intractable size. It contains a distinct leaf for every possible output from a cryptographic hash function, and can be simulated efficiently because the tree is sparse (i.e., most leaves are empty). We are the first to provide complete, succinct, and recursive definitions of a sparse Merkle tree and related operations. We show that our definitions enable efficient space-time trade-offs for different caching strategies, and that verifiable audit paths can be generated to prove (non-)membership in practically constant time~($<4$~ms) when using SHA-512/256. This is despite a limited amount of space for the cache---smaller than the size of the underlying data structure---and full security in the multi-instance setting.

Ideas from Fourier analysis have been used in cryptography for three decades. Akavia, Goldwasser and Safra unified some of these ideas to give a complete algorithm that finds significant Fourier coefficients of functions on any finite abelian group. Their algorithm stimulated a lot of interest in the cryptography community, especially in the context of ``bit security''. This paper attempts to be a friendly and comprehensive guide to the tools and results in this field. The intended readership is cryptographers who have heard about these tools and seek an understanding of their mechanics, and their usefulness and limitations. A compact overview of the algorithm is presented with emphasis on the ideas behind it. We survey some applications of this algorithm, and explain that several results should be taken in the right context. We point out that some of the most important bit security problems are still open. Our original contributions include: an approach to the subject based on modulus switching; a discussion of the limitations on the usefulness of these tools; an answer to an open question about the modular inversion hidden number problem.

We propose a new zero-knowledge protocol for proving knowledge of short preimages under additively homomorphic functions that map integer vectors to an Abelian group. The protocol achieves amortized efficiency in that it only needs to send $O(n)$ auxiliary function values to prove knowledge of $n$ preimages. Furthermore we significantly improve previous bounds on how short a secret we can extract from a dishonest prover, namely our bound is a factor $O(k)$ larger than the size of secret used by the honest prover. In the best previous result, the factor was $O(k^{\log k} n)$. Our main technique is derived from the theory of expanders. Our protocol can be applied to give proofs of knowledge for plaintexts in (Ring-)LWE-based cryptosystems, knowledge of preimages of homomorphic hash functions as well as knowledge of committed values in some integer commitment schemes.

The Institute of Networks and Security (INS) at Johannes Kepler University (JKU) in Linz, Austria, is looking for a full-time post-doc (or, in exceptional cases, PhD candidate) researcher to extend the current team starting with 1. September 2016 for a duration of up to 6 years.

Main research topics are clusterered in two strategic areas: digital identity (including smart cards and NFC, secure execution environments, cryptographic signatures and revocation protocols, scalable communication between provers and verifiers on a global scale, user interaction, etc.) and secure code (formal modeling and verification, code generation, source code annotations, compiler and runtime based verification, virtualization, hardware support for secure execution, etc.). Previous experience in either (or even both) of these areas is not strictly required, but helpful.

INS (together with the research center on user-friendly secure mobile environments) currently hosts 14 staff members and supervises a number of external PhD and Master\'s students. Applicants are expected to integrate with the team and co-operate on research projects, but are free to develop their own research focus. Teaching duties currently involve introductory low-level systems programming and networking with the option to offer advanced courses on specific research areas. Although some courses are primarily tought in German, exceptions for teaching in English are possible.

The Austrian University collective contract currently grants €3.546,00 per month (with 2 extra payments amounting to 14 monthly payments per year) before taxes. Organizational support for relocation is available. Interested applicants should send their resume and relevant proofs of qualification via email to office (at) ins.jku.at until 31. July 2016 with decisions expected within the first two weeks of August. Funding is open from 1. September, but later starting dates (until November) are possible.

Closing date for applications: 31 July 2016

Contact: Rene Mayrhofer, Head of Institute, rm (at) ins.jku.at

More information: https://ins.jku.at/news/ins-job-posting

The program for Crypto 2016 is now online. It includes the announcement of two papers recognized for their excellence:

• The program committee has chosen Breaking the Circuit Size Barrier for Secure Computation Under DDH by Elette Boyle, Niv Gilboa, and Yuval Ishai as the best paper of Crypto 2016. The paper can be found on ePrint at https://eprint.iacr.org/2016/585.
• The program committee has also recognized Mark Zhandry with the early career award for his paper The Magic of ELFs. The award recognizes the best paper authored exclusively by early-career researchers (current student or PhD awarded in 2014 or later). A full version of the paper can be found on ePrint at https://eprint.iacr.org/2016/114.

Congratulations to these authors for their excellent work. Crypto 2016 will be held in Santa Barbara, August 14-18.

Client puzzles have been proposed as a mechanism for proving legitimate intentions by providing ``proofs of work'', which can be applied to discourage malicious usage of resources. A typical problem of puzzle constructions is the difference in expected solving time on different computing platforms. We call puzzles which can be solved independently of client computing resources \emph{fair client puzzles}.

We propose a construction for client puzzles requiring widely distributed computational effort for their solution. These puzzles can be solved using the mining process of Bitcoin, or similar cryptocurrencies. Adapting existing definitions, we show that our puzzle construction satisfies formal requirements of client puzzles under reasonable assumptions. We describe a way of transforming our client puzzles for use in denial of service scenarios and demonstrate a practical construction.

White-box cryptography aims at providing security against an adversary that has access to the encryption process. Numerous white-box encryption schemes were proposed since the introduction of white-box cryptography by Chow et al. in 2002. However, most of them are slow, and thus, can be used in practice only to protect very small amounts of information, such as encryption keys.

In this paper we present a new threat model for white-box cryptography which corresponds to the practical abilities of the adversary in a wide range of applications. Furthermore, we study design criteria for white-box primitives that are important from the industry point of view. Finally, we propose a class of new primitives that combine a white-box algorithm with a standard block cipher to obtain white-box protection for encrypting long messages, with high security and reasonable performance.

We define the concept of and present provably secure constructions for Anonymous RAM (AnonRAM), a novel multi-user storage primitive that offers strong privacy and integrity guarantees. AnonRAM combines privacy features of anonymous communication and oblivious RAM (ORAM) schemes, allowing it to protect, simultaneously, the privacy of content, access patterns and user’s identity, from curious servers and from other (even adversarial) users. AnonRAM further protects integrity, i.e., it prevents malicious users from corrupting data of other users. We present two secure AnonRAM schemes, differing in design and time-complexity. The first scheme has simpler design; like efficient ORAM schemes, its time-complexity is poly-logarithmic in the number of cells (per user), however, it is linear in the number of users. The second AnonRAM scheme reduces the overall complexity to poly-logarithmic in the total number of cells (of all users), at the cost of requiring two (non-colluding) servers.

We analyze the security of Android KeyStore, a system service whose purpose is to shield users credentials and cryptographic keys. The KeyStore protects the integrity and the confidentiality of keys by using a particular encryption scheme. Our main results are twofold. First, we formally prove that the used encryption scheme does not provide integrity, which means that an attacker is able to undetectably modify the stored keys. Second, we exploit this flaw to define a forgery attack breaching the security guaranteed by the KeyStore. In particular, our attack allows a malicious application to make mobile apps to unwittingly perform secure protocols using weak keys. The threat is concrete: the attacker goes undetected while compromising the security of users. Our findings highlight an important fact: intuition often goes wrong when security is concerned. Unfortunately, system designers still tend to choose cryptographic schemes not for their proved security but for their apparent simplicity. We show, once again, that this is not a good choice, since it usually results in severe consequences for the whole underlying system.

Midori is a hardware-oriented lightweight block cipher designed by Banik \emph{et al.} in ASIACRYPT 2015. It has two versions according to the state sizes, i.e. Midori64 and Midori128. In this paper, we explore the security of Midori64 against truncated differential and related-key differential attacks. By studying the compact representation of Midori64, we get the branching distribution properties of almost MDS matrix used by Midori64. By applying an automatic truncated differential search algorithm developed by Moriai \emph{et al.} in SAC 1999, we get 3137 4-round truncated differentials of Midori64. In addition, we find some 2-round iterative differential patterns for Midori64. By searching the differential characteristics matching the differential pattern, we find some iterative 2-round differentials with probability of $2^{-24}$, based on these differentials, a 11-round related-key differential characteristic is constructed. Then we mount a 14-round(out of 16 full rounds) related-key differential attack on Midori64. As far as we know, this is the first related-key differential attack on Midori64.

Fully Homomorphic Encryption (FHE) schemes are conceptually very powerful tools for outsourcing computations on confidential data. However, experience shows that FHE-based solutions are not sufficiently efficient for practical applications yet. Hence, there is a huge interest in improving the performance of applying FHE to concrete use cases. What has been mainly overlooked so far is that not only the FHE schemes themselves contribute to the slowdown, but also the choice of data encoding. While FHE schemes usually allow for homomorphic executions of algebraic operations over finite fields (often $\mathbb{Z}_2$), many applications call for different algebraic structures like signed rational numbers. Thus, before an FHE scheme can be used at all, the data needs to be mapped into the structure supported by the FHE scheme.

We show that the choice of the encoding can already incur a significant slowdown of the overall process, which is independent of the efficiency of the employed FHE scheme. We compare different methods for representing signed rational numbers and investigate their impact on the effort needed for processing encrypted values. In addition to forming a new encoding technique which is superior under some circumstances, we also present further techniques to speed up computations on encrypted data under certain conditions, each of independent interest. We confirm our results by experiments.

Security features are of paramount importance for IoT, and implementations are challenging given the resource-constrained IoT set-up. We have developed a lightweight identity-based cryptosystem suitable for IoT, to enable secure authentication and message exchange among the devices. Our scheme employs Physically Unclonable Function (PUF), to generate the public identity of each device, which is used as the public key for each device for message encryption. We have provided formal proofs of security in the Session Key security and Universally Composable Framework of the proposed protocol, which demonstrates the resilience of the scheme against passive as well as active attacks. We have demonstrated the set up required for the protocol implementation and shown that the proposed protocol implementation incurs low hardware and software overhead.