Paper 2018/945

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

Balthazar Bauer, Jevgēnijs Vihrovs, and Hoeteck Wee

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 $\vec x$ and $y$ to $\vec y$ so that $$P(x,y) = 1 \Longleftrightarrow \langle\vec x,\vec y\rangle= 0 \bmod 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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. FSTTCS 2018
Keywords
Predicate EncryptionInner Product EncodingMatching Vector Families
Contact author(s)
jevgenijs vihrovs @ lu lv
History
2018-10-09: received
Short URL
https://ia.cr/2018/945
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/945,
      author = {Balthazar Bauer and Jevgēnijs Vihrovs and Hoeteck Wee},
      title = {On the Inner Product Predicate and a Generalization of Matching Vector Families},
      howpublished = {Cryptology ePrint Archive, Paper 2018/945},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/945}},
      url = {https://eprint.iacr.org/2018/945}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.