Aarhus MPC Workshop ’14, Friday

May 11, 2014 by mpclounge

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 Aarhus Crypto Group, hosting the event and taking care of this series of blog posts.

The abstract of the talks, as well as some of the slides are available here.

Binary Tree Oblivious RAM Framework and Applications in MPC

Elaine Shi

Elaine started her talk visibly touched by remembering her coauthor and friend Emil Stefanov who tragically passed away this year.

http://www.rememberingemil.org/

In the first part of the talk Elain talked about oblivious RAM (ORAM): in many applications the access pattern leak significant information: if one wants to do outsource genetic data, the access pattern is sensitive (as different part of genome encode different information). A different example (Islam et al., 2012) is how access pattern leads to to severe leakage in email searches.

Clearly, if the following piece of code is run

If(sensitive variable) then read x else read y;

then the access pattern leaks sensitive information. Oblivious RAM (ORAM) [G096] is the solution to this problem. According to Elaine the two main open problems in this area of research are

Can we achieve an ORAM with logN bandwidth overehad and 1 client storage? (GO96 proved logn lower bound and the best known before this work was log2N/loglogN).
The second question, can it be practical?

A promising approach to ORAM is the binary-tree ORAM framework, which is very simple and can be implemented in 15-30 lines of pseudo-code. The key observation in ORAM is that data should move around all the time: if not, if the user access the same data twice the server will learn this.

All existing constructions move data around using oblivious sort, which is the main bottleneck of existing approaches. In binary-tree ORAM this is avoided: The data is stored on the server side in a binary-tree, and each node is a bucket of size B. The client assigns each block x to a path (identified by a leaf l), and the invariant is that x will reside in some bucket somewhere on the path between the root and l (of course the client need to store this mapping now, but using recursion this will be put in the ORAM as well). To look up block x one looks at the position map and reads all the buckets on the path, and x is guaranteed to be there.

After the block is accessed, one has to write it back to a different path r (otherwise, this creates a linkage problem). So we pick a new leaf at random r and write x between the root to there. We cannot write it on the leaf, otherwise the server learns more than it should. The same reasoning apply for any node on the path to r, and it turns out that the only safe thing is to write it on the root node.

This is fine at first but soon the root node overflow. This is dealt by doing clever eviction, and pushing blocks towards the leaves subject to their invariants/paths. Random eviction works by choosing two random buckets at each level, doing a real eviction on one of them and a dummy one on the other one. (If there is nothing on the bucket two dummy evictions are perfomed). Obliviousness is trivial (every data access visitis a random path and two random buckets at each level) and recursion alllows to give O(1) client storage to store the position map on the extenral ram as well. Different ways of parametrizing this approach give rise to different results.

In the second part of the talk Elaine presented some applications of ORAM to secure computation for “big-data”. The main idea here is that naive RAM to circuit compilers incur for O(N) cost for each dynamic memory access. Gordon et al. demonstrated how ORAM can give sublinear MPC (in the input size) for repeated queries. Here Elaine argued that in fact ORAM can lead to significant advantages even for one-time tasks, and presented an architecture for automating RAM-based secure computation, by converting programs into secure computation protocol. Among the features, usability for non expert and efficiency using static analysis were mentioned.

Elaine Shi

Advances in Obfuscation

Amit Sahai

Amit Sahai talked about program obfuscation. Informally, an obfuscator O is a compiler which on input a program P outputs a new program O(P) that has the same functionality as P but it cannot be reversed-engineered. It was shown that general-purpose obfuscation [B+01], in which the source code of P reveals no more information than can be learned from oracle access to P, is impossible to achieve for general programs. More specifically, it was showed that there are contrived ‘self-eating programs’ for which black box obfuscation suffers from explicit attacks. Since then, very few techniques and ad-hoc methods for simple programs were proposed. Hence, from a theoretical point of view, the safest way forward is indistinguishability Obfuscation (iO).

Recently, the proposal of candidate multilinear maps (mmaps) from ideal lattices restarted the research on program obfuscation. Using graded encoding schemes a candidate iO for all programs was proposed by [GGHRSW13]. iO is a weaker notion which requires that given any two equivalent programs P0 or P1 of similar size, the obfuscations of P0 or P1 should be computational indistinguishable. This was the first non-trivial candidate in the literature for all programs.

Amit rasied the question of the confidence we have about obfuscation, and where does security come from. So, the talk was focused on the security of obfuscation. Two recent works were discussed:

Generic security for obfuscation. [B+14]
iO from the multilinear subgroup elimination assumption [GLSW14].

As for the first part, [B+14] is a variant of [GGHRSW13] considering a more restricted adversary based on stronger assumptions. More specifically, they prove that the [GGHRSW13] compiler is a virtual black box obfuscator in a generic multilinear map model. This work shows that there is a candidate obfuscator that cannot be broken by algebraic attacks, hence reducing the task of creating secure obfuscators in the plain model to obtaining sufficiently strong security guarantees on candidate instantiations of multilinear maps.

Regarding part two, the authors of [GLSW14], give a construction of general-purpose iO proven secure via a reduction to an instance-independent computational assumption over multilinear maps, the Multilinear Subgroup Elimination Assumption. Therefore, they base security on an assumption that does not directly provide obfuscated programs to the adversary.

