International Association
for Cryptologic Research

In SAC 2013, Berger et al. defined Extended Generalized Feistel Networks (EGFN) and analyzed their security. Later, they proposed a cipher based on this structure: LILLIPUT. Impossible differential attacks and integral attacks have been mounted on LILLIPUT. We propose a tool which has found some classical, impossible and improbable differential attacks by using the variance method. It has highlighted unusual differential conditions which lead to efficient attacks by the complexity. Moreover, it is the first time we apply the generic variance method to a concrete cipher.

We consider a recent security definition of Chenette, Lewi, Weis, and Wu for order-revealing encryption (ORE) and order-preserving encryption (OPE) (FSE 2016). Their definition says that the comparison of two ciphertexts should only leak the index of the most significant bit on which the differ. While their work could achieve ORE with short ciphertexts that expand the plaintext by a factor approximate 1.58, it could only find OPE with longer ciphertxts that expanded the plaintext by a security-parameter factor. We give evidence that this gap between ORE and OPE is inherent, by proving that any OPE meeting the information-theoretic version of their security definition (for instance, in the random oracle model) must have ciphertext length close to that of their constructions. We extend our result to identify an abstract security property of any OPE that will result in the same lower bound.

The disassembled code of an executable program can be seen as a graph representing the possible sequence of instructions (Control Flow Graph). grap is a YARA-like tool, completely open-source, and able to detect graph patterns, defined by the analyst, within an executable program.

We used grap to detect cryptographic algorithms: we created patterns for AES and ChaCha20 that are based on parts of the assembly code produced by compiling popular implementations (available in LibreSSL and libsodium). Our approach is thus based on the algorithms and their structure and does not rely on constant detection.

The decentralized cryptocurrency Bitcoin has experienced great success but also encountered many challenges. One of the challenges has been the long confirmation time. Another challenge is the lack of incentives at certain steps of the protocol, raising concerns for transaction withholding, selfish mining, etc. To address these challenges, we propose Solida, a decentralized blockchain protocol based on reconfigurable Byzantine consensus augmented by proof-of-work. Solida improves on Bitcoin in confirmation time, and provides safety and liveness assuming the adversary control less than (roughly) one-third of the total mining power.

In this work we seek to construct collusion-resistant traitor tracing systems with small ciphertexts from standard assumptions that also move toward practical efficiency. In our approach we will hold steadfast to the principle of collusion resistance, but relax the requirement on catching a traitor from a successful decoding algorithm. We define a $f$-risky traitor tracing system as one where the probability of identifying a traitor is $f(\lambda,n)$ times the probability a successful box is produced. We then go on to show how to build such systems from composite order bilinear groups with assumptions close to those used in prior works. Our core system achieves $f(\lambda,n) = \frac{1}{n}$ where ciphertexts consists of three group elements and decryption requires just two pairing operations. In addition, we show a generic way to increase $f$ by approximately a factor of $k$ if we increase the size of the ciphertext and decryption time also by a factor of $k$.

At first glance the utility of such a system might seem questionable since the $f$ we achieve for short ciphertexts is relatively small. Indeed an attacker in such a system can more likely than not get away with producing a decoding box. However, we believe this approach to be viable for three reasons:

1. A risky traitor tracing system will provide deterrence against risk averse attackers. In some settings the consequences of being caught might bear a high cost and an attacker will have to weigh his utility of producing a decryption $D$ box against the expected cost of being caught.

2. One potential use of a risky traitor tracing system is to place it in a continual use situation where users will periodically receive fresh traitor tracing secret keys via a key refresh mechanism that is built using standard encryption. If an attacker wishes to produce a decoder $D$ that continues to work through these refreshes the decoder will be taking an $f$ risk of being caught after each key refresh, which presents a Russian roulette situation for the attacker.

2. Finally, we can capture impossibility results for differential privacy from risky traitor tracing. Since our ciphertexts are short ($O(\lambda)$), thus we get the negative result which matches what one would get plugging in the obfuscation based tracing system Boneh-Zhandry (CRYPTO 2014) solution into the prior impossibility result of Dwork et al. (STOC 2009).

Event date: 4 June 2018
Submission deadline: 15 January 2018
Notification: 28 February 2018

The David R. Cheriton School of Computer Science invites applications for up to ten tenure-track (assistant professor) or tenured (associate/full professor) faculty positions.

Excellent faculty members are sought who will enhance the school’s strength in Computer Science. Priority areas include:

Computer Security, Cryptography, Privacy, and related.

Tenured appointments at the associate and full professor level are possible as circumstances warrant.

The David R. Cheriton School of Computer Science is the largest computer science school in Canada, with 89 faculty members. It enjoys an excellent reputation in pure and applied research and houses a diverse research program of international stature. Because of its recognized capabilities, the school attracts exceptionally well-qualified students at both undergraduate and graduate levels. In addition, the University of Waterloo has an enlightened intellectual property policy that vests all rights in the inventor. Please see the school’s website for more information: https://www.cs.uwaterloo.ca.

To submit an application, please register at the submission site: https://www.cs.uwaterloo.ca/faculty-recruiting. Once registered, instructions will be provided regarding how to submit your full application. Applications will be considered when they are complete and as long as positions are available. However, full consideration is assured only for applications received by November 30, 2017.

Closing date for applications: 31 December 2017

More information: https://cs.uwaterloo.ca/about/open-positions/faculty-positions#Tenure-Track or Tenured Faculty

The IMDEA Software Institute invites applications for multiple tenure-track (Assistant Professor) faculty positions. We are primarily interested in recruiting excellent candidates in the areas of Data Science, including machine learning; Privacy; and Systems, including parallel and distributed systems, embedded systems, hybrid and heterogeneous architectures, etc. However, we are open to other areas within the general research focus of the Institute. Tenured-level applications will also be considered.

The primary mission of the IMDEA Software Institute is to perform research of excellence at the highest international level in the area of software development technologies. It is one of the highest ranked institutions worldwide in its main topic areas.

All positions require a doctoral degree in Computer Science or a closely related area, earned by the expected start date. Candidates for tenure-track positions will have shown exceptional promise in research and will have displayed an ability to work independently as well as collaboratively. Candidates for tenured positions must possess an outstanding research record, have recognized international stature, and demonstrated leadership abilities. Experience in graduate student supervision is also valued at this level.

Working at the IMDEA Software Institute

The institute is located in the vibrant area of Madrid, Spain. It offers an ideal working environment, combining the best aspects of a research center and a university department. The institute offers institutional funding and also encourages its members to participate in national and international research projects. The working language at the institute is English.

Salaries at the Institute are internationally competitive and established on an individual basis. They include social security provisions in accordance with existing national Spanish legislation, and in particular access to an excellent public health care system.

Further information about the Institute\'s current faculty and research can be found at

http://www.software.imdea.org

Closing date for applications: 15 January 2018

Contact: Applications should be completed using the application form at

https://careers.imdea.org/software/

For full consideration, complete applications must be received by January 15, 2018 but will continue to be accepted until the positions are filled.

More information: https://software.imdea.org/open_positions/call_for_faculty.html

We present a signature scheme with the tightest security-reduction among known constant-size signature schemes secure under the computational Diffie-Hellman (CDH) assumption. It is important to reduce the security-reduction loss of a cryptosystem, which enables choosing of a smaller security parameter without compromising security; hence, enabling constant-size signatures for cryptosystems and faster computation. The tightest security reduction far from the CDH assumption is $\mathcal{O}(q)$, presented by Hofheinz et al., where $q$ is the number of signing queries. They also proved that the security loss of $\mathcal{O}(q)$ is optimal if signature schemes are ``re-randomizable". In this paper, we revisit the non-re-randomizable signature scheme proposed by Bohl et al. Their signature scheme is the first that is fully secure under the CDH assumption and has a compact public key. However, they constructed the scheme with polynomial-order security-reduction loss. We first constructed a new existentially unforgeable againt extended random-message attack (EUF-XRMA) secure scheme based on Bohl et al.'s scheme, which has tighter security reduction of $\mathcal{O}(q/d)$ to the CDH assumption, where $d$ is the number of group elements in a verification key. We then transformed the EUF-XRMA secure signature scheme into an existentially unforgeable against adaptively chosen-message attack (EUF-CMA) secure one using Abe et al.'s technique. In this construction, no pseudorandom function, which results in increase of reduction loss, is used, and the above reduction loss can be achieved. Moreover, a tag can be generated more efficiently than Bohl et al.'s signature scheme, which results in smaller computation. Consequently, our EUF-CMA secure scheme has tighter security reduction to the CDH assumption than any previous schemes.

This chapter compares Peter Montgomery's modular multiplication method with traditional techniques for suitability on hardware platforms. It also covers systolic array implementations and side channel leakage.

The rise of machine learning -- and most particularly the one of deep neural networks -- multiplies scenarios where one faces a privacy dilemma: either sensitive user data must be revealed to the entity that evaluates the cognitive model (e.g. in the Cloud), or the model itself must be revealed to the user so that the evaluation can take place locally. The use of homomorphic encryption promises to reconcile these conflicting interests in the Cloud-based scenario: the computation is performed remotely and homomorphically on an encrypted input and the user decrypts the returned result. A typical task is that of classifying input patterns and a number of works have already attempted to implement homomorphic classification based on Somewhat Homomorphic Encryption. The resulting running times are not only disappointing but also quickly degrade with the number of layers in the network. Surely, this approach is not adapted to deep neural networks, that are composed of tens or possibly hundreds of layers.

