Updated: 3 hours 6 min ago

### Attacks and Countermeasures for White-box Designs

Wed, 11/07/2018 - 12:00

### Untagging Tor: A Formal Treatment of Onion Encryption

Tue, 11/06/2018 - 13:11
Tor is a primary tool for maintaining anonymity online. It provides a low-latency, circuit-based, bidirectional secure channel between two parties through a network of onion routers, with the aim of obscuring exactly who is talking to whom, even to adversaries controlling part of the network. Tor relies heavily on cryptographic techniques, yet its onion encryption scheme is susceptible to tagging attacks (Fu and Ling, 2009), which allow an active adversary controlling the first and last node of a circuit to deanonymize with near-certainty. This contrasts with less active traffic correlation attacks, where the same adversary can at best deanonymize with high probability. The Tor project has been actively looking to defend against tagging attacks and its most concrete alternative is proposal 261, which specifies a new onion encryption scheme based on a variable-input-length tweakable cipher. We provide a formal treatment of low-latency, circuit-based onion encryption, relaxed to the unidirectional setting, by expanding existing secure channel notions to the new setting and introducing circuit hiding to capture the anonymity aspect of Tor. We demonstrate that circuit hiding prevents tagging attacks and show proposal 261's relay protocol is circuit hiding and thus resistant against tagging attacks.

### Port Contention for Fun and Profit

Tue, 11/06/2018 - 13:07
Simultaneous Multithreading (SMT) architectures are attractive targets for side-channel enabled attackers, with their inherently broader attack surface that exposes more per physical core microarchitecture components than cross-core attacks. In this work, we explore SMT execution engine sharing as a side-channel leakage source. We target ports to stacks of execution units to create a high-resolution timing side-channel due to port contention, inherently stealthy since it does not depend on the memory subsystem like other cache or TLB based attacks. Implementing said channel on Intel Skylake and Kaby Lake architectures featuring Hyper-Threading, we mount and end-to-end attack that recovers a P-384 private key from an OpenSSL-powered TLS server using a small number of repeated TLS handshake attempts. Furthermore, we show that traces targeting shared libraries, static builds, and SGX enclaves are essentially identical, hence our channel has wide target application.

### A Certain Family of Subgroups of $\mathbb Z_n^\star$ Is Weakly Pseudo-Free under the General Integer Factoring Intractability Assumption

Tue, 11/06/2018 - 10:57
Let $\mathbb G_n$ be the subgroup of elements of odd order in the group $\mathbb Z_n^\star$ and let $\mathcal U(\mathbb G_n)$ be the uniform probability distribution on $\mathbb G_n$. In this paper, we establish a probabilistic polynomial-time reduction from finding a nontrivial divisor of a composite number $n$ to finding a nontrivial relation between $l$ elements chosen independently and uniformly at random from $\mathbb G_n$, where $l\ge1$ is given in unary as a part of the input. Assume that finding a nontrivial divisor of a random number in some set $N$ of composite numbers (for a given security parameter) is a computationally hard problem. Then, using the above-mentioned reduction, we prove that the family $\{(\mathbb G_n,\mathcal U(\mathbb G_n))\}_{n\in N}$ of computational abelian groups is weakly pseudo-free. The disadvantage of this result is that the probability ensemble $\{\mathcal U(\mathbb G_n)\}_{n\in N}$ is not polynomial-time samplable. To overcome this disadvantage, we construct a polynomial-time computable function $\nu\colon D\to N$ (where $D\subseteq\{0,1\}^*$) and a polynomial-time samplable probability ensemble $\{\mathcal G_d\}_{d\in D}$ (where $\mathcal G_d$ is a distribution on $\mathbb G_{\nu(d)}$ for each $d\in D$) such that the family $\{(\mathbb G_{\nu(d)},\mathcal G_d)\}_{d\in D}$ of computational abelian groups is weakly pseudo-free.

### New Perspectives on Zero-Knowledge Multi-Prover Interactive Proofs