The Multilinear Subgroup Elimination Assumption considers a multilinear map over a composite N with many large prime factors, out of which one is a “special” prime factor c, plus k “distinguised” prime factors a_1, a_2,…,a_k and polynomial other ones. The adversary gets level-1 encoding of (random) generators of each prime subgroup (expect c) and random element of order c(a_1, a_2,…,a_(i-1),a_(i+1),…,a_k). Finally the adversary is asked to distinguish between Level-1 encoding of:

a random element T of order (a_1, a_2,…,a_k)
a random element T of order c(a_1, a_2,…,a_k)

Recall, that the assumption doesn’t incorporate branching program matrices, stradding sets ( stradding sets allow decomposition of the adversary’s queries into queries that only depend on matrices corresponding to a single input) and circuits . Previous iO assumptions were ad-hoc and directly incorporating obfuscated programs or they were meta-assumptions ( assumptions on assumptions, e.g. all assumptions that satisfy X,Y,Z are true [PST13] ).

To sum up, the results presented by Amit help understanding where the security of obfuscation comes from: one could say that now it is less likely that there might be a [B+01]-style negative result hiding in the iO works.

As pointed out by Amit, the open problems are several such as to propose completely different obfuscation methods, avoid mmap-like functionality altogether or obtain greater efficiency and security from more standard assumptions like LWE.

Amit Sahai, (Picture from WIRED http://www.wired.com/2014/02/cryptography-breakthrough/)

Private Function Evaluation: A General Framework and Efficient Instantiations

Payman Mohassel

Payman presented a general framework for private function evaluation (PFE). PFE is similar to secure function evaluation (SFE), but contrary to SFE where the parties agree on a publicly known function F to be evaluated and only the inputs are private, PFE requires also that F itself is kept private, say, only known by one of the involved parties.

Applications of PFE include cases where the function to be evaluated is either classified, proprietary (i.e., protecting intellectual properties), or where it may in other ways reveal vulnerabilities. In addition, Payman pointed out, PFE may sometimes help increasing security in cases where too much information is leaked from the output of an SFE evaluation.

PFE constructions follow immediately by combining universal circuits, such as Valiants construction from 1986, with standard SFE. As a consequence, Payman explained, all feasibility results from SFE carries over to PFE and the focus of current PFE research hence is on efficiency rather than feasibility.

Most existing PFE constructions, with the exception of a result of Kolesnikov and Schneider (2008), are indeed based on universal circuits, combined with general MPC such as Yao or GMW in the case of boolean circuits or HE-based MPC such as that of Cramer, Damgård and Nielsen (2001) for arithmetic circuits. The downside of these PFE solutions based on universal circuits is their asymptotic complexity which is super-linear in the size of the circuit. Furthermore, PFE based on universal circuits tend to be complicated to implement in practice.

The key idea of the PFE framework that Payman presented in this talk is based on the observation that universal circuits essentially carries out two distinct jobs when used for PFE:

They hide the topology of the circuit itself, i.e. the specific wiring of the gates and
They hide the function that each gate implements, i.e., whether a gate is an AND, XOR, NOT gate for a boolean circuit, etc.

With this insights, Payman and his colleagues were able to avoid resorting to universal circuits by instead splitting PFE into two separate ideal functionalities: One for circuit topology hiding (CTH) and another for private gate evaluation (PGE). As a consequence, their PFE framework becomes quite flexible, allowing each of the two functionalities, CTH and PGE, to be implemented by separate subprotocols in various ways. In particular, CTH can be realized either with any singly homomorphic encryption scheme, a general MPC or more specialized and efficient protocols. Depending on how the subprotocols for CTH and PGE are implemented, the properties of the resulting PFE vary, and Payman and his colleagues were able to achieve several results:

By combining the GMW protocol with a realization of CTH using additively homomorphic encryption, the first general multiparty PFE for boolean circuits with complexity linear in the circuit size is obtained.
By instead plugging in e.g. the protocol of Cramer, Damgård, and Nielsen (2001), the first general multiparty PFE for arithmetic circuits with linear complexity is obtained.
In the boolean circuit two-party case, by using instead the well-known Yao protocol, a two-party PFE protocol with linear complexity is achieved that improves on the only earlier result of Kolesnikov and Schneider (2008) that was not based on universal circuits.
In the above cases, by replacing the CTH implementation based on additively homomorphic encryption with one based on OTs, a PFE solution that despite its non-linear complexity has good concrete efficiency since OT-extension can be used.

Payman concluded by mentioning that, recently, their team managed to improve the protocols to also achieve linear complexity in the presence of a malicious adversary, and he pointed out some open problems such as how to increase security by also hiding the circuit size without using FHE, and how to improve the practicality of PFE by using only a linear amount of symmetric operations rather than public key operations.

Payman Mohassel

Adaptive MPC from New Notions of Non-Malleability

Muthu Venki

Muthu presented a general approach for obtaining adaptive-UC-security. He started his talk reviewing his work in STOC‘09 with Lin and Pass [LPV09], who considered only static adversaries.

Typically to obtain UC-security, it is necessary to show simulability of the honest parties and a flavor on Non-Malleability.
Usually both properties are obtained from a trusted setup. In [LPV09], their main insight was that the non-malleability requirement could be decoupled from the simulation requirement to achieve UC-security. Surprisingly, it is still the case even when considering adaptive security.The main ingredient to obtain that is a commitment scheme that satisfies a strong definition of non-malleability. The commitment scheme needs to be concurrent equivocal and non-malleable w.r.t. opening at the same time. It means that both it is possible to equivocate and even if to the concurrent MiM adversary is given a commitment and the relative opening it is still hard for him to come up with a commitment that opens to a related value. Notice that the MiM-adversary has to send the “right” commitment *before* receiving the “left” opening, i.e. the knowledge of the opening doesn’t allow the MiM adversary to equivocate his already committed value. The non-malleability is defined via extractability, interestingly the extractor can use rewind techniques (otherwise the definition collapse to standard UC-Commitment).

The main theorem is that adaptive UC-Puzzle + concurrent equivocal Non-Malleable Commitment scheme + simulatable public-key encryption scheme implies adaptively UC-MPC.UC-secure puzzle captures the property that no adversary can successfully complete a puzzle (an NP-Problem) and also obtain a trapdoor, but a simulator exists that can generate (correctly distributed) puzzles together with trapdoors. UC-Puzzle represent a unified framework for UC-security that allows to define many different models. The main theorem implies then as corollary that adaptively UC-MPC is realizable under many different kind of models. The approach lead to all previous results on adaptive concurrent secure computation, both in relaxed models (e.g., quasi-polynomial time simulation), as well as trusted setup models.

Muthu Venki

Aarhus MPC Workshop ’14, Thursday

May 10, 2014 by mpclounge

The Aarhus Crypto Group, hosting the event and taking care of this series of blog posts.

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

Yuval Ishai

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).

Yuval Ishai

Distributed Obfuscation and Non-Interactive Secure Multiparty Computation

Eyal Kushilevitz

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.

Eyal Kushilevitz

Indistinguishability Obfuscation from Semantically-Secure Multilinear Encodings

Rafael Pass

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.

Rafael Pass

2-party secure computation & applications

Abhi Shelat

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.

abhi shelat

Large-Scale Secure Computation

Elette Boyle

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 Rosulek

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 Archer

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.

Aarhus MPC Workshop ’14, Wednesday

May 8, 2014 by mpclounge

The abstract of the talks, as well as some of the slides are available here.

The participants.

5 Years of FHE

Zvika Brakerski

Fully Homomorphic Encryption (FHE) allows one to compute arbitrary functions over encrypted data without the decryption key. This problem was first raised by Rivest, Adleman, and Dertouzos in 1978. However, it was conjectured that this is impossible to achieve. 30 years after the introduction of the problem, Gentry gave an evidence that such an encryption exists, by proposing a candidate construction that is secure under relatively reasonable computational assumptions. Followup works used the same blueprint of Gentry but improved the construction in a number of dimensions. Most importantly, the computational assumptions considered were weakened to standard ones.

Unsurprisingly, FHE is “the swiss army knife of Cryptography”, as pointed out by Zvika, allowing for several cryptographic applications such as private information retrieval, multiparty secure computation, functional encryption, indistinguishability obfuscation – to name just a few. The talk focused on the properties we hope an FHE scheme to satisfy.

First of all, simplicity and security assumptions are important. Regarding efficiency, we care about the overhead of the evaluation function, the size of the keys/ciphertexts and the computation model.

Next, the talk moved to the “Second generation” FHE based on standard assumptions. The work of [BV11a] and the key-switching trick were presented.

Finally, the recent approximate eigenvector method of [GSW13] was described which eliminates the need of a key-switching in the evaluation key. The scheme of [GSW13] is simpler and asymptotically faster since homomorphic addition and multiplication are just matrix addition and multiplication.

To sum up, lots of exciting work has been done during the last 5 years on “improving” FHE.

Outsourced Pattern Matching

Carmit Hazay

The topic of Carmit Hazay’s talk was a line of work concerning outsourced pattern matching. Pattern matching is the problem where we have a text and a ”pattern” (a smaller string of text) and we want to determine all positions in the text where this pattern appears. In cryptography we want to study the setting where the text and pattern are held by different players (respectively the “sender” and the “receiver”) and the receiver should only learn the positions where the pattern appears (and nothing else about the rest of the text) while the sender should not get any information about the pattern. Carmit remarked that there are several known results using tools such as oblivious PRF, oblivious automaton evaluation or garbling. However all these works have the drawback that the complexity depends linearly on the size of the text.

That motivates the main topic of the talk, which is introducing a third party (a server) that will be used to execute most of the computations. This is especially interesting due to the recent advent of cloud computing services. The protocols in this setting have a preprocessing phase, where the sender sends a message to the server, and the query phase, where the receiver can interact with both sender and server. We aim to prevent the server from learning anything else than the number of the pattern matches, and we want to minimize as much as possible the communication between the receiver and the other parties during the query phase. Carmit discussed three recent works of hers in this topic (the first was a joint work with Sebastian Faust and Daniele Venturi, while the second was together with Hila Zarosim).

In her work with Sebastian and Daniele, optimal communication (linear in the length of the pattern and the number of matches) is achieved, but at the cost of using the random oracle model. Their solution involves having the server solve easy subset sum problems.
In her work with Zarosim, she proved that the limitation of working the random oracle model is inherent since it is impossible to have optimal protocols otherwise in the cases where the receiver may collude with the server, or see the preprocessed message from the sender.
Finally Carmit described recent results where she could bypass the imposibility result described before by assuming that the server cannot collude with other parties.

Carmit finished by describing a couple of possible future research directions. First, an interesting question is whether better solutions can be achieved if we allow a higher round complexity. Second, variations of the problem are also worth studying, an example being approximate pattern matching.

On the Intrinsic Complexity of Broadcast

Martin Hirt

Martin’s energetic talk.

The talk by Martin Hirt was about the intrinsic complexity of broadcasting. In the problem of broadcasting we assume that a dealer wants to broadcast a message among a set of n parties (where we count the dealer as a party as well) and each pair of parties is connected by a bidirectional secure channel. Furthermore t of the parties are corrupted. Our goals are consistency (the messages received by the different honest parties at the end of the protocol should be the same) and validity (if the dealer is honest, that message should be the one sent by the dealer). It is well known that, without extra assumptions, broadcast is impossible if (and only if) t>=n/3. Therefore, in order to achieve broadcasting one needs to have some extra assumption: there are solutions if we assume that some public key infrastructure has been set up by some trusted third party.

But a different point of view is to assume that we already have access to a broadcast primitive, only that this primitive is restricted in the sense that we can use it to broadcast only “small” messages, and wonder whether we can “amplify” this broadcast primitive, meaning that using this primitive together with additional communication between the players we can broadcast larger messages. Martin not only showed that this is possible, but in fact he could quantify how much of this resource it is sufficient and necessary to assume. He introduced a function to measure this, the intrinsic complexity of broadcasting among n players. Perhaps surprisingly it turns out that the bounds for this complexity do not depend on the size of the message being broadcasted.

For example, he showed that in the case n=3, if our primitive allows us to broadcast a message from a domain of size just 3, then we can use it to broadcast a message from an arbitrarily large domain. Moreover, in this case 3 is also a lower bound. In the protocol, the message is first circulated among the players in two different ways, and then the broadcast primitive is used to broadcast a “hint” (smaller than the message) which allows the honest players to eliminate possible discrepancies in the information received before.

In the case n>=4, Martin showed that broadcasting 8n log n bits in total by means of the primitive is enough to broadcast a message from an arbitrarily large domain. On the other hand, in this case we know that it is not sufficient to broadcast only n-3 bits through the primitive. The protocols in this case use the notion of graded broadcast, which was explained in the talk, where the players output a message and a grade which quantifying the player’s perception about the honesty of the dealer and about other player’s perceptions. Martin showed how to amplify graded broadcast and how to use this in turn to amplify broadcast.

A potentially interesting question is whether cryptographic (rather than perfect as in the talk) security would help bringing the complexity down.

Faster Private Set Intersection based on OT Extension

Benny Pinkas

The last talk of the 3rd day of the MPC workshop in Aarhus was titled “Faster Private Set Intersection based on OT Extension” and was presented by Benny Pinkas. The talk was a survey of existing solutions to the Private Set Intersection problem (PSI) as well as a new solution based on OT Extension. Also the work presented included actual implementations of all the surveyed protocols meant to enable meaningful comparison.

Benny starts off by introducing the PSI problem which in a nutshell consists of a client and a server each holding a set of items. The goal is that the client learns the intersection of these sets while the server learns nothing. Next a range of applications were presented including human genome and vehicle proximity testing, but clearly only your imagination sets the limits of the applications of PSI.

Before jumping to the current protocols for PSI, the model was covered. All protocols are phrased in the semi-honest model and some also employ random oracles for efficiency benefits. Also Benny explained a naive approach to solve the problem: Have the server hash each entry of his set and send the hashes to the client. The client can now perform hashes on his set and check for collisions. At first this approach could work, but a lot of the servers privacy is lost since the client can simply hash all kinds of items and check if the hashes match.

The survey covered 4 approaches where some of the approaches had additional optimizations and variants.

The first approach, dated back to 86′, was based on the DDH assumption + random oracles and was indeed very simple and elegant both in terms of computation and communication. Also the work performed was trivially parallelizible.
The next was based on a blind RSA approach, but in this setting one party has to do all the computation wheres in the former DDH protocol the work was shared between client/server. It was clear that Benny prefer the DDH approach, also because of it being implementable using elliptic curves.
Next up was a generic circuit approach which employed a sorting network to first take the union of the two sets, sort them and compare adjacent elements (will be identical) and finally shuffle the elements to hide which indexes of the sets were indeed identical. To evaluate the circuit in a GMW approach OT-extension was heavily used and with recent optimizations for random-OTs this had a significant impact. Although it turns out this approach is the least efficient in the end, because of the generic nature of this approach it can be used in any setting.
Fourth approach was done on bloom filters and was also based on OT. There was no time to go into details of the scheme, but it was clear that the parties need to run an OT for each entry in the bloom filter. Since these entries could be random strings the random-OT optimizations could also be used here.

