Papers tagged as 2018
1. tches.iacr.org
Gildas Avoine, Loïc Ferreira

We describe in this paper how to perform a padding oracle attack against
the GlobalPlatform SCP02 protocol. SCP02 is implemented in smart cards and
used by transport companies, in the banking world and by mobile network operators
(UICC/SIM cards). The attack allows an adversary to efficiently retrieve plaintext
bytes from an encrypted data field. We provide results of our experiments done
with 10 smart cards from six different card manufacturers, and show that, in our
experimental setting, the attack is fully practical. Given that billions SIM cards are
produced every year, the number of affected cards, although difficult to estimate,
is potentially high. To the best of our knowledge, this is the first successful attack
against SCP02.

2. eprint.iacr.org
Rosario Gennaro and Steven Goldfeder

A threshold signature scheme enables distributed signing among n players such that any subgroup of size t+1 can sign, whereas any group with t or fewer players cannot. While there exist previous threshold schemes for the ECDSA signature scheme, we present the first protocol that supports multiparty signatures for any t≤n with efficient, dealerless key generation. Our protocol is faster than previous solutions and significantly reduces the communication complexity as well. We prove our scheme secure against malicious adversaries with a dishonest majority. We implemented our protocol, demonstrating its efficiency and suitability to be deployed in practice.

3. eprint.iacr.org
Toshinori Araki, Assi Barak, Jun Furukawa, Marcel Keller, Yehuda Lindell, Kazuma Ohara, and Hikaru Tsuchida

Protocols for secure multiparty computation (MPC) enable a set of mutually distrusting parties to compute an arbitrary function of their inputs while preserving basic security properties like \emph{privacy} and \emph{correctness}. The study of MPC was initiated in the 1980s where it was shown that any function can be securely computed, thus demonstrating the power of this notion. However, these proofs of feasibility were theoretical in nature and it is only recently that MPC protocols started to become efficient enough for use in practice. Today, we have protocols that can carry out large and complex computations in very reasonable time (and can even be very fast, depending on the computation and the setting). Despite this amazing progress, there is still a major obstacle to the adoption and use of MPC due to the huge expertise needed to design a specific MPC execution. In particular, the function to be computed needs to be represented as an appropriate Boolean or arithmetic circuit, and this requires very specific expertise. In order to overcome this, there has been considerable work on compilation of code to (typically) Boolean circuits. One work in this direction takes a different approach, and this is the SPDZ compiler (not to be confused with the SPDZ protocol) that takes high-level Python code and provides an MPC run-time environment for securely executing that code. The SPDZ compiler can deal with arithmetic and non-arithmetic operations and is extremely powerful. However, until now, the SPDZ compiler could only be used for the specific SPDZ family of protocols, making its general applicability and usefulness very limited.

In this paper, we extend the SPDZ compiler so that it can work with general underlying protocols. Our SPDZ extensions were made in mind to enable the use of SPDZ for arbitrary protocols and to make it easy for others to integrate existing and new protocols. We integrated three different types of protocols, an honest-majority protocol for computing arithmetic circuits over a field (for any number of parties), a three-party honest majority protocol for computing arithmetic circuits over the ring of integers \Z2n, and the multiparty BMR protocol for computing Boolean circuits. We show that a single high-level SPDZ-Python program can be executed using all of these underlying protocols (as well as the original SPDZ protocol), thereby making SPDZ a true general run-time MPC environment.

In order to be able to handle both arithmetic and non-arithmetic operations, the SPDZ compiler relies on conversions from field elements to bits and back. However, these conversions do not apply to ring elements (in particular, they require element division), and we therefore introduce new bit decomposition and recomposition protocols for the ring over integers with replicated secret sharing. These conversions are of independent interest and utilize the structure of \Z2n (which is much more amenable to bit decomposition than prime-order fields), and are thus much more efficient than all previous methods.

We demonstrate our compiler extensions by running a complex SQL query and a decision tree evaluation over all protocols.

4. eprint.iacr.org
Rafael del Pino, Vadim Lyubashevsky, and Gregor Seiler

We present a group signature scheme, based on the hardness of lattice problems, whose outputs are more than an order of magnitude smaller than the currently most efficient schemes in the literature. Since lattice-based schemes are also usually non-trivial to efficiently implement, we additionally provide the first experimental implementation of lattice-based group signatures demonstrating that our construction is indeed practical – all operations take less than half a second on a standard laptop.

A key component of our construction is a new zero-knowledge proof system for proving that a committed value belongs to a particular set of small size. The sets for which our proofs are applicable are exactly those that contain elements that remain stable under Galois automorphisms of the underlying cyclotomic number field of our lattice-based protocol. We believe that these proofs will find applications in other settings as well.

The motivation of the new zero-knowledge proof in our construction is to allow the efficient use of the selectively-secure signature scheme (i.e. a signature scheme in which the adversary declares the forgery message before seeing the public key) of Agrawal et al. (Eurocrypt 2010) in constructions of lattice-based group signatures and other privacy protocols. For selectively-secure schemes to be meaningfully converted to standard signature schemes, it is crucial that the size of the message space is not too large. Using our zero-knowledge proofs, we can strategically pick small sets for which we can provide efficient zero-knowledge proofs of membership.

5. eprint.iacr.org
Sahar Mazloom and S. Dov Gordon

We explore a new security model for secure computation on large datasets. We assume that two servers have been employed to compute on private data that was collected from many users, and, in order to improve the efficiency of their computation, we establish a new tradeoff with privacy. Specifically, instead of claiming that the servers learn nothing about the input values, we claim that what they do learn from the computation preserves the differential privacy of the input. Leveraging this relaxation of the security model allows us to build a protocol that leaks some information in the form of access patterns to memory, while also providing a formal bound on what is learned from the leakage.

We then demonstrate that this leakage is useful in a broad class of computations. We show that computations such as histograms, PageRank and matrix factorization, which can be performed in common graph-parallel frameworks such as MapReduce or Pregel, benefit from our relaxation. We implement a protocol for securely executing graph-parallel computations, and evaluate the performance on the three examples just mentioned above. We demonstrate marked improvement over prior implementations for these computations.

6. homes.sice.indiana.edu
Ruiyu Zhu, Darion Cassel, Amr Sabry, and Yan Huang

Existing actively-secure MPC protocols require either linear rounds or linear space. Due to this fundamental space-round dilemma, no existing MPC protocols is able to run large-scale computations without significantly sacrificing performance. To mitigate this issue, we developed nanoPI, which is practically efficient in terms of both time and space. Our protocol is based on WRK but introduces interesting and necessary modifications to address several important programmatic and cryptographic challenges. A technique that may be of independent interest (in transforming other computation-oriented cryptographic protocols) is a staged execution model, which we formally define and realize using a combination of lightweight static and dynamic program instrumentation. Our techniques are integrated in nanoPI, an open-source tool for efficiently building and running actively-secure extreme-scale MPC applications. We demonstrate the unprecedented scalability and performance of nanoPI by building and running a suit of bench- mark applications, including an actively-secure four-party logistical regression (involving 4.7 billion ANDs and 8.9 billion XORs) which finished in less than 28 hours on four small-memory machines.

7. eprint.iacr.org
Christian Badertscher, Peter Gazi, Aggelos Kiayias, Alexander Russell, and Vassilis Zikas

