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

2015-01-02
13:17 [Pub][ePrint]

For large ranks, there is no good algorithm that decides whether a given lattice has an orthonormal basis. But when the lattice is given with enough symmetry, we can construct a provably deterministic polynomial-time algorithm to accomplish this, based on the work of Gentry and Szydlo. The techniques involve algorithmic algebraic number theory, analytic number theory, commutative algebra, and lattice basis reduction.

13:17 [Pub][ePrint]

At the center of many lattice-based constructions is an algorithm that samples a short vector $s$, satisfying $[A|AR-HG]s=t\\bmod q$ where $A,AR, H, G$ are public matrices and $R$ is a trapdoor. Although the algorithm crucially relies on the knowledge of the trapdoor $R$ to perform this sampling efficiently, the distribution it outputs should be independent of $R$ given the public values. We present a new, simple algorithm for performing this task. The main novelty of our sampler is that the distribution of $s$ does not need to be Gaussian, whereas all previous works crucially used the properties of the Gaussian distribution to produce such an $s$. The advantage of using a non-Gaussian distribution is that we are able to avoid the high-precision arithmetic that is inherent in Gaussian sampling over arbitrary lattices. So while the norm of our output vector $s$ is on the order of $\\sqrt{n}$ to $n$ - times larger (the representation length, though, is only a constant factor larger) than in the samplers of Gentry, Peikert, Vaikuntanathan (STOC 2008) and Micciancio, Peikert (EUROCRYPT 2012), the sampling itself can be done very efficiently. This provides a useful time/output trade-off for devices with constrained computing power. In addition, we believe that the conceptual simplicity and generality of our algorithm may lead to it finding other applications.

13:17 [Pub][ePrint]

Attribute-based Encryption (ABE) has found enormous application in

ne-grained access control of shared data, particularly in public cloud. In 2013, Zhang et al proposed a scheme called match-then-decrypt [1], where before running the decryption algorithm the user requires to perform a match operation with attribute(s) that provides the required information to identify whether a particular user is the intended recipient for the ciphertext. As in [1], the match-then-decrypt operation saves the computational cost at the receiver and the scheme supports receivers\' anonymity. In this paper, we show that Zhang et al \'s scheme [1] does not support receivers\' anonymity. Any legitimate user or an adversary can successfully check whether an attribute is required in the matching phase, in turn, can reveal the receivers\' identity from the attribute.

2015-01-01
16:17 [Pub][ePrint]

Secure Multi-party Computation (MPC) is one of the foundational achievements of modern cryptography,

allowing multiple, distrusting, parties to jointly compute a function of their inputs, while revealing nothing but the

output of the function. Following the seminal works of Yao and Goldreich, Micali and Wigderson and Ben-Or, Goldwasser and Wigderson,

the study of MPC has expanded to consider a wide variety of questions, including variants in the attack model,

underlying assumptions, complexity and composability of the resulting protocols.

One question that appears to have received very little attention, however, is that of MPC over an

underlying communication network whose structure is, in itself, sensitive information. This question, in addition to being

of pure theoretical interest, arises naturally in many contexts: designing privacy-preserving social-networks, private peer-to-peer computations,

vehicle-to-vehicle networks and the internet of things\'\' are some of the examples.

In this paper, we initiate the study of topology-hiding computation\'\' in the computational setting. We give formal definitions

in both simulation-based and indistinguishability-based flavors. We show that, even for fail-stop adversaries, there are some strong

impossibility results. Despite this, we show that protocols for topology-hiding computation can be constructed in the semi-honest

and fail-stop models, if we somewhat restrict the set of nodes the adversary may corrupt.

2014-12-31
19:17 [Pub][ePrint]

We analyse the complexity of algebraic algorithms for solving systems of linear equations with \\emph{noise}. Such systems arise naturally in the theory of error-correcting codes as well as in computational learning theory. More recently, linear systems with noise have found application in cryptography. The \\emph{Learning with Errors} (LWE) problem has proven to be a rich and versatile source of innovative cryptosystems, such as fully homomorphic encryption schemes. Despite the popularity of the LWE problem, the complexity of algorithms for solving it is not very well understood, particularly when variants of the original problem are considered. Here, we focus on and generalise a particular method for solving these systems, due to Arora \\& Ge, which reduces the problem to non-linear but noise-free system solving. Firstly, we provide a refined complexity analysis for the original Arora-Ge algorithm for LWE. Secondly, we study the complexity of applying algorithms for computing Gröbner basis, a fundamental tool in computational commutative algebra, to solving Arora-Ge-style systems of non-linear equations. We show positive and negative results. On the one hand, we show that the use of Gröbner bases yields an exponential speed-up over the basic Arora-Ge approach. On the other hand, we give a negative answer to the natural question whether the use of such techniques can yield a subexponential algorithm for the LWE problem. Under a mild algebraic assumption, we show that it is highly unlikely that such an improvement exists.

We also consider a variant of LWE known as BinaryError-LWE introduced by Micciancio and Peikert recently. By combining Gröbner basis algorithms with the Arora-Ge modelling, we show under a natural algebraic assumption that BinaryError-LWE can be solved in subexponential time as soon as the number of samples is quasi-linear, e.g.\\

