### Symbolic Encryption with Pseudorandom Keys

IACR Eprint - Fri, 02/23/2018 - 12:08
We give an efficient decision procedure that, on input two (acyclic) cryptographic expressions making arbitrary use of an encryption scheme and a (length doubling) pseudorandom generator, determines (in polynomial time) if the two expressions produce computationally indistinguishable distributions for any pseudorandom generator and encryption scheme satisfying the standard security notions of pseudorandomness and indistinguishability under chosen plaintext attack. The procedure works by mapping each expression to a symbolic pattern that captures, in a fully abstract way, the information revealed by the expression to a computationally bounded observer. We then prove that if any two (possibly cyclic) expressions are mapped to the same pattern, then the associated distributions are indistinguishable. At the same time, if the expressions are mapped to different symbolic patterns and do not contain encryption cycles, there are secure pseudorandom generators and encryption schemes for which the two distributions can be distinguished with overwhelming advantage.

### Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing

IACR Eprint - Fri, 02/23/2018 - 10:24
Recently, it was shown that angular locality-sensitive hashing (LSH) can be used to significantly speed up lattice sieving, leading to a heuristic time complexity for solving the shortest vector problem (SVP) of $2^{0.337n + o(n)}$ (and space complexity $2^{0.208n + o(n)}$. We study the possibility of applying other LSH methods to sieving, and show that with the spherical LSH method of Andoni et al.\ we can heuristically solve SVP in time $2^{0.298n + o(n)}$ and space $2^{0.208n + o(n)}$. We further show that a practical variant of the resulting SphereSieve is very similar to Wang et al.'s two-level sieve, with the key difference that we impose an order on the outer list of centers.

### Efficient (ideal) lattice sieving using cross-polytope LSH

IACR Eprint - Fri, 02/23/2018 - 10:21
Combining the efficient cross-polytope locality-sensitive hash family of Terasawa and Tanaka with the heuristic lattice sieve algorithm of Micciancio and Voulgaris, we show how to obtain heuristic and practical speedups for solving the shortest vector problem (SVP) on both arbitrary and ideal lattices. In both cases, the asymptotic time complexity for solving SVP in dimension n is 2^(0.298n). For any lattice, hashes can be computed in polynomial time, which makes our CPSieve algorithm much more practical than the SphereSieve of Laarhoven and De Weger, while the better asymptotic complexities imply that this algorithm will outperform the GaussSieve of Micciancio and Voulgaris and the HashSieve of Laarhoven in moderate dimensions as well. We performed tests to show this improvement in practice. For ideal lattices, by observing that the hash of a shifted vector is a shift of the hash value of the original vector and constructing rerandomization matrices which preserve this property, we obtain not only a linear decrease in the space complexity, but also a linear speedup of the overall algorithm. We demonstrate the practicability of our cross-polytope ideal lattice sieve IdealCPSieve by applying the algorithm to cyclotomic ideal lattices from the ideal SVP challenge and to lattices which appear in the cryptanalysis of NTRU.

### A Parallel Variant of LDSieve for the SVP on Lattices

IACR Eprint - Fri, 02/23/2018 - 10:18
In this paper, we propose a parallel implementation of LDSieve, a recently published sieving algorithm for the SVP, which achieves the best theoretical complexity to this day, on parallel shared-memory systems. In particular, we propose a scalable parallel variant of LDSieve that is probabilistically lock-free and relaxes the properties of the algorithm to favour parallelism. We use our parallel variant of LDSieve to answer a number of important questions pertaining to the algorithm. In particular, we show that LDSieve scales fairly well on sharedmemory systems and uses much less memory than HashSieve on random lattices, for the same or even less execution time.

### Multivariate Profiling of Hulls for Linear Cryptanalysis

IACR Eprint - Fri, 02/23/2018 - 05:27
Extensions of linear cryptanalysis making use of multiple approximations, such as multiple and multidimensional linear cryptanalysis, are an important tool in symmetric-key cryptanalysis, among others being responsible for the best known attacks on ciphers such as Serpent and PRESENT. At CRYPTO 2015, Huang et al. provided a refined analysis of the key-dependent capacity leading to a refined key equivalence hypothesis, however at the cost of additional assumptions. Their analysis was extended by Blondeau and Nyberg to also cover an updated wrong key randomization hypothesis, using similar assumptions. However, a recent result by Nyberg shows the equivalence of linear dependence and statistical dependence of linear approximations, which essentially invalidates a crucial assumption on which all these multidimensional models are based. In this paper, we develop a model for linear cryptanalysis using multiple linearly independent approximations which takes key-dependence into account and complies with Nyberg's result. Our model considers an arbitrary multivariate joint distribution of the correlations, and in particular avoids any assumptions regarding normality. The analysis of this distribution is then tailored to concrete ciphers in a practically feasible way by combining a signal/noise decomposition approach for the linear hulls with a profiling of the actual multivariate distribution of the signal correlations for a large number of keys, thereby entirely avoiding assumptions regarding the shape of this distribution. As an application of our model, we provide an attack on 26 rounds of PRESENT which is faster and requires less data than previous attacks, while using more realistic assumptions and far fewer approximations. We successfully extend the attack to present the first 27-round attack which takes key-dependence into account.

### Information-theoretic Indistinguishability via the Chi-squared Method

IACR Eprint - Thu, 02/22/2018 - 12:28
Proving tight bounds on information-theoretic indistinguishability is a central problem in symmetric cryptography. This paper introduces a new method for information-theoretic indistinguishability proofs, called the chi-squared method''. At its core, the method requires upper-bounds on the so-called $\chi^2$ divergence (due to Neyman and Pearson) between the output distributions of two systems being queries. The method morally resembles, yet also considerably simplifies, a previous approach proposed by Bellare and Impagliazzo (ePrint, 1999), while at the same time increasing its expressiveness and delivering tighter bounds. We showcase the chi-squared method on some examples. In particular: (1) We prove an optimal bound of $q/2^n$ for the XOR of two permutations, and our proof considerably simplifies previous approaches using the $H$-coefficient method, (2) we provide improved bounds for the recently proposed encrypted Davies-Meyer PRF construction by Cogliati and Seurin (CRYPTO '16), and (3) we give a tighter bound for the Swap-or-not cipher by Hoang, Morris, and Rogaway (CRYPTO '12).

### Hidden in Plain Sight: Storing and Managing Secrets on a Public Ledger

IACR Eprint - Thu, 02/22/2018 - 12:15
Current blockchain systems are incapable of holding sensitive data securely on their public ledger while supporting accountability of data access requests and revocability of data access rights. Instead, they either keep the sensitive data off-chain as a semi-centralized solution or they just publish the data on the ledger ignoring the problem altogether. In this work, we introduce SCARAB the first secure decentralized access control mechanism for blockchain systems that addresses the challenges of accountability, by publicly logging each request before granting data access, and of revocability, by introducing collectively managed data access policies. SCARAB introduces, therefore, on-chain secrets, which utilize verifiable secret sharing to enable collectively managed secrets under a Byzantine adversary, and identity skipchains, which enable the dynamic management of identities and of access control policies. The evaluation of our SCARAB implementation shows that the latency of a single read/write request scales linearly with the number of access-securing trustees and is in the range of 200 ms to 8 seconds for 16 to 128 trustees.

### Efficient MPC from Syndrome Decoding (or: Honey, I Shrunk the Keys)

IACR Eprint - Thu, 02/22/2018 - 12:13
We present a new approach to designing concretely efficient MPC protocols with semi-honest security in the dishonest majority setting. Motivated by the fact that within the dishonest majority setting the efficiency of most practical protocols \emph{does not depend on the number of honest parties}, we investigate how to construct protocols which improve in efficiency as the number of honest parties increases. Our central idea is to take a protocol which is secure for $n-1$ corruptions and modify it to use short symmetric keys, with the aim of basing security on the concatenation of all honest parties' keys. This results in a more efficient protocol tolerating fewer corruptions, whilst also introducing an LPN-style syndrome decoding assumption. We first apply this technique to a modified version of the semi-honest GMW protocol, using OT extension with short keys, to improve the efficiency of standard GMW with fewer corruptions. We also obtain more efficient constant-round MPC, using BMR-style garbled circuits with short keys, and present an implementation of the online phase of this protocol. Our techniques start to improve upon existing protocols when there are around $n=20$ parties with $h=6$ honest parties, and as these increase we obtain up to a 13 times reduction (for $n=400,h=120$) in communication complexity for our GMW variant, compared with the best-known GMW-based protocol modified to use the same threshold.

### Non-Malleable Codes for Small-Depth Circuits

IACR Eprint - Thu, 02/22/2018 - 12:13
We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial size (i.e.~$\mathsf{AC^0}$ tampering functions), our codes have codeword length $n = k^{1+o(1)}$ for a $k$-bit message. This is an exponential improvement of the previous best construction due to Chattopadhyay and Li (STOC 2017), which had codeword length $2^{O(\sqrt{k})}$. Our construction remains efficient for circuit depths as large as $\Theta(\log(n)/\log\log(n))$ (indeed, our codeword length remains $n\leq k^{1+\epsilon})$, and extending our result beyond this would require separating $\mathsf{P}$ from $\mathsf{NC^1}$. We obtain our codes via a new efficient non-malleable reduction from small-depth tampering to split-state tampering. A novel aspect of our work is the incorporation of techniques from unconditional derandomization into the framework of non-malleable reductions. In particular, a key ingredient in our analysis is a recent pseudorandom switching lemma of Trevisan and Xue (CCC 2013), a derandomization of the influential switching lemma from circuit complexity; the randomness-efficiency of this switching lemma translates into the rate-efficiency of our codes via our non-malleable reduction.

### Reading in the Dark: Classifying Encrypted Digits with Functional Encryption

IACR Eprint - Thu, 02/22/2018 - 12:11
As machine learning grows into a ubiquitous technology that finds many interesting applications, the privacy of data is becoming a major concern. This paper deals with machine learning and encrypted data. Namely, our contribution is twofold: we first build a new Functional Encryption scheme for quadratic multi-variate polynomials, which outperforms previous schemes. It enables the efficient computation of quadratic polynomials on encrypted vectors, so that only the result is in clear. We then turn to quadratic networks, a class of machine learning models, and show that their design makes them particularly suited to our encryption scheme. This synergy yields a technique for efficiently recovering a plaintext classification of encrypted data. Eventually, we prototype our construction and run it on the MNIST dataset to demonstrate practical relevance. We obtain 97.54% accuracy, with decryption and encryption taking few seconds.

### Static-Memory-Hard Functions and Nonlinear Space-Time Tradeoffs via Pebbling

IACR Eprint - Thu, 02/22/2018 - 12:01
Pebble games were originally formulated to study time-space tradeoffs in computation, modeled by games played on directed acyclic graphs (DAGs). Close connections between pebbling and cryptography have been known for decades. A series of recent research starting with (Alwen and Serbinenko, STOC 2015) has deepened our understanding of the notion of memory-hardness in cryptography --- a useful property of hash functions for deterring large-scale password-cracking attacks --- and has shown memory-hardness to have intricate connections with the theory of graph pebbling. Definitions of memory-hardness are not yet unified in this somewhat nascent field, however, and the guarantees proven are with respect to a range of proposed definitions. In this work, we improve upon two main limitations of existing models of memory-hardness. First, existing measures of memory-hardness only account for dynamic (i.e., runtime) memory usage, and do not consider static memory usage. We propose a new definition of static-memory-hard function (SHF) which takes into account static memory usage and allows the formalization of larger memory requirements for efficient functions, than in the dynamic setting (where memory usage is inherently bounded by runtime). We then give two SHF constructions based on pebbling; to prove static-memory-hardness, we define a new pebble game (black-magic pebble game''), and new graph constructions with optimal complexity under our proposed measure. Secondly, existing memory-hardness models implicitly consider linear tradeoffs between the costs of time and space. We propose a new model to capture nonlinear time-space trade-offs and prove that nonlinear tradeoffs can in fact cause adversaries to employ different strategies from linear tradeoffs. Finally, as an additional contribution of independent interest, we present the first asymptotically tight graph construction that achieves the best possible space complexity up to loglogn-factors for an existing memory-hardness measure called cumulative complexity.

### Short Non-Malleable Codes from Related-Key Secure Block Ciphers

IACR Eprint - Thu, 02/22/2018 - 12:00
A non-malleable code is an unkeyed randomized encoding scheme that offers the strong guarantee that decoding a tampered codeword either results in the original message, or in an unrelated message. We consider the simplest possible construction in the computational split-state model, which simply encodes a message $m$ as $k||E_k(m)$ for a uniformly random key $k$, where $E$ is a block cipher. This construction is comparable to, but greatly simplifies over, the one of Kiayias et al. (ACM CCS 2016), who eschewed this simple scheme in fear of related-key attacks on $E$. In this work, we prove this construction to be a strong non-malleable code as long as $E$ is: (i) a pseudorandom permutation under leakage and (ii) related-key secure with respect to an arbitrary but fixed key relation. Both properties are believed to hold for "good" block ciphers, such as AES-128, making this non-malleable code very efficient with short codewords of length $|m| + 2\tau$ (where $\tau$ is the security parameter, e.g., 128 bits), without significant security penalty.

### Impeccable Circuits

IACR Eprint - Thu, 02/22/2018 - 11:55
Active physical attacks pose a serious threat to cryptographic hardware, i.e., by injecting faults during the computation. The tools to inject such faults have evolved over the last years and are becoming increasingly powerful. A promising approach to thwart this type of attacks is employing Concurrent Error Detection (CED) schemes. They are usually based on an Error-Detecting Code (EDC) which provides the capability to detect certain injected faults. Depending on the assumed adversary model, the potency of the CED scheme can be adapted during the design phase by adjusting the underlying code. In this work, we propose a methodology to enable a correct, practical, and robust implementation of code-based CED schemes. Indeed, we show that a straightforward hardware implementation of a given code-based CED scheme very likely suffers from severe vulnerabilities and does not provide the desired level of protection against fault attacks. In particular, the propagation of faults into the combinatorial logic is often not considered in the security evaluation of these schemes. First, we formally define this detrimental effect and demonstrate its impact on the security of common CED schemes. Second, we introduce an implementation strategy to limit the negative effect of fault propagation. Third, in contrast to many other works where the fault coverage of an implementation equipped with an EDC is considered, we present a detailed implementation strategy which - based on the specification of the underlying EDC - can guarantee (i.e., 100% coverage rate) the detection of any fault. Fitting to the defined adversary model, this holds for any time of the computation and any location of the circuit - both in the data processing and in the control part. In short, we provide practical guidelines how to construct efficient CED schemes with arbitrary EDCs to achieve the desired level of protection against fault attacks. We evaluate the efficiency of our methodology in a case study considering several symmetric block ciphers (i.e., PRESENT, Skinny, Midori, GIFT, LED, and SIMON) for different design architectures and various linear EDCs with different fault detection capabilities.

### Doing Real Work with FHE: The Case of Logistic Regression

IACR Eprint - Thu, 02/22/2018 - 11:54
We describe our recent experience, building a system that uses fully-homomorphic encryption (FHE) to approximate the coefficients of a logistic-regression model, built from genomic data. The aim of this project was to examine the feasibility of a solution that operates "deep within the bootstrapping regime," solving a problem that appears too hard to be addressed just with somewhat-homomorphic encryption. As part of this project, we implemented optimized versions of many "bread and butter" FHE tools. These tools include binary arithmetic, comparisons, partial sorting, and low-precision approximation of "complicated functions" such as reciprocals and logarithms. Our eventual solution can handle thousands of records and hundreds of fields, and it takes a few hours to run. To achieve this performance we had to be extremely frugal with expensive bootstrapping and data-movement operations. We believe that our experience in this project could server as a guide for what is or is not currently feasible to do with fully-homomorphic encryption.

### Efficient Parallel Binary Operations on Homomorphic Encrypted Real Numbers

IACR Eprint - Thu, 02/22/2018 - 11:52
A number of homomorphic encryption application areas, such as privacy-preserving machine learning analysis in the cloud, could be better enabled if there existed a general solution for combining sufficiently expressive logical and numerical circuit primitives to form higher-level algorithms relevant to the application domain. Logical primitives are more efficient in a binary plaintext message space, whereas numeric primitives favour a word-based message space before encryption. In a step closer to an overall strategy of combining logical and numeric operation types, this paper examines accelerating binary operations on real numbers suitable for somewhat homomorphic encryption. A parallel solution based on SIMD can be used to efficiently perform addition, subtraction and comparison operations in a single step. The result maximises computational efficiency, memory space usage and minimises multiplicative circuit depth. Performance of these primitives and their application in min-max and sorting operations are demonstrated. In sorting real numbers, a speed up of 25-30 times is observed.

### Hermes. A framework for cryptographically assured access control and data security

IACR Eprint - Thu, 02/22/2018 - 11:51
This paper presents Hermes – a practical data security scheme with a reference implementation, which enables distributed sharing and collaboration, enforcing access control with the help of cryptographic methods (public key cryptography and traditional symmetric cryptography).

### Bloom Filter Encryption and Applications to Efficient Forward-Secret 0-RTT Key Exchange

IACR Eprint - Thu, 02/22/2018 - 11:48
Forward secrecy is considered an essential design goal of modern key establishment (KE) protocols, such as TLS 1.3, for example. Furthermore, efficiency considerations such as zero round-trip time (0-RTT), where a client is able to send cryptographically protected payload data along with the very first KE message, are motivated by the practical demand for secure low-latency communication. For a long time, it was unclear whether protocols that simultaneously achieve 0-RTT and full forward secrecy exist. Only recently, the first forward-secret 0-RTT protocol was described by Günther et al. (Eurocrypt 2017). It is based on Puncturable Encryption. Forward secrecy is achieved by "puncturing" the secret key after each decryption operation, such that a given ciphertext can only be decrypted once (cf. also Green and Miers, S&P 2015). Unfortunately, their scheme is completely impractical, since one puncturing operation takes between 30 seconds and several minutes for reasonable security and deployment parameters, such that this solution is only a first feasibility result, but not efficient enough to be deployed in practice. In this paper, we introduce a new primitive that we term Bloom Filter Encryption (BFE), which is derived from the probabilistic Bloom filter data structure. We describe different constructions of BFE schemes, and show how these yield new puncturable encryption mechanisms with extremely efficient puncturing. Most importantly, a puncturing operation only involves a small number of very efficient computations, plus the deletion of certain parts of the secret key, which outperforms previous constructions by orders of magnitude. This gives rise to the first forward-secret 0-RTT protocols that are efficient enough to be deployed in practice. We believe that BFE will find applications beyond forward-secret 0-RTT protocols.

### A Key-recovery Attack on 855-round Trivium

IACR Eprint - Thu, 02/22/2018 - 11:45
In this paper, we propose a key-recovery attack on Trivium reduced to 855 rounds. As the output is a complex Boolean polynomial over secret key and IV bits and it is hard to find the solution of the secret keys, we propose a novel nullification technique of the Boolean polynomial to reduce the output Boolean polynomial of 855-round Trivium. Then we determine the degree upper bound of the reduced nonlinear boolean polynomial and detect the right keys. These techniques can be applicable to most stream ciphers based on nonlinear feedback shift registers (NFSR). Our attack on $855$-round Trivium costs time complexity $2^{77}$. As far as we know, this is the best key-recovery attack on round-reduced Trivium. To verify our attack, we also give some experimental data on 721-round reduced Trivium.

### Green Mining: toward a less energetic impact of cryptocurrencies

IACR Eprint - Thu, 02/22/2018 - 11:45
While cryptocurrencies continue to gain popularity, their energy cost is increasingly becoming unsustainable. In this paper, we present an innovative scheme which eliminates the burden of the proof of work which is the main cause of the energy waste in cryptocurrencies such as Bitcoin. The scheme is based on a green leader election scheme which guarantees a bounded average number of simultaneous mining whatever the size of the population in competition.

### Non-Profiled Deep Learning-Based Side-Channel Attacks

IACR Eprint - Thu, 02/22/2018 - 11:44
Deep Learning has recently been introduced as a new alternative to perform Side-Channel analysis. Until now, studies have been focused on applying Deep Learning techniques to perform Profiled Side-Channel attacks where an attacker has a full control of a profiling device and is able to collect a large amount of traces for different key values in order to characterize the device leakage prior to the attack. In this paper we introduce a new method to apply Deep Learning techniques in a Non-Profiled context, where an attacker can only collect a limited number of side-channel traces for a fixed unknown key value from a closed device. We show that by combining key guesses with observations of Deep Learning metrics, it is possible to recover information about the secret key. The main interest of this method, is that it is possible to use the power of Deep Learning and Neural Networks in a Non-Profiled scenario. We show that it is possible to exploit the translation-invariance property of Convolutional Neural Networks against de-synchronized traces and use Data Augmentation techniques also during Non-Profiled side-channel attacks. Additionally, the present work shows that in some conditions, this method can outperform classic Non-Profiled attacks as Correlation Power Analysis. We also highlight that it is possible to target masked implementations without leakages combination pre-preprocessing and with less assumptions than classic high-order attacks. To illustrate these properties, we present a series of experiments performed on simulated data and real traces collected from the ChipWhisperer board and from the ASCAD database. The results of our experiments demonstrate the interests of this new method and show that this attack can be performed in practice.