This paper achieves unprecedentedly fast, scale-invariant homomorphic evaluation of neural networks. Scale-invariance here means that the computation carried out by every neuron in the network is independent of the total number of neurons and layers, thus opening the way to privacy-preserving applications of deep neural networks. We refine the recent R/LWE-based Torus- FHE construction by Chillotti et al. (ASIACRYPT 2016) and make use of its efficient bootstrapping to refresh ciphertexts propagated throughout the network. For our techniques to be applicable, we require the neural network to be discretized, meaning that signals are binarized values in $\{-1, 1\}$, weights are signed integers in a prescribed interval and neurons are activated by the sign function. We show how to train such networks using a specifically designed backpropagation algorithm. We report experimental results on the MNIST dataset and show-case a discretized neural network that recognizes handwritten numbers with over 92% accuracy and is evaluated homomorphically in just about 0.88 seconds on a single core of an average-level laptop. We believe that this work can help bridge the gap between machine learning's capabilities and its practical, efficient and privacy-preserving implementation.

This paper studies discrete-log algorithms that use preprocessing. In our model, an adversary may use a very large amount of precomputation to produce an "advice" string about a specific group (e.g., NIST P-256). In a subsequent online phase, the adversary's task is to use the preprocessed advice to quickly compute discrete logarithms in the group. Motivated by surprising recent preprocessing attacks on the discrete-log problem, we study the power and limits of such algorithms.

In particular, we focus on generic algorithms—these are algorithms that operate in every cyclic group. We show that any generic discrete-log algorithm with preprocessing that uses an $S$-bit advice string, runs in online time $T$, and succeeds with probability $\epsilon$ in a group of prime order $N$ must satisfy $ST^2 = \Omega(\epsilon N)$. Our lower bound, which is tight up to logarithmic factors, uses a synthesis of incompressibility techniques and classic methods for generic-group lower bounds. We apply our techniques to prove related lower bounds for the CDH, DDH, and multiple-discrete-log problems.

Finally, we demonstrate two new generic preprocessing attacks: one for the multiple-discrete-log problem and one for certain decisional-type problems in groups. This latter result demonstrates that, for generic algorithms with preprocessing, distinguishing tuples of the form $(g, g^x, g^{(x^2)})$ from random is much easier than the discrete-log problem.

Linear dimensionality reduction plays a very important role in side channel attacks, but it is helpless when meeting the non-linear leakage of masking implementations. Increasing the order of masking makes the attack complexity grow exponentially, which makes the research of nonlinear dimensionality reduction very meaningful. However, the related work is seldom studied. A kernel function was firstly introduced into Kernel Discriminant Analysis (KDA) in CARDIS 2016 to realize nonlinear dimensionality reduction. This is a milestone for attacking masked implementations. However, KDA is supervised and noise-sensitive. Moreover, several parameters and a specialized kernel function are needed to be set and customized. Different kernel functions, parameters and the training results, have great influence on the attack efficiency. In this paper, the high dimensional non-linear leakage of masking implementation is considered as high dimensional manifold, and manifold learning is firstly introduced into side channel attacks to realize nonlinear dimensionality reduction. Several classical and practical manifold learning solutions such as ISOMAP, Locally Linear Embedding (LLE) and Laplacian Eigenmaps (LE) are given. The experiments are performed on the simulated unprotected, first-order and second-order masking implementations. Compared with supervised KDA, manifold learning schemes introduced here are unsupervised and fewer parameters need to be set. This makes manifold learning based nonlinear dimensionality reduction very simple and efficient for attacking masked implementations.

Consider key agreement by two parties who start out knowing a common secret (which we refer to as “pass-string”, a generalization of “password”), but face two complications: (1) the pass-string may come from a low-entropy distribution, and (2) the two parties’ copies of the pass-string may have some noise, and thus not match exactly. We provide the first efficient and general solutions to this problem that enable, for example, key agreement based on commonly used biometrics such as iris scans. The problem of key agreement with each of these complications individually has been well studied in literature. Key agreement from low-entropy shared pass-strings is achieved by password-authenticated key exchange (PAKE), and key agreement from noisy but high-entropy shared pass-strings is achieved by information-reconciliation protocols as long as the two secrets are “close enough.” However, the problem of key agreement from noisy low-entropy pass-strings has never been studied. We introduce (universally composable) fuzzy password-authenticated key exchange (fPAKE), which solves exactly this problem. fPAKE does not have any entropy requirements for the pass-strings, and enables secure key agreement as long as the two pass-strings are “close” for some notion of closeness. We also give two constructions. The first construction achieves our fPAKE definition for any (efficiently computable) notion of closeness, including those that could not be handled before even in the high-entropy setting. It uses Yao’s Garbled Circuits in a way that is only two times more costly than their use against semi-honest adversaries, but that guarantees security against malicious adversaries. The second construction is more efficient, but achieves our fPAKE definition only for pass-strings with low Hamming distance. It builds on very simple primitives: robust secret sharing and PAKE.