Proof-of-stake-based (in short, PoS-based) blockchains aim to overcome scalability, effi- ciency, and composability limitations of the proof-of-work paradigm, which underlies the security of several mainstream cryptocurrencies including Bitcoin. Our work puts forth the first (global universally) composable (GUC) treatment of PoS-based blockchains in a setting that captures—for the first time in GUC—arbitrary numbers of parties that may not be fully operational, e.g., due to network problems, reboots, or updates of their OS that affect all or just some of their local resources including their network interface and clock. This setting, which we refer to as dynamic availability, naturally captures decentralized environments within which real-world deployed blockchain protocols are assumed to operate. We observe that none of the existing PoS-based blockchain protocols can realize the ledger functionality under dynamic availability in the same way that bitcoin does (using only the information available in the genesis block). To address this we propose a new PoS-based protocol, “Ouroboros Genesis”, that adapts one of the latest cryptographically-secure PoS-based blockchain protocols with a novel chain selection rule. The rule enables new or offline parties to safely (re-)join and bootstrap their blockchain from the genesis block without any trusted advice—such as checkpoints—or assumptions regarding past availability. We say that such a blockchain protocol can “bootstrap from genesis.” We prove the GUC security of Ouroboros Genesis against a fully adaptive adversary controlling less than half of the total stake. Our model allows adversarial scheduling of messages in a network with delays and captures the dynamic availability of participants in the worst case. Importantly, our protocol is effectively independent of both the maximum network delay and the minimum level of availability— both of which are run-time parameters. Proving the security of our construction against an adaptive adversary requires a novel martingale technique that may be of independent interest in the analysis of blockchain protocols.

8. eprint.iacr.org
Rosario Gennaro, Michele Minelli, Anca Nitulescu and Michele Orrù

Zero-knowledge SNARKs (zk-SNARKs) are non-interactive proof systems with short (i.e., independent of the size of the witness) and efficiently verifiable proofs. They elegantly resolve the juxtaposition of individual privacy and public trust, by providing an efficient way of demonstrating knowledge of secret information without actually revealing it. To this day, zk-SNARKs are widely deployed all over the planet and are used to keep alive a system worth billion of euros, namely the cryptocurrency Zcash. However, all current SNARKs implementations rely on so-called pre-quantum assumptions and, for this reason, are not expected to withstand cryptanalitic efforts over the next few decades.

In this work, we introduce a new zk-SNARK that can be instantiated from lattice-based assumptions, and which is thus believed to be post-quantum secure. We provide a generalization in the spirit of Gennaro et al. (Eurocrypt’13) to the SNARK of Danezis et al. (Asiacrypt’14) that is based on Square Span Programs (SSP) and relies on weaker computational assumptions. We focus on designated-verifier proofs and propose a protocol in which a proof consists of just 5 LWE encodings. We provide a concrete choice of parameters, showing that our construction is practically instantiable.

9. eprint.iacr.org
Xiaoqian Jiang, Miran Kim, Kristin Lauter, and Yongsoo Song

Homomorphic Encryption (HE) is a powerful cryptographic primitive to address privacy and security issues in outsourcing computation on sensitive data to an untrusted computation environment. Comparing to secure Multi-Party Computation (MPC), HE has advantages in supporting non-interactive operations and saving on communication costs. However, it has not come up with an optimal solution for modern learning frameworks, partially due to a lack of efficient matrix computation mechanisms.

In this work, we present a practical solution to encrypt a matrix homomorphically and perform arithmetic operations on encrypted matrices. Our solution includes a novel matrix encoding method and an efficient evaluation strategy for basic matrix operations such as addition, multiplication, and transposition. We also explain how to encrypt more than one matrix in a single ciphertext, yielding better amortized performance.

Our solution is generic in the sense that it can be applied to most of the existing HE schemes. It also achieves reasonable performance for practical use; for example, our implementation takes 0.6 seconds to multiply two encrypted square matrices of order 64 and 0.09 seconds to transpose a square matrix of order 64.

Our secure matrix computation mechanism has a wide applicability to our new framework E2DM, which stands for encrypted data and encrypted model. To the best of our knowledge, this is the first work that supports secure evaluation of the prediction phase based on both encrypted data and encrypted model, whereas previous work only supported applying a plain model to encrypted data. As a benchmark, we report an experimental result to classify handwritten images using convolutional neural networks (CNN). Our implementation on the MNIST dataset takes 1.69 seconds to compute ten likelihoods of 64 input images simultaneously, yielding an amortized rate of 26 milliseconds per image.

Abdelrahaman Aly, Aysajan Abidin, and Svetla Nikova

Bit-decomposition is a powerful tool which can be used to design constant round protocols for bit-oriented multiparty computation (MPC) problems, such as comparison and Hamming weight computation. However, protocols that involve bit-decomposition are expensive in terms of performance. In this paper, we introduce a set of protocols for distributed exponentiation without bit-decomposition. We improve upon the current state-of-the-art by Ning and Xu [1, 2], in terms of round and multiplicative complexity. We consider different cases where the inputs are either private or public and present privacy-preserving protocols for each case. Our protocols offer perfect security against passive and active adversaries and have constant multiplicative and round complexity, for any fixed number of parties. Furthermore, we showcase how these primitives can be used, for instance, to perform secure distributed decryption for some public key schemes, that are based on modular exponentiation.

11. eprint.iacr.org
Hao Chen, Zhicong Huang, Kim Laine and Peter Rindal

Private Set Intersection (PSI) allows two parties, the sender and the receiver, to compute the intersection of their private sets without revealing extra information to each other. We are interested in the {\it unbalanced} PSI setting, where (1) the receiver’s set is significantly smaller than the sender’s, and (2) the receiver (with the smaller set) has a low-power device. Also, in a {\it Labeled PSI} setting, the sender holds a label per each item in its set, and the receiver obtains the labels from the items in the intersection. We build upon the unbalanced PSI protocol of Chen, Laine, and Rindal (CCS 2017) in several ways: we add efficient support for arbitrary length items, we construct and implement an unbalanced Labeled PSI protocol with small communication complexity, and also strengthen the security model using Oblivious Pseudo-Random Function (OPRF) in a pre-processing phase. Our protocols outperform previous ones: for an intersection of 220 and 512 size sets of arbitrary length items our protocol has a total online running time of just 1 second (single thread), and a total communication cost of 4 MB. For a larger example, an intersection of 228 and 1024 size sets of arbitrary length items has an online running time of 12 seconds (multi-threaded), with less than 18 MB of total communication.

12. eprint.iacr.org
Vladimir Kolesnikov and Mike Rosulek and Ni Trieu

Suppose a server holds a long text string and a receiver holds a short pattern string. Secure pattern matching allows the receiver to learn the locations in the long text where the pattern appears, while leaking nothing else to either party besides the length of their inputs. In this work we consider secure wildcard pattern matching WPM, where the receiver’s pattern is allowed to contain wildcards that match to any character.

We present SWiM, a simple and fast protocol for WPM that is heavily based on oblivious transfer (OT) extension. As such, the protocol requires only a small constant number of public-key operations and otherwise uses only very fast symmetric-key primitives. SWiM is secure against semi-honest adversaries. We implemented a prototype of our protocol to demonstrate its practicality. We can perform WPM on a DNA text (4-character alphabet) of length 10^5
and pattern of length 10^3 in just over 2 seconds, which is over two orders of magnitude faster than the state-of-the-art scheme of Baron et al. (SCN 2012).

13. obj.umiacs.umd.edu

We study the problem of dynamic symmetric searchable encryption. In that setting, it is crucial to minimize the information revealed to the server as a result of update operations (insertions and deletions). Two relevant privacy properties have been defined in that context: forward and backward privacy. The first makes it hard for the server to link an update operation with previous queries and has been extensively studied in the literature. The second limits what the server can learn about entries that were deleted from the database, from queries that happen after the deletion. Backward privacy was formally studied only recently (Bost et al., CCS 2017) in a work that introduced a formal definition with three variable types of leakage (Type-I to Type-III ordered from most to least secure), as well as the only existing schemes that satisfy this property. In this work, we introduce three novel constructions that improve previous results in multiple ways. The first scheme achieves Type-II backward privacy and our experimental evaluation shows it has 145-253X faster search computation times than previous constructions with the same leakage. Surprisingly, it is faster even than schemes with Type-III leakage which makes it the most efficient implementation of a forward and backward private scheme so far. The second one has search time that is asymptotically within a polylogarithmic multiplicative factor of the theoretical optimal (i.e., the result size of a search), and it achieves the strongest level of backward privacy (Type-I). All previous Type-I constructions require time that is at least linear in the total number of updates for the requested keywords, even the (arbitrarily many) previously deleted ones. Our final scheme improves upon the second one by reducing the number of roundtrips for a search at the cost of extra leakage (Type-III).

