Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Distributed Protocols for Oblivious Transfer and Polynomial Evaluation

  • Conference paper
  • First Online:
Progress in Cryptology – INDOCRYPT 2023 (INDOCRYPT 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14460))

Included in the following conference series:

  • 152 Accesses

Abstract

A secure multiparty computation (MPC) allows several parties to compute a function over their inputs while keeping their inputs private. In its basic setting, the protocol involves only parties that hold inputs. In distributed MPC, there are also external servers who perform a distributed protocol that executes the needed computation, without learning information on the inputs and outputs. Here we propose distributed protocols for several fundamental MPC functionalities. We begin with a Distributed Scalar Product (DSP) protocol for computing scalar products of private vectors. We build upon DSP in designing various protocols for Oblivious Transfer (OT): k-out-of-N OT, Priced OT, and Generalized OT. We also use DSP for Oblivious Polynomial Evaluation (OPE) and Oblivious Multivariate Polynomial Evaluation (OMPE). All those problems involve a sender and a receiver that hold private vectors and they wish to compute their scalar product. However, in each of these problems the receiver must submit a vector of a specified form. Hence, a crucial ingredient in our protocols is a sub-protocol for validating that the receiver’s vector complies with the relevant restrictions, without learning anything else on that vector. Therefore, while previous studies presented distributed protocols for 1-out-of-N OT and OPE, our protocols are the first ones that are secure against malicious receivers. Our distributed protocols for the other OT variants and for OMPE are the first ones that handle such problems. Our protocols offer information-theoretic security, under the assumption that the servers are semi-honest and have an honest majority, and they are very efficient.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 49.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 64.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    In our discussion of related work we replace the original parameter notations with the ones that we used in the present work, for consistency and clarity.

