Improved Garbled Circuit Building Blocks and Applications to Auctions and Computing Minima

We consider generic Garbled Circuit (GC)-based techniques for Secure Function Evaluation (SFE) in the semi-honest model.

We describe efficient GC constructions for addition, subtraction, multiplication, and comparison functions. Our circuits for subtraction and comparison are approximately two times smaller (in terms of garbled tables) than previous constructions. This implies corresponding computation and communication improvements in SFE of functions using our efficient building blocks. The techniques rely on recently proposed “free XOR” GC technique.

Further, we present concrete and detailed improved GC protocols for the problem of secure integer comparison, and related problems of auctions, minimum selection, and minimal distance. Performance improvement comes both from building on our efficient basic blocks and several problem-specific GC optimizations. We provide precise cost evaluation of our constructions, which serves as a baseline for future protocols.

Supported by EU FP6 project SPEED, EU FP7 project CACE and ECRYPT II.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic €32.70 /Month

Buy Now

Price includes VAT (France)

eBook EUR 85.59 Price includes VAT (France)

Softcover Book EUR 105.49 Price includes VAT (France)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Preview

Similar content being viewed by others

On Multiparty Garbling of Arithmetic Circuits

Chapter © 2018

Garbled Circuits Checking Garbled Circuits: More Efficient and Secure Two-Party Computation

Chapter © 2013

Verifiable Multi-party Computation with Perfectly Private Audit Trail

Chapter © 2016

