*22:17* [Pub][ePrint]
Black Box Separations for Differentially Private Protocols, by Dakshita Khurana and Hemanta K. Maji and Amit Sahai
We study the maximal achievable accuracy of distributed differentially private protocols for a large natural class of boolean functions, in the computational setting.In the information theoretic model, McGregor et al. [FOCS 2010] and Goyal et al. [CRYPTO 2013] have demonstrated several functionalities whose differentially private computation results in much lower accuracies in the distributed setting, as compared to the client-server setting.

We explore lower bounds on the computational assumptions under which this particular accuracy gap can be possibly reduced for general two-party boolean output functions. In the distributed setting, it is possible to achieve optimal accuracy, i.e. the maximal achievable accuracy in the client-server setting, for any function, if a semi-honest secure protocol for oblivious transfer exists. However, we show the following strong impossibility results:

1) For any boolean function and fixed level of privacy, the maximal achievable accuracy of any (fully) black-box construction based on existence of key-agreement protocols is at least a constant smaller than optimal achievable accuracy. Since key-agreement protocols imply the existence of one-way functions, this separation also extends to one-way functions.

2) Our results are tight for the AND and XOR functions. For AND, there exists an accuracy threshold such that any accuracy up to the threshold can be information theoretically achieved; while no (fully) black-box construction based on existence of key-agreement can achieve accuracy beyond this threshold. An analogous statement is also true for XOR (albeit with a different accuracy threshold).

Our results build on recent developments in black-box separation techniques for functions with private input; and consequently translate information theoretic impossibilities into black-box separation results.

*22:17* [Pub][ePrint]
Non-Interactive Secure Multiparty Computation, by Amos Beimel and Ariel Gabizon and Yuval Ishai and Eyal Kushilevitz and Sigurd Meldgaard and Anat Paskin-Cherniavsky
We introduce and study the notion of non-interactive secure multiparty computation (NIMPC). An NIMPC protocol for a function $f(x_1,\\ldots,x_n)$ is specified by a joint probability distribution $R=(R_1,\\ldots,R_n)$ and local encodingfunctions $Enc_i(x_i,R_i)$, $1

*22:17* [Pub][ePrint]
When are Fuzzy Extractors Possible?, by Benjamin Fuller and Leonid Reyzin and Adam Smith
Fuzzy extractors (Dodis et al., Eurocrypt 2004) convert repeated noisy readings of a high-entropy secret into the same uniformly distributed key. A minimum condition for the security of the key is the hardness of guessing a value that is similar to the secret, because the fuzzy extractor converts such a guess to the key. We define fuzzy min-entropy to quantify this property of a noisy source of secrets.High fuzzy min-entropy is necessary for the existence of a fuzzy extractor; moreover, there is evidence that it may be sufficient when only computational security is required. Nevertheless, information-theoretic fuzzy extractors are not known for many practically relevant sources of high fuzzy min-entropy. In this work, we ask: is fuzzy min-entropy sufficient to build information-theoretic fuzzy extractors?

We give a positive answer to this question when the fuzzy extractor knows the precise distribution of the physical source. On the other hand, because it is imprudent to assume precise knowledge of a complicated distribution, fuzzy extractors are typically designed to work for families of sources. We show that this uncertainty is an impediment to security by building a family of high fuzzy min-entropy sources for which no fuzzy extractor can exist.

We provide similar but stronger results for secure sketches, whose goal is not to derive a consistent key, but to recover a consistent reading of the secret.

*22:17* [Pub][ePrint]
Malicious-Client Security in Blind Seer: A Scalable Private DBMS, by Ben Fisch, Binh Vo, Fernando Krell, Abishek Kumarasubramanian, Vladimir Kolesnikov, Tal Malkin, Steven M. Bellovin
The Blind Seer system (Oakland 2014) is an efficient and scalable DBMS that affords both client query privacy and server data protection. It also provides the ability to enforce authorization policies on the system, restricting client\'s queries while maintaining the privacy of both query and policy. Blind Seer supports a rich query set, including arbitrary boolean formulas, and is provably secure with respect to a controlled amount of search pattern leakage. No other system to date achieves this tradeoff of performance, generality, and provable privacy.A major shortcoming of Blind Seer is its reliance on semi-honest security, particularly for access control and data protection. A malicious client could easily cheat the query authorization policy and obtain any database records satisfying any query of its choice, thus violating basic security features of any standard DBMS. In sum, Blind Seer offers additional privacy to a client, but sacrifices a basic security tenet of DBMS.

In the present work, we completely resolve the issue of a malicious client. We show how to achieve robust access control and data protection in Blind Seer with virtually no added cost to performance or privacy. Our approach also involves a novel technique for a semi-private function secure function evaluation (SPF-SFE) that may have independent applications.

We fully implement our solution and report on its performance.

*22:17* [Pub][ePrint]
On two windows multivariate cryptosystem depending on random parameters, by Urszula RomaĆczuk-Polubiec, Vasyl Ustimenko
The concept of multivariate bijective map of an affine space $K^n$ over commutativeRing $K$ was already used in Cryptography. We consider the idea of nonbijective multivariate

polynomial map $F_n$ of $K^n$ into $K^n$ represented as \'\'partially invertible decomposition\'\'

$F^{(1)}_nF^{(2)}_n \\dots

F^{(k)}_n$, $k=k(n)$, such that knowledge on the decomposition and given

value $u=F(v)$ allow to restore a special part $v\'$ of reimage $v$.

We combine an idea of \'\'oil and vinegar signatures cryptosystem\'\' with the idea of linguistic graph based map with partially invertible decomposition to introduce a new

cryptosystem. The decomposition will be induced by pseudorandom walk on the linguistic graph

and its special quotient (homomorphic image). We estimate the complexity of such general algorithm in case of special family of graphs with quotients, where both graphs form known

families of Extremal Graph Theory. The map created by key holder (Alice) corresponds to

pseudorandom sequence of ring elements.

The postquantum version of the algorithm can be obtained simply by the usage of random strings

instead of pseudorandom.

*22:17* [Pub][ePrint]
Predicate Encryption for Multi-Dimensional Range Queries from Lattices, by Romain Gay and Pierrick M\\\'eaux and Hoeteck Wee
We construct a lattice-based predicate encryption scheme formulti-dimensional range and multi-dimensional subset queries. Our

scheme is selectively secure and weakly attribute-hiding, and its

security is based on the standard learning with errors (LWE)

assumption. Multi-dimensional range and subset queries capture many interesting applications pertaining to searching on encrypted data. To the best of our knowledge, these are the first lattice-based predicate encryption schemes for functionalities beyond IBE and inner product.