Document Open Access Logo

On the Inner Product Predicate and a Generalization of Matching Vector Families

Authors Balthazar Bauer, Jevgenijs Vihrovs, Hoeteck Wee

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2018.41.pdf
  • Filesize: 484 kB
  • 13 pages

Document Identifiers

Author Details

Balthazar Bauer
  • ENS, 45 Rue d'Ulm, 75005 Paris, France
Jevgenijs Vihrovs
  • Centre for Quantum Computer Science, University of Latvia, Raiņa 19, LV-1586 Riga, Latvia
Hoeteck Wee
  • CNRS and ENS, 45 Rue d'Ulm, 75005 Paris, France

Funding

  • Vihrovs, Jevgenijs: Work done in part while interning at Centre for Quantum Technologies at NUS. Supported by the ERC Advanced Grant MQC.
  • Wee, Hoeteck: Work done in part while visiting Centre for Quantum Technologies at NUS. Supported in part by ERC Project aSCEND (H2020 639554).

Cite AsGet BibTex

Balthazar Bauer, Jevgenijs Vihrovs, and Hoeteck Wee. On the Inner Product Predicate and a Generalization of Matching Vector Families. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 41:1-41:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.FSTTCS.2018.41

Abstract

Motivated by cryptographic applications such as predicate encryption, we consider the problem of representing an arbitrary predicate as the inner product predicate on two vectors. Concretely, fix a Boolean function P and some modulus q. We are interested in encoding x to x_vector and y to y_vector so that P(x,y) = 1 <=> <x_vector,y_vector> = 0 mod q, where the vectors should be as short as possible. This problem can also be viewed as a generalization of matching vector families, which corresponds to the equality predicate. Matching vector families have been used in the constructions of Ramsey graphs, private information retrieval (PIR) protocols, and more recently, secret sharing. Our main result is a simple lower bound that allows us to show that known encodings for many predicates considered in the cryptographic literature such as greater than and threshold are essentially optimal for prime modulus q. Using this approach, we also prove lower bounds on encodings for composite q, and then show tight upper bounds for such predicates as greater than, index and disjointness.

Subject Classification

ACM Subject Classification
  • Security and privacy → Public key encryption
Keywords
  • Predicate Encryption
  • Inner Product Encoding
  • Matching Vector Families

Metrics

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

References

  1. Josh Alman and Ryan Williams. Probabilistic Rank and Matrix Rigidity. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 641-652, New York, NY, USA, 2017. ACM. Google Scholar
  2. Benny Applebaum. Randomly Encoding Functions: A New Cryptographic Paradigm - (Invited Talk). In ICITS, pages 25-31, 2011. Google Scholar
  3. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography in NC⁰. SIAM J. Comput., 36(4):845-888, 2006. Google Scholar
  4. Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. Foundations of Garbled Circuits. In ACM CCS, 2012. Also Cryptology ePrint Archive, Report 2012/265. Google Scholar
  5. Abhishek Bhowmick, Zeev Dvir, and Shachar Lovett. New bounds for matching vector families. In STOC, pages 823-832, 2013. Google Scholar
  6. Dan Boneh and Brent Waters. Conjunctive, Subset, and Range Queries on Encrypted Data. In TCC, pages 535-554, 2007. Google Scholar
  7. Zeev Dvir, Parikshit Gopalan, and Sergey Yekhanin. Matching Vector Codes. SIAM J. Comput., 40(4):1154-1178, 2011. Google Scholar
  8. Zeev Dvir and Sivakanth Gopi. 2-Server PIR with Sub-Polynomial Communication. In STOC, pages 577-584, 2015. Google Scholar
  9. Zeev Dvir and Guangda Hu. Matching-Vector Families and LDCs over Large Modulo. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 513-526, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. Google Scholar
  10. Klim Efremenko. 3-Query Locally Decodable Codes of Subexponential Length. SIAM J. Comput., 41 (6):1694-1703, 2012. Google Scholar
  11. Uriel Feige, Joe Kilian, and Moni Naor. A minimal model for secure computation. In STOC, pages 554-563, 1994. Google Scholar
  12. Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee. Predicate Encryption for Circuits from LWE. In CRYPTO (2), pages 503-523, 2015. Also, Cryptology ePrint Archive, Report 2015/029. Google Scholar
  13. Vince Grolmusz. Superpolynomial Size Set-systems with Restricted Intersections mod 6 and Explicit Ramsey Graphs. Combinatorica, 20(1):71-86, 2000. Google Scholar
  14. Yuval Ishai and Eyal Kushilevitz. Randomizing Polynomials: A New Representation with Applications to Round-Efficient Secure Computation. In FOCS, pages 294-304, 2000. Google Scholar
  15. Jonathan Katz, Amit Sahai, and Brent Waters. Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products. In EUROCRYPT, pages 146-162, 2008. Google Scholar
  16. Tianren Liu and Vinod Vaikuntanathan. Breaking the Circuit-Size Barrier in Secret Sharing. STOC 2018. Cryptology ePrint Archive, Report 2018/333, 2018. Google Scholar
  17. Tianren Liu, Vinod Vaikuntanathan, and Hoeteck Wee. Conditional Disclosure of Secrets via Non-linear Reconstruction. In Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part I, pages 758-790, 2017. Google Scholar
  18. Tianren Liu, Vinod Vaikuntanathan, and Hoeteck Wee. Towards Breaking the Exponential Barrier for General Secret Sharing. In Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part I, pages 567-596, 2018. Google Scholar
  19. Manoj Prabhakaran and Amit Sahai. Secure Multi-Party Computation. IOS Press, 2003. Google Scholar
  20. Andrew Chi-Chih Yao. Theory and Applications of Trapdoor Functions. In FOCS, pages 80-91, 1982. Google Scholar
  21. Sergey Yekhanin. Towards 3-query locally decodable codes of subexponential length. J. ACM, 55(1):1:1-1:16, 2008. Google Scholar
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