Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IOS Press eBooks

Randomization Techniques for Secure Computation

Yuval Ishai

Published Jan 1, 2013• 22 citations
Publisher

Abstract

To what extent can a computation be made “simpler” by settling for computing a randomized encoding of the output? Originating from Yao's seminal idea of garbled circuits, answers to this question have found applications in cryptography and elsewhere. We will survey the state of the art on different flavors of this question that are motivated by different problems in secure computation and correspond to different notions of simplicity.

DOI
10.3233/978-1-61499-169-4-222

Related papers

Equivocating Yao

Ran Canetti, Oxana Poburinnaya, Muthuramakrishnan Venkitasubramaniam

Yao's circuit garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable two-message, two-party secure computation, the scheme has been extended in many ways and has innumerable applications. Still, a basic question has remained open throughout the years: Can the scheme be extended to guarantee security in the face of an adversary that corrupts both parties, adaptively, as the computation proceeds?

ACM Symposium on Theory of Computing (STOC)•Jun 15, 2017•15 citations

Fast Garbling of Circuits Under Standard Assumptions.

Shay Gueron, Yehuda Lindell, Ariel Nof +1 more

Protocols for secure computation enable mutually distrustful parties to jointly compute on their private inputs without revealing anything but the result. Over recent years, secure com-putation has become practical and considerable effort has been made to make it more and more efficient. A highly important tool in the design of two-party protocols is Yao’s garbled circuit construction (Yao 1986), and multiple optimizations on this primitive have led to performance improvements of orders of magnitude over the last years. However, many of these improvements come at the price of making very strong assumptions on the underlying cryptographic primitives being used (e.g., that AES is secure for related keys, that it is circular secure, and even that it behaves like a random permutation when keyed with a public fixed key). The justification behind making these strong assumptions has been that otherwise it is not possible to achieve fast garbling and thus fast secure computation. In this paper, we take a step back and examine whether it is really the case that such strong assumptions are needed. We provide new methods for garbling that are secure solely under the assumption that the primitive used (e.g., AES) is a pseudorandom function. Our results show that in many cases, the penalty incurred is not significant, and so a more conservative approach to the assumptions being used can be adopted.

•Jan 1, 2015•0 citations

Fast Garbling of Circuits Under Standard Assumptions

Shay Gueron, Yehuda Lindell, Ariel Nof +1 more

Protocols for secure computation enable mutually distrustful parties to jointly compute on their private inputs without revealing anything but the result. Over recent years, secure computation has become practical and considerable effort has been made to make it more and more efficient. A highly important tool in the design of two-party protocols is Yao's garbled circuit construction (Yao 1986), and multiple optimizations on this primitive have led to performance improvements of orders of magnitude over the last years. However, many of these improvements come at the price of making very strong assumptions on the underlying cryptographic primitives being used (e.g., that AES is secure for related keys, that it is circular secure, and even that it behaves like a random permutation when keyed with a public fixed key). The justification behind making these strong assumptions has been that otherwise it is not possible to achieve fast garbling and thus fast secure computation. In this paper, we take a step back and examine whether it is really the case that such strong assumptions are needed. We provide new methods for garbling that are secure solely under the assumption that the primitive used (e.g., AES) is a pseudorandom function. Our results show that in many cases, the penalty incurred is not significant, and so a more conservative approach to the assumptions being used can be adopted.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 6, 2015•71 citations

Secure Two-Party Computation is Practical.

Benny Pinkas B, Thomas H. Schneider, Nigel Paul Smart +1 more

Abstract. Secure multi-party computation has been considered by the cryptographic community for a number of years. Until recently it has been a purely theoretical area, with few implementations with which to test various ideas. This has led to a number of optimisations being proposed which are quite restricted in their application. In this paper we describe an implementation of the two-party case, using Yao’s garbled circuits, and present various algorithmic protocol improvements. These optimisations are analysed both theoretically and empirically, using experiments of various adversarial situations. Our experimental data is provided for reasonably large circuits, including one which performs an AES encryption, a problem which we discuss in the context of various possible applications. 1

•Jan 1, 2009•1 citation

Efficient Secure Computation with Garbled Circuits

Yan Huang, Chih-Hao Shen, David Evans +2 more

Lecture notes in computer science•Jan 1, 2011•146 citations

How to Garble Arithmetic Circuits

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz Z