In the process of profiled side-channel analysis there is a number of steps one needs to make. One important step that is often conducted without a proper attention is selection of the points of interest (features) within the side-channel measurement trace. Most of the related work start with an assumption that the features are selected and various attacks are then considered and compared to find the best approach. In this paper, we concentrate on the feature selection step and show that if a proper selection is done, most of the attack techniques offer satisfactory results. We investigate how more advanced feature selection techniques stemming from the machine learning domain can be used to improve the side-channel attack efficiency. Our results show that the so-called Hybrid feature selection methods result in the best classification accuracy over a wide range of test scenarios and number of features selected.

We present EZPC: a secure two-party computation (2PC) framework that generates efficient 2PC protocols from high-level, easy-to-write, programs. EZPC provides formal correctness and security guarantees while maintaining performance and scalability. Previous language frameworks, such as CBMC-GC, ObliVM, SMCL, and Wysteria, generate protocols that use either arithmetic or boolean circuits exclusively. Our compiler is the first to generate protocols that combine both arithmetic sharing and garbled circuits for better performance. We empirically demonstrate that the protocols generated by our framework match or outperform (up to 19x) recent works that provide hand-crafted protocols for various functionalities such as secure prediction and matrix factorization.

This article appeared as Chapter 9 of the book "Topics in Computational Number Theory inspired by Peter L. Montgomery", edited by Joppe W. Bos and Arjen K. Lenstra and published by Cambridge University Press. See https://www.cambridge.org/9781107109353.

A central challenge in differential privacy is to design computationally efficient noninteractive algorithms that can answer large numbers of statistical queries on a sensitive dataset. That is, we would like to design a differentially private algorithm that takes a dataset $D \in X^n$ consisting of some small number of elements $n$ from some large data universe $X$, and efficiently outputs a summary that allows a user to efficiently obtain an answer to any query in some large family $Q$.

Ignoring computational constraints, this problem can be solved even when $X$ and $Q$ are exponentially large and $n$ is just a small polynomial; however, all algorithms with remotely similar guarantees run in exponential time. There have been several results showing that, under the strong assumption of indistinguishability obfuscation (iO), no efficient differentially private algorithm exists when $X$ and $Q$ can be exponentially large. However, there are no strong separations between information-theoretic and computationally efficient differentially private algorithms under any standard complexity assumption.

In this work we show that, if one-way functions exist, there is no general purpose differentially private algorithm that works when $X$ and $Q$ are exponentially large, and $n$ is an arbitrary polynomial. In fact, we show that this result holds even if $X$ is just subexponentially large (assuming only polynomially-hard one-way functions). This result solves an open problem posed by Vadhan in his recent survey.

This paper firstly introduces a novel security definition for BLAC-like schemes (BLAC represents TTP-free BLacklist-able Anonymous Credentials) in the symbolic model using applied pi calculus, which is suitable for automated reasoning via a certain formal analysis tool. We model the definitions of some common security properties: authenticity, non-framebility, mis-authentication resistance and privacy (anonymity and unlinkability). Then the case study of these security definitions is demonstrated by modelling and analyzing BLACR (BLAC with Reputation) system. We verify these security properties by Blanchet’s ProVerif and a ZKP (Zero-Knowledge Proof) compiler developed by Backes et al.. In particular, we model and analyze the express-lane authentication in BLACR system. The analysis discovers a known attack that can be carried out by any potential user. This attack allows a user escaping from being revoked as he wishes. We provide a revised variant that can be proved successfully by ProVerif as well, which also indicates that the fix provided by ExBLACR (Extending BLACR) is incorrect.

Searchable Symmetric Encryption (SSE) has been widely applied in the design of encrypted database for exact queries or even range queries in practice. In spite of its efficiency and functionalities, it always suffers from information leakages. Some recent attacks point out that forward privacy is the desirable security goal. However, there are only a very small number of schemes achieving this security. In this paper, we propose a new forward secure SSE scheme, denoted as ``FFSSE'', which has the best performance in the literature, namely with fast search operation, fast token generation and O(1) update complexity. It also supports both add and delete operations in the unique instance. Technically, we exploit a novel ``key-based blocks chain'' technique based on symmetric cryptographic primitive, which can be deployed in arbitrary index tree structures or key-value structures directly to provide forward privacy. In order to reduce the storage on the client side, we further propose an efficient permutation technique (with similar function as trapdoor permutation) to support the re-construction of the search tokens. Experiments show that our scheme is 4 times, 300 times and 300 times faster than the state-of-the-art forward private SSE scheme (proposed in CCS 2016) in search, update and token generation, respectively. Security analysis shows that our scheme is secure.