Document Open Access Logo

Algebraic Restriction Codes and Their Applications

Authors Divesh Aggarwal, Nico Döttling , Jesko Dujmovic, Mohammad Hajiabadi, Giulio Malavolta, Maciej Obremski

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.2.pdf
  • Filesize: 0.71 MB
  • 15 pages

Document Identifiers

Author Details

Divesh Aggarwal
  • National University of Singapore, Singapore
Nico Döttling
  • Helmholtz Center for Information Security (CISPA), Saarbrücken, Germany
Jesko Dujmovic
  • Helmholtz Center for Information Security (CISPA), Saarbrücken, Germany
  • Saarland University, Saarbrücken, Germany
Mohammad Hajiabadi
  • University of Waterloo, ON, Canada
Giulio Malavolta
  • Max Planck Institute for Security and Privacy, Bochum, Germany
Maciej Obremski
  • National University of Singapore, Singapore

Funding

  • Aggarwal, Divesh: This work is supported in part by the Singapore National Research Foundation under NRF RF Award No. NRF-NRFF2013-13, the Ministry of Education, Singapore under the Research Centres of Excellence programme by the Tier-3 grant Grant "Random numbers from quantum processes" No. MOE2012-T3-1-009.
  • Döttling, Nico: This work is partially funded by the Helmholtz Association within the project "Trustworthy Federated Data Analytics" (TFDA) (funding number ZT-I-OO1 4).
  • Dujmovic, Jesko: This work is partially funded by the Helmholtz Association within the project "Trustworthy Federated Data Analytics" (TFDA) (funding number ZT-I-OO1 4).
  • Obremski, Maciej: This author was supported by MOE2019-T2-1-145 Foundations of quantum-safe cryptography.

Cite AsGet BibTex

Divesh Aggarwal, Nico Döttling, Jesko Dujmovic, Mohammad Hajiabadi, Giulio Malavolta, and Maciej Obremski. Algebraic Restriction Codes and Their Applications. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.2

Abstract

Consider the following problem: You have a device that is supposed to compute a linear combination of its inputs, which are taken from some finite field. However, the device may be faulty and compute arbitrary functions of its inputs. Is it possible to encode the inputs in such a way that only linear functions can be evaluated over the encodings? I.e., learning an arbitrary function of the encodings will not reveal more information about the inputs than a linear combination. In this work, we introduce the notion of algebraic restriction codes (AR codes), which constrain adversaries who might compute any function to computing a linear function. Our main result is an information-theoretic construction AR codes that restrict any class of function with a bounded number of output bits to linear functions. Our construction relies on a seed which is not provided to the adversary. While interesting and natural on its own, we show an application of this notion in cryptography. In particular, we show that AR codes lead to the first construction of rate-1 oblivious transfer with statistical sender security from the Decisional Diffie-Hellman assumption, and the first-ever construction that makes black-box use of cryptography. Previously, such protocols were known only from the LWE assumption, using non-black-box cryptographic techniques. We expect our new notion of AR codes to find further applications, e.g., in the context of non-malleability, in the future.

Subject Classification

ACM Subject Classification
  • Security and privacy → Information-theoretic techniques
  • Security and privacy → Public key (asymmetric) techniques
Keywords
  • Algebraic Restriction Codes
  • Oblivious Transfer
  • Rate 1
  • Statistically Sender Private
  • OT
  • Diffie-Hellman
  • DDH

Metrics

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

Related Versions

