HVE ⇒ Subset and range queries

Fully-black-box reduction · standard model · BW07 · security loss: tight: the adversary runs unchanged through the encodings, with the same advantage

Statement

Every HVE scheme over $\Sigma =\{0,1\}$ supports subset and range queries through fixed encodings of attributes and predicates into vectors and wildcard patterns: membership $x\in T$ by encoding $x$ as its indicator vector over the domain and $T$ as the pattern with wildcards exactly on $T$ and $0$ elsewhere; comparison $x\ge a$ over a domain of size $n$ by encoding $x$ in unary and $a$ as the pattern with a single non-wildcard position; ranges $a\le x\le b$ as conjunctions of comparisons. The encodings preserve every predicate outcome, so the derived scheme inherits the HVE scheme’s security with the same advantage. Ciphertext size is linear in the domain size — BW07.

Sketch

The indicator vector of $x$ has its only $1$ at position $x$, which the pattern for $T$ leaves as a wildcard iff $x\in T$. On the unary encoding $1^x{0}^{n-x}$, $x\ge a$ iff position $a$ holds $1$; a range conjoins two such tests.