International Association for Cryptologic Research

# IACR News Central

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2014-11-25
22:17 [Pub][ePrint]

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]

In this work, we look at authenticated encryption schemes from a new perspective. As opposed to focusing solely on the {\\em security\'\'} implications of the different methods for constructing authenticated encryption schemes, we investigate the effect of the method used to construct an authenticated encryption scheme on the {\\em performance\'\'} of the construction. We show that, as opposed to the current NIST standard, by performing the authentication operation before the encryption operation, the computational efficiency of the construction can be increased, without affecting the security of the overall construction. In fact, we show that the proposed construction is even more secure than standard authentication based on universal hashing in the sense that the hashing key is resilient to key recovery attacks.

22:17 [Pub][ePrint]

Web applications are subject to several types of attacks. In particular, side-channel attacks consist in performing a statistical analysis of the web traffic to gain sensitive information about a client. In this paper, we investigate how side-channel leaks can be used on search engines such as Google or Bing to retrieve the client\'s search query. In contrast to previous works, due to payload randomization and compression, it is not always possible to uniquely map a search query to a web traffic signature and hence stochastic algorithms must be used. They yield, for the French language, an exact recovery of search word in more than 30% of the cases. Finally, we present some methods to mitigate such side-channel leaks.

22:17 [Pub][ePrint]

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 encoding

functions $Enc_i(x_i,R_i)$, $1 22:17 [Pub][ePrint] 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] Solving polynomial systems with noise over F_2 is a funda- mental problem in computer science, especially in cryptanalysis. ISBS is a new method for solving this problem based on the idea of incremen- tally solving the noisy polynomial systems and backtracking all the pos- sible noises. It had better performance than other methods in solving the Cold Boot Key recovery problem. In this paper, some further researches on ISBS are presented. We proposed a polynomial ordering scheme by which we can accelerate the incremental solving process of ISBS. We present some computation complexity bounds of ISBS. Two major im- provement strategies, artificial noise-bound strategy and two-direction searching strategy, are proposed and theoretically analyzed. Based on these improvements, we propose a variant ISBS algorithm, and by the experiments of solving the Cold Boot key recovery problem of Serpent with symmetric noise, we show that our new algorithm is more efficient than the old one. 22:17 [Pub][ePrint] 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] The concept of multivariate bijective map of an affine space$K^n$over commutative Ring$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

22:17 [Pub][ePrint]

We construct a lattice-based predicate encryption scheme for

multi-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.

2014-11-23
07:54 [Event][New]

Submission: 16 February 2015