Abstract
We propose Gate Evaluation Secret Sharing (GESS) – a new kind of secret sharing, designed for use in secure function evaluation (SFE) with minimal interaction. The resulting simple and powerful GESS approach to SFE is a generalization of Yao’s garbled circuit technique.
We give efficient GESS schemes for evaluating binary gates and prove (almost) matching lower bounds. We give a more efficient information-theoretic reduction of SFE of a boolean formula F to oblivious transfer. Its complexity is ≈ ∑ d i 2, where d i is the depth of the i-th leaf of F.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Algesheimer, J., Cachin, C., Camenisch, J., Karjoth, G.: Cryptographic security for mobile code. In: SP 2001: Proceedings of the IEEE Symposium on Security and Privacy, p. 2. IEEE Computer Society Press, Los Alamitos (2001)
Barrington, D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. In: Proc. 18th ACM Symp. on Theory of Computing, pp. 1–5. ACM Press, New York (1986)
Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols. In: Proc. 22nd ACM Symp. on Theory of Computing, pp. 503–513 (1990)
Beaver, D.: Minimal-latency secure function evaluation. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 335–350. Springer, Heidelberg (2000)
Blake, I.F., Kolesnikov, V.: Strong conditional oblivious transfer and computing on intervals. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 515–529. Springer, Heidelberg (2004)
Bonet, M.L., Buss, S.R.: Size-depth tradeoff for boolean formulae. Information Processing Letters 11, 151–155 (1994)
Bshouty, N.H., Cleve, R., Eberly, W.: Size-depth tradeoffs for algebraic formulae. In: Proc. 32nd IEEE Symp. on Foundations of Comp. Science, pp. 334–341. IEEE, Los Alamitos (1991)
Cachin, C., Camenisch, J., Kilian, J., Muller, J.: One-round secure computation and secure autonomous mobile agents. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, p. 512. Springer, Heidelberg (2000)
Cleve, R.: Towards optimal simulations of formulas by bounded-width programs. In: STOC 1990: Proceedings of the twenty-second annual ACM symposium on Theory of computing, pp. 271–277. ACM Press, New York (1990)
Cramer, R., Fehr, S., Ishai, Y., Kushilevitz, E.: Efficient multi-party computation over rings. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 596–613. Springer, Heidelberg (2003)
Feige, U., Killian, J., Naor, M.: A minimal model for secure computation (extended abstract). In: Proc. 26th ACM Symp. on Theory of Computing, pp. 554–563. ACM Press, New York (1994)
Feldman, P., Micali, S.: An optimal probabilistic protocol for synchronous byzantine agreement. SIAM J. Comput. 26(4), 873–933 (1997)
Fischlin, M.: A cost-effective pay-per-multiplication comparison method for millionaires. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 457–471. Springer, Heidelberg (2001)
Giel, O.: Branching program size is almost linear in formula size. J. Comput. Syst. Sci. 63(2), 222–235 (2001)
Goldreich, O.: Foundations of Cryptography. Basic Applications, vol. 2. Cambridge University Press, Cambridge (2004)
Goldreich, O., Vainish, R.: How to solve any protocol problem - an efficiency improvement. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 73–86. Springer, Heidelberg (1988)
Ishai, Y., Kushilevitz, E.: Private simultaneous messages protocols with applications. In: ISTCS 1997: Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems (ISTCS 1997), Washington, DC, USA, p. 174. IEEE Computer Society, Los Alamitos (1997)
Ishai, Y., Kushilevitz, E.: Randomizing polynomials: A new representation with applications to round-efficient secure computation. In: Proc. 41th IEEE Symp. on Foundations of Comp. Science, p. 294. IEEE Computer Society, Los Alamitos (2000)
Ishai, Y., Kushilevitz, E.: Perfect constant-round secure computation via perfect randomizing polynomials. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 244–256. Springer, Heidelberg (2002)
Kilian, J.: Founding cryptography on oblivious transfer. In: Proc. 20th ACM Symp. on Theory of Computing, Chicago, pp. 20–31. ACM, New York (1988)
Lindell, Y., Pinkas, B.: A proof of Yao’s protocol for secure two-party computation. Cryptology ePrint Archive, Report 2004/175 (2004), http://eprint.iacr.org/
Naor, M., Nissim, K.: Communication preserving protocols for secure function evaluation. In: STOC 2001: Proceedings of the thirty-third annual ACM symposium on Theory of computing, pp. 590–599. ACM Press, New York (2001)
Naor, M., Pinkas, B.: Distributed oblivious transfer. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 205–219. Springer, Heidelberg (2000); vol. 293
Naor, M., Pinkas, B., Sumner, R.: Privacy preserving auctions and mechanism design. In: 1st ACM Conf. on Electronic Commerce, pp. 129–139 (1999)
Rogaway, P.: The round complexity of secure protocols. PhD thesis. MIT (1991)
Sander, T., Young, A., Yung, M.: Non-interactive cryptocomputing for NC 1. In: Proceedings 40th IEEE Symposium on Foundations of Computer Science, pp. 554–566. IEEE, New York (1999)
Yao, A.C.: How to generate and exchange secrets. In: Proc. 27th IEEE Symp. on Foundations of Comp. Science, Toronto, pp. 162–167. IEEE, Los Alamitos (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kolesnikov, V. (2005). Gate Evaluation Secret Sharing and Secure One-Round Two-Party Computation. In: Roy, B. (eds) Advances in Cryptology - ASIACRYPT 2005. ASIACRYPT 2005. Lecture Notes in Computer Science, vol 3788. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11593447_8
Download citation
DOI: https://doi.org/10.1007/11593447_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30684-9
Online ISBN: 978-3-540-32267-2
eBook Packages: Computer ScienceComputer Science (R0)