Yao's garbled circuit construction transforms a boolean circuit $C:\{0,1\}^n\to\{0,1\}^m$ into a “garbled circuit” $\hat{C}$ along with $n$ pairs of $k$-bit keys, one for each input bit, such that $\hat{C}$ together with the $n$ keys corresponding to an input $x$ reveal $C(x)$ and no additional information about $x$. The garbled circuit construction is a central tool for constant-round secure computation and has several other applications. Motivated by these applications, we suggest an efficient arithmetic variant of Yao's original construction. Our construction transforms an arithmetic circuit $C : \mathbb{Z}^n\to\mathbb{Z}^m$ over integers from a bounded (but possibly exponential) range into a garbled circuit $\hat{C}$ along with $n$ affine functions $L_i : \mathbb{Z}\to \mathbb{Z}^k$ such that $\hat{C}$ together with the $n$ integer vectors $L_i(x_i)$ reveal $C(x)$ and no additional information about $x$. The security of our construction relies on the intractability of the learning with errors problem.

SIAM Journal on Computing•Jan 1, 2014•34 citations
To what extent can a computation be made “simpler” by settling for computing a randomized encoding of the output? Originating from Yao's seminal idea of garbled circuits, answers to this question have found applications in cryptography and elsewhere. We will survey the state of the art on different flavors of this question that are motivated by different problems in secure computation and correspond to different notions of simplicity.
Protocols for secure computation enable mutually distrustful parties to jointly compute on their private inputs without revealing anything but the result. Over recent years, secure com-putation has become practical and considerable effort has been made to make it more and more efficient. A highly important tool in the design of two-party protocols is Yao’s garbled circuit construction (Yao 1986), and multiple optimizations on this primitive have led to performance improvements of orders of magnitude over the last years. However, many of these improvements come at the price of making very strong assumptions on the underlying cryptographic primitives being used (e.g., that AES is secure for related keys, that it is circular secure, and even that it behaves like a random permutation when keyed with a public fixed key). The justification behind making these strong assumptions has been that otherwise it is not possible to achieve fast garbling and thus fast secure computation. In this paper, we take a step back and examine whether it is really the case that such strong assumptions are needed. We provide new methods for garbling that are secure solely under the assumption that the primitive used (e.g., AES) is a pseudorandom function. Our results show that in many cases, the penalty incurred is not significant, and so a more conservative approach to the assumptions being used can be adopted.
Protocols for secure computation enable mutually distrustful parties to jointly compute on their private inputs without revealing anything but the result. Over recent years, secure computation has become practical and considerable effort has been made to make it more and more efficient. A highly important tool in the design of two-party protocols is Yao's garbled circuit construction (Yao 1986), and multiple optimizations on this primitive have led to performance improvements of orders of magnitude over the last years. However, many of these improvements come at the price of making very strong assumptions on the underlying cryptographic primitives being used (e.g., that AES is secure for related keys, that it is circular secure, and even that it behaves like a random permutation when keyed with a public fixed key). The justification behind making these strong assumptions has been that otherwise it is not possible to achieve fast garbling and thus fast secure computation. In this paper, we take a step back and examine whether it is really the case that such strong assumptions are needed. We provide new methods for garbling that are secure solely under the assumption that the primitive used (e.g., AES) is a pseudorandom function. Our results show that in many cases, the penalty incurred is not significant, and so a more conservative approach to the assumptions being used can be adopted.
Abstract. Secure multi-party computation has been considered by the cryptographic community for a number of years. Until recently it has been a purely theoretical area, with few implementations with which to test various ideas. This has led to a number of optimisations being proposed which are quite restricted in their application. In this paper we describe an implementation of the two-party case, using Yao’s garbled circuits, and present various algorithmic protocol improvements. These optimisations are analysed both theoretically and empirically, using experiments of various adversarial situations. Our experimental data is provided for reasonably large circuits, including one which performs an AES encryption, a problem which we discuss in the context of various possible applications. 1
Yao's garbled circuit construction transforms a boolean circuit C:{0,1}n→{0,1}mC:\{0,1\}^n\to\{0,1\}^mC:{0,1}n→{0,1}m into a “garbled circuit” C^\hat{C}C^ along with nnn pairs of kkk-bit keys, one for each input bit, such that C^\hat{C}C^ together with the nnn keys corresponding to an input xxx reveal C(x)C(x)C(x) and no additional information about xxx. The garbled circuit construction is a central tool for constant-round secure computation and has several other applications. Motivated by these applications, we suggest an efficient arithmetic variant of Yao's original construction. Our construction transforms an arithmetic circuit C:Zn→ZmC : \mathbb{Z}^n\to\mathbb{Z}^mC:Zn→Zm over integers from a bounded (but possibly exponential) range into a garbled circuit C^\hat{C}C^ along with nnn affine functions Li:Z→ZkL_i : \mathbb{Z}\to \mathbb{Z}^kLi​:Z→Zk such that C^\hat{C}C^ together with the nnn integer vectors Li(xi)L_i(x_i)Li​(xi​) reveal C(x)C(x)C(x) and no additional information about xxx. The security of our construction relies on the intractability of the learning with errors problem.