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

2012-05-29
21:17 [Pub][ePrint]

In this work, we study a new multivariate quadratic (MQ) assumption that can be used to construct public-key encryption schemes. In particular, we research in the following two directions:

We establish a precise \\emph{asymptotic} formulation of a family of hard MQ problems, and provide empirical evidence to confirm the hardness. %Since there are many practical solvers studied and implemented during the studies of algebraic attacks, we use

We construct public-key encryption schemes, and prove their security under the hardness assumption of this family. Also, we provide a new \\emph{perspective} to look at MQ systems that plays a key role to our design and proof of security.

As a consequence, we construct the \\emph{first} public-key encryption scheme that is \\emph{provably secure} under the MQ assumption.

Moreover, our public-key encryption scheme is efficient in the sense that it only needs a ciphertext length $L + \\poly(k)$ to encrypt a message $M\\in \\{0, 1 \\}^{L}$ for any un-prespecified polynomial $L$, where $k$ is the security parameter. This is essentially \\emph{optimal} since an additive overhead is the best we can hope for.

21:17 [Pub][ePrint]

SM3 is a hash function designed by Xiaoyun Wang et al., and

for the use of electronic authentication service system. The design of

SM3 builds upon the design of the SHA-2 hash function, but introduces

additional strengthening features. In this paper, using a higher order

differential cryptanalysis approach, we present a practical 4-sum

distinguisher against the compression function of SM3 reduced to 32

rounds. In addition, we point out a slide-rotational property of

SM3-XOR, which exists due to the fact that constants used in the rounds

are not independent.

21:17 [Pub][ePrint]

In 2013 Intel will release the AVX2 instructions, which introduce 256-bit single-instruction multiple-data (SIMD) integer arithmetic. This will enable desktop and server processors from this vendor to support 4-way SIMD computation of 64-bit add-rotate-xor algorithms, as well as 8-way 32-bit SIMD computations. AVX2 also includes interesting instructions for cryptographic functions, like any-to-any permute and vectorized table-lookup. In this paper, we explore the potential of AVX2 to speed-up the SHA-3 finalist BLAKE, and present the first working assembly implementations of BLAKE-256 and BLAKE-512 with AVX2. We then investigate the potential of the recent AVX and XOP instructions to accelerate BLAKE, and report new speed records on Sandy Bridge and Bulldozer microarchitectures (7.47 and 11.64 cycles per byte for BLAKE-256, 5.71 and 6.95 for BLAKE-512).

21:17 [Pub][ePrint]

Many cryptographic protocols exist that enable two parties to exchange items (e.g., e-commerce) or agree on something (e.g., contract-signing). In such settings, disputes may arise. Official arbitration refers to the process of resolving disputes between two (or more) parties by a trusted and authorized Judge, based on evidence provided. As an example, consider the secure cloud storage scenario where there needs to be an official arbitration process between the client and the server in case of data loss or corruption. Without such a mechanism that can be officially used by the Judge in the court, the barrier on the enterprise adoption of such systems is high.

In this paper we first formally define official arbitration, and then provide several general purpose official arbitration protocols. Later, we focus on secure cloud storage, and provide efficient official arbitration schemes that can be used on top of any secure cloud storage scheme. We furthermore present a completely automated system where the Judge can just be a computer instead of a human being. All our constructions have security proofs, and we conclude with performance measurements showing that our overhead for official arbitration is roughly 2 ms and 80 bytes for each update on the stored data.

21:17 [Pub][ePrint]

This work fall within the cadre of Cryptanalysis. Because, under

certain condition, we would give a fairly simple method to solve

the CDHP (the Problem Computational of Diffie and Hellman) and

others problems associated to it. Since, solving this problem, will help

us to provide a solution to the BDH (Problem Bilinear of Diffie and

Hellman). The CDHP and BDHP are the heart of many cryptosystems

in the point of view security, so solving it may be a threat to this

cryptosystem\'s. To elucidate this, we use a concept of geometry

algebraic named Tate Pairing.

This work is purely theoretical, we give firstly an overview on the

idea and we illustrate it by an examples to see its efficiency.

21:17 [Pub][ePrint]