Finally Benny presented their new protocol for solving PSI which relied heavily on OT-extension as well. The idea was to implement a private equality tester using the OTs and run it for all elements in the sets in parallel. Thus the communication was O(n^2*\lambda). This could further be improved using hashing techniques and it turned out cuckoo hashing achieved the best results.

As a conclusion they showed tables comparing all the implementations of the above protocols and it was evident that the new protocol had the fastest running time of all the protocols. However the DDH approach, because of it’s simplicity had a better communication complexity.

The presentation was based on joint work with Thomas Schneider and Michael Zohner.

Aarhus MPC Workshop ’14, Tuesday Afternoon

May 8, 2014 by mpclounge

The abstract of the talks, as well as some of the slides are available here.

The audience

Structured Encryption and Leakage Suppression

Seny Kamara

Seny Kamara gave a talk about an approach to encrypt databases and perform queries on the stored data. As usual in such a setting, the goal is to minimize leakage from storage and queries, while keeping the size of the encrypted data, the search time and the round complexity low. He started with an introduction into Searchable Symmetric Encryption(SSE) and ORAM. SSE is basically a two-party protocol between a server and a client, which allows not just to store and search a database, but also add or remove data. Such an SSE normally leaks information about the search or access pattern. On the other hand, ORAM-based solutions store a RAM (and not a database) and hide the access pattern. As a caveat, ORAMs are not optimized for searches and hence such a search must be simulated using read queries (with an inherent overhead). The idea is now to start from Structured Encryption(SE) and derive an ORAM scheme from it.

SE is a generalization of SSE, where other data structures than just a database can be encrypted. Such that it can be queried privately, and the queries will leak information over time. In order to accomplish the task of encrypted database queries, one has to augment such an SE with a “restructure” algorithm (this is not part of the original definition of SE) to bound and/or suppress leakage (trivially, this restructure algorithm should have small space complexity for the client). This restructuring is done using a transformation on the encrypted data structure using an encrypted dictionary. While the access pattern to the data structure continuously leaks information (until a transformation occurs), one cannot leak from the dictionary. The transformation does then return a new instance of the encrypted data structure and thereby invalidates the old leakage.

Seny then presented a formal construction, and information on three different implementations of the SE which have different types of leakage. Those schemes, together with a transform, then yield different asymptotics for the search.

Size-Hiding Secure Computation: Revisiting the Ideal Model

Melissa Chase

In the second talk in the afternoon session, Melissa Chase talked about size-hiding secure computation. In all existing definitions and constructions of secure computation, the size of the parties’ inputs is revealed. In her joint work with Rafail Ostrovsky and Ivan Visconti, Melissa considers secure two-party computation (2PC) where the size of one party’s input is private and constructs schemes for general functionalities that are secure against malicious adversaries under standard assumptions.

Size hiding is easily achieved in the case where a bound on the length of A’s input is known in advance. In this case, the input can simply be padded to this maximal length. Size hiding where there is no a priori polynomial bound on the parties’ input sizes has been considered for some specific functionalities. Last year, Yehuda Lindell, Kobbi Nissim and Claudio Orlandi (LNO13) investigated size-hiding secure computation for general functionalities in the semi-honest model. They defined several classes of size hiding, of which Melissa considers class 1.c: A’s input size |a| is hidden, but the input size |b| of B is revealed to A; only B receives the output f(a, b), and the length of the output is fixed.

In this setting, there is a problem when considering malicious adversaries who corrupt party A: Since A can choose its input freely, it cannot be excluded that, even though A is PPT, |a| is superpolynomial, but A can still execute the protocol, e.g. by somehow forming a valid commitment to a. In this case, the PPT simulator S is faced with the impossible task of extracting this superpolynomially long input in order to simulate. To prevent this, one can use a proof of polynomial work (PPW), and require A to prove that its input has polynomial size in addition to committing to it. There is no known way to construct PPW under standard assumptions, and they are shown to be necessary for general size-hiding 2PC against malicious adversaries as defined in LNO13. Melissa presented an interesting way out of this dilemma by using a polynomial-size representation of the input a instead of working with a directly. This requires a change in the security definition.

The first observation was that we require three properties from the ideal world in a simulation-based definition. It should 1) provide clear functionality and security guarantees, 2) be unconditionally secure and 3) be efficient. The last point rules out superpolynomial simulators. The key point here is that the trusted party T does not require a, it only needs to be able to compute f(a, b) for any b. The ideal model is changed so that A no longer gives its input a to T, but a polynomial-size representation rep(a) that uniquely defines a, along with a circuit C that computes both f(a, .) as well as a statistically sound and PPT-verifiable proof that the computation was done correctly. The trusted party then runs C on input b to obtain y and a proof that y = f(a, b). It outputs y to B if the proof is valid, otherwise it throws a special error that can only occur in the ideal world. Now the simulator needs to come up with rep(a) and C, but both are guaranteed to be of polynomial size. Security is defined as usual: For all PPT attackers A there is a PPT simulator S such that S almost never causes T to output the special error and the real world is indistinguishable from the ideal world. A nice feature of this definition is its equivalence to the standard definition in the case that input sizes are public and polynomial and a can be extracted from its representation in time poly(|a|).

The paper also contains a construction to show that this new notion is achievable under standard assumptions, but this was skipped in the talk due to the lack of time resulting from the questions and the lively discussion during the presentation.

