[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Reverse Firewalls for Oblivious Transfer Extension and Applications to Zero-Knowledge

  • Conference paper
  • First Online:
Advances in Cryptology – EUROCRYPT 2023 (EUROCRYPT 2023)

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

  • 1592 Accesses

Abstract

In the setting of subversion, an adversary tampers with the machines of the honest parties thus leaking the honest parties’ secrets through the protocol transcript. The work of Mironov and Stephens-Davidowitz (EUROCRYPT’15) introduced the idea of reverse firewalls (RF) to protect against tampering of honest parties’ machines. All known constructions in the RF framework rely on the malleability of the underlying operations in order for the RF to rerandomize/sanitize the transcript. RFs are thus limited to protocols that offer some structure, and hence based on public-key operations. In this work, we initiate the study of efficient Multiparty Computation (MPC) protocols in the presence of tampering. In this regard,

  • We construct the first Oblivious Transfer (OT) extension protocol in the RF setting. We obtain \(\textsf {poly}(\kappa )\) maliciously-secure OTs using \(\mathcal {O}(\kappa )\) public key operations and \(\mathcal {O}(1)\) inexpensive symmetric key operations, where \(\kappa \) is the security parameter.

  • We construct the first Zero-knowledge protocol in the RF setting where each multiplication gate can be proven using \(\mathcal {O}(1)\) symmetric key operations. We achieve this using our OT extension protocol and by extending the ZK protocol of Quicksilver (Yang, Sarkar, Weng and Wang, CCS’21) to the RF setting.

  • Along the way, we introduce new ideas for malleable interactive proofs that could be of independent interest. We define a notion of full malleability for Sigma protocols that unlike prior notions allow modifying the instance as well, in addition to the transcript. We construct new protocols that satisfy this notion, construct RFs for such protocols and use them in constructing our OT extension.

The key idea of our work is to demonstrate that correlated randomness may be obtained in an RF-friendly way without having to rerandomize the entire transcript. This enables us to avoid expensive public-key operations that grow with the circuit-size.

S. Chakraborty—The work was done while the author was at ETH Zurich. The author is supported in part by ERC grant 724307.

C. Ganesh—The author is supported by a Google India Faculty Research Award, and Infosys Young Investigator Award, Infosys Foundation.

P. Sarkar—The author is supported by NSF Awards 1931714, 1414119, and the DARPA SIEVE program.

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
£29.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
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 71.50
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 89.99
Price includes VAT (United Kingdom)
  • 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.

    Our cOT protocol allows the receiver to learn c bits of sender’s secret with probability \(2^{-c}\). We capture this leakage in the ideal functionality \(\mathcal {F}_{\textsf {cOT}}\), and show that this weakened functionality suffices for constructing OT-based RF friendly ZK protocol.

  2. 2.

    Each invocation of \(\mathcal {F}_{\textsf {rOT}}\) returns \((a_0, a_1)\) to the sender and \((b, a_b)\) to the receiver where \(a_0, a_1 \leftarrow _R\{0,1\}^\kappa \) and \(b\leftarrow _R\{0,1\}\) are randomly sampled by the functionality.

  3. 3.

    The \(\mathcal {F}_\textsf {RO}\) functionality is parametrized by 0 so that we can reuse the same functionality later for a different input/output pair by changing the parameter to 1.

References

  1. Ateniese, G., Magri, B., Venturi, D.: Subversion-resilient signature schemes. In: Ray, I., Li, N., Kruegel, C. (eds.) ACM CCS 2015, pp. 364–375. ACM Press, October 2015. https://doi.org/10.1145/2810103.2813635

  2. Ball, J., Borger, J., Greenwald, G., et al.: Revealed: how US and UK spy agencies defeat internet privacy and security. Know Your Neighborhood (2013)

    Google Scholar 

  3. Baum, C., Malozemoff, A.J., Rosen, M.B., Scholl, P.: Mac’n’cheese: zero-knowledge proofs for boolean and arithmetic circuits with nested disjunctions. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021, Part IV. LNCS, vol. 12828, pp. 92–122, Virtual Event. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84259-8_4

  4. Bellare, M., Micali, S.: Non-interactive oblivious transfer and applications. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 547–557. Springer, Cham (1990). https://doi.org/10.1007/0-387-34805-0_48

  5. Boyle, E., et al.: Efficient two-round OT extension and silent non-interactive secure computation. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J. (eds.) ACM CCS 2019, pp. 291–308. ACM Press, November 2019. https://doi.org/10.1145/3319535.3354255

  6. Byali, M., Patra, A., Ravi, D., Sarkar, P.: Fast and universally-composable oblivious transfer and commitment scheme with adaptive security. Cryptology ePrint Archive, Report 2017/1165 (2017). https://eprint.iacr.org/2017/1165

  7. Canetti, R., Sarkar, P., Wang, X.: Blazing fast OT for three-round UC OT extension. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020, Part II. LNCS, vol. 12111, pp. 299–327. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45388-6_11

  8. Canetti, R., Sarkar, P., Wang, X.: Efficient and round-optimal oblivious transfer and commitment with adaptive security. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020, Part III. LNCS, vol. 12493, pp. 277–308. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64840-4_10

  9. Canetti, R., Sarkar, P., Wang, X.: Triply adaptive UC NIZK. In: Agrawal, S., Lin, D. (eds.) Advances in Cryptology - ASIACRYPT 2022–28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, 5–9 December 2022, Proceedings, Part II. LNCS, vol. 13792, pp. 466–495. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22966-4_16

  10. Chakraborty, S., Dziembowski, S., Nielsen, J.B.: Reverse firewalls for actively secure MPCs. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020, Part II. LNCS, vol. 12171, pp. 732–762. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_26

  11. Chakraborty, S., Ganesh, C., Pancholi, M., Sarkar, P.: Reverse firewalls for adaptively secure MPC without setup. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13091, pp. 335–364. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92075-3_12

    Chapter  Google Scholar 

  12. Chakraborty, S., Ganesh, C., Sarkar, P.: Reverse firewalls for oblivious transfer extension and applications to zero-knowledge. IACR Cryptol. ePrint Arch., p. 1535 (2022). https://eprint.iacr.org/2022/1535, https://eprint.iacr.org/2022/1535

  13. Chakraborty, S., Magri, B., Nielsen, J.B., Venturi, D.: Universally composable subversion-resilient cryptography. In: Dunkelman, O., Dziembowski, S. (eds.) Advances in Cryptology - EUROCRYPT 2022–41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, 30 May–3 June 2022, Proceedings, Part I. LNCS, vol. 13275, pp. 272–302. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-06944-4_10

  14. Chase, M., Kohlweiss, M., Lysyanskaya, A., Meiklejohn, S.: Malleable proof systems and applications. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 281–300. Springer, Cham (2012). https://doi.org/10.1007/978-3-642-29011-4_18

  15. Chen, R., Mu, Y., Yang, G., Susilo, W., Guo, F., Zhang, M.: Cryptographic reverse firewall via malleable smooth projective hash functions. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part I. LNCS, vol. 10031, pp. 844–876. Springer, Cham (2016). https://doi.org/10.1007/978-3-662-53887-6_31

  16. Couteau, G., Rindal, P., Raghuraman, S.: Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021, Part III. LNCS, vol. 12827, pp. 502–534, Virtual Event. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84252-9_17

  17. Cramer, R., Damgård, I., Schoenmakers, B.: Proofs of partial knowledge and simplified design of witness hiding protocols. In: Desmedt, Y. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 174–187. Springer, Cham (1994). https://doi.org/10.1007/3-540-48658-5_19

  18. Diamond, B.E.: On the security of KOS. Cryptology ePrint Archive, Paper 2022/1371 (2022). https://eprint.iacr.org/2022/1371, https://eprint.iacr.org/2022/1371

  19. Dodis, Y., Farshim, P., Mazaheri, S., Tessaro, S.: Towards defeating backdoored random oracles: indifferentiability with bounded adaptivity. In: Pass, R., Pietrzak, K. (eds.) TCC 2020, Part III. LNCS, vol. 12552, pp. 241–273. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64381-2_9

  20. Dodis, Y., Ganesh, C., Golovnev, A., Juels, A., Ristenpart, T.: A formal treatment of backdoored pseudorandom generators. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part I. LNCS, vol. 9056, pp. 101–126. Springer, Cham (2015). https://doi.org/10.1007/978-3-662-46800-5_5

  21. Dodis, Y., Mironov, I., Stephens-Davidowitz, N.: Message transmission with reverse firewalls–secure communication on corrupted machines. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 341–372. Springer, Cham (2016). https://doi.org/10.1007/978-3-662-53018-4_13

  22. Doerner, J., Kondi, Y., Lee, E., Shelat, A.: Secure two-party threshold ECDSA from ECDSA assumptions. In: 2018 IEEE Symposium on Security and Privacy, pp. 980–997. IEEE Computer Society Press, May 2018. https://doi.org/10.1109/SP.2018.00036

  23. Fischlin, M., Janson, C., Mazaheri, S.: Backdoored hash functions: Immunizing HMAC and HKDF. In: Chong, S., Delaune, S. (eds.) CSF 2018 Computer Security Foundations Symposium, pp. 105–118. IEEE Computer Society Press (2018). https://doi.org/10.1109/CSF.2018.00015

  24. Ganesh, C., Magri, B., Venturi, D.: Cryptographic reverse firewalls for interactive proof systems. In: Czumaj, A., Dawar, A., Merelli, E. (eds.) ICALP 2020. LIPIcs, vol. 168, pp. 55:1–55:16. Schloss Dagstuhl, July 2020. https://doi.org/10.4230/LIPIcs.ICALP.2020.55

  25. Goldreich, O., Kahan, A.: How to construct constant-round zero-knowledge proof systems for NP. J. Cryptol. 9(3), 167–190 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  26. Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: Aho, A. (ed.) 19th ACM STOC, pp. 218–229. ACM Press, May 1987. https://doi.org/10.1145/28395.28420

  27. 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, Cham (2003). https://doi.org/10.1007/978-3-540-45146-4_9

  28. Jawurek, M., Kerschbaum, F., Orlandi, C.: Zero-knowledge using garbled circuits: how to prove non-algebraic statements efficiently. In: Sadeghi, A.R., Gligor, V.D., Yung, M. (eds.) ACM CCS 2013, pp. 955–966. ACM Press, November 2013. https://doi.org/10.1145/2508859.2516662

  29. Keller, M., Orsini, E., Scholl, P.: Actively secure OT extension with optimal overhead. In: Gennaro, R., Robshaw, M.J.B. (eds.) CRYPTO 2015, Part I. LNCS, vol. 9215, pp. 724–741. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47989-6_35

  30. Masny, D., Rindal, P.: Endemic oblivious transfer. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J. (eds.) ACM CCS 2019, pp. 309–326. ACM Press, November 2019. https://doi.org/10.1145/3319535.3354210

  31. Maurer, U.: Unifying zero-knowledge proofs of knowledge. In: Preneel, B. (ed.) AFRICACRYPT 2009. LNCS, vol. 5580, pp. 272–286. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02384-2_17

    Chapter  Google Scholar 

  32. Mironov, I., Stephens-Davidowitz, N.: Cryptographic reverse firewalls. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 657–686. Springer, Cham (2015). https://doi.org/10.1007/978-3-662-46803-6_22

  33. Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: Kosaraju, S.R. (ed.) 12th SODA, pp. 448–457. ACM-SIAM, January 2001

    Google Scholar 

  34. Patra, A., Sarkar, P., Suresh, A.: Fast actively secure OT extension for short secrets. In: 24th Annual Network and Distributed System Security Symposium, NDSS 2017, San Diego, California, USA, 26 February–1 March 2017. The Internet Society (2017)

    Google Scholar 

  35. Peikert, C., Vaikuntanathan, V., Waters, B.: A framework for efficient and composable oblivious transfer. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 554–571. Springer, Cham (2008). https://doi.org/10.1007/978-3-540-85174-5_31

  36. Schnorr, C.P.: Efficient identification and signatures for smart cards. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239–252. Springer, Cham (1990). https://doi.org/10.1007/0-387-34805-0_22

  37. Wang, X., Ranellucci, S., Katz, J.: Authenticated garbling and efficient maliciously secure two-party computation. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, pp. 21–37. ACM Press, October/November 2017. https://doi.org/10.1145/3133956.3134053

  38. Yang, K., Sarkar, P., Weng, C., Wang, X.: QuickSilver: efficient and affordable zero-knowledge proofs for circuits and polynomials over any field. In: Kim, Y., Kim, J., Vigna, G., Shi, E. (eds.) CCS 2021: 2021 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, Republic of Korea, 15–19 November 2021, pp. 2986–3001. ACM (2021)

    Google Scholar 

  39. Yang, K., Wang, X., Zhang, J.: More efficient MPC from improved triple generation and authenticated garbling. In: Ligatti, J., Ou, X., Katz, J., Vigna, G. (eds.) ACM CCS 2020, pp. 1627–1646. ACM Press, November 2020. https://doi.org/10.1145/3372297.3417285

  40. Yang, K., Weng, C., Lan, X., Zhang, J., Wang, X.: Ferret: fast extension for correlated OT with small communication. In: Ligatti, J., Ou, X., Katz, J., Vigna, G. (eds.) ACM CCS 2020, pp. 1607–1626. ACM Press, November 2020. https://doi.org/10.1145/3372297.3417276

Download references

Author information

Authors and Affiliations

  1. Visa Research, Palo Alto, USA

    Suvradip Chakraborty

  2. Indian Institute of Science, Bengaluru, India

    Chaya Ganesh

  3. Department of Computer Science, Boston University, Boston, USA

    Pratik Sarkar

Authors
  1. Suvradip Chakraborty
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chaya Ganesh
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pratik Sarkar
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pratik Sarkar .

Editor information

Editors and Affiliations

  1. Bar-Ilan University, Ramat Gan, Israel

    Carmit Hazay

  2. Simula UiB, Bergen, Norway

    Martijn Stam

Rights and permissions

Reprints and permissions

Copyright information

© 2023 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Chakraborty, S., Ganesh, C., Sarkar, P. (2023). Reverse Firewalls for Oblivious Transfer Extension and Applications to Zero-Knowledge. In: Hazay, C., Stam, M. (eds) Advances in Cryptology – EUROCRYPT 2023. EUROCRYPT 2023. Lecture Notes in Computer Science, vol 14004. Springer, Cham. https://doi.org/10.1007/978-3-031-30545-0_9

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-30545-0_9

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-30544-3

  • Online ISBN: 978-3-031-30545-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation