  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.
