This week a large part of the MPC community is meeting in Aarhus for a workshop on Theory and Practice of Secure Computation. The local Crypto Group is going to blog live(ish) about all the talks at the workshop. As we are blogging live, our posts might contain inaccuracies and errors. Please write us if you find any!
The abstract of the talks, as well as some of the slides are available here.
Circuits Resilient to Additive Attacks with Applications to Secure Computation
Can a circuit defend itself while it is being corrupted? Yuval’s talk provided the audience a great insight towards answering this question. The problem of computing on corrupted hardware has been studied in many theoretical papers each either assuming some bound on the powers of the adversary such as number of attacked wires, spatial limitations or assuming that the attack fails with some probability.
In this work, the authors investigate the task of protecting hardware against an adversary that can perform an unbounded number of always successful attacks. Towards that direction, there are two major problems: firstly, the adversary can corrupt the inputs and outputs of the circuit making it output arbitrary chosen values. They solved this by assuming “small” and “trusted” tamper-proof encoder and decoder to protect the outputs and inputs. Secondly, the adversary can corrupt the inputs of the decoder making it output arbitrary chosen values which they solved by limiting the adversary’s power to some restricted class of attacks namely the additive attack. In more detail, additive attacks allow an adversary to add arbitrary field element to any wire inside the circuit. This work can be considered as an extension of classical random faults model of Shannon and Von Neumann, and at the same time finds application to secure multiparty computation.
In order to achieve protection against additive attack they used “additively secure code” called AMD code due Cramer et al. (2008) which guarantees that any additive modification will be detected. They replace each gate of the circuit by a gadget that gets input encoded by the above code and outputs the encoding of the computed value.
In the second part Yuval talked briefly about the application to secure multi-party computation. Using their result they proposed an innovative approach to achieve active security. In fact, in many cases (such as the BGW protocol), to securely evaluate a circuit in the presence of active adversaries, it suffices to apply the passive-case protocol to the additively secure version. He concluded with a number of interesting open problems, e.g. how to improve the attack model using some stronger code (e.g. non-malleable code which attracts significant research attention these days).
Distributed Obfuscation and Non-Interactive Secure Multiparty Computation
This talk focuses on the problem of non-interactive secure computation. This model involves three sets of parties: a dealer, the
players and the receiver. In a setup phase, a trusted dealer sends some information to the parties. In the second phase, the players send some values based on his input to the receiver and then in the third phase, the receiver extracts the output. We then consider what could learn a dishonest receiver interacting with dishonest players. In particular, we cannot prevent the cheaters from learning anything that they could learn given access to an oracle to the function where the honest players are fixed. A protocol is t-robust if for any set of t corrupt parties the receiver cannot learn more than what would give the oracle defined previously. A couple of results are noted in this model. In particular, we get full robustness against any function with complexity polynomial in the domain size by using many instances of the singleton function.
Known garbling schemes and PSM schemes are not 1-robust. Another result is that obfuscation and a variant of functional encryption imply NIMPC and that NIMPC implies obfuscation. The study of NIMPC has other interesting impossibility proofs and
constructions for certain functions.
Indistinguishability Obfuscation from Semantically-Secure Multilinear Encodings
Rafael talked about his work with Karn Seth and Sidharth Telang on basing indistinguishability obfuscation on simple and well-studied computational intractability assumptions. He started with a motivation and a review of previous results on obfuscation.
Intuitively, program obfuscation is the problem of making program code unintelligible without disturbing its functionality. There are many practical applications of program obfuscation such as protecting software or private API (most prominently used by Skype). Despite the availability of many “obfuscation tools”, program obfuscation was merely an art until recently when a rigorous treatment of this problem was proposed.
A program obfuscator takes a program and turns it efficiently into an obfuscated program that is functionally equivalent and has at most polynomial slow-down. The natural notion of Virtual Black Box obfuscation [Barak et al.’01] (i.e., given obfuscation of a program it is not possible to learn more than just given black-box access to the program itself) is not achievable in general. This motivated the definition of indistinguishability obfuscation (i.e., obfuscations of two functionally equivalent programs are computationally indistinguishable). As it turns out this relaxed notion of obfuscation is sufficient for many appealing cryptographic applications. Last year, [Garg et al.’13] showed that indistinguishability obfuscation is achievable by giving a candidate construction based on multilinear encodings.
At this point, Rafael asked the main question of his talk: “Is it possible to reduce security of indistinguishability obfuscation to some low-level intractability assumption?” In particular, an assumption that fulfills following natural desiderata
- the assumption is general, simple, and interesting
- the security proof is non-trivial and the assumption is falsifiable
- the assumption is well studied.
After the motivation, Rafael presented their main result that indistinguishability obfuscation is achievable for all functions in the class NC1 assuming semantic security of multilinear encodings. Moreover, it can be achieved for all functions in P/poly under the additional assumption of levelled fully homomorphic encryption.
The rest of the talk was dedicated to the definition of semantic security for multilinear encodings and the construction of their indistinguishability obfuscator. The construction is similar to previous results and uses the common main components: branching programs, Kilian’s randomization and multilinear encodings. However, there are new ideas in the security proof that allow to rely on semantic security of multilinear encodings. In particular, Rafael introduced a technique of merging two branching programs that allows to use hybrid argument in the security proof. An important property of the merging is to avoid non-unique outputs, or else the Kilian’s randomization need not ensure security.
2-party secure computation & applications
This talk discusses the difficulty of implementing the stable matching problem in secure computation. In this problem there are two set of players, each person in the first set wants to be matched with someone in the second set and vice versa. In addition, each player has an order of preference for each member of the other set.
This idea can be used to map students to universities and men to women in marriages. A matching is stable if no player can improve by breaking up his match and matching himself with someone unmatched or two players breaking up a couple to be matched. The approach by garbled circuits is inefficient due to the worst case run time of the algorithm. Another solution based on Oblivious Ram was presented; unfortunately it is still inefficient for many practical applications. It is suggested that a new underlying protocol for stable matching would be the best way to improve secure computation of this function.
Large-Scale Secure Computation
Usually MPC focus on settings with just a handful of parties. Hence, most of current protocols can end up being unfeasible in scenarios with a massive number of parties, such as social networks. In this talk, Elette Boyle analyses the problem of performing large-scale secure computation, presenting information theoretically secure protocols that scale well in large-scale scenarios.
The basic approach used by Elette consists in obtaining protocols that scale well in the size of a RAM program that describes the function to be computed instead of a circuit. Traditionally, MPC based on circuits has protocol complexity at lower bounded by the circuit size, while previous RAM based approaches requires do not scale well with the number of players.
Even though using RAM programs for MPC makes it possible to obtain highly scalable protocols, it introduces a basic need to touch all parties’ inputs during the computation in order not to leak information through data access patterns. Thus, the minimum
computational complexity we can expect from this kind of protocol is in the order of n*|x|, where n is the number of parties and |x| is the size of inputs.
On the other hand, basing MPC on RAM programs has nice advantages such as allowing for a single (potentially expensive) setup to be sufficient for running an arbitrary number of RAM programs. Round complexity wise, Elette’s solution is independent from the number of parties. Space complexity is also pretty good, adding an overhead proportional to the size of the RAM program to the lower bound. In this protocol, parties are given access to a broadcast channel but do not utilize it extensively. The protocol aims at keeping communication local.
A main ingredient of this construction is an oblivious RAM protocol, that allows the parties to run the original RAM describing their desired function without revealing data access patterns. Each party should hold a share of the database containing the ORAM compiled RAM program. However, this construction differs from previous works on ORAM in that they implement a distributed ORAM, where each party in fact maintains an individual node of a ORAM access tree. In this setting, parties act as committees to evaluate the program and the communication patterns between parties hide which inputs are accessed.
Moreover, their scheme allows for parallel insertion of input entries into the ORAM.
Basically, the parties organize themselves sin to committees that will act as individual CPUs and ORAMs. First, they insert their verifiably secret shared inputs into one of the ORAMs by talking to the ORAM committees using the parallel insertion procedure. Later on, the CPU committees run the RAM program over using both the input ORAM and a second workspace ORAM.
By using committees for executing the ORAMs and then the RAM program over the previously setup ORAMs, this approach achieves memory balancing, since the parties share the storage different nodes of the ORAM and the work of executing the RAM programs. However, more work is needed to actually achieve load balancing, which is implemented through job passing, i.e. if a committee has to much work it can pass it to another committee.
The last piece of this construction consists in achieving communication locality, since in large-scale scenarios it is important
to make sure that a single party doesn’t have to contact many other parties. In order to achieve this, a fixed topology communication network is setup in the beginning of protocol execution and a committee of parties is elected to take care of each of the network nodes. Later on, messages are passed between different committees through a routing protocol that requires only neighboring parties to talk to each other.
FleXOR: Flexible garbling for XOR gates that beats free-XOR
Mike talks about a new optimization for general garbled circuits called FleXOR. Currently we already know several optimizations for garbled circuits such as the row reduction, which makes it possible to eliminate two ciphertexts per gate and the free-XOR technique, which makes it possible to evaluate XOR gates for free (i.e. without any communication or cryptographic operations).
Unfortunately it is not possible to combine these two techniques (we can still get free XOR and eliminate one ciphertext though). Furthermore, the free-XOR approach also requires a quite strong assumption on circular encryption security. Mike explains how to get (almost) the best of everything: cheap XOR and few ciphertexts per gate under a weak security assumption.
The optimizations arrive by carefully dissecting and generalizing the free-XOR approach and involves solving an NP-hard
problem of wire ordering. It should be noted that quite simple and efficient heuristics work to find a suitable ordering which still
gives very good results. It turns out that on average the amount of ciphertexts per gate is significantly less (for most circuits) than the 2 ciperhertexts per gates using the row reduction without free-XOR. This is in fact achievable under a weaker assumption than free-XOR needs. Thus we get a substantial increase in efficiency with a weak assumption.
If we wish to assume the stronger circular security assumption of free-XOR we can get even greater optimizations and on average (for most circuits) a fleXOR gate will require less ciphertexts than a free-XOR gate. Mike concludes by saying that there is still future
work in fleXOR, which includes finding better heuristics for wire ordering along with actual implementation benchmarks.
Performance Optimization of Linear Secret Sharing MPC for Real Applications
David’s talk mainly described an MPC platform that was developed at Galois in order to demonstrate that MPC can be used in practical applications.
A first proof of concept is secure voice over IP protocols (actually, on-demand, streaming cloud privacy VoIP). The model considered is the one in which the adversary is honest but curious (hbc) and secure channels are available for the communications between parties. The privacy is granted by using a linear secret sharing and more security could be gained by different architectures, different administrators or locations. For three parties, the LSSS used is the one in which each secret is written as sum of three random elements from the same field, s=s1+s2+s3 (mod 2^n).
The main goal of the presentation was to show how to obtain significant performance optimizations of such MPC computations. First of all, David described a dedicated programming platform, that is a secret-sharing computation language that allows to optimize the programs with specific functionalities (math like operation on share, bit-numeric conversion, etc…) and ad-hoc instruction set architecture.
After that, the talk showed in detail the main optimizations they have found useful in the platform, both at the program and the circuit level:
- substitution of table lookups for certain classes of circuits
- partitioning of large lookup tables,
- SAT-based optimization of Boolean circuits
- scheduling communication among share servers (to minimize peak bandwidth utilization).
An example outcome obtained for the Voip protocol implemented with the described platforms was reported: 4 voice “accumulators” at 16kB/s sampling rate, 25ms of processing per incoming 1440-sample blocks return 65ms left in for the network delay to and from clients (Amazon ECS VMs for MPC and Apple iPhones for clients).
The same platform was also used for implementing a eMail border guard. In this case the aim is to ensure the intellectual property and privacy for all the clients using the eMail server. In this case David showed an outcome of almost 15ms of delay to accept or reject a one-page email (private cloud VMs for the MPC computations and Linux laptops for clients).
David concluded the talk saying that optimizations can bring interesting applications to practice, but in many settings traditional crypto protocols are cheaper and faster. For LSS schemes it seems that the communication if often the main bottleneck. Some directions about future works suggested are finding additional instruction for the MPC machine, putting more automation for scheduling of communications among share servers and, finally, improving the security consider stronger than hbc adversaries.