Arithmetic Cryptography

Benny Applebaum

Wednesday’s last talk was given by Benny Applebaum under the title “arithmetic cryptography”. Benny started by pointing out that arithmetic circuits are much better suited for some tasks than arithmetic circuits, since boolean simulation can be expensive, non-modular and in some cases even infeasible. An arithmetic circuit parametrized by a field F takes as input a vector of field elements and provides in addition to the standard field operations zero comparison and choice of a random field element and the neutral elements. This allows solving linear equations, but not less-than comparison or operations on the bit representation of field elements, which is completely concealed to the point that no information on the length of the bit representation is available. While honest parties are modeled as arithmetic circuits, the adversary in this setting is non-arithmetic and allowed to choose the concrete field F that is used in the computation.

Previous work showed that several information theoretic primitives can be implemented in this model, such as one-time pads, one-time MACs, secret sharing and MPC over fields, and randomized encodings. Computational primitives were only known to be implementable in weaker models, where e. g. an arbitrary bit-representation of field elements is available or a special encoding scheme over F is given.

In this joint work with Jonathan Avron and Christina Brzuska, Benny found positive and negative results. Assuming pseudorandmness of noisy random linear codes, he shows that commitment, symmetric and public-key encryption, and arithmetic OT exist, which is sufficient for secure two-party computation. On the negative side, additively homomorphic encryption, arithmetic garbled circuits, and secure computation with “low” communication complexity are all impossible. This shows that the standard boolean model is different from the arithmetic model, which can explain some limitations of of previous constructions.

The rest of the talk consisted of the proof of an impossibility result in the arithmetic model.

Aarhus MPC Workshop ’14, Tuesday Morning

May 7, 2014 by mpclounge

The abstract of the talks, as well as some of the slides are available here.

Outsourcing RAM Computation

Daniel Wichs

Daniel delivered a talk on some recent exciting works on RAM computations. This talk was mostly based on two of his recent papers: (1) Garbled RAM, revisited [Published at Eurocrypt 2014] (joint work with Gentry, Halevi, Lu, Ostrovsky and Raykova) and (2) Outsourcing Private RAM computation [Available online] (joint work with Gentry, Halevi and Raykova). In general there are two equivalent models of computation in computer science: (i) Circuit and (ii) Random Access Machine (RAM in short) and most of the previous works concentrated only on circuits. One importance of considering RAM separately is that the equivalent circuit suffers from enormous blow up in size.

In this talk the main goal was to enable a weak client to leverage resources of a powerful server to compute some function P(x) (viewed as a program P in this model) without revealing the input x. The efficiency requirements are as follows: (a) Client does much less work than computing P(x) and the server does not work much than it is required to compute P(x). Previously, this kind of requirements were achieved using Fully Homomorphic Encryption but one might notice that FHE is only applicable on circuits, not on RAMs. To achieve their goal they used “Reusable/One-time garbled RAM” which was one of the most innovative parts of the talk. A well-aware reader might recall that although garbled circuits were quite famous from late 80’s and being used in numerous cryptographic applications since then, this direction of work considered “garbled RAM” for the first time. The term “reusable” refers to the fact that a garbled RAM can compute on several inputs (garbled, of course) instead of only one input which is applicable to one-time Garbled RAM. In this talk, Daniel explained both the one-time Garbled RAM as well as the Reusable variant although for simplicity he focused more on the one-time RAM

Talking more detail about the one-time garbled RAM, one may consider by assuming that a RAM consists of memory and a CPU such that the memory is a large array of data whereas the CPU does all the computations accessing the memory in some specified manner. Basically, the CPU can be considered as a circuit. Essentially they garbled the circuit of the CPU and then used PRF to protect the data and stored the key of the PRF inside the garbled CPU. So the security of the garbled RAM can be established from the security of the above mentioned well-known primitives. However, eventually there were some circular arguments in the proof which can only be solved using ID-based Encryption. He also talked about another possible fix solely based on OWF, but then the overhead (of server computation) becomes fairly large.

In the second part, he talked about Reusable garbled RAM briefly which essentially uses Reusable garbled circuit to garble the CPU instead of one-time garbling. But, they could not prove using the standard security notion of reusable circuit. Rather they introduced a weaker notion which can be instantiated using obfuscation.

RAM don't like being turned into circuits.

RAMs don’t like being turned into circuits.

Efficient Oblivious Transfer Extensions and Applications

Thomas Schneider

Thomas gave a talk considering the practicality of oblivious transfers (OT). The talk had two parts: How efficiently can we realize OT? And why is this so important? He answers the first question by considering that it has previously been established that there cannot exist a black box reduction of OT to a one way function (if there is this would imply P!=NP), but that it is possible to “extend” a few OTs into many OTs using a one way function. This is what is called an OT extension. A way of doing this is given in [IKNP03]. Thomas et al. implemented this protocol and discovered that, contrary to what one might expect, the computational bottleneck of this protocol was not any kind of cryptographic operations, but rather transposing a binary matrix. Thomas goes on to describe some optimizations of the original protocol which yields a much more efficient implementation. In the end the bottleneck remaining turns out to be network communication.

For the second part of the talk Thomas tells us a little about why OT is so interesting. First of all, besides it being a cornerstone of
general secure computation and in fact complete for secure computation, it can also be used to yield very efficient special
purpose protocols by itself. One example being privacy preserving face recognition. This computation can be done by comparing the hamming distance of a new picture and each reference picture in a database, which turns out to very efficiently realizable by OT.

Thomas Schneider

Reconstructing a shared secret in the presence of faulty shares – a survey

Serge Fehr

The talk presented the state of art about the t-out of-n secret sharing schemes (SSS) with the usually privacy property (any t shares give no information on the shared secret) and the *robust* reconstructability property. The latter means that we want to be able to reconstruct the secret even if t of the n shares are faulty. Unconditional security is considered and the dealer is assumed to be honest. An interesting application of these schemes can be found in solving the problem of secure data storage.

It is well-know that if t<n/3, Shamir’s scheme (plus Reed-Solomon decoding) gives a robust SSS, while if t>=n/2 the reconstruction of a shared secret in the presence of faulty shares is not possible. So the interesting interval is when n/3 <= t < n/2, for which the talk showed three different solutions, all of them having the robust reconstruction property, but with some small failure probability.

The first one is due to Rabin and Ben-Or (1989) and is based on Shamir’s scheme: the shares are computed evaluating polynomials of degree <=t, but now, in the sharing phase, the dealer will sent to player P_i the share s_i together with the pairs (k_ij, y_ji) where the y_ji is a MAC of the share s_i under the key k_ji (for any j=1,2,…,n). In other words the player P_i will receive his share, the MACs of his share and the keys necessary to verify all the other shares in the reconstruction phase. In the latter, a share will be accepted iff it is consistent with at least t+1 MACs from other players and then the secret is reconstructed using just the accepted shares. This scheme has good computational complexity, poly(k,n), but the overhead in the share size is Omega(k*n), where k is the security parameter.

The second scheme presented, due to Cramer, Damgard and Fehr (2001), exploits the idea that together with the secret the dealer can share a random element and a relation involving both of them (e.g. sharing the secret s, a random element r and their product, rxs, using Shamir’s scheme). Then in the reconstruction phase, we keep trying to reconstruct from different sets of t+1 shares until we find out that the reconstructed elements satisfy indeed the given relation. This scheme presents a lower share size overhead, O(k + n), but its reconstruction phase is computationally inefficient.

Finally, the recent solution by Cevallos, Fehr, Ostrovsky and Rabani (2012) was presented. In this scheme the sharing phase is exactly the same as in the Rabin&Ben-Or protocol, except for the fact that MACs with smaller tags and keys are used. That is, |k_ij|,|y_ij| = O(k/n) instead of O(k). To compensate for the higher probability in cheating in the MACs the reconstruction phase is done in a cleverer way: whenever a share is rejected, the correspondent player is eliminated from the consistency check list and it will not be considered when determining if the shares from the others players have to be rejected. The CFOR scheme achieves short shares of size O(k + n log(n)) and runs in polynomial time. Serge showed the security proof in order to underline that it is non-trivial and non-standard. Indeed in the new protocol it is not clear which is the best strategy for an adversary and there is a circular dependency in the definition of an accepted share.

Finding robust SSS with O(k) overhead (which is the proven lower bound) and adapting the solution for non-threshold access/adversary structure are some of the open problems which were illustrated briefly at the end of the talk.

Practical Private Database Querying

Vladimir Kolesnikov

The cool blind seer project logo.

In this talk, Vladimir Kolesnikov describes BLIND SEER, a scalable platform for privacy preserving database querying. This is a joint work with a large team from Columbia University and Toronto University, whose name is in fact an acronym that sheds light over the platform functionality, BLIND SEER: BLoom INDex SEarch of Encrypted Results.

This platform combines a number of engineering tricks with fine tuned cryptographic techniques to achieve private database
querying without large overheads, which makes it practical.

Traditional databases use different query languages (usually variations of SQL) to select and retrieve individual records out of
large data stores. These query languages allow an user to select records according to a number of parameters and/or relations between different records. However, in performing these searches, the database learns which records the user retrieves and the parameters used for the queries. Such leaks might be a huge liability in applications involving sensitive data and also in outsourcing of database engines.

The BLIND SEER infrastructure consists basically of a server that stores decryption keys, a index server that stores encrypted data in a structured format, a policy enforcement server that examines queries (guaranteeing they don’t break access policies) and an end user. As Vladimir and the team tried to come up with BLIND SEER to counter this information leakage, the first challenge encountered was to define what constitutes leakage and what kind of leakage is meaningful. These turns out to depend on the exact application and, of course, to be limited by the crypto graphical techniques employed.

In order to prevent leakage of search parameters and data access patterns, BLIND SEER uses a Bloom Filter (BF). This mechanism allows for querying keywords in constant time while having the same data access pattern for *every* search. Hence, if the BF is masked with a random pad, the index server cannot determine the concrete search parameters and retrieved records by observing the queries (which are also masked) or differences between access patterns of different queries (since the pattern is always the same).

Yao’s garbled circuits are used to make it possible for a user to perform a “masked query” that searches for a given keyword over a
binary tree of masked bloom filters stored in the index server.
Basically, the user obtains the appropriate mask from the decryption keys server and runs a (garbled) circuit with the index server where it inputs the mask and the index server inputs the masked BF. This circuit outputs the plaintext index (or corresponding decryption key) of the retrieved record to the user and nothing to the server. The system also offers security against malicious users who might deviate from the protocol by means of the policy checking server, which runs a policy checking circuit to verify access policies.

Unfortunately BLIND SEER can’t fully prevent leakage of access patterns. Due to the exact way the search tree is constructed and
traversed, the tree search pattern and the record access pattern are revealed in some types of queries. Nevertheless, this is a price this platform must pay for its very high efficiency, which is proportional to the number of query matches and appears to be asymptotically optimal for some types of queries.

Vladimir presented an interesting comparison of a (unoptimized) implementation of BLIND SEER and MySQL. Amazingly, for most types of queries, BLIND SEER performs pretty fast, being not too slower than MySQL. It is important to notice that the implementation used for this comparison was very basic and not optimized at all (not even parallel), so better performance results can be expected with further optimized implementations.

Aarhus MPC Workshop ’14, Monday

May 6, 2014 by mpclounge

The registration desk

Tutorials

Multilinear Maps

Sanjam Garg

The MPC workshop in Aarhus kicked off with a talk by Sanjam Garg on Multilinear Maps. The talk was divided into three parts: background on bilinear maps, definitions of multilinear maps and the concrete candidate construction of Garg, Gentry and Halevi.

At first background on bilinear maps was covered. We saw a number of applications of bilinear maps in cryptography, including non-interactive key agreement for 3 players by Joux’00. It was evident that a k-linear map implies non-interactive key agreement for k+1 players. Also the bilinear Diffie-Hellmann assumption was covered and we saw that standard DDH is easy in bilinear group.

Next we moved into the realm of multilinear maps and the definition from [BS03] was presented. This definition includes encoding procedure, uniformly sampling, possibility of equality testing and operators for addition and multiplication. Sanjam stressed that this definition is not what they achieve in their construction, but a relaxed version. In their construction each element has an associated noise (much like FHE) and this noise grows as one performs the addition and multiplication operations. As long as this noise stays under an a priori bound however, everything works out. This is why for most applications the approximation multilinear maps construction is sufficient.

In the concrete construction we work in two rings R = Z[x]/f(x) for an irreducible polynomial f(x) and R_q where the coefficient are in Z_q for a large q. In the setup of the scheme two trapdoors g \in R_q and z \in R_q^* are chosen once and for all. We let I = <g>, i.e. the ideal generated by g. The scheme now encodes elements of the quotient ring QR = R/I using z. Next Sanjam walked the audience through how this scheme fulfills the above requirements of a multilinear map, with some relaxations because of the noise. Finally a notion of re-randomization is introduced which is necessary to achieve security of the scheme. This included adding a large number of encoding to 0 to the public parameters which was then added to an encoding.

Lastly a brief overview of the security of the scheme was covered and it was mentioned that an adversary that only adds, subtracts, multiplies or divides pairs of elements an cannot break the scheme. This notion of security is similar to proofs in the generic group model.

Garbled Circuits Old and New

Vinod Vaikuntanatan

The talk focused on achieving Reusable Garbled Circuits(RGC) from Attribute-based Encryption(ABE): Yao’s original construction only gives you a Garbled Circuit (GC) that you can evaluate once (without compromising security). If you give the evaluator two different garbled inputs, mix-and-match attacks let the security break down. Moreover, Vinod explained other interesting and related notions such as Compact Garbled Circuits, which I will not discuss here.

The talk started with an introduction into ABE, which basically is a Public Key Encryption scheme with an additional (possibly public) attribute vector. The secret key is now tailored to a circuit C such that the decryption reveals the encrypted value if C evaluates to 1 during decryption. A particular flavor of ABE is called Two-Input ABE, where you encrypt to two values and obtain either of them during decryption (it’s like Rabin OT vs. 1 out of 2 OT). In order to construct such an ABE, one can use the Learning With Errors (LWE) assumption as follows: For a single use symmetric key ABE, one can let the secret key be a GC and the encryption of the message m be the input labels of the GC chosen according to the attribute vector, plus the xor of the output label and m. Now to make a full-fledged ABE out of it, one replaces the labels with functions, and at each gate we distill a new function out of the input functions. To actually implement that, these functions will be LWE samples (for fixed matrices), and the “distiller” at each gate applies linear transformations to these samples. Here you need some additional work to make the matrices “small” in order to bound the noise growth throughout the evaluation. To make it deterministic, one can use Learning With Rounding instead.

Afterwards, Vinod presented how to go from this ABE to a RGC that is only correct (without giving privacy). Here we give the evaluator the circuit C plus an instance of a Two-Input ABE, where the secret key is tailored for the circuit C. An input x is encoded as a ciphertext with two random values as messages and the input x as the label, and circuit evaluation consists of computing C(x) together with decrypting the correct value using the Two-Input ABE as the “proof of correctness”.

To get to full RGC, one then uses Fully Homomorphic Encryption(FHE) to encrypt everything and achieve privacy. But now the output of the evaluation is encrypted under the FHE. The solution now is to use a standard GC to give away a one-time decryption circuit for the output values of the encrypted weak RGC.