14. eprint.iacr.org
Amanda Cristina Davi Resende and Diego de Freitas Aranha

Protocols for Private Set Intersection (PSI) are important cryptographic primitives that perform joint operations on datasets in a privacy-preserving way. They allow two parties to compute the intersection of their private sets without revealing any additional information beyond the intersection itself. Unfortunately, PSI implementations in the literature do not usually employ the best possible cryptographic implementation techniques. This results in protocols presenting computational and communication complexities that are prohibitive, particularly in the case when one of the participants is a low-powered device and there are bandwidth restrictions. This paper builds on modern cryptographic engineering techniques and proposes optimizations for a promising one-way PSI protocol based on public-key cryptography. For the case when one of the parties holds a set much smaller than the other (a realistic assumption in many scenarios) we show that our improvements and optimizations yield a protocol that outperforms the communication complexity and the run time of previous proposals by around one thousand times.

15. web.eecs.umich.edu
Eric Crockett, Chris Jason Peikert, and Chad Sharp

Fully Homomorphic Encryption (FHE) is a cryptographic “holy grail” that allows a worker to perform arbitrary computations on client-encrypted data, without learning anything about the data itself. Since the first plausible construction in 2009, a variety of FHE implementations have been given and used for particular applications of interest. Unfortunately, using FHE is currently very complicated, and a great deal of expertise is required to properly implement nontrivial homomorphic computations. This work introduces ALCHEMY, a modular and extensible system that simplifies and accelerates the use of FHE. ALCHEMY compiles “in-the-clear” computations on plaintexts, written in a modular domain-specific language~(DSL), into corresponding homomorphic computations on ciphertexts—with no special knowledge of FHE required of the programmer. The compiler automatically chooses (most of the) parameters by statically inferring ciphertext noise rates, generates keys and “key-switching hints,” schedules appropriate ciphertext “maintenance” operations, and more. In addition, its components can be combined modularly to provide other useful functionality, such logging the empirical noise rates of ciphertexts throughout a computation, without requiring any changes to the original DSL code. As a testbed application, we demonstrate fast homomorphic evaluation of a pseudorandom function~(PRF) based on Ring-LWR, whose entire implementation is only a few dozen lines of simple DSL code. For a single (non-batched) evaluation, our unoptimized implementation takes only about 10 seconds on a commodity PC, which is more than an order of magnitude faster than state-of-the-art homomorphic evaluations of other PRFs, including some specifically designed for amenability to homomorphic evaluation.

16. eprint.iacr.org
Christina Boura and Ilaria Chillotti and Nicolas Gama and Dimitar Jetchev and Stanislav Peceny and Alexander Petric

We propose a novel multi-party computation protocol for evaluating continuous real-valued functions with high numerical precision. Our method is based on approximations with Fourier series and uses at most two rounds of communication during the online phase. For the offline phase, we propose a trusted-dealer and honest-but-curious aided solution, respectively. We apply our algorithm to train a logistic regression classifier via a variant of Newton’s method (known as IRLS) to compute unbalanced classification problems that detect rare events and cannot be solved using previously proposed privacy-preserving optimization algorithms (e.g., based on piecewise-linear approximations of the sigmoid function). Our protocol is efficient as it can be implemented using standard quadruple-precision floating point arithmetic. We report multiple experiments and provide a demo application that implements our algorithm for training a logistic regression model.

