Eurocrypt 2013: Day Three, Secure Computation

On the third day of Eurocrypt, there were three presentations on secure computation. This post will cover two of them.

Tore Frederiksen from Aarhus University presented an efficiency improvement for active two party computation based on Yao's garbled circuits. The core component is an XOR-homomorphic commitment based on OT, which makes the approach compatible with garbled circuit optimizations like free-XOR. This was not the case for a previous work by the same group where they used Pedersen commitments. However, both use cut-and-choose at gate level as opposed to at circuit level to achieve active security.

Most of the talk was devoted to the XOR-homomorphic commitment scheme based on OT and a linear error correcting code. The latter is required to have secret-sharing properties in order to achieve hiding. To produce a commitment, the input is encoded using the code and then input to a k-out-of-n random-OT. For the binding property, the receiver selects some bits of the encoded vector to check them against the output of the OT protocol.

By using OT extension, the usage of asymmetric cryptography can be reduced to depend only on the security parameter. Furthermore, all protocols are parallelizable, which leads to an overall constant number of rounds.

At the end of the session, Hoeteck Wee from George Washington University gave a pleasant talk about a result on secure computation with limited interaction. In the so-called one-pass model, the parties interact with a server once in a fixed order, after which the server announces the result. There is some inherent leakage: If the server colludes with the last k parties, they can evaluation the function with all possible inputs from those parties

Previous work in this model covered symmetric functions like sum and majority, and proved that pseudo-random functions are impossible to compute. The contribution presented at the conference extends the achievable functions to sparse multi-variate polynomials (e.g., variance) and read-once branching programs (e.g., string matching, finite automata, second-prize auctions), which allow branching once per player.

The protocol works as follows: The server encrypts all possible outputs under the keys of all parties and the server in order according to the branching in the program, that is, the outer-most encryption is under the key of the party associated with the last branching. The parties then interact with the server in the reverse order, that is, the party associated to the last branching comes first. Every party picks the possible ciphertexts according to his input, decrypts them and sends them to the server, who forwards them to the next party. At the end, the server decrypts the result.

The complexity of the protocol is determined by the width of the branching program. If the server is honest, secrecy is guaranteed by the encryption under the public key of the server. However, if the server colludes with the last k parties, the protocol inherently leaks information as described above, but not more. To achieve active security, non-interactive zero-knowledge arguments can be used. Finally, the biggest open question is the gap between the functions known how to compute in this model and the impossibility result.