$m=O(n \\log \\log n)$. We also derive precise complexity bounds for BinaryError-\\LWE with $m=O(n)$, showing that this new approach yields better results than best currently-known generic (exact) CVP solver as soon as $m/n \\geq 6.6$. More generally, our results provide a good picture of the hardness degradation of BinaryError-LWE for a number of samples ranging from $m=n\\left(1+\\Omega\\big(1/{\\rm log}(n)\\big)$ (a case for which BinaryError-\\LWE{} is as hard as solving some lattice problem in the worst case) to $m=O(n^2)$ (a case for which it can be solved in polynomial-time). This addresses an open question from Micciancio and Peikert. Whilst our results do not contradict the hardness results obtained by Micciancio and Peikert, they should rule out BinaryError-\\LWE for many cryptographic applications. The results in this work depend crucially on the assumption the algebraic systems considered systems are not easier and not harder to solve than a random system of equations. We have verified experimentally such hypothesis. We also have been able to prove formally the assumptions is several restricted situations. We emphasize that these issues are highly non-trivial since proving our assumptions in full generality would allow to prove a famous conjecture in commutative algebra known as Fröberg\'s Conjecture.

19:17 [Pub][ePrint]

ITU{\\scriptsize{BEE}} is a software oriented lightweight block cipher, which is first proposed at LightSec 2013. The cipher is especially suitable for limited resource application, such as sensor nodes in wireless sensor networks. To evaluate the security level of the cipher, we perform differential attacks on ITU{\\scriptsize{BEE}} reduced to 10 rounds and 11 rounds with the time complexities ${2^{65.97}}$ and ${2^{79.03}}$, respectively. To our best knowledge, our analysis is the first related-key differential cryptanalysis on the security of 10-round ITU{\\scriptsize{BEE}}.

19:17 [Pub][ePrint]

Security and safety critical devices must undergo penetration testing including Side-Channel Attacks (SCA) before certification.

SCA are powerful and easy to mount but often need huge computation power, especially in the presence of countermeasures.

Few efforts have been done to reduce the computation complexity of SCA by selecting a small subset of points where leakage prevails.

In this paper, we propose a method to detect relevant leakage points in side-channel traces.

The method is based on Normalized Inter-Class Variance (NICV).

A key advantage of NICV over state-of-the-art is that NICV does neither need a clone device nor the knowledge of secret parameters of the crypto-system.

NICV has a low computation requirement and it detects leakage using public information like input plaintexts or output ciphertexts only.

It is shown that NICV can be related to Pearson correlation and signal to noise ratio (SNR) which are standard metrics.

NICV can be used to theoretically compute the minimum number of traces required to attack an implementation.

A theoretical rationale of NICV with some practical application on real crypto-systems are provided to support our claims.

19:17 [Pub][ePrint]

We give a new framework for obtaining signatures with a tight security reduction from standard hardness assumptions. Concretely, we show that any Chameleon Hash function can be transformed into a (binary) tree-based signature scheme with tight security. The transformation is in the standard model, i.e., it does not make use of any random oracle. For specific assumptions (such as RSA, Diffie-Hellman and Short Integer Solution (SIS)) we further manage to obtain a more efficient flat-tree construction. Our framework explains and generalizes most of the existing schemes as well as providing a generic means for constructing tight signature schemes based on arbitrary assumptions, which improves the standard Merkle tree transformation. Moreover, we obtain the first tightly secure signature scheme from the SIS assumption and several schemes based on Diffie-Hellman in the standard model.

Some of our signature schemes are also structure-preserving and can (using known techniques) be combined with Groth-Sahai proof methodology to yield tightly secure and efficient simulation-sound NIZK proofs of knowledge and CCA-secure encryption in the multi-user/-challenge setting under classical assumptions.

2014-12-29
16:17 [Pub][ePrint]

We study the problem of private outsourced sorting of encrypted

data. We start by proposing a novel sorting protocol that allows a user to outsource his data to a cloud server in an encrypted form and then request the server to perform computations on this data and sort the result. To perform the sorting the server is assisted by a secure coprocessor with minimal computational and memory resources. The server and the coprocessor are assumed to be honest but curious, i.e., they honestly follow the protocol but are interested in learning more about the user data. We refer to the new protocol as private outsourced sorting\'\' since it guarantees that neither the server

nor the coprocessor learn anything about user data as long as they are

non-colluding. We formally define private outsourced sorting and provide an efficient construction that is based on semi-homomorphic encryption.

As an application of our private sort, we present MSRE: the first scheme for outsourced search over encrypted data that efficiently answers multi-term queries with the result ranked using frequency of query terms in the data, while maintaining data privacy. To construct MSRE we use searchable encryption techniques combined with our new private sort framework. Finally, although not discussed in this work, we believe that our private sort framework can turn out to be an important tool for more applications that require outsourced sorting while maintaining data privacy, e.g., database queries.

2014-12-27
01:17 [Pub][ePrint]

n this paper, we study the security margins of hash functions BLAKE and BLAKE2 against the boomerang attack. We launch boomerang attacks on all four members of BLAKE and BLAKE2, and compare their complexities. We propose 8.5-round boomerang attacks on both BLAKE-512 and BLAKE2b with complexities $2^{464}$ and $2^{474}$ respectively. We also propose 8-round attacks on BLAKE-256 with complexity $2^{198}$ and 7.5-round attacks on BLAKE2s with complexity $2^{184}$. We verify the correctness of our analysis by giving practical 6.5-round Type I boomerang quartets for each member of BLAKE and BLAKE2.

According to our analysis, some tweaks introduced by BLAKE2 have increased its resistance against boomerang attacks to a certain extent.

But on the whole, BLAKE still has higher a secure margin than BLAKE2.

01:17 [Pub][ePrint]

We will introduce different notions of independence, especially computational independence (or more precise independence by polynomial-size circuits (PSC)), which is the analog to computational indistinguishability. We will give some first implications and will show that an encryption scheme having PSC independent plaintexts and ciphertexts is equivalent to having indistinguishable encryptions.