References

  1. Aiello, B., 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). https://doi.org/10.1007/3-540-44987-6_8

    Chapter  Google Scholar 

  2. Alwen, J., Katz, J., Lindell, Y., Persiano, G., shelat, A., Visconti, I.: Collusion-free multiparty computation in the mediated model. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 524–540. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_31

    Chapter  Google Scholar 

  3. Alwen, J., Shelat, A., Visconti, I.: Collusion-free protocols in the mediated model. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 497–514. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_28

    Chapter  Google Scholar 

  4. Blundo, C., D’Arco, P., De Santis, A., Stinson, D.R.: On unconditionally secure distributed oblivious transfer. J. Cryptol. 20(3), 323–373 (2007)

    Article  MathSciNet  Google Scholar 

  5. Brassard, G., Crepeau, C., Robert, J.-M.: All-or-nothing disclosure of secrets. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 234–238. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_17

    Chapter  Google Scholar 

  6. Catrina, O., Kerschbaum, F.: Fostering the uptake of secure multiparty computation in e-commerce. In: ARES, pp. 693–700 (2008)

    Google Scholar 

  7. Chor, B., Kushilevitz, E., Goldreich, O., Sudan, M.: Private information retrieval. J. ACM 45(6), 965–981 (1998)

    Article  MathSciNet  Google Scholar 

  8. Cianciullo, L., Ghodosi, H.: Unconditionally secure oblivious polynomial evaluation: a survey and new results. J. Comput. Sci. Technol. 37(2), 443–458 (2022)

    Article  Google Scholar 

  9. Corniaux, C.L.F., Ghodosi, H.: Scalar product-based distributed oblivious transfer. In: Rhee, K.-H., Nyang, D.H. (eds.) ICISC 2010. LNCS, vol. 6829, pp. 338–354. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-24209-0_23

    Chapter  Google Scholar 

  10. Damgård, I., Ishai, Y.: Constant-round multiparty computation using a black-box pseudorandom generator. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 378–394. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_23

    Chapter  Google Scholar 

  11. Dery, L., Tassa, T., Yanai, A.: Fear not, vote truthfully: secure multiparty computation of score based rules. Expert Syst. Appl. 168, 114434 (2021)

    Article  Google Scholar 

  12. Dery, L., Tassa, T., Yanai, A., Zamarin, A.: Demo: a secure voting system for score based elections. In: CCS, pp. 2399–2401 (2021)

    Google Scholar 

  13. Du, W., Atallah, M.J.: Privacy-preserving cooperative statistical analysis. In: ACSAC, pp. 102–110 (2001)

    Google Scholar 

  14. Du, W., Zhan, J.Z.: A practical approach to solve secure multi-party computation problems. In: NSPW, pp. 127–135 (2002)

    Google Scholar 

  15. Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Commun. ACM 28(6), 637–647 (1985)

    Article  MathSciNet  Google Scholar 

  16. Ben Horin, A., Tassa, T.: Privacy preserving collaborative filtering by distributed mediation. In: RecSys, pp. 332–341 (2021)

    Google Scholar 

  17. Ishai, Y., Kushilevitz, E.: Private simultaneous messages protocols with applications. In: ISTCS, pp. 174–184 (1997)

    Google Scholar 

  18. Kamara, S., Mohassel, P., Raykova, M.: Outsourcing multi-party computation. IACR Cryptology ePrint Archive (2011). 272

    Google Scholar 

  19. Kilian, J.: Founding cryptography on oblivious transfer. In: STOC, pp. 20–31 (1988)

    Google Scholar 

  20. Kolesnikov, V., Kumaresan, R., Rosulek, M., Trieu, N.: Efficient batched oblivious PRF with applications to private set intersection. In: CCS, pp. 818–829 (2016)

    Google Scholar 

  21. Kushilevitz, E., Ostrovsky, R.: Replication is NOT needed: SINGLE database, computationally-private information retrieval. In: FOCS, pp. 364–373 (1997)

    Google Scholar 

  22. Li, H.-D., Yang, X., Feng, D., Li, B.: Distributed oblivious function evaluation and its applications. J. Comput. Sci. Technol. 19(6), 942–947 (2004)

    Article  MathSciNet  Google Scholar 

  23. Naor, M., Pinkas, B.: Oblivious transfer and polynomial evaluation. In: STOC, pp. 245–254 (1999)

    Google Scholar 

  24. Naor, M., Pinkas, B.: Distributed oblivious transfer. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 205–219. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44448-3_16

    Chapter  Google Scholar 

  25. Nikov, V., Nikova, S., Preneel, B., Vandewalle, J.: On unconditionally secure distributed oblivious transfer. In: Menezes, A., Sarkar, P. (eds.) INDOCRYPT 2002. LNCS, vol. 2551, pp. 395–408. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-36231-2_31

    Chapter  Google Scholar 

  26. Rabin, M.O.: How to exchange secrets by oblivious transfer. Technical Report TR-81, Aiken Computation Laboratory, Harvard University (1981)

    Google Scholar 

  27. Schneider, J.: Lean and fast secure multi-party computation: minimizing communication and local computation using a helper. In: SECRYPT, pp. 223–230 (2016)

    Google Scholar 

  28. Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979)

    Article  MathSciNet  Google Scholar 

  29. Shmueli, E., Tassa, T.: Mediated secure multi-party protocols for collaborative filtering. ACM Trans. Intell. Syst. Technol. 11, 1–25 (2020)

    Article  Google Scholar 

  30. Tassa, T.: Generalized oblivious transfer by secret sharing. Des. Codes Cryptogr. 58(1), 11–21 (2011)

    Article  MathSciNet  Google Scholar 

  31. Tassa, T., Dyn, N.: Multipartite secret sharing by bivariate interpolation. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 288–299. Springer, Heidelberg (2006). https://doi.org/10.1007/11787006_25

    Chapter  Google Scholar 

  32. Tassa, T., Grinshpoun, T., Yanai, A.: PC-SyncBB: a privacy preserving collusion secure DCOP algorithm. Artif. Intell. 297, 103501 (2021)

    Article  MathSciNet  Google Scholar 

  33. Tassa, T., Jarrous, A., Ben-Ya’akov, Y.: Oblivious evaluation of multivariate polynomials. J. Math. Cryptol. 7(1), 1–29 (2013)

    Article  MathSciNet  Google Scholar 

  34. Vaidya, J., Clifton, C.: Privacy preserving association rule mining in vertically partitioned data. In: SIGKDD, pp. 639–644 (2002)

    Google Scholar 

  35. Yao, A.C.: Protocols for secure computation. In: FOCS, pp. 160–164 (1982)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. The Open University of Israel, Ra’anana, Israel

    Aviad Ben Arie & Tamir Tassa

Authors
  1. Aviad Ben Arie
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tamir Tassa
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tamir Tassa .

Editor information

Editors and Affiliations

  1. Nanyang Technological University, Singapore, Singapore

    Anupam Chattopadhyay

  2. Nanyang Technological University, Singapore, Singapore

    Shivam Bhasin

  3. Radboud University, Nijmegen, The Netherlands

    Stjepan Picek

  4. Indian Institute of Technology Madras, Chennai, India

    Chester Rebeiro

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Ben Arie, A., Tassa, T. (2024). Distributed Protocols for Oblivious Transfer and Polynomial Evaluation. In: Chattopadhyay, A., Bhasin, S., Picek, S., Rebeiro, C. (eds) Progress in Cryptology – INDOCRYPT 2023. INDOCRYPT 2023. Lecture Notes in Computer Science, vol 14460. Springer, Cham. https://doi.org/10.1007/978-3-031-56235-8_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-56235-8_4

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-56234-1

  • Online ISBN: 978-3-031-56235-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation