Papers tagged as 2017
1. acmccs.github.io
Vladimir Kolesnikov, Naor Matania, Benny Pinkas, Mike Rosulek, and Ni Trieu

We present a new paradigm for multi-party private set intersection (PSI) that allows $n$ parties to compute the intersection of their datasets without revealing any additional information. We explore a variety of instantiations of this paradigm. Our protocols avoid computationally expensive public-key operations and are secure in the presence of any number of semi-honest participants (i.e., without an honest majority).

We demonstrate the practicality of our protocols with an implementation. To the best of our knowledge, this is the first implementation of a multi-party PSI protocol. For 5 parties with data-sets of 220 items each, our protocol requires only 72 seconds. In an optimization achieving a slightly weaker variant of security (augmented semi-honest model), the same task requires only 22 seconds.

The technical core of our protocol is oblivious evaluation of a programmable pseudorandom function (OPPRF), which we instantiate in three different ways. We believe our new OPPRF abstraction and constructions may be of independent interest.

2. acmccs.github.io
Peter Rindal and Mike Rosulek

Private set intersection (PSI) allows two parties, who each hold a set of items, to compute the intersection of those sets without revealing anything about other items. Recent advances in PSI have significantly improved its performance for the case of semi-honest security, making semi-honest PSI a practical alternative to insecure methods for computing intersections. However, the semi-honest security model is not always a good fit for real-world problems.

In this work we introduce a new PSI protocol that is secure in the presence of malicious adversaries. Our protocol is based entirely on fast symmetric-key primitives and inherits important techniques from state-of-the-art protocols in the semi-honest setting. Our novel technique to strengthen the protocol for malicious adversaries is inspired by the dual execution technique of Mohassel & Franklin (PKC 2006). Our protocol is optimized for the random-oracle model, but can also be realized (with a performance penalty) in the standard model.

We demonstrate our protocol’s practicality with a prototype implementation. To securely compute the intersection of two sets of size 220 requires only 13 seconds with our protocol, which is ~12x faster than the previous best malicious-secure protocol (Rindal & Rosulek, Eurocrypt 2017), and only 3x slower than the best semi-honest protocol (Kolesnikov et al., CCS 2016).

3. fc17.ifca.ai
Matthew Smith, Daniel Moser, Martin Strohmeier, Vincent Lenders, Ivan Martinovic

Recent research has shown that a number of existing wireless avionic systems lack encryption and are thus vulnerable to eavesdropping and message injection attacks. The Aircraft Communications Addressing and Reporting System (ACARS) is no exception to this rule with 99% of the traffic being sent in plaintext. However, a small portion of the traffic coming mainly from privately-owned and government aircraft is encrypted, indicating a stronger requirement for security and privacy by those users. In this paper, we take a closer look at this protected communication and analyze the cryptographic solution being used. Our results show that the cipher used for this encryption is a mono-alphabetic substitution cipher, broken with little effort. We assess the impact on privacy and security to its unassuming users by characterizing months of real-world data, decrypted by breaking the cipher and recovering the keys. Our results show that the decrypted data leaks privacy sensitive information including existence, intent and status of aircraft owners.

4. fc17.ifca.ai
Helger Lipmaa, Kateryna Pavlyk

In PETS 2015, Kiayias, Leonardos, Lipmaa, Pavlyk, and Tang proposed the first (n, 1)-CPIR protocol with rate 1−𝑜(1). They use advanced techniques from multivariable calculus (like the Newton-Puiseux algorithm) to establish optimal rate among a large family of different CPIR protocols. It is only natural to ask whether one can achieve similar rate but with a much simpler analysis. We propose parameters to the earlier (n, 1)-CPIR protocol of Lipmaa (ISC 2005), obtaining a CPIR protocol that is asymptotically almost as communication-efficient as the protocol of Kiayias et al. However, for many relevant parameter choices, it is slightly more communication-efficient, due to the cumulative rounding errors present in the protocol of Kiayias et al. Moreover, the new CPIR protocol is simpler to understand, implement, and analyze. The new CPIR protocol can be used to implement (computationally inefficient) FHE with rate 1−𝑜(1).

