International Association
for Cryptologic Research

Event date: 30 May to 1 June 2018
Submission deadline: 5 March 2018
Notification: 26 March 2018

Event date: 25 March to 28 March 2019
Submission deadline: 23 November 2018
Notification: 23 January 2019

We propose a domain-specific language for smart contracts, which allows participants to transfer cryptocurrency according to agreed contract terms. We define a symbolic and a computational model for reasoning about their security. In the symbolic model, participants act according to the semantics of the domain-specific language. Instead, in the computational model they exchange bitstrings, and publish transactions on the Bitcoin blockchain. A compiler is provided to translate smart contracts into standard Bitcoin transactions. We prove the correctness of our compiler, showing that computational attacks to compiled smart contracts are also observable in the symbolic model.

The field size $8^{91}+5$ for elliptic curve cryptography offers simplicity, security, and efficiency.

While there has been a lot of progress in designing efficient custom protocols for computing Private Set Intersection (PSI), there has been less research on using generic Multi-Party Computation (MPC) protocols for this task. However, there are many variants of the set intersection functionality that are not addressed by the existing custom PSI solutions and are easy to compute with generic MPC protocols (e.g., comparing the cardinality of the intersection with a threshold or measuring ad conversion rates).

Generic PSI protocols work over circuits that compute the intersection. For sets of size $n$, the best known circuit constructions conduct $O(n \log n)$ or $O(n \log n / \log\log n)$ comparisons (Huang et al., NDSS'12 and Pinkas et al., USENIX Security'15). In this work, we propose new circuit-based protocols for computing \emph{variants of the intersection} with an almost linear number of comparisons. Our constructions are based on new variants of Cuckoo hashing in two dimensions.

We present an asymptotically efficient protocol as well as a protocol with better concrete efficiency. For the latter protocol, we determine the required sizes of tables and circuits experimentally, and show that the run-time is concretely better than that of existing constructions.

The protocol can be extended to a larger number of parties. The proof technique for analyzing Cuckoo hashing in two dimensions is new and can be generalized to analyzing standard Cuckoo hashing as well as other new variants of it.

We show how malicious web content can extract cryptographic secret keys from the user's computer. The attack uses portable scripting languages supported by modern browsers to induce contention for CPU cache resources, and thereby gleans information about the memory accesses of other programs running on the user's computer. We show how this side-channel attack can be realized in both WebAssembly and PNaCl; how to attain very fine-grained measurements; and how to use these to extract ElGamal, ECDH and RSA decryption keys from various cryptographic libraries.

The attack does not rely on bugs in the browser's nominal sandboxing mechanisms, or on fooling users. It applies even to locked-down platforms with strong confinement mechanisms and browser-only functionality, such as Chromebook devices.

Moreover, on browser-based platforms the attacked software too may be written in portable JavaScript; and we show that in this case even implementations of supposedly-secure constant-time algorithms, such as Curve25519's, are vulnerable to our attack.

An updatable encryption scheme allows to periodically rotate the encryption key and move already existing ciphertexts from the old to the new key. These ciphertext updates are done with the help of a so-called update token and can be performed by an untrusted party, as the update never decrypts the data. Updatable encryption is particularly useful in settings where encrypted data is outsourced, e.g., stored on a cloud server. The data owner can produce an update token, and the cloud server can update the ciphertexts. We provide a comprehensive treatment of ciphertext-independent schemes, where a single token is used to update all ciphertexts. We show that the existing ciphertext-independent schemes and models by Boneh et al. (CRYPTO’13) and Everspaugh et al. (CRYPTO’17) do not guarantee the post-compromise security one would intuitively expect from key rotation. In fact, the simple scheme recently proposed by Everspaugh et al. allows to recover the current key upon corruption of a single old key. Surprisingly, none of the models so far reflects the timely aspect of key rotation which makes it hard to grasp when an adversary is allowed to corrupt keys. We propose strong security models that clearly capture post-compromise and forward security under adaptive attacks. We then analyze various existing schemes and show that none of them is secure in this strong model, but we formulate the additional constraints that suffice to prove their security in a relaxed version of our model. Finally, we propose a new updatable encryption scheme that achieves our strong notions while being (at least) as efficient as the existing solutions.