17. eprint.iacr.org
Sarvar Patel, Giuseppe Persiano, and Kevin Yeo

Private information retrieval (PIR) is a fundamental tool for preserving query privacy when accessing outsourced data. All previous PIR constructions have significant costs preventing widespread use. In this work, we present private stateful information retrieval (PSIR), an extension of PIR, allowing clients to be stateful and maintain information between multiple queries. Our design of the PSIR primitive maintains three important properties of PIR: multiple clients may simultaneously query without complex concurrency primitives, query privacy should be maintained if the server colludes with other clients, and new clients should be able to enroll into the system by exclusively interacting with the server.

We present a PSIR framework that reduces an online query to performing one single-server PIR on a sub-linear number of database records. All other operations beyond the single-server PIR consist of cryptographic hashes or plaintext operations. In practice, the dominating costs of resources occur due to the public-key operations involved with PIR. By reducing the input database to PIR, we are able to limit expensive computation and avoid transmitting large ciphertexts. We show that various instantiations of PSIR reduce server CPU by up to 10x and online network costs by up to 10x over the previous best PIR construction.

18. fc18.ifca.ai
Ian Martiny, Ian Miers, and Eric Wustrow

Content providers often face legal or economic pressures to censor or remove objectionable or infringing content they host. While decentralized providers can enable censorship-resistant storage, centralized content providers remain popular for performance and usability reasons. But centralized content providers can always choose not to respond to requests for a specific file, making it difficult to prevent censorship. If it is not possible to prevent, is it possible to detect and punish censorship on a centralized service?

A natural approach is to periodically audit the service provider by downloading the file. However, failure to download a file is not a proof of censorship. First, the provider could claim benign failure. Second, the proof is non-transferable: verifying censorship requires third parties to individually request the censored file. Moreover, a content provider may only selectively deny access to particular users or only for a short time frame. As such, checking by downloading does not work even for third parties who are online and willing to make queries.

In this paper, we introduce proof of censorship, whereby a content provider cannot delete or otherwise selectively remove content from their service without creating transferable cryptographic proof of their misdeed. Even if the provider restores the file at a later date, the proof remains valid, allowing the reputation of a content provider’s commitment to censorship resistance to be based on the existence (or absence) of such proofs.

19. eprint.iacr.org
Rouzbeh Behnia, Muslum Ozgur Ozmen, Attila A. Yavuz, and Mike Rosulek

We introduce a simple, yet efficient digital signature scheme which offers post-quantum security promise. Our scheme, named TACHYON, is based on a novel approach for extending one-time hash-based signatures to (polynomially bounded) many-time signatures, using the additively homomorphic properties of generalized compact knapsack functions. Our design permits TACHYON to achieve several key properties. First, its signing and verification algorithms are the fastest among its current counterparts with a higher level of security. This allows TACHYON to achieve the lowest end-to-end delay among its counterparts, while also making it suitable for resource-limited signers. Second, its private keys can be as small as κ bits, where κ is the desired security level. Third, unlike most of its lattice-based counterparts, TACHYON does not require any Gaussian sampling during signing, and therefore, is free from side-channel attacks targeting this process. We also explore various speed and storage trade-offs for TACHYON, thanks to its highly tunable parameters. Some of these trade-offs can speed up TACHYON signing in exchange for larger keys, thereby permitting TACHYON to further improve its end-to-end delay.

20. csee.umbc.edu
Sisi Duan, Michael K. Reiter, and Haibin Zhang

We present BEAT, a set of practical Byzantine fault-tolerant (BFT) protocols for completely asynchronous environments. BEAT is flexible, versatile, and extensible, consisting of five asynchronous BFT protocols that are designed to meet different goals (e.g., different performance metrics, different application scenarios). Due to modularity in its design, features of these protocols can be mixed to achieve even more meaningful trade-offs between functionality and performance for various applications. Through a 92-instance, five-continent deployment of BEAT on Amazon EC2, we show that BEAT is efficient: roughly, all our BEAT instances significantly outperform, in terms of both latency and throughput, HoneyBadgerBFT, the most efficient asynchronous BFT known.