Mon, 11/05/2018 - 23:21
In multi-prover interactive proofs (MIPs), the verifier can provide non-local resources for the provers intrinsically. In most cases, this is undesirable. Existing proofs of soundness do not account for the verifier's non-local potential. We show that this may be a problem for many MIPs. We provide a solution by constructing a generalization of the MIP model, of which standard MIPs are a special case. This new model accounts for both the prover and the verifier's non-local correlations. A new property of multi-prover zero-knowledge naturally emerges as a result.

### Indistinguishability Obfuscation Without Multilinear Maps: iO from LWE, Bilinear Maps, and Weak Pseudorandomness

Mon, 11/05/2018 - 17:16
The existence of secure indistinguishability obfuscators (iO) has far-reaching implications, significantly expanding the scope of problems amenable to cryptographic study. All known approaches to constructing iO rely on \emph{$d$-linear maps} which allow the encoding of elements from a large domain, evaluating degree $d$ polynomials on them, and testing if the output is zero. While secure \emph{bilinear maps} are well established in cryptographic literature, the security of candidates for $d>2$ is poorly understood. We propose a new approach to constructing iO for general circuits. Unlike all previously known realizations of iO, we avoid the use of $d$-linear maps of degree $d \ge 3$. At the heart of our approach is the assumption that a new \emph{weak} pseudorandom object exists, that we call a \emph{perturbation resilient generator} ($\Delta\mathsf{RG}$). Informally, a $\Delta\mathsf{RG}$ maps $n$ integers to $m$ integers, and has the property that for any sufficiently short vector $a \in \mathbb{Z}^m$, all efficient adversaries must fail to distinguish the distributions $\Delta\mathsf{RG}(s)$ and $\Delta\mathsf{RG}(s)+a$, with at least some probability that is inverse polynomial in the security parameter. $\Delta\mathsf{RG}s$ have further implementability requirements; most notably they must be computable by a family of degree-3 polynomials over $\mathbb{Z}$. We use techniques building upon the Dense Model Theorem to deal with adversaries that have nontrivial but non-overwhelming distinguishing advantage. In particular, we obtain a new security amplification theorem for functional encryption. As a result, we obtain iO for general circuits assuming: - Subexponentially secure LWE - Bilinear Maps - $poly(\lambda)$-secure 3-block-local PRGs - $(1-1/poly(\lambda))$-secure $\Delta\mathsf{RG}s$

### Faster key compression for isogeny-based cryptosystems

Mon, 11/05/2018 - 15:47
Supersingular isogeny-based cryptography is one of the more recent families of post-quantum proposals. An interesting feature is the comparatively low bandwidth occupation in key agreement protocols, which stems from the possibility of key compression. However, compression and decompression introduce a significant overhead to the overall processing cost despite recent progress. In this paper we address the main processing bottlenecks involved in key compression and decompression, and suggest substantial improvements for each of them. Some of our techniques may have an independent interest for other, more conventional areas of elliptic curve cryptography as well.

### Subversion-Resilient Signatures: Definitions, Constructions and Applications