We present an optimized implementation of the Fan-Vercauteren variant of the scale-invariant homomorphic encryption scheme of Brakerski. Our algorithmic improvements focus on optimizing decryption and homomorphic multiplication in the Residue Number System (RNS), using the Chinese Remainder Theorem (CRT) to represent and manipulate the large coefficients in the ciphertext polynomials. In particular, we propose efficient procedures for scaling and CRT basis extension that do not require translating the numbers to standard (positional) representation. Compared to the previously proposed RNS design due to Bajard et al., our procedures are simpler and they do not introduce any additional noise. We implement our optimizations in the PALISADE library and evaluate the runtime performance for the range of multiplicative depths from 1 to 50. Our results show that the homomorphic multiplication for the depth-20 setting can be executed in 63 ms on a modern server system, which is already practical for some outsourced-computing applications. Our algorithmic improvements can also be applied to other scale-invariant homomorphic encryption schemes, such as YASHE.

We present simpler and improved constructions of unbounded attribute-based encryption (ABE) schemes with constant-size public parameters under static assumptions in bilinear groups. Concretely, we obtain:

- a simple and adaptively secure unbounded ABE scheme in composite-order groups, improving upon a previous construction of Lewko and Waters (Eurocrypt '11) which only achieves selective security;

- an improved adaptively secure unbounded ABE scheme based on the $k$-linear assumption in prime-order groups with shorter ciphertexts and secret keys than those of Okamoto and Takashima (Asiacrypt '12);

- the first adaptively secure unbounded ABE scheme for arithmetic branching programs under static assumptions.

At the core of all of these constructions is a "bilinear entropy expansion" lemma that allows us to generate any polynomial amount of entropy starting from constant-size public parameters; the entropy can then be used to transform existing adaptively secure "bounded" ABE schemes into unbounded ones.

In this paper we study the affine equivalence problem, where given two functions $\vec{F},\vec{G}: \{0,1\}^n \rightarrow \{0,1\}^n$, the goal is to determine whether there exist invertible affine transformations $A_1,A_2$ over $GF(2)^n$ such that $\vec{G} = A_2 \circ \vec{F} \circ A_1$. Algorithms for this problem have several well-known applications in the design and analysis of Sboxes, cryptanalysis of white-box ciphers and breaking a generalized Even-Mansour scheme.

We describe a new algorithm for the affine equivalence problem and focus on the variant where $\vec{F},\vec{G}$ are permutations over $n$-bit words, as it has the widest applicability. The complexity of our algorithm is about $n^3 2^n$ bit operations with very high probability whenever $\vec{F}$ (or $\vec{G})$ is a random permutation. This improves upon the best known algorithms for this problem (published by Biryukov et al. at EUROCRYPT 2003), where the first algorithm has time complexity of $n^3 2^{2n}$ and the second has time complexity of about $n^3 2^{3n/2}$ and roughly the same memory complexity.

Our algorithm is based on a new structure (called a \emph{rank table}) which is used to analyze particular algebraic properties of a function that remain invariant under invertible affine transformations. Besides its standard application in our new algorithm, the rank table is of independent interest and we discuss several of its additional potential applications.

We design a group key exchange protocol where most of the participants remain offline until they wish to compute the key. This is well suited to a cloud storage environment where users are often offline, but have online access to the server which can assist in key exchange. We define and instantiate a new primitive, a blinded KEM, which we show can be used in a natural way as part of our generic protocol construction. Our new protocol has a security proof based on a well-known model for group key exchange. Our protocol provides a restricted form of forward secrecy which we argue is as strong as can be achieved in practice. Our protocol is efficient, requiring Diffie--Hellman with a handful of standard public key operations per user in our concrete instantiation.

S-boxes, typically the only nonlinear part of a block cipher, are the heart of symmetric cryptographic primitives. They significantly impact the cryptographic strength and the implementation characteristics of an algorithm. Due to their simplicity, quadratic vectorial Boolean functions are preferred when efficient implementations for a variety of applications are of concern. Many characteristics of a function stay invariant under affine equivalence. So far, all 6-bit Boolean functions, 3- and 4-bit permutations and 5-bit quadratic permutations have been classified up to affine equivalence. In this work, we propose a highly efficient algorithm to classify $n \times m$ functions for $n \geq m$. Our algorithm enables for the first time a complete classification of 6-bit quadratic permutations as well as all balanced quadratic functions for $n \leq 6$. These functions can be valuable for new cryptographic algorithm designs with efficient multi-party computation or side-channel analysis resistance as goal. In addition, we provide a second tool for finding decompositions of length two. We demonstrate its use by decomposing existing higher degree S-boxes and constructing new S-boxes with good cryptographic and implementation properties.

Event date: 28 March to 29 March 2018

In the past few years billions of user passwords have been exposed to the threat of offline cracking attempts. Such brute-force cracking attempts are increasingly dangerous as password cracking hardware continues to improve and as users continue to select low entropy passwords. Key-stretching techniques such as hash iteration and memory hard functions can help to mitigate the risk, but increased key-stretching effort necessarily increases authentication delay so this defense is fundamentally constrained by usability concerns. We introduce Just in Time Hashing (JIT), a client side key-stretching algorithm to protect user passwords against offline brute-force cracking attempts without increasing delay for the user. The basic idea is to exploit idle time while the user is typing in their password to perform extra key-stretching. As soon as the user types in the first character(s) of their password our algorithm immediately begins filling memory with hash values derived from the character(s) that the user has typed thus far. We conduct a user study to guide the development of JIT e.g. by determining how much extra key-stretching could be performed during idle cycles or how many consecutive deletions JIT may need to handle. Our security analysis demonstrates that JIT can substantially increase guessing costs over traditional key-stretching algorithms with equivalent (or less) authentication delay. Specifically an empirical evaluation using existing password datasets demonstrates that JIT increases guessing costs by nearly an order of magnitude in comparison to standard key-stretching techniques with comparable delay. We provide a proof-of-concept implementation of a Just in Time Hashing algorithm by modifying Argon2.

We show how to build a binary matrix from the MRHS representation of a symmetric-key cipher. The matrix contains the cipher represented as an equation system and can be used to assess a cipher's resistance against algebraic attacks. We give an algorithm for solving the system and compute its complexity. The complexity is normally close to exhaustive search on the variables representing the user-selected key. Finally, we show that for some variants of LowMC, the joined MRHS matrix representation can be used to speed up regular encryption in addition to exhaustive key search.

In this work we analyze the security of cubic cryptographic constructions with respect to rank weakness. We detail how to extend the big field idea from quadratic to cubic, and show that the same rank defect occurs. We extend the min-rank problem and propose an algorithm to solve it in this setting. We show that for fixed small rank, the complexity is even lower than for the quadratic case. However, the rank of a cubic polynomial in $n$ variables can be larger than $n$, and in this case the algorithm is very inefficient. We show that the rank of the differential is not necessarily smaller, rendering this line of attack useless if the rank is large enough. Similarly, the algebraic attack is exponential in the rank, thus useless for high rank.

In this paper, we propose NTRU-LPR IND-CPA, a new secure scheme based on the decisional variant of Bounded Distance Decoding problem over rings (DR-BDD). This scheme is IND-CPA secure and has two KEM variants IND-CCA2 secure in the random oracle model. NTRU-LPR IND-CPA is similar to NTRU LPRime and LPR Cryptosystem. NTRU-LPR IND-CPA doesn't have a problem of decryption failures. Our polynomial ring can be any ring of the form $\mathbb{Z}[x]/(q,f(x))$, where $f$ is a polynomial of degree $n$ and $q$ is an integer. Relatively to the DR-BDD problem, we propose to use square-free polynomials and such polynomials include $f(x)=x^n-x-1$ (as in NTRU LPRime) and $f(x)=x^n-1$ (as in NTRU). To avoid some weaknesses in Ring-LWE or NTRU-like schemes (Meet-in-the-middle attack, Hybrid attack, Weak keys, etc.), we do not use sparse polynomials or inversion of polynomials. Furthermore, to avoid backdoors, all polynomials in our scheme can be generated by hash functions. We also give a short comparative analysis between our new scheme and some proposals of the NIST Post-Quantum call (November 2017).

Feistel Networks (FN) are now massively being used to encrypt credit card numbers through format-preserving encryption. In our work, we focus on FN with two branches, entirely unknown round functions, modular additions (or other group operations), and when the domain size of a branch (called $N$) is small. We investigate round-function-recovery attacks.

The best known attack so far is an improvement of Meet-In-The-Middle (MITM) attack by Isobe and Shibutani from ASIACRYPT~2013 with optimal data complexity $q=r \frac{N}{2}$ and time complexity $N^{ \frac{r-4}{2}N + o(N)}$, where $r$ is the round number in FN. We construct an algorithm with a surprisingly better complexity when $r$ is too low, based on partial exhaustive search. When the data complexity varies from the optimal to the one of a codebook attack $q=N^2$, our time complexity can reach $N^{O \left( N^{1-\frac{1}{r-2}} \right) }$. It crosses the complexity of the improved MITM for $q\sim N\frac{\mathrm{e}^3}{r}2^{r-3}$.

We also estimate the lowest secure number of rounds depending on $N$ and the security goal. We show that the format-preserving standards FF1 and FF3 from NIST and ANSI standards cannot offer 128-bit security (as they are supposed to) for $N\leq11$ and $N\leq17$, respectively (the NIST standard only requires $N \geq 10$), and improve the results by Durak and Vaudenay from CRYPTO~2017.

Ring signatures, as introduced by Rivest, Shamir, and Tauman (Asiacrypt ’01), allow to generate a signature for a message on be half of an ad-hoc set of parties. To sign a message, only the public keys must be known and these can be generated independently. It is furthermore not possible to identify the actual signer based on the signature. Ring signatures have recently gained attention due to their applicability in the construction of practical anonymous cryptocurrencies, where they are used to secure transactions while hiding the identity of the actual spender. To be applicable in that setting, ring signatures must allow to determine when a party signed multiple transactions, which is done using a property called linkability. This work presents a linkable ring signature scheme constructed from a lattice-based collision-resistant hash function. We follow the idea of existing schemes which are secure based on the hardness of the discrete logarithm problem, but adapt and optimize ours to the lattice setting. In comparison to other designs for (lattice-based) linkable ring signatures, our approach avoids the standard solution for achieving linkability, which involves proofs about correct evaluation of a pseudorandom function using heavy zero-knowledge machinery.

While symmetric-key steganography is quite well understood both in the information-theoretic and in the computational setting, many fundamental questions about its public-key counterpart resist persistent attempts to solve them. The computational model for public-key steganography was proposed by von Ahn and Hopper in EUROCRYPT 2004. At TCC 2005, Backes and Cachin gave the first universal public-key stegosystem - i.e. one that works on all channels - achieving security against replayable chosen-covertext attacks (SS-RCCA) and asked whether security against non-replayable chosen-covertext attacks (SS-CCA) is achievable. Later, Hopper (ICALP 2005) provided such a stegosystem for every efficiently sampleable channel, but did not achieve universality. He posed the question whether universality and SS-CCA-security can be achieved simultaneously. No progress on this question has been achieved since more than a decade. In our work we solve Hopper's problem in a somehow complete manner: As our main positive result we design an SS-CCA-secure stegosystem that works for every memoryless channel. On the other hand, we prove that this result is the best possible in the context of universal steganography. We provide a family of 0-memoryless channels - where the already sent documents have only marginal influence on the current distribution - and prove that no SS-CCA-secure steganography for this family exists in the standard non-look-ahead model.