21. arxiv.org
George Kadianakis, Claudia V. Roberts, Laura M. Roberts, and Philipp Winter

In its more than ten years of existence, the Tor network has seen hundreds of thousands of relays come and go. Each relay maintains several RSA keys, amounting to millions of keys, all archived by The Tor Project. In this paper, we analyze 3.7 million RSA public keys of Tor relays. We (i) check if any relays share prime factors or moduli, (ii) identify relays that use non-standard exponents, (iii) characterize malicious relays that we discovered in the first two steps, and (iv) develop a tool that can determine what onion services fell prey to said malicious relays. Our experiments revealed that ten relays shared moduli and 3,557 relays – almost all part of a research project – shared prime factors, allowing adversaries to reconstruct private keys. We further discovered 122 relays that used non-standard RSA exponents, presumably in an attempt to attack onion services. By simulating how onion services are positioned in Tor’s distributed hash table, we identified four onion services that were targeted by these malicious relays. Our work provides both The Tor Project and onion service operators with tools to identify misconfigured and malicious Tor relays to stop attacks before they pose a threat to Tor users.

22. eprint.iacr.org
Adi Akavia, Dan Feldman, and Hayim Shaul

Secure search is the problem of securely retrieving from a database table (or any unsorted array) the records matching specified attributes, as in SQL SELECT…WHERE…’’ queries, but where the database and the query are encrypted. Secure search has been the leading example for practical applications of Fully Homomorphic Encryption (FHE) since Gentry’s seminal work in 2009, attaining the desired properties of a single-round low-communication protocol with semantic security for database and query (even during search). Nevertheless, the wide belief was that the high computational overhead of current FHE candidates is too prohibitive in practice for secure search solutions (except for the restricted case of searching for a uniquely identified record as in SQL UNIQUE constrain and Private Information Retrieval). This is due to the high degree in existing solutions that is proportional at least to the number of database records m.

We present the first algorithm for secure search that is realized by a polynomial of logarithmic degree (log m)^c for a small constant c>0. We implemented our algorithm in an open source library based on HElib, and ran experiments on Amazon’s EC2 cloud with up to 100 processors. Our experiments show that we can securely search to retrieve database records in a rate of searching in millions of database records in less than an hour on a single machine.

We achieve our result by: (1) Designing a novel sketch that returns the first strictly-positive entry in a (not necessarily sparse) array of non-negative real numbers; this sketch may be of independent interest. (2) Suggesting a multi-ring evaluation of FHE – instead of a single ring as in prior works – and leveraging this to achieve an exponential reduction in the degree.

23. papers.mathyvanhoef.com
Mathy Vanhoef and Frank Piessens

We improve key reinstallation attacks (KRACKs) against 802.11 by generalizing known attacks, systematically analyzing all handshakes, bypassing 802.11’s official countermeasure, auditing (flawed) patches, and enhancing attacks using implementation-specific bugs. Last year it was shown that several handshakes in the 802.11 standard were vulnerable to key reinstallation attacks. These attacks manipulate handshake messages to reinstall an already-in-use key, leading to both nonce reuse and replay attacks. We extend this work in several directions. First, we generalize attacks against the 4-way handshake so they no longer rely on hard-to-win race conditions, and we employ a more practical method to obtain the required man-in-the-middle (MitM) position. Second, we systematically investigate the 802.11 standard for key reinstallation vulnerabilities, and show that the Fast Initial Link Setup (FILS) and Tunneled direct-link setup PeerKey (TPK) handshakes are also vulnerable to key reinstallations. These handshakes increase roaming speed, and enable direct connectivity between clients, respectively. Third, we abuse Wireless Network Management (WNM) power-save features to trigger reinstallations of the group key. Moreover, we bypass (and improve) the official countermeasure of 802.11. In particular, group key reinstallations were still possible by combining EAPOL-Key and WNM-Sleep frames. We also found implementation-specific flaws that facilitate key reinstallations. For example, some devices reuse the ANonce and SNonce in the 4-way handshake, accept replayed message 4’s, or improperly install the group key. We conclude that preventing key reinstallations is harder than expected, and believe that (formally) modeling 802.11 would help to better secure both implementations and the standard itself.

