International Association
for Cryptologic Research

Event date: 16 November to 17 November 2017
Submission deadline: 19 June 2017
Notification: 18 September 2017

Event date: 8 November to 10 November 2017
Submission deadline: 21 July 2017
Notification: 4 September 2017

Applications are invited for a 3.5 year D Phil (PhD) Studentships in Post-Quantum Cryptography, funded by the UK Government.

The D.Phil. studentship will start on 1 October 2017, and will be based at the Mathematical Institute. The studentship is fully funded, and includes standard stipends and College and University fees at the Home rate. The studentship is attached to St Hughs College (http://www.st-hughs.ox.ac.uk/).

Many cryptographic protocols that are used today rely on the difficulty of either factoring or some discrete logarithm problem. However due to Shor’s algorithms, these protocols will become completely unsecure once a large-scale quantum computer is built. Given recent advances in that direction, the UK government is supporting research on new cryptographic protocols that can resist attacks by quantum computers, and the DPhil student will work in this context.

The project will aim at developing post-quantum cryptographic protocols and at studying their security with respect to both classical and quantum computers. The D Phil student will be part of the Oxford Cryptography Group and they will work under the supervision of Dr Christophe Petit (http://people.maths.ox.ac.uk/petit/) and of Professor Cas Cremers (https://www.cs.ox.ac.uk/people/cas.cremers/). Information on the Cryptography Group can be found at www.maths.ox.ac.uk/groups/cryptography.

Candidates must have an excellent background in mathematics, computer science or physics and the ability and willingness to work on inter-disciplinary research projects. Acquaintance with cryptography concepts and/or quantum algorithms as well as some programming skills will be considered as strong assets. The students will also be expected to spend a few weeks at Cheltenham every year. Candidates must therefore be able to obtain a DV security clearance prior to starting their D Phil; in particular they must be UK citizens.

Applications should be made online following the link below. They will be reviewed as they arrive, until the position is filled with a suitable candidate.

Closing date for applications: 1 October 2017

Contact: christophe.petit (at) maths.ox.ac.uk

More information: https://evision.ox.ac.uk/urd/sits.urd/run/siw_ipp_lgn.login?process=siw_ipp_app_crs

The engineer will work on subjects such as

- Next generation blockchain and distributed ledger technologies with applications - to cryptocurrencies and beyond.

- Large-scale, low-latency anonymous messaging and blogging.

- Tracking-resistant WiFi and peer-to-peer ad-hoc networking.

- User-friendly, privacy- and security-hardened operating systems.

- Systematic defenses against side-channel and fingerprinting attacks.

Closing date for applications: 31 July 2017

Contact: Bryan Ford, Associate Professor, bryan.ford (at) epfl.ch

Angela Devenoge, Secretary, angela.devenoge (at) epfl.ch

Linus Gasser, Computer Scientist, linus.gasser (at) epfl.ch

More information: http://dedis.epfl.ch

At EUROCRYPT 2013, Garg, Gentry and Halevi proposed a candidate construction of cryptographic multilinear map (MMap). Despite weaknesses uncovered by Hu and Jia (EUROCRYPT 2016), this candidate is still used with tweaks in cryptographic constructions, in particular indistinguishability obfuscation (iO).

The naive version of the GGH13 scheme was deemed susceptible to averaging attacks, i.e., a statistical leak (yet no precise attack was claimed). A countermeasure was therefore devised, but it remains heuristic. Recently, to reach MMaps with low noise and modulus, variants of this countermeasure were developed by Döttling et al. (EPRINT:2016/599), but their effectiveness is even less clear than in the original scheme.

In this work, we propose a systematic study of this statistical leak, to conclude on the effectiveness of the countermeasure and its variants. In particular, among the two variants proposed by Döttling et al., the so-called conservative method is in fact ineffective: a sensitive secret value is leaked, the very same value as in the unprotected method. Additionally, we note that the other methods also leak secret values, but they seem less sensitive.

As a conclusion, we propose yet another countermeasure, for which this leak is made unrelated to all secrets. On our way, we also make explicit and tighten the hidden exponents in the size of the parameters, as an effort to assess and improve the efficiency of MMaps.

In this work, we propose a new public-key cryptosystem whose security is based on the computational intractability of the following problem: Given a Mersenne number p = 2^n - 1, where n is a prime, a positive integer h, and an n-bit integer H, decide whether their exist n-bit integers F, G each of Hamming weight less than h such that H = F/G modulo p.

The Rényi divergence is a measure of divergence between distributions. It has recently found several applications in lattice-based cryptography. The contribution of this paper is twofold.

First, we give theoretic results which renders it more efficient and easier to use. This is done by providing two lemmas, which give tight bounds in very common situations { for distributions that are tailcut or have a bounded relative error. We then connect the Rényi divergence to the max-log distance. This allows the Rényi divergence to indirectly benefit from all the advantages of a distance.

Second, we apply our new results to five practical usecases. It allows us to claim 256 bits of security for a floating-point precision of 53 bits, in cases that until now either required more than 150 bits of precision or were limited to 100 bits of security: rejection sampling, trapdoor sampling (61 bits in this case) and a new sampler by Micciancio and Walter. We also propose a new and compact approach for table-based sampling, and squeeze the standard deviation of trapdoor samplers by a factor that provides a gain of 30 bits of security in practice.

Aggregator oblivious encryption was proposed by Shi et al. (NDSS 2011), where an aggregator can compute an aggregated sum of data and is unable to learn anything else (aggregator obliviousness). Since the aggregator does not learn individual data that may reveal users' habits and behaviors, several applications, such as privacy-preserving smart metering, have been considered. In this paper, we propose aggregator oblivious encryption schemes with public verifiability where the aggregator is required to generate a proof of an aggregated sum and anyone can verify whether the aggregated sum has been correctly computed by the aggregator. Though Leontiadis et al. (CANS 2015) considered the verifiability, their scheme requires an interactive complexity assumption to provide the unforgeability of the proof. Our schemes are proven to be unforgeable under a static and simple assumption (a variant of the Computational Diffie-Hellman assumption). Moreover, our schemes inherit the tightness of the reduction of the Benhamouda et al. scheme (ACM TISSEC 2016) for proving aggregator obliviousness. This tight reduction allows us to employ elliptic curves of a smaller order and leads to efficient implementation.

The current paper studies the probability of differential characteristics for an unkeyed (or with a fixed key) construction. Most notably, it focuses on the gap between two probabilities of differential characteristics: probability with independent S-box assumption, $p_{ind}$, and exact probability, $p_{exact}$. It turns out that $p_{exact}$ is larger than $p_{ind}$ in Feistel network with some S-box based inner function. The mechanism of this gap is then theoretically analyzed. The gap is derived from interaction of S-boxes in three rounds, and the gap depends on the size and choice of the S-box. In particular the gap can never be zero when the S-box is bigger than six bits. To demonstrate the power of this improvement, a related-key differential characteristic is proposed against a lightweight block cipher RoadRunneR. For the 128-bit key version, $p_{ind}$ of $2^{-48}$ is improved to $p_{exact}$ of $2^{-43}$. For the 80-bit key version, $p_{ind}$ of $2^{-68}$ is improved to $p_{exact}$ of $2^{-62}$. The analysis is further extended to SPN with an almost-MDS binary matrix in the core primitive of the authenticated encryption scheme Minalpher: $p_{ind}$ of $2^{-128}$ is improved to $p_{exact}$ of $2^{-96}$, which allows to extend the attack by two rounds.

A constrained pseudorandom function (PRF) is a secure PRF for which one can generate constrained keys that can only be used to evaluate the PRF on a subset of the domain. Constrained PRFs are used widely, most notably in applications of indistinguishability obfuscation (iO). In this paper we show how to constrain an invertible PRF (IPF), which is significantly harder. An IPF is a secure injective PRF accompanied by an inversion algorithm. A constrained key for an IPF can only be used to evaluate the IPF on a subset S of the domain, and to invert the IPF on the image of S. We first define the notion of a constrained IPF and then give two main constructions: one for puncturing an IPF and the other for (single-key) circuit constraints. Both constructions rely on recent work on private constrained PRFs. We also show that constrained pseudorandom permutations are impossible under our definition.

Current signature and encryption schemes secure against continual leakage fail completely if the key in any time period is fully exposed. We suggest forward security as a second line of defense, so that in the event of full exposure of the current secret key, at least uses of keys prior to this remain secure, a big benefit in practice. (For example if the signer is a certificate authority, full exposure of the current secret key would not invalidate certificates signed under prior keys.) We provide definitions for signatures and encryption that are forward-secure under continual leakage. Achieving these definitions turns out to be challenging, and we make initial progress with some constructions and transforms.

The iterated Even--Mansour (EM) ciphers form the basis of many block cipher designs. Several results have established their security in the CPA/CCA models, under related-key attacks, and in the indifferentiability framework. In this work, we study the Even--Mansour ciphers under key-dependent message (KDM) attacks. KDM security is particularly relevant for block ciphers since non-expanding mechanisms are convenient in setting such as full disk encryption (where various forms of key-dependency might exist). We formalize the folklore result that the ideal cipher is KDM secure. We then show that EM ciphers meet varying levels of KDM security depending on the number of rounds and permutations used. One-round EM achieves some form of KDM security, but this excludes security against offsets of keys. With two rounds we obtain KDM security against offsets, and using different round permutations we achieve KDM security against all permutation-independent claw-free functions. As a contribution of independent interest, we present a modular framework that can facilitate the security treatment of symmetric constructions in models such as RKA or KDM that allow for correlated inputs.

Two types of tweakable blockciphers based on classical blockciphers have been presented over the last years: non-tweak-rekeyable and tweak-rekeyable, depending on whether the tweak may influence the key input to the underlying blockcipher. In the former direction, the best possible security is conjectured to be $2^{\sigma n/(\sigma+1)}$, where $n$ is the size of the blockcipher and $\sigma$ is the number of blockcipher calls. In the latter direction, Mennink and Wang et al. presented optimally secure schemes, but only in the ideal cipher model. We investigate the possibility to construct a tweak-rekeyable cipher that achieves optimal security in the standard cipher model. As a first step, we note that all standard-model security results in literature implicitly rely on a generic standard-to-ideal transformation, that replaces all keyed blockcipher calls by random secret permutations, at the cost of the security of the blockcipher. Then, we prove that if this proof technique is adopted, tweak-rekeying will not help in achieving optimal security: if $2^{\sigma n/(\sigma+1)}$ is the best one can get without tweak-rekeying, optimal $2^n$ provable security with tweak-rekeying is impossible.

At CRYPTO 2016, Cogliati and Seurin introduced the Encrypted Davies-Meyer construction, $p_2(p_1(x) \oplus x)$ for two $n$-bit permutations $p_1,p_2$, and proved security up to $2^{2n/3}$. We present an improved security analysis up to $2^n/(67n)$. Additionally, we introduce the dual of the Encrypted Davies-Meyer construction, $p_2(p_1(x)) \oplus p_1(x)$, and prove even tighter security for this construction: $2^n/67$. We finally demonstrate that the analysis neatly generalizes to prove almost optimal security of the Encrypted Wegman-Carter with Davies-Meyer MAC construction and its newly introduced dual. Central to our analysis is a modernization of Patarin's mirror theorem and an exposition of how it relates to fundamental cryptographic problems.

This paper presents a unified framework that supports different types of privacy-preserving search queries over encrypted cloud data. In the framework, users can perform any of the multi-keyword search, range search and k-nearest neighbor search operations in a privacy-preserving manner. All three types of queries are transformed into predicate-based search leveraging bucketization, locality sensitive hashing and homomorphic encryption techniques. The proposed framework is implemented using Hadoop MapReduce, and its efficiency and accuracy are evaluated using publicly available real data sets. The implementation results show that the proposed framework can effectively be used in moderate sized data sets and it is scalable for much larger data sets provided that the number of computers in the Hadoop cluster is increased. To the best of our knowledge, the proposed framework is the first privacy-preserving solution, in which three different types of search queries are effectively applied over encrypted data.

In this paper we show how to totally break the fully homomorphic encryption sccheme of eprint 2017/458.

Password-based Authenticated Key-Exchange (PAKE) protocols allow users, who need only to share a password, to compute a high-entropy shared session key despite passwords being taken from a dictionary. Security models for PAKE protocols aim to capture the desired security properties that such protocols must satisfy when executed in the presence of an active adversary. They are usually classified into i) indistinguishability-based (IND-based) or ii) simulation-based (SIM-based). The relation between these two security notions is unclear and mentioned as a gap in the literature. In this work, we prove that SIM-BMP security from Boyko et al. (EUROCRYPT 2000) implies IND-RoR security from Abdalla et al. (PKC 2005) and that IND-RoR security is equivalent to a slightly modified version of SIM-BMP security. We also investigate whether IND-RoR security implies (unmodified) SIM-BMP security.

We propose a technique of individually modifying an attribute-based encryption scheme (ABE) that is secure against chosen-plaintext attacks (CPA) into an ABE scheme that is secure against chosen-ciphertext attacks (CCA) in the standard model. We demonstrate the technique in the case of the Waters ciphertext-policy ABE (CP-ABE). Our technique is helpful when a Diffie-Hellman tuple to be verified is in the terminal group of a bilinear map. We utilize the Twin Diffie-Hellman Trapdoor Test of Cash, Kiltz and Shoup, and it results in expansion of secret key length and decryption cost of computation by a factor of four, whereas public key length, ciphertext length and encryption cost of computation remain almost the same. In the case that the size of attribute sets are small, those lengths and costs are smaller than those of the CP-ABE obtained via the generic transformation of Yamada et al. in PKC 2011.

Encrypted databases, a popular approach to protecting data from compromised database management systems (DBMS’s), use abstract threat models that capture neither realistic databases, nor realistic attack scenarios. In particular, the “snapshot attacker” model used to support the security claims for many encrypted databases does not reflect the information about past queries available in any snapshot attack on an actual DBMS. We demonstrate how this gap between theory and reality causes encrypted databases to fail to achieve their “provable security” guarantees.

Functional encryption enables fine-grained access to encrypted data. In many scenarios, however, it is important to control not only what users are allowed to read (as provided by traditional functional encryption), but also what users are allowed to send. Recently, Damgård et al. (TCC 2016) introduced a new cryptographic framework called access control encryption (ACE) for restricting information flow within a system in terms of both what users can read as well as what users can write. While a number of access control encryption schemes exist, they either rely on strong assumptions such as indistinguishability obfuscation or are restricted to simple families of access control policies.

In this work, we give the first ACE scheme for arbitrary policies from standard assumptions. Our construction is generic and can be built from the combination of a digital signature scheme, a predicate encryption scheme, and a (single-key) functional encryption scheme that supports randomized functionalities. All of these primitives can be instantiated from standard assumptions in the plain model, and so, we obtain the first ACE scheme capable of supporting general policies from standard assumptions. One possible instantiation of our construction relies upon standard number-theoretic assumptions (namely, the DDH and RSA assumptions) and standard lattice assumptions (namely, LWE). Finally, we conclude by introducing several extensions to the ACE framework to support dynamic and more fine-grained access control policies.