  Private inference refers to a two-party setting in which one has a model
(e.g., a linear classifier), the other has data, and the model is to be applied
over the data while safeguarding the privacy of both parties. In particular,
models in which the weights are quantized (e.g., to 1 or -1) gained increasing
attention lately, due to their benefits in efficient, private, or robust
computations. Traditionally, private inference has been studied from a
cryptographic standpoint, which suffers from high complexity and degraded
accuracy. More recently, Raviv et al. showed that in quantized models, an
information theoretic tradeoff exists between the privacy of the parties, and a
scheme based on a combination of Boolean and real-valued algebra was presented
which attains that tradeoff. Both the scheme and the respective bound required
the computation to be done exactly. In this work we show that by relaxing the
requirement for exact computation, one can break the information theoretic
privacy barrier of Raviv et al., and provide better privacy at the same
communication costs. We provide a scheme for such approximate computation,
bound its error, show its improved privacy, and devise a respective lower bound
for some parameter regimes.