5. fc17.ifca.ai
Tom Chothia, Flavio Garcia, Christopher Heppel, Christopher McMahon-Stone

This paper presents a security review of the mobile apps provided by the UK’s leading banks; we focus on the connections the apps make, and the way in which TLS is used. We apply existing TLS testing methods to the apps which only find errors in legacy apps. We then go on to look at extensions of these methods and find five of the apps have serious vulnerabilities. In particular, we find an app that pins a TLS root CA certificate, but do not verify the hostname. In this case, the use of certificate pinning means that all existing test methods would miss detecting the hostname verification flaw. We also find one app that doesn’t check the certificate hostname, but bypasses proxy settings, resulting in failed detection by pentesting tools. We find that three apps load adverts over insecure connections, which could be exploited for in-app phishing attacks. Some of the apps used the users’ PIN as authentication, for which PCI guidelines require extra security, so these apps use an additional cryptographic protocol; we study the underlying protocol of one banking app in detail and show that it provides little additional protection, meaning that an active man-in-the-middle attacker can retrieve the user’s credentials, login to the bank and perform every operation the legitimate user could.

6. acmccs.github.io
Hao Chen, Kim Laine, and Peter Rindal

Private Set Intersection (PSI) is a cryptographic technique that allows two parties to compute the intersection of their sets without revealing anything except the intersection. We use fully homomorphic encryption to construct a fast PSI protocol with a small communication overhead that works particularly well when one of the two sets is much smaller than the other, and is secure against semi-honest adversaries.

The most computationally efficient PSI protocols have been constructed using tools such as hash functions and oblivious transfer, but a potential limitation with these approaches is the communication complexity, which scales linearly with the size of the larger set. This is of particular concern when performing PSI between a constrained device (cellphone) holding a small set, and a large service provider (e.g. WhatsApp), such as in the Private Contact Discovery application.

Our protocol has communication complexity linear in the size of the smaller set, and logarithmic in the larger set. More precisely, if the set sizes are Ny < Nx, we achieve a communication overhead of O(Ny log Nx). Our running-time-optimized benchmarks show that it takes 36 seconds of online-computation, 71 seconds of non-interactive (receiver-independent) pre-processing, and only 12.5MB of round trip communication to intersect five thousand 32-bit strings with 16 million 32-bit strings. Compared to prior works, this is roughly a 38–115x reduction in communication with minimal difference in computational overhead.

7. fc17.ifca.ai
Karthikeyan Bhargavan, Antoine Delignat-Lavaud, Nadim Kobeissi

Web traffic encryption has shifted from applying only to highly sensitive websites (such as banks) to a majority of all Web requests. Until recently, one of the main limiting factors for enabling HTTPS is the requirement to obtain a valid certificate from a trusted certification authority, a tedious process that typically involves fees and ad-hoc key generation, certificate request and domain validation procedures. To remove this barrier of entry, the Internet Security Research Group created Let’s Encrypt, a new non-profit certificate authority which uses a new protocol called Automatic Certificate Management Environment (ACME) to automate certificate management at all levels (request, validation , issuance, renewal, and revocation) between clients (website operators) and servers (certificate authority nodes). Let’s Encrypt’s success is measured by its issuance of over 12 million free certificates since its launch in April 2016. In this paper, we survey the existing process for issuing domain-validated certificates in major certification authorities to build a security model of domain-validated certificate issuance. We then model the ACME protocol in the applied pi-calculus and verify its stated security goals against our threat model of domain validation. We compare the effective security of different domain validation methods and show that ACME can be secure under a stronger threat model than that of traditional CAs. We also uncover weaknesses in some flows of ACME 1.0 and propose verified improvements that have been adopted in the latest protocol draft submitted to the IETF.

8. fc17.ifca.ai
Yevgeniy Dodis, Dario Fiore

Key Exchange (KE), which enables two parties (e.g., a client and a server) to securely establish a common private key while communicating over an insecure channel, is one of the most fundamental cryptographic primitives. In this work, we address the setting of unilaterally-authenticated key exchange (UAKE), where an unauthenticated (unkeyed) client establishes a key with an authenticated (keyed) server. This setting is highly motivated by many practical uses of KE on the Internet, but received relatively little attention so far.

Unlike the prior work, defining UAKE by downgrading a relatively complex definition of mutually authenticated key exchange (MAKE), our definition follows the opposite approach of upgrading existing definitions of public key encryption (PKE) and signatures towards UAKE. As a result, our new definition is short and easy to understand. Nevertheless, we show that it is equivalent to the UAKE definition of Bellare-Rogaway (when downgraded from MAKE), and thus captures a very strong and widely adopted security notion, while looking very similar to the simple one-oracle’’ definition of traditional PKE/signature schemes. As a benefit of our intuitive framework, we show two exactly-as-you-expect (i.e., having no caveats so abundant in the KE literature!) UAKE protocols from (possibly interactive) signature and encryption. By plugging various one- or two-round signature and encryption schemes, we derive provably-secure variants of various well-known UAKE protocols (such as a unilateral variant of SKEME with and without perfect forward secrecy, and Shoup’s A-DHKE-1), as well as new protocols, such as the first 2-round UAKE protocol which is both (passively) forward deniable and forward-secure.

To further clarify the intuitive connections between PKE/Signatures and UAKE, we define and construct stronger forms of (necessarily interactive) PKE/Signature schemes, called confirmed encryption and confidential authentication, which, respectively, allow the sender to obtain confirmation that the (keyed) receiver output the correct message, or to hide the content of the message being authenticated from anybody but the participating (unkeyed) receiver. Using confirmed PKE/confidential authentication, we obtain two concise UAKE protocols of the form: send confirmed encryption/confidential authentication of a random key K
.’’

9. fc17.ifca.ai
Ryan Stanley-Oakes

Cryptographic APIs like PKCS#11 are interfaces to trusted hardware where keys are stored; the secret keys should never leave the trusted hardware in plaintext. In PKCS#11 it is possible to give keys conflicting roles, leading to a number of key-recovery attacks. To prevent these attacks, one can authenticate the attributes of keys when wrapping, but this is not standard in PKCS#11. Alternatively, one can configure PKCS#11 to place additional restrictions on the commands permitted by the API.

Bortolozzo et al. proposed a configuration of PKCS#11, called the Secure Templates Patch (STP), supporting symmetric encryption and key wrapping. However, the security guarantees for STP given by Bortolozzo et al. are with respect to a weak attacker model. STP has been implemented as a set of filtering rules in Caml Crush, a software filter for PKCS#11 that rejects certain API calls. The filtering rules in Caml Crush extend STP by allowing users to compute and verify MACs and so the previous analysis of STP does not apply to this configuration.

We give a rigorous analysis of STP, including the extension used in Caml Crush. Our contribution is as follows:

(i) We show that the extension of STP used in Caml Crush is insecure.

(ii) We propose a strong, computational security model for configurations of PKCS#11 where the adversary can adaptively corrupt keys and prove that STP is secure in this model.

(iii) We prove the security of an extension of STP that adds support for public-key encryption and digital signatures.

10. eprint.iacr.org
Joel Alwen, Jeremiah Blocki, and Ben Harsha

A memory-hard function (MHF) ƒn with parameter n can be computed in sequential time and space n. Simultaneously, a high amortized parallel area-time complexity (aAT) is incurred per evaluation. In practice, MHFs are used to limit the rate at which an adversary (using a custom computational device) can evaluate a security sensitive function that still occasionally needs to be evaluated by honest users (using an off-the-shelf general purpose device). The most prevalent examples of such sensitive functions are Key Derivation Functions (KDFs) and password hashing algorithms where rate limits help mitigate off-line dictionary attacks. As the honest users’ inputs to these functions are often (low-entropy) passwords special attention is given to a class of side-channel resistant MHFs called iMHFs.