References

  1. Ahn, L.v., Hopper, N.J., Langford, J.: Covert two-party computation. In: ACM Symposium on Theory of Computing (STOC 2005), pp. 513–522. ACM, New York (2005) ChapterGoogle Scholar
  2. Aiello, W., Ishai, Y., Reingold, O.: Priced oblivious transfer: How to sell digital goods. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 119–135. Springer, Heidelberg (2001) ChapterGoogle Scholar
  3. Armknecht, F., Sadeghi, A.-R.: A new approach for algebraically homomorphic encryption. Cryptology ePrint Archive, Report 2008/422 (2008) Google Scholar
  4. Barni, M., Failla, P., Kolesnikov, V., Lazzeretti, R., Sadeghi, A.-R., Schneider, T.: Secure evaluation of private linear branching programs with medical applications. In: Backes, M., Ning, P. (eds.) ESORICS 2009. LNCS, vol. 5789, pp. 424–439. Springer, Heidelberg (2009), http://eprint.iacr.org/2009/195ChapterGoogle Scholar
  5. Beaver, D.: Precomputing oblivious transfer. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 97–109. Springer, Heidelberg (1995) Google Scholar
  6. 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) Google Scholar
  7. Blake, I.F., Kolesnikov, V.: Conditional encrypted mapping and comparing encrypted numbers. In: Di Crescenzo, G., Rubin, A. (eds.) FC 2006. LNCS, vol. 4107, pp. 206–220. Springer, Heidelberg (2006) ChapterGoogle Scholar
  8. Boneh, D., Goh, E.-J., Nissim, K.: Evaluating 2-dnf formulas on ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer, Heidelberg (2005) Google Scholar
  9. Boyar, J., Damgård, I., Peralta, R.: Short non-interactive cryptographic proofs. Journal of Cryptology 13(4), 449–472 (2000) ArticleMATHMathSciNetGoogle Scholar
  10. Boyar, J., Peralta, R.: Short discreet proofs. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 131–142. Springer, Heidelberg (1996) Google Scholar
  11. Boyar, J., Peralta, R., Pochuev, D.: On the multiplicative complexity of boolean functions over the basis ( ∧ , ⊕ , 1). Theor. Comput. Sci. 235(1), 43–57 (2000) ArticleMATHMathSciNetGoogle Scholar
  12. Brickell, J., Porter, D.E., Shmatikov, V., Witchel, E.: Privacy-preserving remote diagnostics. In: ACM Conference on Computer and Communications Security (CCS 2007), pp. 498–507. ACM, New York (2007) ChapterGoogle Scholar
  13. Di Crescenzo, G.: Private selective payment protocols. In: Frankel, Y. (ed.) FC 2000. LNCS, vol. 1962, pp. 72–89. Springer, Heidelberg (2001) ChapterGoogle Scholar
  14. Damgård, I., Geisler, M., Krøigaard, M.: Efficient and secure comparison for on-line auctions. In: Pieprzyk, J., Ghodosi, H., Dawson, E. (eds.) ACISP 2007. LNCS, vol. 4586, pp. 416–430. Springer, Heidelberg (2007) ChapterGoogle Scholar
  15. Damgård, I., Geisler, M., Krøigaard, M.: A correction to efficient and secure comparison for on-line auctions. Cryptology ePrint Archive, Report 2008/321 (2008) Google Scholar
  16. Damgård, I., Geisler, M., Krøigaard, M.: Homomorphic encryption and secure comparison. Journal of Applied Cryptology 1(1), 22–31 (2008) ArticleMATHGoogle Scholar
  17. Damgård, I., Jurik, M.: A generalisation, a simplification and some applications of paillier’s probabilistic public-key system. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119–136. Springer, Heidelberg (2001) ChapterGoogle Scholar
  18. Erkin, Z., Franz, M., Guajardo, J., Katzenbeisser, Lagendijk, I., Toft, T.: Privacy-preserving face recognition. In: Privacy Enhancing Technologies (PET 2009). LNCS, vol. 5672, pp. 235–253. Springer, Heidelberg (2009) ChapterGoogle Scholar
  19. Feigenbaum, J., Pinkas, B., Ryger, R.S., Saint-Jean, F.: Secure computation of surveys. In: EU Workshop on Secure Multiparty Protocols (SMP). ECRYPT (2004) Google Scholar
  20. Fischlin, M.: A cost-effective pay-per-multiplication comparison method for millionaires. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 457–472. Springer, Heidelberg (2001) ChapterGoogle Scholar
  21. Garay, J.A., Schoenmakers, B., Villegas, J.: Practical and secure solutions for integer comparison. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 330–342. Springer, Heidelberg (2007) ChapterGoogle Scholar
  22. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: ACM Symposium on Theory of Computing (STOC 2009), pp. 169–178. ACM, New York (2009) ChapterGoogle Scholar
  23. Giry, D., Quisquater, J.-J.: Cryptographic key length recommendation (March 2009), http://keylength.com
  24. Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and System Sciences 28(2), 270–299 (1984) ArticleMATHMathSciNetGoogle Scholar
  25. Goyal, V., Mohassel, P., Smith, A.: Efficient two party and multi party computation against covert adversaries. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 289–306. Springer, Heidelberg (2008) ChapterGoogle Scholar
  26. Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 145–161. Springer, Heidelberg (2003) Google Scholar
  27. Jarecki, S., Shmatikov, V.: Efficient two-party secure computation on committed inputs. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 97–114. Springer, Heidelberg (2007) ChapterGoogle Scholar
  28. Jarrous, A., Pinkas, B.: Secure hamming distance based computation and its applications. In: Applied Cryptography and Network Security (ACNS 2009). LNCS, vol. 5536, pp. 107–124. Springer, Heidelberg (2009) ChapterGoogle Scholar
  29. Karatsuba, A., Ofman, Y.: Multiplication of many-digital numbers by automatic computers. Proceedings of the SSSR Academy of Sciences 145, 293–294 (1962) Google Scholar
  30. Kerschbaum, F.: Practical privacy-preserving benchmarking. In: International Information Security Conference (SEC 2008), vol. 278, pp. 17–31 (2008) Google Scholar
  31. Kolesnikov, V.: Gate evaluation secret sharing and secure one-round two-party computation. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 136–155. Springer, Heidelberg (2005) ChapterGoogle Scholar
  32. Kolesnikov, V., Sadeghi, A.-R., Schneider, T.: Improved garbled circuit building blocks and applications to auctions and computing minima. Cryptology ePrint Archive, Report 2009/411 (2009) Google Scholar
  33. Kolesnikov, V., Schneider, T.: Improved garbled circuit: Free XOR gates and applications. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 486–498. Springer, Heidelberg (2008) ChapterGoogle Scholar
  34. Lindell, Y., Pinkas, B.: A proof of Yao’s protocol for secure two-party computation. ECCC Report TR04-063, Electronic Colloquium on Computational Complexity, ECCC (2004) Google Scholar
  35. Lindell, Y., Pinkas, B.: An efficient protocol for secure two-party computation in the presence of malicious adversaries. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 52–78. Springer, Heidelberg (2007) ChapterGoogle Scholar
  36. Lipmaa, H.: Verifiable homomorphic oblivious transfer and private equality test. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 416–433. Springer, Heidelberg (2003) Google Scholar
  37. Malkhi, D., Nisan, N., Pinkas, B., Sella, Y.: Fairplay — a secure two-party computation system. In: USENIX (2004) Google Scholar
  38. Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: ACM-SIAM Symposium On Discrete Algorithms (SODA 2001). Society for Industrial and Applied Mathematics, pp. 448–457 (2001) Google Scholar
  39. Naor, M., Pinkas, B., Sumner, R.: Privacy preserving auctions and mechanism design. In: ACM Conference on Electronic Commerce, pp. 129–139 (1999) Google Scholar
  40. Nielsen, J.B., Orlandi, C.: Lego for two-party secure computation. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 474–495. Springer, Heidelberg (2009) Google Scholar
  41. Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999) Google Scholar
  42. Paus, A., Sadeghi, A.-R., Schneider, T.: Practical secure evaluation of semi-private functions. In: Applied Cryptography and Network Security (ACNS 2009). LNCS, vol. 5536, pp. 89–106. Springer, Heidelberg (2009) ChapterGoogle Scholar
  43. Qi, Y., Atallah, M.J.: Efficient privacy-preserving k-nearest neighbor search. In: International Conference on Distributed Computing Systems (ICDCS 2008), pp. 311–319. IEEE, Los Alamitos (2008) Google Scholar
  44. Shaneck, M., Kim, Y., Kumar, V.: Privacy preserving nearest neighbor search. In: International Conference on Data Mining - Workshops (ICDMW 2006), pp. 541–545. IEEE, Los Alamitos (2006) ChapterGoogle Scholar
  45. Yao, A.C.: Protocols for secure computations. In: Symposium on Foundations of Computer Science (SFCS 1982), pp. 160–164. IEEE, Los Alamitos (1982) ChapterGoogle Scholar
  46. Yao, A.C.: How to generate and exchange secrets. In: IEEE Symposium on Foundations of Computer Science (FOCS 1986), pp. 162–167. IEEE, Los Alamitos (1986) ChapterGoogle Scholar

Author information

Authors and Affiliations

  1. Bell Laboratories, 600 Mountain Ave., Murray Hill, NJ 07974, USA Vladimir Kolesnikov
  2. Horst Görtz Institute for IT-Security, Ruhr-University Bochum, Germany Ahmad-Reza Sadeghi & Thomas Schneider
  1. Vladimir Kolesnikov