International Association for Cryptologic Research

# IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also receive updates via:

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-26
16:07 [Event][New]

Submission: 10 February 2015
Notification: 6 April 2015
From July 14 to July 17
Location: Verona, Italy

10: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-25
22:17 [Pub][ePrint]

This paper presents a new and more realistic model for fault attacks and statistical and algebraic techniques to improve fault analysis in general. Our algebraic techniques is an adapted solver for systems of equations based on ElimLin and XSL.

We use these techniques to introduce two new fault attacks on the hardware oriented block cipher Katan32 from the Katan family of block ciphers.

We are able to break full Katan using $4$ faults and $2^{29.04}$ Katan evaluations with a theoretical statistical fault attack and $7.19$ faults in $2^{27.2}$ Katan evaluations with a tested algebraic one.

This is a great improvement over the existing fault attacks which need $115$ and $140$ faults respectively.

Furthermore, our algebraic attack can be executed on a normal computer.

22:17 [Pub][ePrint]

A necessary and sufficient condition for the asymptotic idealness of the Asmuth-Bloom threshold secret sharing scheme is proposed. Apart from this, a comprehensive analysis of the known variants of the Asmuth-Bloom threshold secret sharing scheme is provided, clarifying the security properties achieved by each of them.

22:17 [Pub][ePrint]

We consider a public and keyless code $(\\Enc,\\Dec)$ which is used to encode a message $m$ and derive a codeword $c = \\Enc(m)$. The codeword can be adversarially tampered via a function $f \\in \\F$ from some tampering function family $\\F$, resulting in a tampered value $c\' = f(c)$. We study the different types of security guarantees that can be achieved in this scenario for different families $\\F$ of tampering attacks.

Firstly, we initiate the general study of tamper-detection codes, which must detect that tampering occurred and output $\\Dec(c\') = \\bot$. We show that such codes exist for any family of functions $\\F$ over $n$ bit codewords, as long as $|\\F| < 2^{2^n}$ is sufficiently smaller than the set of all possible functions, and the functions $f \\in \\F$ are further restricted in two ways: (1) they can only have a few fixed points $x$ such that $f(x)=x$, (2) they must have high entropy of $f(x)$ over a random $x$. Such codes can also be made efficient when $|\\F| = 2^{\\poly(n)}$. For example, $\\F$ can be the family of all low-degree polynomials excluding constant and identity polynomials. Such tamper-detection codes generalize the algebraic manipulation detection (AMD) codes of Cramer et al. (EUROCRYPT \'08).

Next, we revisit non-malleable codes, which were introduced by Dziembowski, Pietrzak and Wichs (ICS \'10) and require that $\\Dec(c\')$ either decodes to the original message $m$, or to some unrelated value (possibly $\\bot$) that doesn\'t provide any information about $m$. We give a modular construction of non-malleable codes by combining tamper-detection codes and leakage-resilient codes. This gives an alternate proof of the existence of non-malleable codes with optimal rate for any family $\\F$ of size $|\\F| < 2^{2^n}$, as well as efficient constructions for families of size $|\\F| = 2^{\\poly(n)}$.

Finally, we initiate the general study of continuous non-malleable codes, which provide a non-malleability guarantee against an attacker that can tamper a codeword multiple times. We define several variants of the problem depending on: (I) whether tampering is persistent and each successive attack modifies the codeword that has been modified by previous attacks, or whether tampering is non-persistent and is always applied to the original codeword, (II) whether we can self-destruct and stop the experiment if a tampered codeword is ever detected to be invalid or whether the attacker can always tamper more. In the case of persistent tampering and self-destruct (weakest case), we get a broad existence results, essentially matching what\'s known for standard non-malleable codes. In the case of non-persistent tampering and no self-destruct (strongest case), we must further restrict the tampering functions to have few fixed points and high entropy. The two intermediate cases correspond to requiring only one of the above two restrictions.

These results have applications in cryptography to related-key attack (RKA) security and to protecting devices against tampering attacks without requiring state or randomness.

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.