Updated: 9 hours 16 min ago

### CAPA: The Spirit of Beaver against Physical Attacks

Mon, 06/11/2018 - 06:18
In this paper we introduce two things: On one hand we introduce the Tile-Probe-and-Fault model, a model generalising the wire-probe model of Ishai et al. extending it to cover both more realistic side-channel leakage scenarios on a chip and also to cover fault and combined attacks. Secondly we introduce CAPA: a combined Countermeasure Against Physical Attacks. Our countermeasure is motivated by our model, and aims to provide security against higher-order SCA, multiple-shot FA and combined attacks. The tile-probe-and-fault model leads one to naturally look (by analogy) at actively secure multi-party computation protocols. Indeed, CAPA draws much inspiration from the MPC protocol SPDZ. So as to demonstrate that the model, and the CAPA countermeasure, are not just theoretical constructions, but could also serve to build practical countermeasures, we present initial experiments of proof-of-concept designs using the CAPA methodology. Namely, a hardware implementation of the KATAN and AES block ciphers, as well as a software bitsliced AES S-box implementation. We demonstrate experimentally that the design can resist second-order DPA attacks, even when the attacker is presented with many hundreds of thousands of traces. In addition our proof-of-concept can also detect faults within our model with high probability in accordance to the methodology.

### Two-Round Multiparty Secure Computation Minimizing Public Key Operations

Mon, 06/11/2018 - 02:42
We show new constructions of semi-honest and malicious two-round multiparty secure computation protocols using only (a fixed) $\mathsf{poly}(n,\lambda)$ invocations of a two-round oblivious transfer protocol (which use expensive public-key operations) and $\mathsf{poly}(\lambda, |C|)$ cheaper one-way function calls, where $\lambda$ is the security parameter, $n$ is the number of parties, and $C$ is the circuit being computed. All previously known two-round multiparty secure computation protocols required $\mathsf{poly}(\lambda,|C|)$ expensive public-key operations.

### Privacy-Preserving Search of Similar Patients in Genomic Data

Sun, 06/10/2018 - 15:22
The growing availability of genomic data holds great promise for advancing medicine and research, but unlocking its full potential requires adequate methods for protecting the privacy of individuals whose genome data we use. One example of this tension is running Similar Patient Query on remote genomic data: In this setting a doctor that holds the genome of his/her patient may try to find other individuals with close" genomic data, and use the data of these individuals to help diagnose and find effective treatment for that patient's conditions. This is clearly a desirable mode of operation. However, the privacy exposure implications are considerable, and so we would like to carry out the above closeness'' computation in a privacy preserving manner. In this work we put forward a new approach for highly efficient secure computation for computing an approximation of the Similar Patient Query problem. We present contributions on two fronts. First, an approximation method that is designed with the goal of achieving efficient private computation. Second, further optimizations of the two-party protocol. Our tests indicate that the approximation method works well, it returns the exact closest records in 98% of the queries and very good approximation otherwise. As for speed, our protocol implementation takes just a few seconds to run on databases with thousands of records, each of length thousands of alleles, and it scales almost linearly with both the database size and the length of the sequences in it. As an example, in the datasets of the recent iDASH competition, after a one-time preprocessing of around 12 seconds, it takes around a second to find the nearest five records to a query, in a size-500 dataset of length-3500 sequences. This is 2-3 orders of magnitude faster than using state-of-the-art secure protocols with existing edit distance algorithms.

### GLYPH: A New Instantiation of the GLP Digital Signature Scheme

Thu, 06/07/2018 - 15:23
In 2012 Guneysu, et al. proposed GLP, a practical and efficient post-quantum digital signature scheme based on the computational hardness of the Ring Learning With Errors problem. It has some advantages over more recent efficient post-quantum digital signature proposals such as BLISS and Ring-TESLA, but Ring Learning With Errors hardness is more fully understood now than when GLP was published a half decade ago. Although not broken, GLP as originally proposed is no longer considered to offer strong levels of security. We propose GLYPH, a new instantiation of GLP, parametrised for 128 bits of security under the very conservative assumptions proposed in [2], which gives a strong assurance that it will be secure against forgery even if there are further developments in lattice cryptanalysis. Parameters to obtain this strong security level in an efficient manner were not possible within the original formulation of GLP, as they are not compatible with a signature compression algorithm, and to address this we also propose a new form of the compression algorithm which works efficiently with wider ranges of parameters. We have produced a software implementation of GLYPH, and we place it in the public domain at github.com/quantumsafelattices/glyph.