References

  1. Divesh Aggarwal, Yevgeniy Dodis, and Shachar Lovett. Non-malleable codes from additive combinatorics. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 774-783. ACM, 2014. URL: https://doi.org/10.1145/2591796.2591804.
  2. Divesh Aggarwal, Nico Döttling, Jesko Dujmovic, Mohammad Hajiabadi, Giulio Malavolta, and Maciej Obremski. Algebraic restriction codes and their applications. IACR Cryptol. ePrint Arch., page 1177, 2021. URL: https://eprint.iacr.org/2021/1177.
  3. William Aiello, Yuval Ishai, and Omer Reingold. Priced oblivious transfer: How to sell digital goods. In Birgit Pfitzmann, editor, Advances in Cryptology - EUROCRYPT 2001, International Conference on the Theory and Application of Cryptographic Techniques, Innsbruck, Austria, May 6-10, 2001, Proceeding, volume 2045 of Lecture Notes in Computer Science, pages 119-135. Springer, 2001. URL: https://doi.org/10.1007/3-540-44987-6_8.
  4. Saikrishna Badrinarayanan, Rex Fernando, Aayush Jain, Dakshita Khurana, and Amit Sahai. Statistical ZAP arguments. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part III, volume 12107 of Lecture Notes in Computer Science, pages 642-667. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-45727-3_22.
  5. Saikrishna Badrinarayanan, Sanjam Garg, Yuval Ishai, Amit Sahai, and Akshay Wadia. Two-message witness indistinguishability and secure computation in the plain model from new assumptions. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part III, volume 10626 of Lecture Notes in Computer Science, pages 275-303. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-70700-6_10.
  6. Zvika Brakerski and Nico Döttling. Two-message statistically sender-private OT from LWE. In Amos Beimel and Stefan Dziembowski, editors, Theory of Cryptography - 16th International Conference, TCC 2018, Panaji, India, November 11-14, 2018, Proceedings, Part II, volume 11240 of Lecture Notes in Computer Science, pages 370-390. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-03810-6_14.
  7. Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta. Leveraging linear decryption: Rate-1 fully-homomorphic encryption and time-lock puzzles. In Dennis Hofheinz and Alon Rosen, editors, Theory of Cryptography - 17th International Conference, TCC 2019, Nuremberg, Germany, December 1-5, 2019, Proceedings, Part II, volume 11892 of Lecture Notes in Computer Science, pages 407-437. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-36033-7_16.
  8. Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 97-106. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/FOCS.2011.12.
  9. Mahdi Cheraghchi and Venkatesan Guruswami. Non-malleable coding against bit-wise and split-state tampering. In Yehuda Lindell, editor, Theory of Cryptography - 11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24-26, 2014. Proceedings, volume 8349 of Lecture Notes in Computer Science, pages 440-464. Springer, 2014. URL: https://doi.org/10.1007/978-3-642-54242-8_19.
  10. Yevgeniy Dodis, Xin Li, Trevor D. Wooley, and David Zuckerman. Privacy amplification and non-malleable extractors via character sums. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 668-677. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/FOCS.2011.67.
  11. Yevgeniy Dodis and Daniel Wichs. Non-malleable extractors and symmetric key cryptography from weak secrets. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 601-610. ACM, 2009. URL: https://doi.org/10.1145/1536414.1536496.
  12. Nico Döttling, Sanjam Garg, Yuval Ishai, Giulio Malavolta, Tamer Mour, and Rafail Ostrovsky. Trapdoor hash functions and their applications. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part III, volume 11694 of Lecture Notes in Computer Science, pages 3-32. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-26954-8_1.
  13. Stefan Dziembowski, Tomasz Kazana, and Maciej Obremski. Non-malleable codes from two-source extractors. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part II, volume 8043 of Lecture Notes in Computer Science, pages 239-257. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40084-1_14.
  14. Stefan Dziembowski, Krzysztof Pietrzak, and Daniel Wichs. Non-malleable codes. J. ACM, 65(4):20:1-20:32, 2018. URL: https://doi.org/10.1145/3178432.
  15. Shimon Even, Oded Goldreich, and Abraham Lempel. A randomized protocol for signing contracts. In David Chaum, Ronald L. Rivest, and Alan T. Sherman, editors, Advances in Cryptology: Proceedings of CRYPTO '82, Santa Barbara, California, USA, August 23-25, 1982, pages 205-210. Plenum Press, New York, 1982. URL: https://doi.org/10.1007/978-1-4757-0602-4_19.
  16. Taher El Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In G. R. Blakley and David Chaum, editors, Advances in Cryptology, Proceedings of CRYPTO '84, Santa Barbara, California, USA, August 19-22, 1984, Proceedings, volume 196 of Lecture Notes in Computer Science, pages 10-18. Springer, 1984. URL: https://doi.org/10.1007/3-540-39568-7_2.
  17. Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 169-178. ACM, 2009. URL: https://doi.org/10.1145/1536414.1536440.
  18. Craig Gentry and Shai Halevi. Compressible FHE with applications to PIR. In Dennis Hofheinz and Alon Rosen, editors, Theory of Cryptography - 17th International Conference, TCC 2019, Nuremberg, Germany, December 1-5, 2019, Proceedings, Part II, volume 11892 of Lecture Notes in Computer Science, pages 438-464. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-36033-7_17.
  19. Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, volume 8042 of Lecture Notes in Computer Science, pages 75-92. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40041-4_5.
  20. Oded Goldreich and Yair Oren. Definitions and properties of zero-knowledge proof systems. J. Cryptol., 7(1):1-32, 1994. Google Scholar
  21. Vipul Goyal, Abhishek Jain, Zhengzhong Jin, and Giulio Malavolta. Statistical zaps and new oblivious transfer protocols. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part III, volume 12107 of Lecture Notes in Computer Science, pages 668-699. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-45727-3_23.
  22. Shai Halevi and Yael Tauman Kalai. Smooth projective hashing and two-message oblivious transfer. J. Cryptol., 25(1):158-193, 2012. URL: https://doi.org/10.1007/s00145-010-9092-8.
  23. Yuval Ishai and Anat Paskin. Evaluating branching programs on encrypted data. In Salil P. Vadhan, editor, Theory of Cryptography, 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21-24, 2007, Proceedings, volume 4392 of Lecture Notes in Computer Science, pages 575-594. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-70936-7_31.
  24. Joe Kilian. Founding cryptography on oblivious transfer. In Janos Simon, editor, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 20-31. ACM, 1988. URL: https://doi.org/10.1145/62212.62215.
  25. Eyal Kushilevitz and Rafail Ostrovsky. Replication is NOT needed: SINGLE database, computationally-private information retrieval. In 38th Annual Symposium on Foundations of Computer Science, FOCS '97, Miami Beach, Florida, USA, October 19-22, 1997, pages 364-373. IEEE Computer Society, 1997. URL: https://doi.org/10.1109/SFCS.1997.646125.
  26. Xin Li. Non-malleable extractors, two-source extractors and privacy amplification. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 688-697. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.26.
  27. Moni Naor and Benny Pinkas. Efficient oblivious transfer protocols. In S. Rao Kosaraju, editor, Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA, pages 448-457. ACM/SIAM, 2001. URL: http://dl.acm.org/citation.cfm?id=365411.365502.
  28. Rafail Ostrovsky, Anat Paskin-Cherniavsky, and Beni Paskin-Cherniavsky. Maliciously circuit-private FHE. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I, volume 8616 of Lecture Notes in Computer Science, pages 536-553. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-44371-2_30.
  29. Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Jacques Stern, editor, Advances in Cryptology - EUROCRYPT '99, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, May 2-6, 1999, Proceeding, volume 1592 of Lecture Notes in Computer Science, pages 223-238. Springer, 1999. URL: https://doi.org/10.1007/3-540-48910-X_16.
  30. Michael O. Rabin. How to exchange secrets with oblivious transfer. IACR Cryptol. ePrint Arch., page 187, 2005. URL: http://eprint.iacr.org/2005/187.
  31. Umesh Vazirani. Randomness, Adversaries and Computation. PhD thesis, EECS, UC Berkeley, 1986. Ph.D. Thesis. Google Scholar
  32. Andrew Chi-Chih Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pages 80-91. IEEE Computer Society, 1982. URL: https://doi.org/10.1109/SFCS.1982.45.
  33. Andrew Chi-Chih Yao. How to generate and exchange secrets (extended abstract). In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986, pages 162-167. IEEE Computer Society, 1986. URL: https://doi.org/10.1109/SFCS.1986.25.
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