International Association
for Cryptologic Research

We are constantly moving to a digital world, whereby the majority of information is stored at the weakest link: users' devices and data enclaves -- vulnerable to attacks by adversaries. Users are often interested to share some information, such as the set intersection of their data sets. So as to reduce the communication bandwidth, cloud based protocols have been proposed in the literature, with a rather weak security model. Either there is a semi-honest cloud, which is far from realistic nowadays, or the leakage from the protocol puts the data at risk. In this paper, we achieve the best of the two worlds: We design and analyze a non-interactive, cloud based private set intersection (PSI) protocol secure in a stronger security model. Our protocol assures privacy on data set inputs in case of a malicious cloud and enforces authorized only computations by the users. Moreover the computation is verifiable and the asymptotic communication cost for the computation of the intersection is linear on the common elements $k$. Our protocol is secure in the random oracle model under standard assumptions and a new mathematical assumption whose security evidence is given in the generic group model.

Event date: 13 November to 15 November 2017

Event date: 29 August to 1 September 2017
Submission deadline: 24 April 2017
Notification: 24 May 2017

In this work, we present a new universally composable, actively secure, constant round multi-party protocol for generating BMR garbled circuits with free-XOR and reduced costs. Specifically, the cost of garbling an AND gate is essentially the same as securely evaluating one AND gate using any non-constant-round, GMW-style multi-party computation (MPC) protocol, with a small additive communication overhead that is linear in the security parameter. We further introduce a second realization of the preprocessing phase that is less generic but more efficient, by building on optimized multi-party `TinyOT'-style protocols based on information-theoretic message authentication codes.

An interesting consequence of our work is that, with current techniques, constant round MPC for binary circuits is not much more expensive than practical, non-constant round protocols. We estimate that the concrete communication cost of our preprocessing protocol improves upon previous works by up to three orders of magnitude, and with low computational complexity. We also improve asymptotically by reducing the overall communication complexity from $O(n^3)$ to $O(n^2)$, and our construction is even highly competitive in the two-party setting.

The security of code-based cryptosystems such as the McEliece cryptosystem relies primarily on the difficulty of decoding random linear codes. The best decoding algorithms are all improvements of an old algorithm due to Prange: they are known under the name of information set decoding techniques. It is also important to assess the security of such cryptosystems against a quantum computer. This research thread started in Overbeck and Sendrier's 2009 survey on code-based cryptography, and the best algorithm to date has been Bernstein's quantising of the simplest information set decoding algorithm, namely Prange's algorithm. It consists in applying Grover's quantum search to obtain a quadratic speed-up of Prange's algorithm. In this paper, we quantise other information set decoding algorithms by using quantum walk techniques which were devised for the subset-sum problem by Bernstein, Jeffery, Lange and Meurer. This results in improving the worst-case complexity of $2^{0.06035n}$ of Bernstein's algorithm to $2^{0.05869n}$ with the best algorithm presented here (where $n$ is the codelength).

Three decades ago, Montgomery introduced a new elliptic curve model for use in Lenstra's ECM factorization algorithm. Since then, his curves and the algorithms associated with them have become foundational in the implementation of elliptic curve cryptosystems. This article surveys the theory and cryptographic applications of Montgomery curves over non-binary finite fields, including Montgomery's x-only arithmetic and Ladder algorithm, x-only Diffie--Hellman, y-coordinate recovery, and 2-dimensional and Euclidean differential addition chains such as Montgomery's PRAC algorithm.

Post-doc position in Secure Execution of Cryptographic Algorithms

We have an open position, starting immediately, for a one-year post-doctoral fellowship at the University of Campinas’  Institute of Computing, Brazil, to work in research and development of efficient and secure implementation of cryptographic algorithms. The candidate will be part of a collaborative effort, working on a project funded by Intel and FAPESP, the State of São Paulo research agency. 

The aim of the project encompasses both curve-based and post-quantum crypto algorithms, and is not restricted to software. In fact, we use the whole gamut of possibilities to address the problem of efficient and side-channel-immune code, including the co-design (software and hardware) of solutions.

Candidates should have a good background in implementation of cryptographic algorithms and, desirably, experience in system security. A collaborative attitude and leadership are also an asset.

The fellowship amounts to around US$ 27,000 plus limited travel funds for conferences. Basic free health care is provided by UNICAMP and the Brazilian Public Health System.

The University of Campinas, UNICAMP, is located in Campinas, the center of a vibrant region, with a population of about three-million, distant 100 km from São Paulo and 500 km from Rio de Janeiro, served by an international airport and excellent highways. For a very good introduction to Campinas in English, please watch this short video: https://www.youtube.com/watch?v=MnF3IW1Rekc. Different rankings put UNICAMP in the top-three positions in Brazil and Latin America. Some of its graduate programs lead their areas in Latin America and are prominent worldwide. Please access this page for a brief summary and intro video about UNICAMP: http://www.unicamp.br/unicamp/english.

Interested candidates should email their CV to

Ricardo Dahab - rdahab (at) ic.unicamp.br

Deadline for applications: March 20, 2017

Closing date for applications: 20 March 2017

Contact: Ricardo Dahab

Associate Professor

IC-UNICAMP

rdahab (at) ic.unicamp.br

Applications are invited for two posts in the Information Security Group at Royal Holloway, University of London.

One position is a 4 year-post and is teaching-focussed, with 10% time available for research. The other is a permanent position with a regular balance between teaching and research. This position is roughly equivalent to a tenure-track Assistant Professor in North America or a Junior Professor in Europe.

For the teaching-focussed position, the post holder will contribute to the creation and/or revision, delivery and assessment of postgraduate (MSc) and undergraduate teaching modules across a wide range of topics in the field of information/cyber security. Applicants should have a Ph.D. in a relevant subject or equivalent and have a sound knowledge of information/cyber security. Applicants should be able to demonstrate an enthusiasm for teaching and communicating with diverse audiences, as well as show an awareness of contemporary issues relating to cyber security.

For the permanent position, applications are invited from researchers whose interests are related to, or complement, current strengths of the ISG. We are particularly interested in applicants with outstanding research achievements and/or potential in relevant information/cyber security areas. Applicants should have a Ph.D. in a relevant subject or equivalent, be a self-motivated researcher, and have a strong publication record. Applicants should be able to demonstrate an enthusiasm for teaching and communicating with diverse audiences, as well as show an awareness of contemporary issues relating to cyber security.

We particularly welcome female applicants as they are under-represented at this level in the Department.

4 year teaching-position: https://jobs.royalholloway.ac.uk/vacancy.aspx?ref=0217-089

Permanent regular position: https://jobs.royalholloway.ac.uk/vacancy.aspx?ref=0217-090

Closing date for applications: 9 April 2017

Contact: Professor Keith Mayes

keith.mayes (at) rhul.ac.uk.

More information: https://jobs.royalholloway.ac.uk/vacancy.aspx?ref=0217-090

As a postdoctoral researcher, you will join the European research project DECODE (DEcentralised Citizens Owned Data Ecosystem) that aims to develop distributed architectures for decentralised data governance. You will conduct research on decentralised identity and reputation management using attribute-based credentials and distributed ledgers. You will communicate your findings through papers in peer-reviewed research journals and at international conferences. You will also be involved in training and teaching PhD and BSc/MSc students.

Closing date for applications: 2 April 2017

Contact: Jaap-Henk Hoepman (associate professor), jhh (at) cs.ru.nl

More information: http://www.ru.nl/werken/details/details_vacature_0/?recid=596939

Remote storage delivers a cost effective solution for data storage. If data is of a sensitive nature, it should be encrypted prior to outsourcing to ensure confidentiality; however, searching then becomes challenging. Searchable encryption is a well-studied solution to this problem. Many schemes only consider the scenario where users can search over the entirety of the encrypted data. In practice, sensitive data is likely to be classified according to an access control policy and different users should have different access rights. It is unlikely that all users have unrestricted access to the entire data set. Current schemes that consider multi-level access to searchable encryption are predominantly based on asymmetric primitives. We investigate symmetric solutions to multi-level access in searchable encryption where users have different access privileges to portions of the encrypted data and are not permitted to search over, or learn information about, data for which they are not authorised.

Passwords bootstrap symmetric and asymmetric cryptography, tying keys to an individual user. Biometrics are intended to strengthen this tie. Unfortunately, biometrics exhibit noise between repeated readings. Fuzzy extractors (Dodis et al., Eurocrypt 2004) derive stable symmetric keys from noisy sources.

We ask if it is also possible for noisy sources to directly replace private keys in asymmetric cryptosystems. We propose a new primitive called public-key cryptosystems with noisy keys. Such a cryptosystem functions when the private key varies according to some metric. An intuitive solution is to combine a fuzzy extractor with a public key cryptosystem. Unfortunately, fuzzy extractors need static helper information to account for noise. This helper information creates fundamental limitations on the resulting cryptosytems.

To overcome these limitations, we directly construct public-key encryption and digital signature algorithms with noisy keys. The core of our constructions is a computational version of the fuzzy vault (Juels and Sudan, Designs, Codes, and Cryptography 2006). Security of our schemes is based on graded encoding schemes (Garg et al., Eurocrypt 2013, Garg et al., TCC 2016). Importantly, our public-key encryption algorithm is based on a weaker model of grading encoding. If functional encryption or indistinguishable obfuscation exist in this weaker model, they also exist in the standard model.

In addition, we use the computational fuzzy vault to construct the first reusable fuzzy extractor (Boyen, CCS 2004) supporting a linear fraction of errors.

There is some evidence that indistinguishability obfuscation (iO) requires either exponentially many assumptions or (sub)exponentially hard assumptions, and indeed, all known ways of building obfuscation suffer one of these two limitations. As such, any application built from iO suffers from these limitations as well. However, for most applications, such limitations do not appear to be inherent to the application, just the approach using iO. Indeed, several recent works have shown how to base applications of iO instead on functional encryption (FE), which can in turn be based on the polynomial hardness of just a few assumptions. However, these constructions are quite complicated and recycle a lot of similar techniques. In this work, we unify the results of previous works in the form of a weakened notion of obfuscation, called Exploding iO. We show (1) how to build exploding iO from functional encryption, and (2) how to build a variety of applications from exploding iO, including all of the applications already known from FE. The construction in (1) hides most of the difficult techniques in the prior work, whereas the constructions in (2) are much closer to the comparatively simple constructions from iO. As such, exploding iO represents a convenient new platform for obtaining more applications from polynomial hardness.

Randomness plays an important role in multiple applications in cryptography. It is required in fundamental tasks such as key generation, masking and hiding values, nonces and initialization vectors generation. Pseudo-random number generators have been studied by numerous authors, either to propose clear security notions and associated constructions or to point out potential vulnerabilities. In this systematization of knowledge paper, we present the three notions of generators that have been successively formalized: standard generators, stateful generators and generators with input. For each notion, we present expected security properties, where adversaries have increasing capabilities (including access to partial information on the internal variables) and we propose secure and efficient constructions, all based on the block cipher AES. In our description of generators with input, we revisit the notions of accumulator and extractor and we point out that security crucially relies on the independence between the randomness source and the seeds of the accumulator and the extractor. To illustrate this requirement, we identify a potential vulnerability of the NIST standard CTR_DRBG.

One of the tasks in the iDASH Secure Genome Analysis Competition in 2016 was to demonstrate the feasibility of privacy-preserving queries on homomorphically encrypted genomic data. More precisely, given a list of up to 100,000 mutations, the task was to encrypt the data using homomorphic encryption in a way that allows it to be stored securely in the cloud, and enables the data owner to query the dataset for the presence of specific mutations, without revealing any information about the dataset or the queries to the cloud. We devise a novel string matching protocol that works particularly nicely with homomorphically encrypted data, and show how it yields an efficient solution to the competition task. The protocol we describe is also of independent interest to the homomorphic encryption community, as it can be applied just as well to any kind of data.

Recently, Wang (2016) introduced a random linear code based quantum resistant public encryption scheme RLCE which is a variant of McEliece encryption scheme. In this paper, we introduce a revised version of the RLCE encryption scheme. The revised RLCE schemes are more efficient than the original RLCE scheme. Specifically, it is shown that RLCE schemes have smaller public key sizes compared to binary Goppa code based McEliece encryption schemes for corresponding security levels. The paper further investigates message padding schemes for RLCE to achieve IND-CCA2 security. Practical RLCE parameters for the security levels of $128, 192$, and $256$ are recommended. Furthermore, we point out that the algorithm proposed by Sendrier (ISIT 2005) for encoding extra information symbols within error locations of McEliece encryption scheme is incorrect.

Tag-based message authentication is a popular cryptographic technique to digitally sign messages. However, for short messages, it often incurs additional costs due to large tags. In this paper, we propose a new scheme that achieves tagless message authentication. The scheme leverages a trade-off between character support and complexity of forgery to provide information security and authenticity.

This paper deals with linear approximations having absolute bias smaller than $2^{-\frac{n}{2}}$ which were previously believed to be unusable for a linear attack. We show how a series of observations which are individually not statistically significant can be used to create a $\chi^2$ distinguisher. This is different from previous works which combined a series of significant observations to reduce the data complexity of a linear attack. We test the distinguisher on a real-world cipher and show that it can be used to improve previous results.

We give Proofs of Work (PoWs) whose hardness is based on a wide array of computational problems, including Orthogonal Vectors, 3SUM, All-Pairs Shortest Path, and any problem that reduces to them (this includes deciding any graph property that is statable in first-order logic). This results in PoWs whose completion does not waste energy but instead is useful for the solution of computational problems of practical interest.

The PoWs that we propose are based on delegating the evaluation of low-degree polynomials originating from the study of average-case fine-grained complexity. We prove that, beyond being hard on the average (based on worst-case hardness assumptions), the task of evaluating our polynomials cannot be amortized across multiple~instances.

For applications such as Bitcoin, which use PoWs on a massive scale, energy is typically wasted in huge proportions. We give a framework that can utilize such otherwise wasteful work.

We present functions that can be computed in some fixed polynomial time but are hard on average for any algorithm that runs in slightly smaller time, assuming widely-conjectured worst-case hardness for problems from the study of fine-grained complexity. Unconditional constructions of such functions are known from before (Goldmann et al., IPL '94), but these have been canonical functions that have not found further use, while our functions are closely related to well-studied problems and have considerable algebraic structure.

We prove our hardness results in each case by showing fine-grained reductions from solving one of three problems -- namely, Orthogonal Vectors (OV), 3SUM, and All-Pairs Shortest Paths (APSP) -- in the worst case to computing our function correctly on a uniformly random input. The conjectured hardness of OV and 3SUM then gives us functions that require $n^{2-o(1)}$ time to compute on average, and that of APSP gives us a function that requires $n^{3-o(1)}$ time. Using the same techniques we also obtain a conditional average-case time hierarchy of functions.

Based on the average-case hardness and structural properties of our functions, we outline the construction of a Proof of Work scheme and discuss possible approaches to constructing fine-grained One-Way Functions. We also show how our reductions make conjectures regarding the worst-case hardness of the problems we reduce from (and consequently the Strong Exponential Time Hypothesis) heuristically falsifiable in a sense similar to that of (Naor, CRYPTO '03).

In this work we investigate the problem of using public consensus networks -- exemplified by systems like Ethereum and Bitcoin -- to perform cryptographic functionalities that involve the manipulation of secret data, such as cryptographic access control. We consider a hybrid paradigm in which a secure client-side functionality manages cryptographic secrets, while an online consensus network performs public computation. Using this approach, we explore both the constructive and potentially destructive implications of such systems. We first show that this combination allows for the construction of stateful interactive functionalities (including general computation) from a stateless client-side functionality, which can be implemented using inexpensive trusted hardware or even purely cryptographic functionalities such as Witness Encryption. We then describe a number of practical applications that can be achieved today. These include rate limited mandatory logging; strong encrypted backups from weak passwords; enforcing fairness in multi-party computation; and destructive applications such as autonomous ransomware, which allows for payments without an online party.