Sat, 11/03/2018 - 09:36
We provide a formal treatment of security of digital signatures against subversion attacks (SAs). Our model of subversion generalizes previous work in several directions, and is inspired by the proliferation of software attacks (e.g., malware and buffer overflow attacks), and by the recent revelations of Edward Snowden about intelligence agencies trying to surreptitiously sabotage cryptographic algorithms. The main security requirement we put forward demands that a signature scheme should remain unforgeable even in the presence of an attacker applying SAs (within a certain class of allowed attacks) in a fully-adaptive and continuous fashion. Previous notions---e.g., the notion of security against algorithm-substitution attacks introduced by Bellare et al. (CRYPTO '14) for symmetric encryption---were non-adaptive and non-continuous. In this vein, we show both positive and negative results for the goal of constructing subversion-resilient signature schemes. Negative results. As our main negative result, we show that a broad class of randomized signature schemes is unavoidably insecure against SAs, even if using just a single bit of randomness. This improves upon earlier work that was only able to attack schemes with larger randomness space. When designing our new attack we consider undetectability as an explicit adversarial goal, meaning that the end-users (even the ones knowing the signing key) should not be able to detect that the signature scheme was subverted. Positive results. We complement the above negative results by showing that signature schemes with unique signatures are subversion-resilient against all attacks that meet a basic undetectability requirement. A similar result was shown by Bellare et al. for symmetric encryption, who proved the necessity to rely on stateful schemes; in contrast unique signatures are stateless, and in fact they are among the fastest and most established digital signatures available. As our second positive result, we show how to construct subversion-resilient identification schemes from subversion-resilient signature schemes. We finally show that it is possible to devise signature schemes secure against arbitrary tampering with the computation, by making use of an un-tamperable cryptographic reverse firewall (Mironov and Stephens-Davidowitz, EUROCRYPT '15), i.e., an algorithm that "sanitizes" any signature given as input (using only public information). The firewall we design allows to successfully protect so-called re-randomizable signature schemes (which include unique signatures as special case). As an additional contribution, we extend our model to consider multiple users and show implications and separations among the various notions we introduced. While our study is mainly theoretical, due to its strong practical motivation, we believe that our results have important implications in practice and might influence the way digital signature schemes are selected or adopted in standards and protocols.

### Quantum circuits for the CSIDH: optimizing quantum evaluation of isogenies

Fri, 11/02/2018 - 15:02
Choosing safe post-quantum parameters for the new CSIDH isogeny-based key-exchange system requires concrete analysis of the cost of quantum attacks. The two main contributions to attack cost are the number of queries in hidden-shift algorithms and the cost of each query. This paper analyzes algorithms for each query, introducing several new speedups while showing that some previous claims were too optimistic for the attacker. This paper includes a full computer-verified simulation of its main algorithm down to the bit-operation level.

### Ciphertext-Policy Attribute-Based Encrypted Data Equality Test and Classification

Fri, 11/02/2018 - 15:02
Thanks to the ease of access and low expenses, it is now popular for people to store data in cloud servers. To protect sensitive data from being leaked to the outside, people usually encrypt the data in the cloud. However, management of these encrypted data becomes a challenging problem, e.g. data classification. Besides, how to selectively share data with other users is also an important and interesting problem in cloud storage. In this paper, we focus on ciphertext-policy attribute based encryption with equality test (CP-ABEET). People can use CP-ABEET to implement not only flexible authorization for the access to encrypted data, but also efficient data label classification, i.e. test of whether two encrypted data contain the same message. We construct an efficient CP-ABEET scheme, and prove its security based on a reasonable number-theoretic assumption. Compared with the only existing CP-ABEET scheme, our construction is more efficient in key generation, and has shorter attribute-related secret keys and better security.

### On the Leakage Resilience of Ring-LWE Based Public Key Encryption

Fri, 11/02/2018 - 14:17
We consider the leakage resilience of the Ring-LWE analogue of the Dual-Regev encryption scheme (R-Dual-Regev for short), originally presented by Lyubashevsky et al.~(Eurocrypt '13). Specifically, we would like to determine whether the R-Dual-Regev encryption scheme remains IND-CPA secure, even in the case where an attacker leaks information about the secret key. We consider the setting where $R$ is the ring of integers of the $m$-th cyclotomic number field, for $m$ which is a power-of-two, and the Ring-LWE modulus is set to $q \equiv 1 \mod m$. This is the common setting used in practice and is desirable in terms of the efficiency and simplicity of the scheme. Unfortunately, in this setting $R_q$ is very far from being a field so standard techniques for proving leakage resilience in the general lattice setting, which rely on the leftover hash lemma, do not apply. Therefore, new techniques must be developed. In this work, we put forth a high-level approach for proving the leakage resilience of the R-Dual-Regev scheme, by generalizing the original proof of Lyubashevsky et al.~(Eurocrypt '13). We then give three instantiations of our approach, proving that the R-Dual-Regev remains IND-CPA secure in the presence of three natural, non-adaptive leakage classes.

