Cryptographic Reverse Firewalls for Interactive Proof Systems

Authors Chaya Ganesh, Bernardo Magri, Daniele Venturi



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.55.pdf
  • Filesize: 0.51 MB
  • 16 pages

Document Identifiers

Author Details

Chaya Ganesh
  • Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India
Bernardo Magri
  • Department of Computer Science, Aarhus University, Denmark
Daniele Venturi
  • Department of Computer Science, Sapienza University of Rome, Italy

Cite AsGet BibTex

Chaya Ganesh, Bernardo Magri, and Daniele Venturi. Cryptographic Reverse Firewalls for Interactive Proof Systems. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.55

Abstract

We study interactive proof systems (IPSes) in a strong adversarial setting where the machines of honest parties might be corrupted and under control of the adversary. Our aim is to answer the following, seemingly paradoxical, questions: - Can Peggy convince Vic of the veracity of an NP statement, without leaking any information about the witness even in case Vic is malicious and Peggy does not trust her computer? - Can we avoid that Peggy fools Vic into accepting false statements, even if Peggy is malicious and Vic does not trust her computer? At EUROCRYPT 2015, Mironov and Stephens-Davidowitz introduced cryptographic reverse firewalls (RFs) as an attractive approach to tackling such questions. Intuitively, a RF for Peggy/Vic is an external party that sits between Peggy/Vic and the outside world and whose scope is to sanitize Peggy’s/Vic’s incoming and outgoing messages in the face of subversion of her/his computer, e.g. in order to destroy subliminal channels. In this paper, we put forward several natural security properties for RFs in the concrete setting of IPSes. As our main contribution, we construct efficient RFs for different IPSes derived from a large class of Sigma protocols that we call malleable. A nice feature of our design is that it is completely transparent, in the sense that our RFs can be directly applied to already deployed IPSes, without the need to re-implement them.

Subject Classification

ACM Subject Classification
  • Security and privacy → Cryptography