Essentially all iMHFs can be viewed as some mode of operation (making n calls to some round function) given by a directed acyclic graph (DAG) with very low indegree. Recently, a combinatorial property of a DAG has been identified (called “depth-robustness”) which results in good provable security for an iMHF based on that DAG. Depth-robust DAGs have also proven useful in other cryptographic applications. Unfortunately, up till now, all known very depth-robust DAGs are impractically complicated and little is known about their exact (i.e. non-asymptotic) depth-robustness both in theory and in practice.

In this work we build and analyze (both formally and empirically) several exceedingly simple and efficient to navigate practical DAGs for use in iMHFs and other applications. For each DAG we:
Prove that their depth-robustness is asymptotically maximal.
Prove bounds of at least 3 orders of magnitude better on their exact depth-robustness compared to known bounds for other practical iMHF.
Implement and empirically evaluate their depth-robustness and aAT against a variety of state-of-the art (and several new) depth-reduction and low aAT attacks. We find that, against all attacks, the new DAGs perform significantly better in practice than Argon2i, the most widely deployed iMHF in practice.

Along the way we also improve the best known empirical attacks on the aAT of Argon2i by implementing and testing several heuristic versions of a (hitherto purely theoretical) depth-reduction attack. Finally, we demonstrate practicality of our constructions by modifying the Argon2i code base to use one of the new high aAT DAGs. Experimental benchmarks on a standard off-the-shelf CPU show that the new modifications do not adversely affect the impressive throughput of Argon2i (despite seemingly enjoying significantly higher aAT).

11. fc17.ifca.ai
Wakaha Ogata, Kaoru Kurosawa

In the model of “no-dictionary” verifiable searchable symmetric encryption (SSE) scheme, a client does not need to keep the set of keywords W in the search phase, where W is called a dictionary. Still a malicious server cannot cheat the client by saying that your search word w does not exist in the dictionary W” when it exists. In the previous such schemes, it takes O(logm) time for the server to prove that w∉W, where m=|W| is the number of keywords. In this paper, we show a generic method to transform any SSE scheme (that is only secure against passive adversaries) to a no-dictionary verifiable SSE scheme. In the transformed scheme, it takes only O(1) time for the server to prove that w∉W.

12. fc17.ifca.ai

Isolated Execution Environments (IEE) offered by novel commodity hardware such as Intel’s SGX deployed in Skylake processors permit executing software in a protected environment that shields it from a malicious operating system; it also permits a remote user to obtain strong interactive attestation guarantees on both the code running in an IEE and its input/output behaviour. In this paper we show how IEEs provide a new path to constructing general secure multiparty computation (MPC) protocols. Our protocol is intuitive and elegant: it uses code within an IEE to play the role of a trusted third party (TTP), and the attestation guarantees of SGX to bootstrap secure communications between participants and the TTP. In our protocol the load of communications and computations on participants only depends on the size of each party’s inputs and outputs and is thus small and independent from the intricacy of the functionality to be computed. The remaining computational load– essentially that of computing the functionality – is moved to an untrusted party running an IEE-enabled machine, an appealing feature for Cloud-based scenarios. However, as often the case even with the simplest cryptographic protocols, we found that there is a large gap between this intuitively appealing solution and a protocol with rigorous security guarantees. We bridge this gap through a comprehensive set of results that include: i. a detailed construction of a protocol for secure computation for arbitrary functionalities; ii. formal security definitions for the security of the overall protocol and that of its components; and iii. a modular security analysis of our protocol that relies on a novel notion of labeled attested computation. We implemented and extensively evaluated our solution on SGX-enabled hardware, providing detailed measurements of our protocol as well as comparisons with software-only MPC solutions. Furthermore, we show the cost induced by using constant-time, i.e., timing side channel resilient, code in our implementation.

13. fc17.ifca.ai

Blind signatures are at the core of e-cash systems and have numerous other applications. In this work we construct efficient blind and partially blind signature schemes over bilinear groups in the standard model. Our schemes yield short signatures consisting of only a couple of elements from the shorter source group and have very short communication overhead consisting of 1 group element on the user side and 3 group elements on the signer side. At 80-bit security, our schemes yield signatures consisting of only 40 bytes which is 67% shorter than the most efficient existing scheme with the same security in the standard model. Verification in our schemes requires only a couple of pairings. Our schemes compare favorably in every efficiency measure to all existing counterparts offering the same security in the standard model. In fact, the efficiency of our signing protocol as well as the signature size compare favorably even to many existing schemes in the random oracle model. For instance, our signatures are shorter than those of Brands’ scheme which is at the heart of the U-Prove anonymous credential system used in practice. The unforgeability of our schemes is based on new intractability assumptions of a one-more’’ type which we show are intractable in the generic group model, whereas their blindness holds w.r.t.~malicious signing keys in the information-theoretic sense. We also give variants of our schemes for a vector of messages.

14. fc17.ifca.ai
Albrecht Petzoldt, Alan Szepieniec, Mohamed Saied Emam Mohamed

Multivariate Cryptography is one of the main candidates for creating post-quantum cryptosystems. Especially in the area of digital signatures, there exist many practical and secure multivariate schemes. However, there is a lack of multivariate signature schemes with special properties such as blind, ring and group signatures. In this paper, we propose a generic technique to transform multivariate signature schemes into blind signature schemes and show the practicality of the construction on the example of Rainbow. The resulting scheme satisfies the usual blindness criterion and a one-more-unforgeability criterion adapted to MQ signatures, produces short blind signatures and is very efficient.

15. acmccs.github.io
Dmitry Kogan, Nathan Manohar, and Dan Boneh

Time-based one-time password (TOTP) systems in use today require storing secrets on both the client and the server. As a result, an attack on the server can expose all second factors for all users in the system. We present T/Key, a time-based one-time password system that requires no secrets on the server. Our work modernizes the classic S/Key system and addresses the challenges in making such a system secure and practical. At the heart of our construction is a new lower bound analyzing the hardness of inverting hash chains composed of independent random functions, which formalizes the security of this widely used primitive. Additionally, we develop a near-optimal algorithm for quickly generating the required elements in a hash chain with little memory on the client. We report on our implementation of T/Key as an Android application. T/Key can be used as a replacement for current TOTP systems, and it remains secure in the event of a server-side compromise. The cost, as with S/Key, is that one-time passwords are longer than the standard six characters used in TOTP.

16. fc17.ifca.ai
Aanchal Malhotra, Matthew Van Gundy, Mayank Varia, Haydn Kennedy, Jonathan Gardner, Sharon Goldberg

For decades, the Network Time Protocol (NTP) has been used to synchronize computer clocks over untrusted network paths. This work takes a new look at the security of NTP’s datagram protocol. We argue that NTP’s datagram protocol in RFC5905 is both underspecified and flawed. The NTP specifications do not sufficiently respect (1) the conflicting security requirements of different NTP modes, and (2) the mechanism NTP uses to prevent off-path attacks. A further problem is that (3) NTP’s control-query interface reveals sensitive information that can be exploited in off-path attacks. We exploit these problems in several attacks that remote attackers can use to maliciously alter a target’s time. We use network scans to find millions of IPs that are vulnerable to our attacks. Finally, we move beyond identifying attacks by developing a cryptographic model and using it to prove the security of a new backwards-compatible client/server protocol for NTP.

17. fc17.ifca.ai
Leonid Reyzin, Dmitry Meshkov, Alexander Chepurnoy, Sasha Ivanov

We improve the design and implementation of two-party and three-party authenticated dynamic dictionaries and apply these dictionaries to cryptocurrency ledgers.

A public ledger (blockchain) in a cryptocurrency needs to be easily verifiable. However, maintaining a data structure of all account balances, in order to verify whether a transaction is valid, can be quite burdensome: a verifier who does not have the large amount of RAM required for the data structure will perform slowly because of the need to continually access secondary storage. We demonstrate experimentally that authenticated dynamic dictionaries can considerably reduce verifier load. On the other hand, per-transaction proofs generated by authenticated dictionaries increase the size of the blockchain, which motivates us to find a solution with most compact proofs.

Our improvements to the design of authenticated dictionaries reduce proof size and speed up verification by 1.4-2.5 times, making them better suited for the cryptocurrency application. We further show that proofs for multiple transactions in a single block can compressed together, reducing their total length by approximately an additional factor of 2.

We simulate blockchain verification, and show that our verifier can be about 20 times faster than a disk-bound verifier under a realistic transaction load.

18. fc17.ifca.ai
Patrick McCorry, Siamak Shahandashti, Feng Hao

We present the first implementation of a decentralised and self-tallying internet voting protocol with maximum voter privacy using the Blockchain. The Open Vote Network is suitable for boardroom elec- tions and is written as a smart contract for Ethereum. Unlike previously proposed Blockchain e-voting protocols, this is the first implementation that does not rely on any trusted authority to compute the tally or to protect the voter’s privacy. Instead, the Open Vote Network is a self- tallying protocol, and each voter is in control of the privacy of their own vote such that it can only be breached by a full collusion involving all other voters. The execution of the protocol is enforced using the consensus mechanism that also secures the Ethereum blockchain. We tested the implementation on Ethereum’s official test network to demonstrate its feasibility. Also, we provide a financial and computational breakdown of its execution cost.

19. fc17.ifca.ai
Orfeas Stefanos, Thyfronitis Litos, Dionysis Zindros

Centralized reputation systems use stars and reviews and thus require algorithm secrecy to avoid manipulation. In autonomous open source decentralized systems this luxury is not available. We create a reputation network for decentralized marketplaces where the trust each user gives to the other users is quantifiable and expressed in monetary terms. We introduce a new model for bitcoin wallets in which user coins are split among trusted associates. Direct trust is defined using shared bitcoin accounts via bitcoin’s 1-of-2 multisig. Indirect trust is subsequently defined transitively. This enables formal game theoretic arguments pertaining to risk analysis. We prove that risk and maximum flows are equivalent in our model and that our system is Sybil-resilient. Our system allows for concrete financial decisions on the subjective monetary amount a pseudonymous party can be trusted with. Risk remains invariant under a direct trust redistribution operation followed by a purchase.

20. fc17.ifca.ai
Steven Goldfeder, Joseph Bonneau, Rosario Gennaro, Arvind Narayanan

We consider the problem of buying physical goods with cryptocurrencies. There is an inherent circular dependency: should be the buyer trust the seller and pay before receiving the goods or should the seller trust the buyer and ship the goods before receiving payment? This dilemma is addressed in practice using a third party escrow service. However, we show that naive escrow protocols introduce both privacy and security issues. We formalize the escrow problem and present a suite of schemes with improved security and privacy properties. Our schemes are compatible with Bitcoin and similar blockchain-based cryptocurrencies.

21. fc17.ifca.ai
Gunnar Hartung

We present four attacks on three cryptographic schemes in-tended for securing log files against illicit retroactive modification. Our first two attacks regard the LogFAS scheme by Yavuz et al. (FinancialCryptography 2012), whereas our third and fourth attacks break the BM-and AR-FssAgg schemes by Ma (AsiaCCS 2008).All schemes have an accompanying security proof, seemingly contradicting the existence of attacks. We point out flaws in these proofs, resolvingthe contradiction.

22. fc17.ifca.ai
Reihaneh Safavi-Naini, Viliam Lisy, Yvo Desmedt

Cryptographic authentication protects messages against forgeries. In real life, messages carry information of different value and the gain of the adversary in a successful forgery and the corresponding cost of the system designers, depend on the “meaning” of the message. This is easy to see by comparing the successful forgery of a $1,000 transaction with the forgery of a$1 one. Cryptographic protocols require computation and increase communication cost of the system, and an economically optimal system must optimize these costs such that message protection be commensurate to their values. This is especially important for resource limited devices that rely on battery power. A MAC (Message Authentication Code) provides protection by appending a cryptographic tag to the message. For secure MACs, the tag length is the main determinant of the security level: longer tags provide higher protection and at the same time increase the communication cost of the system. Our goal is to find the economically optimal tag lengths when messages carry information of different values.