Indifferentiability security of a hash mode of operation guarantees the mode\'s resistance against \\emph{all} generic attacks. It is also useful to establish the security of protocols that use hash functions as random functions. The JH hash function is one of the five finalists in the ongoing NIST SHA-3 hash function competition. Despite several years of analysis, the indifferentiability security of the JH mode (with $n$-bit digest and $2n$-bit permutation) has remained remarkably low, only at n/3 bits (FSE 2010), while the other four finalist modes -- with comparable parameter values -- offer a security guarantee of n/2 bits. In this paper, we improve the indifferentiability security bound for the JH mode to n/2 bits (from 171 to 256 bits when n=512). To put this into perspective, our result guarantees the absence of attacks on both JH-256 and JH-512 hash functions with time less than approximately 2^256 computations of the underlying 1024-bit permutation, under the assumption that the basic permutation is structurally strong. Our bounds are optimal for JH-256, and the best, so far, for JH-512. We obtain this improved bound by establishing an isomorphism of certain query-response graphs through a careful design of the simulators and the bad events. Our experimental data strongly supports the theoretically obtained results.

21:17 [Pub][ePrint]

In this paper we put forward the Bounded Player Model for secure computation. In this new model, the number of players that will ever be involved in secure computations is bounded, but the number of computations has no a-priori bound. Indeed, while the number of devices and people on this planet can be realistically estimated and bounded, the number of computations these devices will run can not be realistically bounded.

We stress that in the Bounded Player model, in addition to no apriori bound on the number of sessions, there is no synchronization barrier, no trusted party, and simulation must be performed in polynomial time.

In this setting, we achieve concurrent Zero Knowledge (cZK) with sub-logarithmic round complexity.

Our security proof is (necessarily) non-black-box, our simulator is straight-line and works as long as the number of rounds is $\\omega(1)$.

We further show that unlike previously studied relaxations of the standard model (e.g., timing assumptions, super-polynomial simulation), concurrent-secure computation is impossible to achieve in the Bounded Player model. This gives evidence that our model is closer to the standard model than previously studied models, and we believe might have additional applications.

21:17 [Pub][ePrint]

The Square attack as a means of attacking reduced round variants of AES was described in the initial description of the Rijndael block cipher. This attack can be applied to AES, with a relatively small number of chosen plaintext-ciphertext pairs, reduced to less than six rounds in the case of AES-128 and seven rounds otherwise and several extensions to this attack have been described in the literature. In this paper we describe new variants of these attacks that have a smaller time complexity than those present in the literature. Specifically, we demonstrate that the quantity of chosen plaintext-ciphertext pairs can be halved producing the same reduction in the time complexity. We also demonstrate that the time complexity can be halved again for attacks applied to AES-128 and reduced by a smaller factor for attacks applied to AES-192. This is achieved by eliminating hypotheses on-the-fly when bytes in consecutive subkeys are related because of the key schedule.

21:17 [Pub][ePrint]

Outsourced computations (where a client requests a server to perform some computation on its behalf) are becoming increasingly important due to the rise of Cloud Computing and the proliferation of mobile devices.

Since cloud providers may not be trusted, a crucial problem is the verification of the integrity and correctness of such computation, possibly in a {\\em public} way, i.e., the result of a computation can be verified by any third party, and requires no secret key -- akin to a digital signature on a message.

We present new protocols for publicly verifiable secure outsourcing of

{\\em Evaluation of High Degree Polynomials} and {\\em Matrix Multiplication}. Compared to previously

proposed solutions, ours improve in efficiency and offer security in a stronger model.

The paper also discusses several practical applications of our protocols.

21:17 [Pub][ePrint]

Recently proposed algebraic attack has been shown to be very effective on several stream ciphers. In this paper, we have investigated the resistance of PingPong family of stream ciphers against algebraic attacks. This stream cipher was proposed in 2008 to enhance the security of the improved summation generator against the algebraic attack. In particular, we focus on the PingPong-128 stream cipher\'s resistance against algebraic attack in this paper. In our analysis, it is found that an algebraic attack on PingPong family of stream ciphers require much more operations compare to the exhaustive key search on the internal state of the LFSRs. It will be shown that due to the irregular and mutual clock controlling in PingPong stream cipher the degree of the generated equation tends to grow up with each successive clock which in turn increases the overall complexity of an algebraic attack. Along with the PingPong 128 stream cipher the other instances of PingPong family stream ciphers are also investigated against the algebraic attack. Our analysis shows that, PingPong family stream ciphers are highly resistant against the algebraic attack due to their mutual and irregular clocking function.

21:17 [Pub][ePrint]

In this paper, we generalize some existing results on Boolean

functions to the $q$-ary functions defined over $\\BBZ_q$, where

$q\\geq 2$ is an integer, and obtain some new characterization of

$q$-ary functions based on spectral analysis. We provide a

relationship between Walsh-Hadamard spectra of two $p$-ary functions

$f$ and $g$ (for $p$ a prime) and their derivative $D_{f, g}$. We

provide a relationship between the Walsh-Hadamard spectra and the

decompositions of any two $p$-ary functions. Further, we investigate

a relationship between the Walsh-Hadamard spectra and the

autocorrelation of any two $q$-ary functions.