International Association
for Cryptologic Research

Event date: 29 August to 1 September 2017
Submission deadline: 10 March 2017
Notification: 22 May 2017

PRIDE is one of the most effcient lightweight block cipher proposed so far for connected objects with high performance and low resource constraints. In this paper we describe the first ever complete Differential Fault Analysis against PRIDE. We describe how fault attacks can be used against implementations of PRIDE to recover the entire encryption key. Our attack has been validated first through simulations, and then in practice on a software implementation of PRIDE running on a device that could typically be used in IoT devices. Faults have been injected using electromagnetic pulses during the PRIDE execution and the faulty ciphertexts have been used to recover the key bits. We also discuss some countermeasures that could be used to thwart such attacks.

There have been many efforts to strengthen security of Instant Messaging (IM) system. One of the typical technologies is the conventional message encryption using a secret or private key. However, the key is fundamentally vulnerable to a bruteforce attack, causing to acquire the original message. In this respect, a countermeasure was suggested as the way to generating plausible-looking but fake plaintexts, which is called Honey Encryption (HE). In this paper, we present a HE-based statistical scheme and design a Honey Chatting application, which is robust to eavesdropping. Besides, we verify the effectiveness of the Honey Chatting by comparing the entropy of decrypted messages through experiments.

Honey encryption (HE) is a new technique to overcome the weakness of conventional password-based encryption (PBE). However, conventional honey encryption still has the limitation that it works only for binary bit streams or integer sequences because it uses a fixed distribution-transforming encoder (DTE). In this paper, we propose a variant of honey encryption called visual honey encryption which employs an adaptive DTE in a Bayesian framework so that the proposed approach can be applied to more complex domains including images and videos. We applied this method to create a new steganography scheme which significantly improves the security level of traditional steganography.

At EUROCRYPT 2015, Zahur et al.\ argued that all linear, and thus, efficient, garbling schemes need at least two $k$-bit elements to garble an AND gate with security parameter $k$. We show how to circumvent this lower bound, and propose an efficient garbling scheme which requires less than two $k$-bit elements per AND gate for most circuit layouts. Our construction slightly deviates from the linear garbling model, and constitutes no contradiction to any claims in the lower-bound proof. With our proof of concept construction, we hope to spur new ideas for more practical garbling schemes. Our construction can directly be applied to semi-private function evaluation by garbling XOR, XNOR, NAND, OR, NOR and AND gates in the same way, and keeping the evaluator oblivious of the gate function.

In this paper, we suggest an advanced method searching for differential trails of block cipher with ARX structure. We use two techniques to optimize the automatic search algorithm of differential trails suggested by Biryukov et al. and obtain 2~3 times faster results than the previous one when implemented in block cipher SPECK.

\begin{abstract} In this paper we will first study two closely related problems:\\ 1. The problem of distinguishing $f(x\Vert 0)\oplus f(x \Vert 1)$ where $f$ is a random permutation on $n$ bits. This problem was first studied by Bellare and Implagliazzo in~\cite{BI}.\\ 2. The so-called ``Theorem $P_i \oplus P_j$'' of Patarin (cf~\cite{P05}). Then, we will see many variants and generalizations of this ``Theorem $P_i \oplus P_j$'' useful in Cryptography. In fact all these results can be seen as part of the theory that analyzes the number of solutions of systems of linear equalities and linear non equalities in finite groups. We have nicknamed these analysis ``Mirror Theory'' due to the multiples induction properties that we have in it. \end{abstract}

Event date: 22 March to 23 March 2017

Isolated Execution Environments (IEEs), such as ARM TrustZone and Intel SGX, offer the possibility to execute sensitive code in isolation from other malicious programs, running on the same machine, or a potentially corrupted OS. A key feature of IEEs is the ability to produce reports binding cryptographically a message to the program that produced it, typically ensuring that this message is the result of the given program running on an IEE. We present a symbolic model for specifying and verifying applications that make use of such features. For this we introduce the S$\ell$APiC process calculus, that allows to reason about reports issued at given locations. We also provide tool support, extending the SAPiC/Tamarin toolchain and demonstrate the applicability of our framework on several examples implementing secure outsourced computation (SOC), a secure licensing protocol and a one-time password protocol that all rely on such IEEs.

PMAC is a simple and parallel block-cipher mode of operation, which was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a (pseudo)random permutation over n-bit strings, PMAC constitutes a provably secure variable input-length (pseudo)random function. For adversaries making q queries, each of length at most $\ell$ (in n-bit blocks), and of total length $\sigma \leq q\ell$, the original paper proves an upper bound on the distinguishing advantage of $O(\sigma^2/2^n)$, while the currently best bound is $O(q\sigma/2^n)$. In this work we show that this bound is tight by giving an attack with advantage $\Omega(q^2\ell/2^n)$. In the PMAC construction one initially XORs a mask to every message block, where the mask for the i-th block is computed as $\tau_i := \gamma_i \cdot L$, where $L$ is a (secret) random value, and $\gamma_i$ is the i-th codeword of the Gray code. Our attack applies more generally to any sequence of $\gamma_{i}$’s which contains a large coset of a subgroup of $GF(2^n)$. We then investigate, if the security of PMAC can be further improved by using $\tau_{i}$’s that are $k$-wise independent, for $k > 1$ (the original distribution is only 1-wise independent). We observe that the security of PMAC will not increase in general, even if the masks are chosen from a 2-wise independent distribution, and then prove that the security increases to $O(q^2/2^n)$, if the $\tau_i$'s are 4-wise independent. Due to simple extension attacks, this is the best bound one can hope for, using any distribution on the masks. Whether 3-wise independence is already sufficient to get this level of security is left as an open problem.

Authenticated encryption schemes in practice have to be robust against adversaries that have access to various types of leakage, for instance decryption leakage on invalid ciphertext (protocol leakage), or leakage on the underlying primitives (side channel leakage). Our work includes several novel contributions: we augment the notion of nonce-base authenticated encryption with the notion of continuous leakage and we prove composition results in the face of protocol and side channel leakage. Moreover, we show how to achieve authenticated encryption that is simultaneously both misuse resistant and leakage resilient, based on a sufficiently leakage resilient PRF, and finally we propose a concrete, pairing-based instantiation of the latter.

This paper reports on the number field sieve computation of a 768-bit prime field discrete logarithm, describes the different parameter optimizations and resulting algorithmic changes compared to the factorization of a 768-bit RSA modulus, and briefly discusses the cryptologic relevance of the result.

In this paper, we construct {\em subring homomorphic encryption} scheme that is a homomorphic encryption scheme build on the decomposition ring, which is a subring of cyclotomic ring. In the scheme, each plaintext slot contains an integer in $\mathbb{Z}_{p^l}$, rather than an element of $\mathrm{GF}(p^d)$ as in conventional homomorphic encryption schemes on cyclotomic rings. Our benchmark results indicate that the subring homomorphic encryption scheme is several times faster than HElib {\em for mod-$p^l$ plaintexts}, due to its high parallelism of mod-$p^l$ slot structure. We believe in that the plaintext structure composed of mod-$p^l$ slots will be more natural, easy to handle, and significantly more efficient for many applications such as outsourced data mining.

Fully homomorphic encryption over the integers (FHE-OI) is currently the only alternative to lattice-based FHE. FHE-OI includes a family of schemes whose security is based on the hardness of different variants of the approximate greatest common divisor (AGCD) problem. A lot of effort was made to port techniques from second generation lattice-based FHE (using tensoring) to FHE-OI. Gentry, Sahai and Waters (Crypto 13) showed that third generation techniques (which were later formalized using the ``gadget matrix'') can also be ported.

However, the majority of these works was based on the noise-free variant of AGCD which is potentially weaker than the general one. In particular, the noise-free variant relies on the hardness of factoring and is thus vulnerable to quantum attacks.

In this work, we propose a comprehensive study of applying third generation FHE techniques to the regime of FHE-OI. We present and analyze a third generation FHE-OI based on decisional AGCD without the noise-free assumption. We proceed to showing a batch version of our scheme where each ciphertext can encode a vector of messages and operations are performed coordinate-wise. We use a similar AGCD variant to Cheon et al.~(Eurocrypt 13) who suggested the batch approach for second generation FHE, but we do not require the noise-free component or a subset sum assumption. However, like Cheon et al., we do require circular security for our scheme, even for bounded homomorphism. Lastly, we discuss some of the obstacles towards efficient implementation of our schemes and discuss a number of possible optimizations.

We introduce a new type of Montgomery-like square root formulae in $GF(2^m)$ defined by an arbitrary irreducible trinomial, which is more efficient compared with classic square root operation. By choosing proper Montgomery factor for different kind of trinomials, the space and time complexities of such square root computations match or outperform the best results. A practical application of the Montgomery-like square root in inversion computation is also presented.

The problem of Byzantine Broadcast (BB) and Byzantine Agreement (BA) are of interest to both distributed computing and cryptography community. Often, these primitives require prohibitive communication and round complexity. The extension protocols have been introduced to handle long messages at the cost of small number of broadcasts for bit. The latter are referred to as seed broadcasts and the number of rounds in which seed broadcasts are invoked in an extension protocol denotes the {\em seed round complexity} of the protocol.

In a setting with $n$ parties and an adversary controlling at most $t$ parties in Byzantine fashion, we present BB and BA extension protocols with and without trusted set-up assumption that are simultaneously optimal in multiple complexity measures. The best communication that an extension protocol can achieve in any setting is $\O(\ell n)$ bits for a message of length $\ell$ bits. The best achievable seed round complexity is one. The best achievable round complexity is $\O(n)$ for the setting $t< n$ and constant otherwise. We now summarize our results below:

\begin{description} \item[--] {\em Without set-up assumption}: In this setting $t<n/3$ is necessary. We present the first extension protocol that is simultaneously communication, round and seed round optimal. Both the round complexity and seed round complexity of the best known communication optimal extension protocol in this setting is $\Omega(n^3)$ that is neither round optimal nor seed round optimal. \item[--] {\em With set-up assumption}: With $t< n/2$, we present the first extension protocol that is simultaneously communication, round and seed round optimal. The round complexity and the seed round complexity of the best known protocol in this setting, though constant, are more than that of our protocol. In the most challenging setting of $t<n$, we present the first extension protocol that is simultaneously communication and round optimal. The best known protocol in this setting is only communication optimal. \end{description}

We propose a new approach for practical secure two-party computation (2PC) achieving security in the presence of malicious adversaries. Given a program to compute, the idea is to identify subcomputations that depend on only one or neither of the parties’ private inputs. Such computations can be secured at significantly lower cost, using different protocol paradigms for each case. We then show how to securely connect these subprotocols together, and with standard 2PC yielding our new approach for 2PC for mixed programs. Our empirical evaluations confirm that the mixed-2PC approach outperforms state-of-the-art monolithic 2PC protocols for most computations.

We introduce a new, simple and non-interactive complexity assumption for cryptographic hash functions, which seems very reasonable for standard functions like SHA-3. We describe how this assumption can be leveraged to obtain standard-model constructions that previously seemed to require a programmable random oracle: a generic construction of identity-based key encapsulation (ID-KEM) with full adaptive security from a scheme with very weak security ("selective and non-adaptive chosen-ID security"), a similar generic construction for digital signatures, and the first constructions of ID-KEMs and signatures over bilinear groups, where a ciphertext or signature consists of only a single group element and which achieve full adaptive security without random oracles.

Continuous collision resistance can be viewed as a way to realize certain potential applications of \emph{extremely lossy functions} (ELFs; Zhandry, CRYPTO 2016) with a standard cryptographic primitive. Furthermore, known ELF constructions had only "nearly black-box" security proofs, because the reduction was assumed to "know" sufficiently close approximations of the running time and success probability of a given adversary. In contrast, our constructions allow for full black-box security proofs without this requirement. The main drawback of our schemes, from a practical perspective, is that the reductions in the security proof are very non-tight, and some are based on strong "q-type" assumptions. Therefore our results are mainly of conceptual interest, but not yet suitable for practical deployment.

The Extended Access Control (EAC) protocol allows to create a shared cryptographic key between a client and a server. It is for instance referenced by the International Civil Aviation Organization for securing the communication between machine readable travel documents and terminals, and is also deployed on current German identity cards. Here we discuss how to enhance the EAC protocol by a so-called zero-round trip time (0RTT) mode. Through this mode the client can, without further interaction, immediately derive a new key from cryptographic material exchanged in previous executions. This makes the 0RTT mode attractive from an efficiency viewpoint such that the upcoming TLS 1.3 standard, for instance, will include its own 0RTT mode. Here we show that the EAC protocol can be augmented to support a 0RTT mode, too. Our proposed EAC+0RTT protocol is compliant with the basic EAC protocol and adds the 0RTT mode smoothly on top. We also prove the security of our proposal according to the common security model of Bellare and Rogaway in the multi-stage setting.

In this paper, we put forward the first adaptively secure recipient revocable broadcast encryption (RR-BE) scheme in the standard model. The scheme is adaptively secure against chosen plaintext attack (CPA) under the q-weaker Decisional Augmented Bilinear Diffie-Hellman Exponent (q-wDABDHE) assumption. Our scheme compares well with the only existing RR-BE scheme of Susilo et al. which is selectively secure in the random oracle model. More interestingly, achieving adaptive security in the standard model does not blow up the communication cost in our construction. To be more precise, the size of the ciphertext which is broadcasted by the broadcaster is constant.