Keywords
  • Subversion
  • Algorithm substitution attacks
  • Cryptographic reverse firewalls
  • Interactive proofs
  • Zero knowledge

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Vulnerability summary for cve-2014-6271 (shellshock), September 2014. URL: http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2014-6271.
  2. Juniper vulnerability, 2015. URL: https://kb.juniper.net/InfoCenter/index?page=content&id=JSA10713.
  3. Marcel Armour and Bertram Poettering. Substitution attacks against message authentication. IACR Trans. Symmetric Cryptol., 2019(3):152-168, 2019. Google Scholar
  4. Giuseppe Ateniese, Danilo Francati, Bernardo Magri, and Daniele Venturi. Public immunization against complete subversion without random oracles. In Robert H. Deng, Valérie Gauthier-Umaña, Martín Ochoa, and Moti Yung, editors, ACNS 19, volume 11464 of LNCS, pages 465-485. Springer, Heidelberg, June 2019. URL: https://doi.org/10.1007/978-3-030-21568-2_23.
  5. Giuseppe Ateniese, Bernardo Magri, and Daniele Venturi. Subversion-resilient signature schemes. In Indrajit Ray, Ninghui Li, and Christopher Kruegel, editors, ACM CCS 2015, pages 364-375. ACM Press, October 2015. URL: https://doi.org/10.1145/2810103.2813635.
  6. Benedikt Auerbach, Mihir Bellare, and Eike Kiltz. Public-key encryption resistant to parameter subversion and its realization from efficiently-embeddable groups. In Michel Abdalla and Ricardo Dahab, editors, PKC 2018, Part I, volume 10769 of LNCS, pages 348-377. Springer, Heidelberg, March 2018. URL: https://doi.org/10.1007/978-3-319-76578-5_12.
  7. James Ball, Julian Borger, and Glenn Greenwald. Revealed: How US and UK spy agencies defeat internet privacy and security. Guardian Weekly, September 2013. Google Scholar
  8. Mihir Bellare, Georg Fuchsbauer, and Alessandra Scafuro. NIZKs with an untrusted CRS: Security in the face of parameter subversion. In Jung Hee Cheon and Tsuyoshi Takagi, editors, ASIACRYPT 2016, Part II, volume 10032 of LNCS, pages 777-804. Springer, Heidelberg, December 2016. URL: https://doi.org/10.1007/978-3-662-53890-6_26.
  9. Mihir Bellare and Oded Goldreich. On defining proofs of knowledge. In Ernest F. Brickell, editor, CRYPTO'92, volume 740 of LNCS, pages 390-420. Springer, Heidelberg, August 1993. URL: https://doi.org/10.1007/3-540-48071-4_28.
  10. Mihir Bellare, Joseph Jaeger, and Daniel Kane. Mass-surveillance without the state: Strongly undetectable algorithm-substitution attacks. In Indrajit Ray, Ninghui Li, and Christopher Kruegel, editors, ACM CCS 2015, pages 1431-1440. ACM Press, October 2015. URL: https://doi.org/10.1145/2810103.2813681.
  11. Mihir Bellare, Kenneth G. Paterson, and Phillip Rogaway. Security of symmetric encryption against mass surveillance. In Juan A. Garay and Rosario Gennaro, editors, CRYPTO 2014, Part I, volume 8616 of LNCS, pages 1-19. Springer, Heidelberg, August 2014. URL: https://doi.org/10.1007/978-3-662-44371-2_1.
  12. Rongmao Chen, Yi Mu, Guomin Yang, Willy Susilo, Fuchun Guo, and Mingwu Zhang. Cryptographic reverse firewall via malleable smooth projective hash functions. In Jung Hee Cheon and Tsuyoshi Takagi, editors, ASIACRYPT 2016, Part I, volume 10031 of LNCS, pages 844-876. Springer, Heidelberg, December 2016. URL: https://doi.org/10.1007/978-3-662-53887-6_31.
  13. Michele Ciampi, Giuseppe Persiano, Alessandra Scafuro, Luisa Siniscalchi, and Ivan Visconti. Improved OR-composition of sigma-protocols. In Eyal Kushilevitz and Tal Malkin, editors, TCC 2016-A, Part II, volume 9563 of LNCS, pages 112-141. Springer, Heidelberg, January 2016. URL: https://doi.org/10.1007/978-3-662-49099-0_5.
  14. Michele Ciampi, Giuseppe Persiano, Alessandra Scafuro, Luisa Siniscalchi, and Ivan Visconti. Online/offline OR composition of sigma protocols. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 63-92. Springer, Heidelberg, May 2016. URL: https://doi.org/10.1007/978-3-662-49896-5_3.
  15. Ronald Cramer, Ivan Damgård, and Berry Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols. In Yvo Desmedt, editor, CRYPTO'94, volume 839 of LNCS, pages 174-187. Springer, Heidelberg, August 1994. URL: https://doi.org/10.1007/3-540-48658-5_19.
  16. Ronald Cramer, Rosario Gennaro, and Berry Schoenmakers. A secure and optimally efficient multi-authority election scheme. In Walter Fumy, editor, EUROCRYPT'97, volume 1233 of LNCS, pages 103-118. Springer, Heidelberg, May 1997. URL: https://doi.org/10.1007/3-540-69053-0_9.
  17. Ivan Damgård and Jens Groth. Non-interactive and reusable non-malleable commitment schemes. In 35th ACM STOC, pages 426-437. ACM Press, June 2003. URL: https://doi.org/10.1145/780542.780605.
  18. Jean Paul Degabriele, Pooya Farshim, and Bertram Poettering. A more cautious approach to security against mass surveillance. In Gregor Leander, editor, FSE 2015, volume 9054 of LNCS, pages 579-598. Springer, Heidelberg, March 2015. URL: https://doi.org/10.1007/978-3-662-48116-5_28.
  19. Jean Paul Degabriele, Kenneth G. Paterson, Jacob C. N. Schuldt, and Joanne Woodage. Backdoors in pseudorandom number generators: Possibility and impossibility results. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part I, volume 9814 of LNCS, pages 403-432. Springer, Heidelberg, August 2016. URL: https://doi.org/10.1007/978-3-662-53018-4_15.
  20. Yevgeniy Dodis, Chaya Ganesh, Alexander Golovnev, Ari Juels, and Thomas Ristenpart. A formal treatment of backdoored pseudorandom generators. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part I, volume 9056 of LNCS, pages 101-126. Springer, Heidelberg, April 2015. URL: https://doi.org/10.1007/978-3-662-46800-5_5.
  21. Yevgeniy Dodis, Ilya Mironov, and Noah Stephens-Davidowitz. Message transmission with reverse firewalls - secure communication on corrupted machines. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part I, volume 9814 of LNCS, pages 341-372. Springer, Heidelberg, August 2016. URL: https://doi.org/10.1007/978-3-662-53018-4_13.
  22. Sebastian Faust, Markulf Kohlweiss, Giorgia Azzurra Marson, and Daniele Venturi. On the non-malleability of the Fiat-Shamir transform. In Steven D. Galbraith and Mridul Nandi, editors, INDOCRYPT 2012, volume 7668 of LNCS, pages 60-79. Springer, Heidelberg, December 2012. URL: https://doi.org/10.1007/978-3-642-34931-7_5.
  23. Uriel Feige, Dror Lapidot, and Adi Shamir. Multiple non-interactive zero knowledge proofs based on a single random string (extended abstract). In 31st FOCS, pages 308-317. IEEE Computer Society Press, October 1990. URL: https://doi.org/10.1109/FSCS.1990.89549.
  24. Uriel Feige and Adi Shamir. Witness indistinguishable and witness hiding protocols. In 22nd ACM STOC, pages 416-426. ACM Press, May 1990. URL: https://doi.org/10.1145/100216.100272.
  25. Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Andrew M. Odlyzko, editor, CRYPTO'86, volume 263 of LNCS, pages 186-194. Springer, Heidelberg, August 1987. URL: https://doi.org/10.1007/3-540-47721-7_12.
  26. Marc Fischlin. Communication-efficient non-interactive proofs of knowledge with online extractors. In Victor Shoup, editor, CRYPTO 2005, volume 3621 of LNCS, pages 152-168. Springer, Heidelberg, August 2005. URL: https://doi.org/10.1007/11535218_10.
  27. Marc Fischlin, Christian Janson, and Sogol Mazaheri. Backdoored hash functions: Immunizing HMAC and HKDF. In 31st IEEE Computer Security Foundations Symposium, CSF 2018, Oxford, United Kingdom, July 9-12, 2018, pages 105-118, 2018. Google Scholar
  28. Marc Fischlin and Sogol Mazaheri. Self-guarding cryptographic protocols against algorithm substitution attacks. In 31st IEEE Computer Security Foundations Symposium, CSF 2018, Oxford, United Kingdom, July 9-12, 2018, pages 76-90, 2018. Google Scholar
  29. Chaya Ganesh, Bernardo Magri, and Daniele Venturi. Cryptographic reverse firewalls for interactive proof systems. IACR Cryptology ePrint Archive, 2020:204, 2020. URL: https://eprint.iacr.org/2020/204.
  30. Juan A. Garay, Philip D. MacKenzie, and Ke Yang. Strengthening zero-knowledge protocols using signatures. Journal of Cryptology, 19(2):169-209, April 2006. URL: https://doi.org/10.1007/s00145-005-0307-3.
  31. Irene Giacomelli, Ruxandra F. Olimid, and Samuel Ranellucci. Security of linear secret-sharing schemes against mass surveillance. In Michael Reiter and David Naccache, editors, CANS 15, LNCS, pages 43-58. Springer, Heidelberg, Dec. 2015. URL: https://doi.org/10.1007/978-3-319-26823-1_4.
  32. Oded Goldreich. Foundations of Cryptography: Basic Tools, volume 1. Cambridge University Press, Cambridge, UK, 2001. Google Scholar
  33. Oded Goldreich and Ariel Kahan. How to construct constant-round zero-knowledge proof systems for NP. Journal of Cryptology, 9(3):167-190, June 1996. Google Scholar
  34. Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, 38(3):691-729, 1991. Google Scholar
  35. Shafi Goldwasser and Silvio Micali. Probabilistic encryption and how to play mental poker keeping secret all partial information. In 14th ACM STOC, pages 365-377. ACM Press, May 1982. URL: https://doi.org/10.1145/800070.802212.
  36. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186-208, 1989. Google Scholar
  37. Louis C. Guillou and Jean-Jacques Quisquater. A practical zero-knowledge protocol fitted to security microprocessor minimizing both trasmission and memory. In C. G. Günther, editor, EUROCRYPT'88, volume 330 of LNCS, pages 123-128. Springer, Heidelberg, May 1988. URL: https://doi.org/10.1007/3-540-45961-8_11.
  38. Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung, and Christophe Wachter. Public keys. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 626-642. Springer, Heidelberg, August 2012. URL: https://doi.org/10.1007/978-3-642-32009-5_37.
  39. Ueli M. Maurer. Unifying zero-knowledge proofs of knowledge. In Bart Preneel, editor, AFRICACRYPT 09, volume 5580 of LNCS, pages 272-286. Springer, Heidelberg, June 2009. Google Scholar
  40. Ilya Mironov and Noah Stephens-Davidowitz. Cryptographic reverse firewalls. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part II, volume 9057 of LNCS, pages 657-686. Springer, Heidelberg, April 2015. URL: https://doi.org/10.1007/978-3-662-46803-6_22.
  41. Tatsuaki Okamoto. Provably secure and practical identification schemes and corresponding signature schemes. In Ernest F. Brickell, editor, CRYPTO'92, volume 740 of LNCS, pages 31-53. Springer, Heidelberg, August 1993. URL: https://doi.org/10.1007/3-540-48071-4_3.
  42. Tatsuaki Okamoto and Kazuo Ohta. Divertible zero knowledge interactive proofs and commutative random self-reducibility. In Jean-Jacques Quisquater and Joos Vandewalle, editors, EUROCRYPT'89, volume 434 of LNCS, pages 134-148. Springer, Heidelberg, April 1990. URL: https://doi.org/10.1007/3-540-46885-4_16.
  43. Rafail Ostrovsky, Vanishree Rao, and Ivan Visconti. On selective-opening attacks against encryption schemes. In Michel Abdalla and Roberto De Prisco, editors, SCN 14, volume 8642 of LNCS, pages 578-597. Springer, Heidelberg, September 2014. URL: https://doi.org/10.1007/978-3-319-10879-7_33.
  44. Torben P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In Joan Feigenbaum, editor, CRYPTO'91, volume 576 of LNCS, pages 129-140. Springer, Heidelberg, August 1992. URL: https://doi.org/10.1007/3-540-46766-1_9.
  45. Nicole Perlroth, Jeff Larson, and Scott Shane. N.S.A. able to foil basic safeguards of privacy on web. The New York Times, September 2013. Google Scholar
  46. Alexander Russell, Qiang Tang, Moti Yung, and Hong-Sheng Zhou. Cliptography: Clipping the power of kleptographic attacks. In Jung Hee Cheon and Tsuyoshi Takagi, editors, ASIACRYPT 2016, Part II, volume 10032 of LNCS, pages 34-64. Springer, Heidelberg, December 2016. URL: https://doi.org/10.1007/978-3-662-53890-6_2.
  47. Alexander Russell, Qiang Tang, Moti Yung, and Hong-Sheng Zhou. Generic semantic security against a kleptographic adversary. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017, pages 907-922. ACM Press, October / November 2017. URL: https://doi.org/10.1145/3133956.3133993.
  48. Alessandra Scafuro and Ivan Visconti. On round-optimal zero knowledge in the bare public-key model. In David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 153-171. Springer, Heidelberg, April 2012. URL: https://doi.org/10.1007/978-3-642-29011-4_11.
  49. Claus-Peter Schnorr. Efficient identification and signatures for smart cards. In Gilles Brassard, editor, CRYPTO'89, volume 435 of LNCS, pages 239-252. Springer, Heidelberg, August 1990. URL: https://doi.org/10.1007/0-387-34805-0_22.
  50. Gustavus J. Simmons. The prisoners' problem and the subliminal channel. In David Chaum, editor, CRYPTO'83, pages 51-67. Plenum Press, New York, USA, 1983. Google Scholar
  51. Dominique Unruh. Quantum proofs of knowledge. In David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 135-152. Springer, Heidelberg, April 2012. URL: https://doi.org/10.1007/978-3-642-29011-4_10.
  52. Adam Young and Moti Yung. Kleptography: Using cryptography against cryptography. In Walter Fumy, editor, EUROCRYPT'97, volume 1233 of LNCS, pages 62-74. Springer, Heidelberg, May 1997. URL: https://doi.org/10.1007/3-540-69053-0_6.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail