LEGO for two-party secure computation. (English) Zbl 1213.94124

Nielsen, Jesper Buus; Orlandi, Claudio

Reingold, Omer (ed.), Theory of cryptography. 6th theory of cryptography conference, TCC 2009, San Francisco, CA, USA, March 15–17, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-00456-8/pbk). Lecture Notes in Computer Science 5444, 368-386 (2009).

Summary: This paper continues the recent line of work of making Yao’s garbled circuit approach to two-party computation secure against an active adversary. We propose a new cut-and-choose based approach called LEGO (Large Efficient Garbled-circuit Optimization): It is specifically aimed at large circuits. Asymptotically it obtains a factor \(\log|\mathcal{C}|\) improvement in computation and communication over previous cut-and-choose based solutions, where \(|\mathcal{C}|\) is the size of the circuit being computed. The protocol is universally composable (UC) in the OT-hybrid model against a static, active adversary.
For the entire collection see [Zbl 1156.94005].

MSC:

94A60

Cryptography