We propose a novel approach to model the cost and benefit of information authentication as a two-party extensive-form game, show how to find a Nash equilibrium for the game, and determine the optimal tag lengths for messages. We prove that computing an optimal solution for the game is NP-complete, and then show how to find an optimal solution using single Mixed Integer Linear Program (MILP). We apply the approach to the protection of messages in an industrial control system using realistic messages, and give our analysis with numerical results obtained using off-the-shelf IBM CPLEX solver.

23. fc17.ifca.ai
Helger Lipmaa

Given a well-chosen additively homomorphic cryptosystem and a Σ protocol with a linear answer, Damgård, Fazio, and Nicolosi proposed a non-interactive designated-verifier zero knowledge argument in the registered public key model that is sound under non-standard complexity-leveraging assumptions. In 2015, Chaidos and Groth showed how to achieve the weaker yet reasonable culpable soundness notion under standard assumptions but only if the plaintext space order is prime. It makes use of Σ protocols that satisfy what we call the \emph{optimal culpable soundness}. Unfortunately, most of the known additively homomorphic cryptosystems (like the Paillier Elgamal cryptosystem that is secure under the standard Decisional Composite Residuosity Assumption) have composite-order plaintext space. We construct optimally culpable sound Σ protocols and thus culpably sound non-interactive designated-verifier zero knowledge protocols for NP under standard assumptions given that the least prime divisor of the plaintext space order is large.

24. eprint.iacr.org
Ruiyu Zhu and Yan Huang

LEGO-style cut-and-choose is known for its asymptotic efficiency in realizing actively-secure computations. The dominant cost of LEGO protocols is due to wire-soldering — the key technique enabling to put independently generated garbled gates together in a bucket to realize a logical gate. Existing wire-soldering constructions rely on homomorphic commitments and their security requires the majority of the garbled gates in every bucket to be correct.

In this paper, we propose an efficient construction of LEGO protocols that does not use homomorphic commitments but is able to guarantee security as long as at least one of the garbled gate in each bucket is correct. Additionally, the faulty gate detection rate in our protocol doubles that of the state-of-the-art LEGO constructions. With moderate additional cost, our approach can even detect faulty gates with probability 1, which enables us to run cut- and-choose on larger circuit gadgets rather than individual AND gates. We have implemented our protocol and our experiments on several benchmark applications show that the performance of our approach is highly competitive in comparison with existing implementations.

25. eprint.iacr.org
W. Sean Kennedy and Vladimir Kolesnikov and Gordon Wilfong

Given a set S = {C_1,…,C_k } of Boolean circuits, we show how to construct a universal for S circuit C_0, which is much smaller than Valiant’s universal circuit or a circuit incorporating all C_1,…,C_k. Namely, given C_1,…,C_k and viewing them as directed acyclic graphs (DAGs) D_1,…,D_k, we embed them in a new graph D_0. The embedding is such that a GC garbling of any of C_1,…,C_k could be implemented by a corresponding garbling of a circuit corresponding to D_0.

We show how to improve Garbled Circuit (GC) and GMW-based secure function evaluation (SFE) of circuits with if/switch clauses using such S-universal circuit.

The most interesting case here is the application to the GMW approach. We provide a novel observation that in GMW the cost of processing a gate is almost the same for 5 (or more) Boolean inputs, as it is for the usual case of 2 Boolean inputs. While we expect this observation to greatly improve general GMW-based computation, in our context this means that GMW gates can be programmed almost for free, based on the secret-shared programming of the clause.

Our approach naturally and cheaply supports nested clauses. Our algorithm is a heuristic; we show that solving the circuit embedding problem is NP-hard. Our algorithms are in the semi-honest model and are compatible with Free-XOR.

We report on experimental evaluations and discuss achieved performance in detail. For 32 diverse circuits in our experiment, our construction results 6.1x smaller circuit than prior techniques.