### Simpler Constructions of Asymmetric Primitives from Obfuscation

Wed, 06/06/2018 - 16:50
We revisit constructions of asymmetric primitives from obfuscation and give simpler alternatives. We consider public-key encryption, (hierarchical) identity-based encryption ((H)IBE), and predicate encryption. Obfuscation has already been shown to imply PKE by Sahai and Waters (STOC'14) and full-fledged functional encryption by Garg et al. (FOCS'13). We simplify all these constructions and reduce the necessary assumptions on the class of circuits that the obfuscator needs to support. Our PKE scheme relies on just a PRG and does not need any puncturing. Our IBE and bounded HIBE schemes convert natural key-delegation mechanisms from (recursive) applications of puncturable PRFs to IBE and HIBE schemes. Our most technical contribution is an unbounded HIBE, which uses (public-coin) differing-inputs obfuscation for circuits and whose proof relies on a recent pebbling-based hybrid argument by Fuchsbauer et al. (ASIACRYPT'14). All our constructions are anonymous, support arbitrary inputs, and have compact keys and ciphertexts.

### Pisa: Arbitration Outsourcing for State Channels

Wed, 06/06/2018 - 15:58
State channels are a leading approach for improving the scalability of blockchains and cryptocurrencies. They allow a group of distrustful parties to optimistically execute an application-defined program amongst themselves, while the blockchain serves as a backstop in case of a dispute or abort. This effectively bypasses the congestion, fees and performance constraints of the underlying blockchain in the typical case. However, state channels introduce a new and undesirable assumption that a party must remain on-line and synchronised with the blockchain at all times to defend against execution fork attacks. An execution fork can revert a state channel’s history, potentially causing financial damage to a party that is innocent except for having crashed. To provide security even to parties that may go off-line for an extended period of time, we present Pisa, a protocol enables such parties to delegate to a third party, called the custodian, to cancel execution forks on their behalf. To evaluate Pisa, we provide a proof-of-concept implementation for a simplified Sprites and we demonstrate that it is cost-efficient to deploy on the Ethereum network.

### Smart contracts for bribing miners

Wed, 06/06/2018 - 15:57
We present three smart contracts that allow a briber to fairly exchange bribes to miners who pursue a mining strategy benefiting the briber. The first contract, CensorshipCon, highlights that Ethereum’s uncle block reward policy can directly subsidise the cost of bribing miners. The second contract, HistoryRevisionCon, rewards miners via an in-band payment for reversing transactions or enforcing a new state of another contract. The third contract, GoldfingerCon, rewards miners in one cryptocurrency for reducing the utility of another cryptocurrency. This work is motivated by the need to understand the extent to which smart contracts can impact the incentive mechanisms involved in Nakamoto-style consensus protocols.

### Secure MPC: Laziness Leads to GOD

Wed, 06/06/2018 - 15:57
Secure multi-party computation (MPC) is a problem of fundamental interest in cryptography. Traditional MPC protocols treat a "lazy" party (one that behaves honestly but aborts in the middle of the protocol execution) as a corrupt party that is colluding with the other corrupt parties. However, this outlook is unrealistic as there are various cases where an honest party may abort and turn "lazy" during the execution of a protocol without colluding with other parties. To address this gap, we initiate the study of what we call secure lazy multi-party computation with a formal definition that achieves meaningful correctness and security guarantees. We then construct a three-round lazy MPC protocol from standard cryptographic assumptions. Our protocol is malicious secure in the presence of a CRS and semi-malicious secure in the plain model without a CRS. Using the techniques from above, we also achieve independently interesting consequences in the traditional MPC model. We construct the first round-optimal (three rounds) MPC protocol in the plain model (without a CRS) that achieves guaranteed output delivery (GOD) and is malicious-secure in the presence of an honest majority of parties. Previously, Gordon et al. [CRYPTO' 15] constructed a three-round protocol that achieves GOD in the honest majority setting, but required a CRS. They also showed that it is impossible to construct two-round protocols for the same even in the presence of a CRS. Thus, our result is the first 3-round GOD protocol that does not require any trusted setup, and it is optimal in terms of round complexity. Furthermore, all our above protocols have communication complexity proportional only to the depth of the circuit being evaluated. The key technical tool in our above protocols is a primitive called threshold multi-key fully homomorphic encryption which we define and construct assuming just learning with errors (LWE). We believe this primitive may be of independent interest.

### PIR-PSI: Scaling Private Contact Discovery

Wed, 06/06/2018 - 15:56
An important initialization step in many social-networking applications is contact discovery, which allows a user of the service to identify which of its existing social contacts also use the service. Naive approaches to contact discovery reveal a user's entire set of social/professional contacts to the service, presenting a significant tension between functionality and privacy. In this work, we present a system for private contact discovery, in which the client learns only the intersection of its own contact list and a server's user database, and the server learns only the (approximate) size of the client's list. The protocol is specifically tailored to the case of a small client set and large user database. Our protocol has provable security guarantees and combines new ideas with state-of-the-art techniques from private information retrieval and private set intersection. We report on a highly optimized prototype implementation of our system, which is practical on real-world set sizes. For example, contact discovery between a client with 1024 contacts and a server with 67 million user entries takes 1.36 sec (when using server multi-threading) and uses only 4.28 MiB of communication.

### Optimizing Authenticated Garbling for Faster Secure Two-Party Computation

Wed, 06/06/2018 - 15:55
Wang et al. (CCS 2017) recently proposed a protocol for malicious secure two-party computation that represents the state-of-the- art with regard to concrete efficiency in both the single-execution and amortized settings, with or without preprocessing. We show here several optimizations of their protocol that result in a significant improvement in the overall communication and running time. Specifically: - We show how to make the “authenticated garbling” at the heart of their protocol compatible with the half-gate optimization of Zahur et al. (Eurocrypt 2015). We also show how to avoid sending an information-theoretic MAC for each garbled row. These two optimizations give up to a 2.6x improvement in communication, and make the communication of the online phase essentially equivalent to that of state-of-the-art semi-honest secure computation. - We show various optimizations to their protocol for generating AND triples that, overall, result in a 1.5x improvement in the communication and a 2x improvement in the computation for that step.

### Fast Distributed RSA Key Generation for Semi-Honest and Malicious Adversaries

Wed, 06/06/2018 - 15:54
We present two new, highly efficient, protocols for securely generating a distributed RSA key pair in the two-party setting. One protocol is semi-honestly secure and the other maliciously secure. Both are constant round and do not rely on any specific number-theoretic assumptions and improve significantly over the state-of-the-art by allowing a slight leakage (which we show to not affect security). For our maliciously secure protocol our most significant improvement comes from executing most of the protocol in a strong'' semi-honest manner and then doing a single, light, zero-knowledge argument of correct execution. We introduce other significant improvements as well. One such improvement arrives in showing that certain, limited leakage does not compromise security, which allows us to use lightweight subprotocols. Another improvement, which may be of independent interest, comes in our approach for multiplying two large integers using OT, in the malicious setting, without being susceptible to a selective-failure attack. Finally, we implement our malicious protocol and show that its performance is an order of magnitude better than the best previous protocol, which provided only semi-honest security.

### An Algorithmic Framework for the Generalized Birthday Problem

Wed, 06/06/2018 - 15:53
The generalized birthday problem (GBP) was introduced by Wagner in 2002 and has shown to have many applications in cryptanalysis. In its typical variant, we are given access to a function $H:\{0,1\}^{\ell} \rightarrow \{0,1\}^n$ (whose specification depends on the underlying problem) and an integer $K>0$. The goal is to find $K$ distinct inputs to $H$ (denoted by $\{x_i\}_{i=1}^{K}$) such that $\sum_{i=1}^{K}H(x_i) = 0$. Wagner's K-tree algorithm solves the problem in time and memory complexities of about $N^{1/(\lfloor \log K \rfloor + 1)}$ (where $N= 2^n$). Two important open problems raised by Wagner were (1) devise efficient time-memory tradeoffs for GBP, and (2) reduce the complexity of the K-tree algorithm for $K$ which is not a power of 2. In this paper, we make progress in both directions. First, we improve the best know GBP time-memory tradeoff curve (published by independently by Nikoli\'{c} and Sasaki and also by Biryukov and Khovratovich) for all $K \geq 8$ from $T^2M^{\lfloor \log K \rfloor -1} = N$ to $T^{\lceil (\log K)/2 \rceil + 1 }M^{\lfloor (\log K)/2 \rfloor} = N$, applicable for a large range of parameters. For example, for $K = 8$ we improve the best previous tradeoff from $T^2M^2 = N$ to $T^3M = N$ and for $K = 32$ the improvement is from $T^2M^4 = N$ to $T^4M^2 = N$. Next, we consider values of $K$ which are not powers of 2 and show that in many cases even more efficient time-memory tradeoff curves can be obtained. Most interestingly, for $K \in \{6,7,14,15\}$ we present algorithms with the same time complexities as the K-tree algorithm, but with significantly reduced memory complexities. In particular, for $K=6$ the K-tree algorithm achieves $T=M=N^{1/3}$, whereas we obtain $T=N^{1/3}$ and $M=N^{1/6}$. For $K=14$, Wagner's algorithm achieves $T=M=N^{1/4}$, while we obtain $T=N^{1/4}$ and $M=N^{1/8}$. This gives the first significant improvement over the K-tree algorithm for small $K$. Finally, we optimize our techniques for several concrete GBP instances and show how to solve some of them with improved time and memory complexities compared to the state-of-the-art. Our results are obtained using a framework that combines several algorithmic techniques such as variants of the Schroeppel-Shamir algorithm for solving knapsack problems (devised in works by Howgrave-Graham and Joux and by Becker, Coron and Joux) and dissection algorithms (published by Dinur, Dunkelman, Keller and Shamir). It then builds on these techniques to develop new GBP algorithms.

### Correctness and Fairness of Tendermint-core Blockchains

Wed, 06/06/2018 - 15:52
Tendermint-core blockchains offer strong consistency (no forks) in an open system relying on two ingredients (i) a set of validators that generate blocks via a variant of Practical Byzantine Fault Tolerant (PBFT) consensus protocol and (ii) a rewarding mechanism that dynamically selects nodes to be validators for the next block via proof-of-stake, a non-energy consuming alternative of proof-of-work. It is well-known that in those open systems the main threat is the tragedy of commons that may yield the system to collapse if the rewarding mechanism is not adequate. At minima the rewarding mechanism must be $fair$, i.e. distributing the rewards in proportion to the merit of participants. The contribution of this paper is two-fold. First, we provide a formal description of Tendermint-core protocol and we prove that in eventual synchronous systems (i) it verifies a variant of one-shot consensus for the validation of one single block and (ii) a variant of the repeated consensus problem for multiple blocks. Our second contribution relates to the fairness of Tendermint rewarding mechanism. We prove that Tendermint rewarding is not fair. However, a small twist in the protocol makes it eventually fair. Additionally, we prove that there exists an (eventual) fair rewarding mechanism in repeated consensus-based blockchains if and only if the system is (eventually) synchronous.

### Actively Private and Correct MPC Scheme in $t < n/2$ from Passively Secure Schemes with Small Overhead

Tue, 06/05/2018 - 21:16
Recently, several efforts to implement and use an unconditionally secure multi-party computation (MPC) scheme have been put into practice. These implementations are {\em passively} secure MPC schemes in which an adversary must follow the MPC schemes. Although passively secure MPC schemes are efficient, passive security has the strong restriction concerning the behavior of the adversary. We investigate how secure we can construct MPC schemes while maintaining comparable efficiency with the passive case, and propose a construction of an {\em actively} secure MPC scheme from passively secure ones. Our construction is secure in the $t < n/2$ setting, which is the same as the passively secure one. Our construction operates not only the theoretical minimal set for computing arbitrary circuits, that is, addition and multiplication, but also high-level operations such as shuffling and sorting. We do not use the broadcast channel in the construction. Therefore, privacy and correctness are achieved but {\em robustness} is absent; if the adversary cheats, a protocol may not be finished but anyone can detect the cheat (and may stop the protocol) without leaking secret information. Instead of this, our construction requires $O((c_B n + n^2)\kappa)$ communication that is comparable to one of the best known passively secure MPC schemes, $O((c_M n + n^2)\log n)$, where $\kappa$ denote the security parameter, $c_B$ denotes the sum of multiplication gates and high-level operations, and $c_M$ denotes the number of multiplication gates. Furthermore, we implemented our construction and confirmed that its efficiency is comparable to the current astest passively secure implementation.

### Improved Lightweight Implementations of CAESAR Authenticated Ciphers

Tue, 06/05/2018 - 14:48
Authenticated ciphers offer potential benefits to resource-constrained devices in the Internet of Things (IoT). The CAESAR competition seeks optimal authenticated ciphers based on several criteria, including performance in resource-constrained (i.e., low-area, low-power, and low-energy) hardware. Although the competition specified a ”lightweight” use case for Round 3, most hardware submissions to Round 3 were not lightweight implementations, in that they employed architectures optimized for best throughput-to-area (TP/A) ratio, and used the Pre- and PostProcessor modules from the CAE-SAR Hardware (HW) Development Package designed for high-speed applications. In this research, we provide true lightweight implementations of selected ciphers (ACORN, NORX, CLOC-AES, SILC-AES, and SILC-LED). These implementations use an improved version of the CAESAR HW DevelopmentPackage designed for lightweight applications, and are fully compliant with the CAESAR HW Application programming interface for Authenticated Ciphers. Our lightweight implementations achieve an average of 55% reduction in area and40% reduction in power compared to their corresponding high-speed versions. Although the average energy per bit of lightweight ciphers increases by a factor of 3.6, the lightweight version of NORX actually uses 47% less energy per bit than its corresponding high-speed implementation.

### Round-Optimal Secure Multiparty Computation with Honest Majority

Tue, 06/05/2018 - 09:13
We study the exact round complexity of secure multiparty computation (MPC) in the honest majority setting. We construct several round-optimal $n$-party protocols, tolerating any $t<\frac{n}{2}$ corruptions. - Security with abort: We give the first construction of two round MPC that achieves security with abort against malicious adversaries in the plain model. Our protocol achieves unconditional security for NC$^1$ computations, and requires one-way functions for general computations. - Guaranteed output delivery: We also construct protocols that achieve security with guaranteed output delivery: (i) Against fail-stop adversaries, we construct two round MPC either in the (bare) public-key infrastructure model with no additional assumptions, or in the plain model assuming two-round semi-honest oblivious transfer. In three rounds, however, we can achieve security assuming only one-way functions (or unconditionally, for NC$^1$ computations). (ii) Against malicious adversaries, we construct three round MPC in the plain model, assuming public-key encryption and Zaps. Previously, such protocols were only known based on specific learning assumptions and required the use of common reference strings. All of our results are obtained via general compilers that may be of independent interest.

### Limits of Practical Sublinear Secure Computation

Tue, 06/05/2018 - 08:50
Secure computations on big data call for protocols that have sublinear communication complexity in the input length. While fully homomorphic encryption (FHE) provides a general solution to the problem, employing it on a large scale is currently quite far from being practical. This is also the case for secure computation tasks that reduce to weaker forms of FHE such as ''somewhat homomorphic encryption'' or single-server private information retrieval (PIR). Quite unexpectedly, Aggarwal, Mishra, and Pinkas (Eurocrypt 2004), Brickell and Shmatikov (Asiacrypt 2005), and shelat and Venkitasubramaniam (Asiacrypt 2015) have shown that in several natural instances of secure computation on big data, there are practical sublinear communication protocols that only require sublinear local computation and minimize the use of expensive public-key operations. This raises the question of whether similar protocols exist for other natural problems. In this paper we put forward a framework for separating ''practical'' sublinear protocols from ''impractical'' ones, and establish a methodology for identifying ''provably hard'' big-data problems that do not admit practical protocols. This is akin to the use of NP-completeness to separate hard algorithmic problems from easy ones. We show that while the previous protocols of Aggarwal et al., Brickell and Shmatikov, and shelat and Venkitasubramaniam are indeed classified as being ''practical'' in this framework, slight variations of the problems they solve and other natural computational problems on big data are hard. Our negative results are established by showing that the problem at hand is ''PIR-hard'' in the sense that any secure protocol for the problem implies PIR on a large database. This imposes a barrier on the local computational cost of secure protocols for the problem. We also identify a new natural relaxation of PIR that we call semi-PIR, which is useful for establishing ''intermediate hardness'' of several practically motivated secure computation tasks. We show that semi-PIR implies slightly sublinear PIR via an adaptive black-box reduction and that ruling out a stronger black-box reduction would imply a major breakthrough in complexity theory. We also establish information-theoretic separations between semi-PIR and PIR, showing that some problems that we prove to be semi-PIR-hard are not PIR-hard.

### Fast Large-Scale Honest-Majority MPC for Malicious Adversaries

Tue, 06/05/2018 - 08:50

### Dissection-BKW

Tue, 06/05/2018 - 08:50
The slightly subexponential algorithm of Blum, Kalai and Wasserman (BKW) provides a basis for assessing LPN/LWE security. However, its huge memory consumption strongly limits its practical applicability, thereby preventing precise security estimates for cryptographic LPN/LWE instantiations. We provide the first time-memory trade-offs for the BKW algorithm. For instance, we show how to solve LPN in dimension $k$ in time $2^{\frac 43\frac k{\log k}}$ and memory $2^{\frac 23\frac k{\log k}}$. Using the Dissection technique due to Dinur et al. (Crypto ’12) and a novel, slight generalization thereof, we obtain fine-grained trade-offs for any available (subexponential) memory while the running time remains subexponential. Reducing the memory consumption of BKW below its running time also allows us to propose a first quantum version QBKW for the BKW algorithm.

### Finding Small Solutions of the Equation $Bx-Ay=z$ and Its Applications to Cryptanalysis of the RSA Cryptosystem

Tue, 06/05/2018 - 08:49
In this paper, we study the condition of finding small solutions $(x,y,z)=(x_0, y_0, z_0)$ of the equation $Bx-Ay=z$. The framework is derived from Wiener's small private exponent attack on RSA and May-Ritzenhofen's investigation about the implicit factorization problem, both of which can be generalized to solve the above equation. We show that these two methods, together with Coppersmith's method, are equivalent for solving $Bx-Ay=z$ in the general case. Then based on Coppersmith's method, we present two improvements for solving $Bx-Ay=z$ in some special cases. The first improvement pays attention to the case where either $\gcd(x_0,z_0,A)$ or $\gcd(y_0,z_0,B)$ is large enough. As the applications of this improvement, we propose some new cryptanalysis of RSA, such as new results about the generalized implicit factorization problem, attacks with known bits of the prime factor, and so on. The motivation of these applications comes from oracle based complexity of factorization problems. The second improvement assumes that the value of $C \equiv z_0\ (\mathrm{mod}\ x_0)$ is known. We present two attacks on RSA as its applications. One focuses on the case with known bits of the private exponent together with the prime factor, and the other considers the case with a small difference of the two prime factors. Our new attacks on RSA improve the previous corresponding results respectively, and the correctness of the approach is verified by experiments.