Zero-knowledge using garbled circuits: Or how to prove non-algebraic statements efficiently

TY - GEN

T1 - Zero-knowledge using garbled circuits

T2 - ACM SIGSAC Conference on Computer & Communications Security

AU - Jawurek, Marek

AU - Kerschbaum, Florian

AU - Orlandi, Claudio

N1 - Conference code: 20

PY - 2013/1/1

Y1 - 2013/1/1

N2 - Zero-knowledge protocols are one of the fundamental concepts in modern cryptography and have countless applications. However, after more than 30 years from their introduction, there are only very few languages (essentially those with a group structure) for which we can construct zero-knowledge protocols that are efficient enough to be used in practice. In this paper we address the problem of how to construct efficient zero-knowledge protocols for generic languages and we propose a protocol based on Yao's garbled circuit technique. The motivation for our work is that in many cryptographic applications it is useful to be able to prove efficiently statements of the form e.g., "I know x s.t.y = SHA-256(x)" for a common input y (or other " unstructured" languages), but no efficient protocols for this task are currently known. It is clear that zero-knowledge is a subset of secure two-party computation (i.e., any protocol for generic secure computation can be used to do zero-knowledge). The main contribution of this paper is to construct an efficient protocol for the special case of secure two-party computation where only one party has input (like in the zero-knowledge case). The protocol achieves active security and is essentially only twice as slow as the passive secure version of Yao's garbled circuit protocol. This is a great improvement with respect to the cut-n-choose technique to make Yao's protocol actively secure, where the complexity grows linearly with the security parameter.

AB - Zero-knowledge protocols are one of the fundamental concepts in modern cryptography and have countless applications. However, after more than 30 years from their introduction, there are only very few languages (essentially those with a group structure) for which we can construct zero-knowledge protocols that are efficient enough to be used in practice. In this paper we address the problem of how to construct efficient zero-knowledge protocols for generic languages and we propose a protocol based on Yao's garbled circuit technique. The motivation for our work is that in many cryptographic applications it is useful to be able to prove efficiently statements of the form e.g., "I know x s.t.y = SHA-256(x)" for a common input y (or other " unstructured" languages), but no efficient protocols for this task are currently known. It is clear that zero-knowledge is a subset of secure two-party computation (i.e., any protocol for generic secure computation can be used to do zero-knowledge). The main contribution of this paper is to construct an efficient protocol for the special case of secure two-party computation where only one party has input (like in the zero-knowledge case). The protocol achieves active security and is essentially only twice as slow as the passive secure version of Yao's garbled circuit protocol. This is a great improvement with respect to the cut-n-choose technique to make Yao's protocol actively secure, where the complexity grows linearly with the security parameter.

UR - https://www.scopus.com/pages/publications/84888985541

U2 - 10.1145/2508859.2516662

DO - 10.1145/2508859.2516662

M3 - Article in proceedings

SN - 9781450324779

T3 - Proceedings of the ACM Conference on Computer and Communications Security

SP - 955

EP - 966

BT - Proceedings of the ACM Conference on Computer and Communications Security, CCS '13

A2 - Sadeghi , Ahmad-Reza

A2 - Gligor, Virgil

A2 - Yung , Moti

PB - Association for Computing Machinery

Y2 - 4 November 2013 through 8 November 2013

ER -