Private inference control
Access control can be used to ensure that database queries pertaining to
sensitive informationare not answered. This is not enough to prevent users from
learning sensitive information though, because users can combine non-sensitive
information to discover something sensitive. Inference control prevents users
from obtaining sensitive information via such ``inference channels'', however,
existing inference control techniques are not private - that is, they require
the server to learn what queries the user is making in order to deny
inference-enabling queries.
We propose a new primitive - private inference control (PIC) - which is a means
for the server to provide inference control without learning what information is
being retrieved. PIC is a generalization of private and symmetrically-private
information retrieval (PIR/SPIR). While it is straightforward to implement
access control using PIR (simply omit sensitive information from the database),
it is nontrivial to implement {\it inference} control efficiently. We measure
the efficiency of a PIC protocol in terms of its communication complexity, its
round complexity, and the work the server performs per query. Under existing
cryptographic assumptions, we give a PIC scheme which is simultaneously optimal,
up to logarithmic factors, in the work the server performs per query, the total
communication complexity, and the number of rounds of interaction. We also
present a scheme requiring more communication but sufficient storage of state by
the server to facilitate private user revocation. Finally, we present a generic
reduction which shows that one can focus on designing PIC schemes for which the
inference channels take a particularly simple threshold form.