### Security Analysis for Randomness Improvements for Security Protocols

Fri, 11/02/2018 - 14:00
Many cryptographic mechanisms depend on the availability of secure random numbers. In practice, the sources of random numbers can be unreliable for many reasons. There exist ways to improve the reliability of randomness, but these often do not work well with practical constraints. One proposal to reduce the impact of untrusted randomness is the proposal by Cremers et al. [draft-irtf-cfrg-randomness-improvements-03.txt], which aims to be effective in existing deployments.

### Multi-Key Homomorphic Signatures Unforgeable under Insider Corruption

Fri, 11/02/2018 - 08:18
Homomorphic signatures (HS) allows the derivation of the signature of the message-function pair $(m, g)$, where $m = g(m_1, \ldots, m_K)$, given the signatures of each of the input messages $m_k$ signed under the same key. Multi-key HS (M-HS) introduced by Fiore et al. (ASIACRYPT'16) further enhances the utility by allowing evaluation of signatures under different keys. While the unforgeability of existing M-HS notions unrealistically assumes that all signers are honest, we consider the setting where an arbitrary number of signers can be corrupted, which is typical in natural applications (e.g., verifiable multi-party computation) of M-HS. Surprisingly, there is a huge gap between M-HS with and without unforgeability under corruption: While the latter can be constructed from standard lattice assumptions (ASIACRYPT'16), we show that the former must rely on non-falsifiable assumptions. Specifically, we propose a generic construction of M-HS with unforgeability under corruption from adaptive zero-knowledge succinct non-interactive arguments of knowledge (ZK-SNARK) (and other standard assumptions), and then show that such M-HS implies adaptive zero-knowledge succinct non-interactive arguments (ZK-SNARG). Our results leave open the pressing question of what level of authenticity can be guaranteed in the multi-key setting under standard assumptions.

### A Key Leakage Preventive White-box Cryptographic Implementation

Fri, 11/02/2018 - 07:32
A white-box cryptographic implementation is to defend against white-box attacks that allow access and modification of memory or internal resources in the computing device. In particular, linear and non-linear transformations applied to this table-based cryptographic implementation are used to prevent key-dependent intermediate values from being seen by white-box attackers. However, it has been shown that there is a correlation before and after the linear and non-linear transformations so that even a gray-box attacker can reveal secret keys hidden in a white-box cryptographic implementation. In this paper, we focus on the problem of linear transformations including the characteristics of block invertible binary matrices and the distribution of intermediate values. Based on our observation, we find out that a random byte insertion in the intermediate values before linear transformations can eliminate a problematic correlation to the key, and propose our white-box AES implementation using this principle. Our proposed implementations reduce the memory requirement by at most 33 percent compared to the masked implementations and also slightly reduce the number of table lookups. In addition, our method is a non-masking technique and does not require a static or dynamic random source, unlike the existing gray-box (power analysis) countermeasures.

### Candidate Differing-Inputs Obfuscation from Indistinguishability Obfuscation and Auxiliary-Input Point Obfuscation

Fri, 11/02/2018 - 01:32
Differing-inputs obfuscation (diO), first proposed by Barak et. al. [4], provides stronger security than that provided by indistinguishability obfuscation (iO). An iO scheme provides indistinguishability between the obfuscations of two programs that are equivalent and have the same length of description. A diO scheme ensures that the obfuscations of two efficiently generated programs with the same description length are indistinguishable if it is hard to find an input on which their outputs differ. Ananth et. al. [1] showed the definition of diO with respect to arbitrary auxiliary inputs. However, Garg et al. [19] showed that the existence of this kind of diO contradicts a certain “special-purpose obfuscation” conjecture. Ishai, Pandey and Sahai [23] suggested a diO variant called public-coin diO, which requires the auxiliary input to be a public random string and given as input to all relevant algorithms. They gave a construction of public-coin diO by assuming the existence of public-coin differing-inputs obfuscator for NC^1 circuits. In this paper, we use a slightly different definition, called public-coin-dependent diO. It allows the obfuscation algorithm to additionally take as input the random coins used to sample the circuit pair (including the circuit to be obfuscated) and thus the obfuscation algorithm can use the property of the circuit pair. We first construct a public-coin differing-inputs obfuscator for a class of new defined function with iO and point obfuscation with auxiliary input (AIPO). And then we use it to complete the public-coin-dependent diO for any pair of circuits that are hard to be found an input on which their outputs differ. The constructions are based on secure iO schemes for NC^1, fully homomorphic encryption scheme, and the existence of AIPO. Besides, we show the applications of our constructions.

### The AlexNet Moment for Homomorphic Encryption: HCNN, the First Homomorphic CNN on Encrypted Data with GPUs

Thu, 11/01/2018 - 22:18
Fully homomorphic encryption, with its widely-known feature of computing on encrypted data, empowers a wide range of privacy-concerned cloud applications including deep learning as a service. This comes at a high cost since FHE includes highly-intensive computation that requires enormous computing power. Although the literature includes a number of proposals to run CNNs on encrypted data, the performance is still far from satisfactory. In this paper, we push the level up and show how to accelerate the performance of running CNNs on encrypted data using GPUs. We evaluated a CNN to classify homomorphically the MNIST dataset into 10 classes. We used a number of techniques such as low-precision training, unified training and testing network, optimized FHE parameters and a very efficient GPU implementation to achieve high performance. Our solution achieved high security level ($> 128$ bit) and high accuracy (99\%). In terms of performance, our best results show that we could classify the entire testing dataset in 14.105 seconds, with per-image amortized time (1.411 milliseconds) 40.41$\times$ faster than prior art.

### Efficient Multi-key FHE with short extended ciphertexts and less public parameters

Thu, 11/01/2018 - 22:10
Multi-Key Full Homomorphic Encryption scheme (MKFHE) can perform arbitrary operation on encrypted data under different public keys (users), and the final ciphertext can be jointly decrypted. Therefore, MKFHE has natural advantages and application value in security multi-party computation (MPC). For BGV-type MKFHE scheme, the amount of ciphertexts and keys are relatively large, and the process of generating evaluation keys is complicated. In this paper, we presented an efficient BGV-type MKFHE scheme with short extended ciphertexts and less public parameters. Firstly, we construct a nested ciphertext extension for BGV and separable ciphertext extension for GSW, which can reduce the amount of the extended ciphertext. Secondly, we construct a hybrid homomorphic multiplication between RBGV ciphertext and RGSW ciphertext, which can reduce the size of input ciphertext and improve the computational efficiency. Finally, the coefficient of user’s secret key is limited to $\{-1,0,1\}$, which can reduce the ciphertext size in key switching process. Comparing to CZW17 proposed in TCC17, analysis shows that the our scheme reduces the amount of ciphertext from $2k$ to $(k + 1)$, and the evaluation key generation materials are reduced from $\sum\nolimits_{l = 0}^L {24\beta _l^2}$ to $\sum\nolimits_{l = 0}^L {4{\beta _B} + 4{\beta _l}}$, and the amount of evaluation keys are reduced from $4{k^2}\beta _l^{}$ to ${(k + 1)^2}{\beta _B}$, where $k$ is the number of users participating in the homomorphic evaluations, $L$ is a bound on the circuit depth, ${\beta _l}$ and ${\beta _B}$ relatively denotes the bit length of modulus $q_l$ and the noise bound $B$. The reduction in the amount of data may lead to improvement in computational efficiency. Further more, the separable ciphertext extension for GSW can also be used in GSW-type MKFHE scheme such as CM15 to reduce the amount of ciphertext and improve the efficiency of homomorphic operations.

### Revisiting Single-server Algorithms for Outsourcing Modular Exponentiation