24. eprint.iacr.org
Jonathan Katz, Vladimir Kolesnikov, and Xiao Wang

Recent work, including ZKBoo, ZKB++, and Ligero, has developed efficient non-interactive zero-knowledge proofs of knowledge (NIZKPoKs) for arbitrary Boolean circuits based on symmetric- key primitives alone using the “MPC-in-the-head” paradigm of Ishai et al. We show how to instantiate this paradigm with MPC protocols in the preprocessing model; once optimized, this results in an NIZKPoK with shorter proofs (and comparable computation) as in prior work for circuits containing roughly 300–100,000 AND gates. In contrast to prior work, our NIZKPoK also supports witness-independent preprocessing, which allows the prover to move most of its work to an offline phase before the witness is known.

We use our NIZKPoK to construct a signature scheme based only on symmetric-key primitives (and hence with “post-quantum” security). The resulting scheme has shorter signatures than the scheme built using ZKB++ (with comparable signing/verification time), and is even competitive with hash-based signature schemes.

To further highlight the flexibility and power of our NIZKPoK, we also use it to build efficient ring and group signatures based on symmetric-key primitives alone. To our knowledge, the resulting schemes are the most efficient constructions of these primitives that offer post-quantum security.

25. eprint.iacr.org
Assi Barak, Martin Hirt and Lior Koskas, and Yehuda Lindell

Protocols for secure multiparty computation enable a set of parties to compute a joint function of their inputs, while preserving \emph{privacy}, \emph{correctness} and more. In theory, secure computation has broad applicability and can be used to solve many of the modern concerns around utilization of data and privacy. Huge steps have been made towards this vision in the past few years, and we now have protocols that can carry out large computations extremely efficiently, especially in the setting of an honest majority. However, in practice, there are still major barriers to widely deploying secure computation, especially in a decentralized manner.

In this paper, we present the first end-to-end automated system for deploying large-scale MPC protocols between end users, called MPSaaS (for \textit{MPC system-as-a-service}). Our system enables parties to pre-enroll in an upcoming MPC computation, and then participate by either running software on a VM instance (e.g., in Amazon), or by running the protocol on a mobile app, in Javascript in their browser, or even on an IoT device. Our system includes an automation system for deploying MPC protocols, an administration component for setting up an MPC computation and inviting participants, and an end-user component for running the MPC protocol in realistic end-user environments. We demonstrate our system for a specific application of running secure polls and surveys, where the secure computation is run end-to-end with each party actually running the protocol (i.e., without relying on a set of servers to run the protocol for them). This is the first such system constructed, and is a big step forward to the goal of commoditizing MPC.

One of the cryptographic difficulties that arise in this type of setting is due to the fact that end users may have low bandwidth connections, making it a challenge to run an MPC protocol with high bandwidth. We therefore present a protocol based on Beerliova-Trubiniova and Hirt (TCC 2008) with many optimizations, that has very low concrete communication, and the lowest published for small fields. Our protocol is secure as long as less than a third of the parties are \textit{malicious}, and is well suited for computing both arithmetic and Boolean circuits. We call our protocol HyperMPC and show that it has impressive performance. In particular, 150 parties can compute statistics—mean, standard deviation and regression—on 4,000,000 inputs (with a circuit of size 16,000,000 gates of which 6,000,000 are multiplication) in five minutes, and 10 parties can compute the same circuit in 30 seconds. Although our end-to-end system can be used to run any MPC protocol (and we have incorporated numerous protocols already), we demonstrate it for our new protocol that is optimized for end-users without high bandwidth.