International Association
for Cryptologic Research

Yao's garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable two-message, two-party secure computation, the scheme has been extended in many ways and has innumerable applications. Still, a basic question has remained open throughout the years: Can the scheme be extended to guarantee security in the face of an adversary that corrupts both parties, adaptively, as the computation proceeds?

We answer this question in the affirmative. We define a new type of encryption, called {\sf functionally equivocal encryption (FEE),} and show that when Yao's scheme is implemented with an FEE as the underlying encryption mechanism, it becomes secure against such adaptive adversaries. We then show how to implement FEE from any one way function.

Combining our scheme with non-committing encryption, we obtain the first two-message, two-party computation protocol, and the first constant-round multiparty computation protocol, in the plain model, that are secure against semi-honest adversaries who can adaptively corrupt all parties. A number of extensions and applications are described within.

This paper gives the first bit security result for the elliptic curve Diffie--Hellman key exchange protocol for elliptic curves defined over prime fields. About $5/6$ of the most significant bits of the $x$-coordinate of the Diffie--Hellman key are as hard to compute as the entire key. A similar result can be derived for the $5/6$ lower bits. The paper also generalizes and improves the result for elliptic curves over extension fields, that shows that computing one component (in the ground field) of the Diffie--Hellman key is as hard to compute as the entire key.

In this paper, we introduce Farfalle, a new mode for building a pseudorandom function (PRF) from a b-bit cryptographic permutation. The constructed PRF takes as input a b-bit key and a sequence of variable-length data strings, and it generates a variable-length output. It consists of a compression layer and an expansion layer, each of them involving the parallel application of the permutation. The construction aims for simplicity and efficiency, among others with the ability to compute it for incremental inputs and with its inherent parallelism. Thanks to its input-output characteristics, Farfalle is very versatile. We specify concrete modes on top of it, for authentication, encryption and authenticated encryption, as well as a wide block cipher mode. Farfalle can be instantiated with any permutation. In particular, we instantiate it with one of the Keccak-p permutations, attach concrete security claims to it and call the result Kravatte. To offer protection against attacks that exploit the low algebraic degree of the round function of Keccak-p, we do domain separation with a particular rolling function that aims at preventing the construction of input sets that form affine spaces of large dimension.

Since the advent of pairing based cryptography, much attention has been given to efficient computation of pairings on elliptic curves with even embedding degrees. The few works that exist in the case of odd embedding degrees require some improvements. This paper considers the computation of optimal ate pairings on elliptic curves of embedding degrees k=9, 15 and 27 which have twists of order three. Mainly, we provide a detailed arithmetic and cost estimation of operations in the tower field of the corresponding extension fields. A good selection of parameters at the $128$, $192$ and $256$-bits security level enables us to improve the theoretical cost for the Miller step and the final exponentiation using the lattice-based method comparatively to the previous few works that exist in these cases. In particular for k=15 we obtain an improvement up to $25\%$ in the computation of the final exponentiation.

Pseudoentropy has found a lot of important applications to cryptography and complexity theory. In this paper we focus on the foundational problem that has not been investigated so far, namely by how much pseudoentropy (the amount seen by computationally bounded attackers) differs from its information-theoretic counterpart (seen by unbounded observers), given certain limits on attacker's computational power?

We provide the following answer for HILL pseudoentropy, which exhibits a \emph{threshold behavior} around the size exponential in the entropy amount: \begin{itemize} \item If the attacker size ($s$) and advantage ($\epsilon$) satisfy $s \gg 2^k\epsilon^{-2}$ where $k$ is the claimed amount of pseudoentropy, then the pseudoentropy boils down to the information-theoretic smooth entropy \item If $s \ll 2^k\epsilon^2$ then pseudoentropy could be arbitrarily bigger than the information-theoretic smooth entropy \end{itemize} Besides answering the posted question, we show an elegant application of our result to the complexity theory, namely that it implies the classical result on the existence of functions hard to approximate (due to Pippenger). In our approach we utilize non-constructive techniques: the duality of linear programming and the probabilistic method.

Event date: 4 September to 8 September 2017
Submission deadline: 1 May 2017
Notification: 1 June 2017

Event date: 3 July to 8 July 2017
Submission deadline: 1 March 2017
Notification: 15 March 2017

Event date: 18 July to 20 July 2017
Submission deadline: 13 March 2017
Notification: 24 April 2017

In this paper we propose a digital signature scheme based on supersingular isogeny problem. We design a signature scheme using the Fiat-Shamir transform. The scheme uses a modified version of zero-knowledge proof proposed by De Feo, Jao, and Pl\^ut. Unlike the original version our zero-knowledge proof uses only one curve as a commitment. A digital signature scheme using the similar idea was proposed recently by Galbraith et al., but our proposal uses a different method in computing isogeny. We take advantage of our proposed version of zero-knowledge proof to speed up signature generation process. We also present a method of compressing signature.

Bitcoin smart contracts allow the development of new protocols on top of Bitcoin itself. This usually involves the definition of complex scripts, far beyond the requirement of a single signature. In this paper we introduce the concept of private key locked transactions, a novel type of transactions that allows the atomic verification of a given private key (belonging to an asymmetric key pair) during the script execution.

In this paper, we determine the Walsh spectra of three classes of quadratic APN functions and we prove that the class of quadratic trinomial APN functions constructed by G\"olo\u glu is affine equivalent to Gold functions.

Public key encryption with equality test (PKEET) is a cryptosystem that allows a tester who has trapdoors issued by one or more users $U_i$ to perform equality tests on ciphertexts encrypted using public key(s) of $U_i$. Since this feature has a lot of practical applications including search on encrypted data, several PKEET schemes have been proposed so far. However, to the best of our knowledge, all the existing proposals are proven secure only under the hardness of number-theoretic problems and the random oracle heuristics.

In this paper, we show that this primitive can be achieved not only generically from well-established other primitives but also even without relying on the random oracle heuristics. More precisely, our generic construction for PKEET employs a two-level hierarchical identity-based encryption scheme, which is selectively secure against chosen plaintext attacks, a strongly unforgeable one-time signature scheme and a cryptographic hash function. Our generic approach toward PKEET has several advantages over all the previous works; it directly leads the first standard model construction and also directly implies the first lattice-based construction. Finally, we show how to extend our approach to the identity-based setting.

In this paper, a new tool searching for impossible differentials against symmetric-key primitives is presented. Compared to the previous tools, our tool can detect any contradiction between input and output differences, and it can take into account the property inside the S-box when its size is small e.g. 4 bits. In addition, several techniques are proposed to evaluate 8-bit S-box. With this tool, the number of rounds of impossible differentials are improved from the previous best results by 1 round for Midori128, Lilliput, and Minalpher. The tool also finds new impossible differentials of ARIA and MIBS. We manually verify the impossibility of the searched results, which reveals new structural properties of those designs. Our tool can be implemented only by slightly modifying the previous differential search tool using Mixed Integer Linear Programming (MILP), while the previous tools need to be implemented independently of the differential search tools. This motivates us to discuss the usage of our tool particular for the design process. With this tool, the maximum number of rounds of impossible differentials can be proven under reasonable assumptions and the tool is applied to various concrete designs.

Electronic information is increasingly often shared among unreliable entities. In this context, one interesting problem involves two parties that secretly want to determine intersection of their respective private data sets while none of them wish to disclose the whole set to other. One can adopt Private Set Intersection (PSI) protocol to address this problem preserving the associated security and privacy issues. This paper presents the first PSI protocol that achieves constant ($p(\kappa)$) communication complexity with linear computation overhead and is fast even for the case of large input sets, where $p(\kappa)$ is a polynomial in security parameter $\kappa$. The scheme is proven to be provably secure in the standard model against semi-honest parties. We combine somewhere statistically binding (SSB) hash function with indistinguishability obfuscation (iO) and Bloom filter to construct our PSI protocol.

Functional encryption (FE) allows an authority to issue tokens associated with various functions, allowing the holder of some token for function f to learn only f(D) from a ciphertext that encrypts D. The standard approach is to model f as a circuit, which yields inefficient evaluations over large inputs. Here, we propose a new primitive that we call updatable functional encryption (UFE), where instead of circuits we deal with RAM programs, which are closer to how programs are expressed in von Neumann architecture. We impose strict efficiency constrains in that the run-time of a token P' on ciphertext CT is proportional to the run-time of its clear-form counterpart (program P on memory D) up to a polylogarithmic factor in the size of D, and we envision tokens that are capable to update the ciphertext, over which other tokens can be subsequently executed. We define a security notion for our primitive and propose a candidate construction from obfuscation, which serves as a starting point towards the realization of other schemes and contributes to the study on how to compute RAM programs over public-key encrypted data.

The record layer is the main bridge between TLS applications and internal sub-protocols. Its core functionality is an elaborate authenticated encryption: streams of messages for each sub-protocol (hand- shake, alert, and application data) are fragmented, multiplexed, and encrypted with optional padding to hide their lengths. Conversely, the sub-protocols may provide fresh keys or signal stream termination to the record layer.

Compared to prior versions, TLS 1.3 discards obsolete schemes in favor of a common construction for Authenticated Encryption with Associated Data (AEAD), instantiated with algorithms such as AES- GCM and ChaCha20-Poly1305. It differs from TLS 1.2 in its use of padding, associated data and nonces. It encrypts the content-type used to multiplex between sub-protocols. New protocol features such as early application data (0-RTT and 0.5-RTT) and late handshake messages require additional keys and a more general model of stateful encryption.

We build and verify a reference implementation of the TLS record layer and its cryptographic algorithms in F*, a dependently typed language where security and functional guarantees can be specified as pre- and post-conditions. We reduce the high-level security of the record layer to cryptographic assumptions on its ciphers. Each step in the reduction is verified by typing an F* module; when the step incurs a security loss, this module precisely captures the corresponding game-based security assumption.

We first verify the functional correctness and injectivity properties of our implementations of one- time MAC algorithms (Poly1305 and GHASH) and provide a generic proof of their security given these properties. We show the security of AEAD given any secure one-time MAC and PRF. We extend AEAD, first to stream encryption, then to length-hiding, multiplexed encryption. Finally, we build a security model of the record layer against an adversary that controls the TLS sub-protocols. We compute concrete security bounds for the AES-GCM and ChaCha20-Poly1305 ciphersuites, and derive recommended limits on sent data before re-keying. Combining our functional correctness and security results, we obtain the first verified implementations of the main TLS 1.3 record ciphers.

We plug our implementation of the record layer into an existing TLS library and confirm that the combination interoperates with Chrome and Firefox, and thus that experimentally the new TLS record layer (as described in RFCs and cryptographic standards) is provably secure.

The slide attack, presented in 1999 by Biryukov and Wagner, has already become a classical tool in cryptanalysis of block ciphers. While it was used to mount practical attacks on a few cryptosystems, its practical applicability is limited, as typically, its time complexity is lower bounded by $2^n$ (where $n$ is the block size). There are only a few known scenarios in which the slide attack performs better than the $2^n$ bound.

In this paper we concentrate on {\it efficient} slide attacks, whose time complexity is less than $2^n$. We present a number of new attacks that apply in scenarios in which previously known slide attacks are either inapplicable, or require at least $2^n$ operations. In particular, we present the first known slide attack on a Feistel construction with a {\it 3-round} self-similarity, and an attack with practical time complexity of $2^{40}$ on a 128-bit key variant of the GOST block cipher with {\it unknown} S-boxes. The best previously known attack on the same variant, with {\it known} S-boxes (by Courtois, 2014), has time complexity of $2^{91}$.

In this paper, we show that the signal function used in RLWE key exchange could leak information to find the secret $s$ of a reused public key $p=as+2e$. This work is motivated by an attack proposed in \cite{cryptoeprint:2016:085} and gives an insight into how RLWE public keys reused for long term can be exploited to find its corresponding secret key. We have also run experiments to verify that the attack succeeds in recovering the secret.

Homomorphic signature schemes allow anyone to perform computation on signed data in such a way that the correctness of computation’s results is publicly certified. In this work we analyze the security notions for this powerful primitive considered in previous work, with a special focus on adaptive security. Motivated by the complications of existing security models in the adaptive setting, we consider a simpler and (at the same time) stronger security definition inspired to that proposed by Gennaro and Wichs (ASIACRYPT’13) for homomorphic MACs. In addition to strength and simplicity, this definition has the advantage to enable the adoption of homomorphic signatures in dynamic data outsourcing scenarios, such as delegation of computation on data streams. Then, since no existing homomorphic signature satisfies this stronger notion, our main technical contribution are general compilers which turn a homomorphic signature scheme secure under a weak definition into one secure under the new stronger notion. Our compilers are totally generic with respect to the underlying scheme. Moreover, they preserve two important properties of homomorphic signatures: context-hiding (i.e. signatures on computation’s output do not reveal information about the input) and efficient verification (i.e. verifying a signature against a program P can be made faster, in an amortized, asymptotic sense, than recomputing P from scratch).

Videos from Asiacrypt 2016 are now available on the IACR youtube channel (youtube.com/theiacr). The conference was held Dec 4-8 in Hanoi, Vietnam.