Thu, 11/01/2018 - 22:10
We investigate the problem of securely outsourcing modular exponentiations to a single, malicious computational resource. We revisit recently proposed schemes using single server and analyse them against two fundamental security properties, namely privacy of inputs and verifiability of outputs. Interestingly, we observe that the chosen schemes do not appear to meet both the security properties. In fact we present a simple polynomial-time attack on each algorithm, allowing the malicious server either to recover a secret input or to convincingly fool the client with wrong outputs. Then we provide a fix to the identified problem in the ExpSOS scheme. With our fix and without pre-processing, the improved scheme becomes the best to-date outsourcing scheme for single-server case. Finally we present the first precomputation-free single-server algorithm, \pi ExpSOS for simultaneous exponentiations.

### Verifiability Analysis of CHVote

Thu, 11/01/2018 - 22:07
This document details analyses of verifiability properties of the CH-Vote v1.3 electronic voting protocol, as defined by the preprint publication [12]. Informally, these properties are: • Individual verifiability: a voter is convinced that a ballot confirmed as coming from the voter contains his intended vote • Ballot verifiability: all ballots that are confirmed contain correct votes • Eligibility uniqueness: there are no two distinct entries in the list of confirmed ballots which correspond to the same voter • Confirmed as intended: if a confirmed ballot is on the bulletin board for some voter, then that ballot records that voter’s voting intention • Universal verifiability: any party can verify that the votes on this board were tallied correctly The analyses employ the currently well-established approach used within the scientific community. Specifically, they rely on mathematical abstractions for the adversary and for the system under analysis, as well as mathematical formulations of the properties to be established. Mathematical proofs are then used to establish that (under certain assumptions) the security properties hold. We provide two types of analysis (which differ in the level of abstraction at which they operate). Part I contains a pen-and-paper computational/cryptographic analysis. Part II describes an automated symbolic analysis. Broadly speaking, both the symbolic and the computational analyses conclude that CH-Vote satisfy the desired security properties under several assumptions. The assumptions include, for example, computational assumptions (which mathematical problems are assumed to be hard), trust assumptions (which parties, if any, are assumed to behave honestly and what are parties assume to know before they interact with the system). Besides the concrete mathematical statements the analyses led to a number of recommendations which aim to improve the security. Part III concludes with a number of recommendations which reflect assumptions made in the analyses and weaknesses that were identified. The recommendations also sum up the results of a (light) code review of the code available via GitHub 1 – commit 9b0e7c9fcd409, from April 2017.

### Lower Bounds for Differentially Private RAMs

Thu, 11/01/2018 - 22:06
In this work, we study privacy-preserving storage primitives that are suitable for use in data analysis on outsourced databases within the differential privacy framework. The goal in differentially private data analysis is to disclose global properties of a group without compromising any individual’s privacy. Typically, differentially private adversaries only ever learn global properties. For the case of outsourced databases, the adversary also views the patterns of access to data. Oblivious RAM (ORAM) can be used to hide access patterns but ORAM might be excessive as in some settings it could be sufficient to be compatible with differential privacy and only protect the privacy of individual accesses. We consider $(\epsilon, \delta)$-Differentially Private RAM, a weakening of ORAM that only protects individual operations and seems better suited for use in data analysis on outsourced databases. As differentially private RAM has weaker security than ORAM, there is hope that we can bypass the $\Omega(\log(n/c))$ bandwidth lower bounds for ORAM by Larsen and Nielsen [CRYPTO ’18] for storing an array of $n$ entries and a client with $c$ bits of memory. We answer in the negative and present an $\Omega(\log(n/c))$ bandwidth lower bound for privacy budgets of $\epsilon = O(1)$ and $\delta \le 1/3$. The information transfer technique used for ORAM lower bounds does not seem adaptable for use with the weaker security guarantees of differential privacy. Instead, we prove our lower bounds by adapting the chronogram technique to our setting. To our knowledge, this is the first work that uses the chronogram technique for lower bounds on privacy-preserving storage primitives.