Document Open Access Logo

Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption

Authors James Bartusek, Yuval Ishai, Aayush Jain, Fermi Ma, Amit Sahai, Mark Zhandry

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.82.pdf
  • Filesize: 0.74 MB
  • 39 pages

Document Identifiers

Author Details

James Bartusek
  • UC Berkeley, CA, USA
Yuval Ishai
  • Technion - Israel Institute of Technology, Haifa, Israel
Aayush Jain
  • UCLA, Los Angeles, CA, USA
Fermi Ma
  • Princeton University, NJ, USA
  • NTT Research, Palo Alto, CA, USA
Amit Sahai
  • UCLA, Los Angeles, CA, USA
Mark Zhandry
  • Princeton University, NJ, USA
  • NTT Research, Palo Alto, CA, USA

Funding

YI was supported by ERC Project NTSC (742754), NSF-BSF grant 2015782, BSF grant 2018393, and a joint Israel-India grant. MZ, FM, AS, and AJ were supported by the Defense Advanced Research Projects Agency through the ARL under Contract W911NF-15-C- 0205. MZ and FM were also supported under NSF grant 1616442. AS and AJ were also supported in part by a DARPA/ARL SAFEWARE award, NSF Frontier Award 1413955, and NSF grant 1619348, BSF grant 2012378, a Xerox Faculty Research Award, a Google Faculty Research Award, an equipment grant from Intel, and an Okawa Foundation Research Grant. AJ was also supported by a Google PhD Fellowship in Privacy and Security. The views expressed are those of the authors and do not reflect the official policy or position of the Department of Defense, the National Science Foundation, the U.S. Government or Google.

Cite AsGet BibTex

James Bartusek, Yuval Ishai, Aayush Jain, Fermi Ma, Amit Sahai, and Mark Zhandry. Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 82:1-82:39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.82

Abstract

An affine determinant program ADP: {0,1}^n → {0,1} is specified by a tuple (A,B_1,…,B_n) of square matrices over ?_q and a function Eval: ?_q → {0,1}, and evaluated on x ∈ {0,1}^n by computing Eval(det(A + ∑_{i∈[n]} x_i B_i)). In this work, we suggest ADPs as a new framework for building general-purpose obfuscation and witness encryption. We provide evidence to suggest that constructions following our ADP-based framework may one day yield secure, practically feasible obfuscation. As a proof-of-concept, we give a candidate ADP-based construction of indistinguishability obfuscation (i?) for all circuits along with a simple witness encryption candidate. We provide cryptanalysis demonstrating that our schemes resist several potential attacks, and leave further cryptanalysis to future work. Lastly, we explore practically feasible applications of our witness encryption candidate, such as public-key encryption with near-optimal key generation.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic primitives
Keywords
  • Obfuscation
  • Witness Encryption

Metrics

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

References

  1. Prabhanjan Ananth, Aayush Jain, Huijia Lin, Christian Matt, and Amit Sahai. Indistinguishability Obfuscation Without Multilinear Maps: New Paradigms via Low Degree Weak Pseudorandomness and Security Amplification. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2019, Part III, LNCS, pages 284-332. Springer, Heidelberg, August 2019. URL: https://doi.org/10.1007/978-3-030-26954-8_10.
  2. Benny Applebaum. Bootstrapping Obfuscators via Fast Pseudorandom Functions. In Palash Sarkar and Tetsu Iwata, editors, ASIACRYPT 2014, Part II, volume 8874 of LNCS, pages 162-172. Springer, Heidelberg, December 2014. URL: https://doi.org/10.1007/978-3-662-45608-8_9.
  3. Benny Applebaum. Cryptographic Hardness of Random Local Functions - Survey. Computational Complexity, 25(3):667-722, 2016. Google Scholar
  4. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography in NC⁰. In 45th FOCS, pages 166-175. IEEE Computer Society Press, October 2004. URL: https://doi.org/10.1109/FOCS.2004.20.
  5. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography with Constant Input Locality. In Alfred Menezes, editor, CRYPTO 2007, volume 4622 of LNCS, pages 92-110. Springer, Heidelberg, August 2007. URL: https://doi.org/10.1007/978-3-540-74143-5_6.
  6. Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (Im)possibility of Obfuscating Programs. In Joe Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages 1-18. Springer, Heidelberg, August 2001. URL: https://doi.org/10.1007/3-540-44647-8_1.
  7. David A. Mix Barrington. Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹. In 18th ACM STOC, pages 1-5. ACM Press, May 1986. URL: https://doi.org/10.1145/12130.12131.
  8. James Bartusek, Tancrède Lepoint, Fermi Ma, and Mark Zhandry. New Techniques for Obfuscating Conjunctions. In Vincent Rijmen and Yuval Ishai, editors, EUROCRYPT 2019, Part III, LNCS, pages 636-666. Springer, Heidelberg, May 2019. URL: https://doi.org/10.1007/978-3-030-17659-4_22.
  9. Allison Bishop, Lucas Kowalczyk, Tal Malkin, Valerio Pastro, Mariana Raykova, and Kevin Shi. A Simple Obfuscation Scheme for Pattern-Matching with Wildcards. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 731-752. Springer, Heidelberg, August 2018. URL: https://doi.org/10.1007/978-3-319-96878-0_25.
  10. Dan Boneh, Yuval Ishai, Alain Passelègue, Amit Sahai, and David J. Wu. Exploring Crypto Dark Matter: New Simple PRF Candidates and Their Applications. In Amos Beimel and Stefan Dziembowski, editors, TCC 2018, Part II, volume 11240 of LNCS, pages 699-729. Springer, Heidelberg, November 2018. URL: https://doi.org/10.1007/978-3-030-03810-6_25.
  11. Dan Boneh, Yuval Ishai, Amit Sahai, and David J. Wu. Lattice-Based SNARGs and Their Application to More Efficient Obfuscation. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, EUROCRYPT 2017, Part III, volume 10212 of LNCS, pages 247-277. Springer, Heidelberg, April/May 2017. URL: https://doi.org/10.1007/978-3-319-56617-7_9.
  12. Zizhong Chen and Jack J. Dongarra. Condition Numbers of Gaussian Random Matrices. SIAM J. Matrix Analysis Applications, 27(3):603-620, 2005. Google Scholar
  13. Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. Practical Multilinear Maps over the Integers. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part I, volume 8042 of LNCS, pages 476-493. Springer, Heidelberg, August 2013. URL: https://doi.org/10.1007/978-3-642-40041-4_26.
  14. Nicolas Courtois and Josef Pieprzyk. Cryptanalysis of Block Ciphers with Overdefined Systems of Equations. In Yuliang Zheng, editor, ASIACRYPT 2002, volume 2501 of LNCS, pages 267-287. Springer, Heidelberg, December 2002. URL: https://doi.org/10.1007/3-540-36178-2_17.
  15. Geoffroy Couteau, Aurélien Dupin, Pierrick Méaux, Mélissa Rossi, and Yann Rotella. On the Concrete Security of Goldreich’s Pseudorandom Generator. In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018, Part II, volume 11273 of LNCS, pages 96-124. Springer, Heidelberg, December 2018. URL: https://doi.org/10.1007/978-3-030-03329-3_4.
  16. Sanjam Garg, Craig Gentry, and Shai Halevi. Candidate Multilinear Maps from Ideal Lattices. In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 1-17. Springer, Heidelberg, May 2013. URL: https://doi.org/10.1007/978-3-642-38348-9_1.
  17. Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits. In 54th FOCS, pages 40-49. IEEE Computer Society Press, October 2013. URL: https://doi.org/10.1109/FOCS.2013.13.
  18. Sanjam Garg, Craig Gentry, Shai Halevi, Amit Sahai, and Brent Waters. Attribute-Based Encryption for Circuits from Multilinear Maps. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 479-499. Springer, Heidelberg, August 2013. URL: https://doi.org/10.1007/978-3-642-40084-1_27.
  19. Sanjam Garg, Craig Gentry, Amit Sahai, and Brent Waters. Witness encryption and its applications. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, 45th ACM STOC, pages 467-476. ACM Press, June 2013. URL: https://doi.org/10.1145/2488608.2488667.
  20. Craig Gentry, Sergey Gorbunov, and Shai Halevi. Graph-Induced Multilinear Maps from Lattices. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, TCC 2015, Part II, volume 9015 of LNCS, pages 498-527. Springer, Heidelberg, March 2015. URL: https://doi.org/10.1007/978-3-662-46497-7_20.
  21. Craig Gentry, Charanjit S. Jutla, and Daniel Kane. Obfuscation Using Tensor Products. Cryptology ePrint Archive, Report 2018/756, 2018. URL: https://eprint.iacr.org/2018/756.
  22. Oded Goldreich. Candidate One-Way Functions Based on Expander Graphs. Cryptology ePrint Archive, Report 2000/063, 2000. URL: http://eprint.iacr.org/2000/063.
  23. Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich. How to Run Turing Machines on Encrypted Data. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 536-553. Springer, Heidelberg, August 2013. URL: https://doi.org/10.1007/978-3-642-40084-1_30.
  24. Vipul Goyal, Yuval Ishai, Amit Sahai, Ramarathnam Venkatesan, and Akshay Wadia. Founding Cryptography on Tamper-Proof Hardware Tokens. In Daniele Micciancio, editor, TCC 2010, volume 5978 of LNCS, pages 308-326. Springer, Heidelberg, February 2010. URL: https://doi.org/10.1007/978-3-642-11799-2_19.
  25. Ilse C. F. Ipsen and Rizwana Rehman. Perturbation Bounds for Determinants and Characteristic Polynomials. SIAM J. Matrix Analysis Applications, 30(2):762-776, 2008. Google Scholar
  26. Yuval Ishai and Eyal Kushilevitz. Private simultaneous messages protocols with applications. In Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems, pages 174-183. IEEE, 1997. Google Scholar
  27. Yuval Ishai and Eyal Kushilevitz. Randomizing Polynomials: A New Representation with Applications to Round-Efficient Secure Computation. In 41st FOCS, pages 294-304. IEEE Computer Society Press, November 2000. URL: https://doi.org/10.1109/SFCS.2000.892118.
  28. Yuval Ishai and Eyal Kushilevitz. Perfect Constant-Round Secure Computation via Perfect Randomizing Polynomials. In Peter Widmayer, Francisco Triguero Ruiz, Rafael Morales Bueno, Matthew Hennessy, Stephan Eidenbenz, and Ricardo Conejo, editors, ICALP 2002, volume 2380 of LNCS, pages 244-256. Springer, Heidelberg, July 2002. URL: https://doi.org/10.1007/3-540-45465-9_22.
  29. Aviad Kipnis and Adi Shamir. Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization. In Michael J. Wiener, editor, CRYPTO'99, volume 1666 of LNCS, pages 19-30. Springer, Heidelberg, August 1999. URL: https://doi.org/10.1007/3-540-48405-1_2.
  30. Adam Klivans and Amir Shpilka. Learning Arithmetic Circuits via Partial Derivatives. In Computational Learning Theory and Kernel Machines, 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings, volume 2777, pages 463-476, January 2003. URL: https://doi.org/10.1007/978-3-540-45167-9_34.
  31. Amit Sahai. New Roads to Cryptopia: A research agenda. New Roads to Cryptopia Workshop at CRYPTO 2019, 2019. Google Scholar
  32. Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: deniable encryption, and more. In David B. Shmoys, editor, 46th ACM STOC, pages 475-484. ACM Press, May/June 2014. URL: https://doi.org/10.1145/2591796.2591825.
  33. Terence Tao and Van Vu. On Random &Plusmn;1 Matrices: Singularity and Determinant. Random Struct. Algorithms, 28(1):1-23, January 2006. URL: https://doi.org/10.1002/rsa.v28:1.
  34. Terrence Tao. Operator Norm of a Random Matrix. Wordpress Bog. URL: https://terrytao.wordpress.com/2010/01/09/254a-notes-3-the-operator-norm-of-a-random-matrix/#utail-wigner.
  35. Enrico Thomae and Christopher Wolf. Solving Underdetermined Systems of Multivariate Quadratic Equations Revisited. In Public Key Cryptography - PKC 2012 - 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, May 21-23, 2012. Proceedings, pages 156-171, 2012. Google Scholar
  36. Joel A. Tropp. An Introduction to Matrix Concentration Inequalities. Foundations and Trends in Machine Learning, 8(1-2):1-230, 2015. Google Scholar
  37. Joe Zimmerman. How to Obfuscate Programs Directly. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part II, volume 9057 of LNCS, pages 439-467. Springer, Heidelberg, April 2015. URL: https://doi.org/10.1007/978-3-662-46803-6_15.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact