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

When represented as a bit string in a standard way, even using point compression, an elliptic curve point is easily distinguished from a random bit string. This property potentially allows an adversary to tell apart network traffic that makes use of elliptic curve cryptography from random traffic, and then intercept, block or otherwise tamper with such traffic.

Recently, Bernstein, Hamburg, Krasnova and Lange proposed a partial solution to this problem in the form of Elligator: an algorithm for representing around half of the points on a large class of elliptic curves as close to uniform random strings. Their proposal has the advantage of being very efficient, but suffers from several limitations:

* Since only a subset of all elliptic curve points can be encoded as a string, their approach only applies to cryptographic protocols transmitting points that are rerandomizable in some sense.

* Supported curves all have non-trivial $2$-torsion, so that Elligator cannot be used with prime-order curves, ruling out standard ECC parameters and many other cryptographically interesting curves such as BN curves.

* For indistinguishability to hold, transmitted points have to be uniform in the whole set of representable points; in particular, they cannot be taken from a prime order subgroup, which, in conjunction with the non-trivial $2$-torsion, rules out protocols that require groups of prime order.

In this paper, we propose an approach to overcome all of these limitations. The general idea is as follows: whereas Bernstein et al. represent an elliptic curve point P as the bit string \\iota^{-1}(P), where \\iota is an injective encoding to the curve (which is only known to exist for some curve families, and reaches only half of all possible points), we propose to use a randomly sampled preimage of P under an admissible encoding of the form f^{\\otimes 2}: (u,v)\\mapsto f(u)+f(v), where f is essentially any algebraic encoding. Such encodings f exist for all elliptic curves, and the corresponding admissible encodings f^{\\otimes 2} are essentially surjective, inducing a close to uniform distribution on the curve.

As a result, our bit string representation is somewhat less compact (about twice as long as Elligator), but it has none of the limitations above, and can be computed quite efficiently when the function f is suitably chosen.

2014-01-15
22:17 [Pub][ePrint]

We provide new provable polynomial time solutions

of a number of problems in noncommutative-algebraic cryptography.

In contrast to the linear centralizer method of \\cite{LinCent}, the new method is

very simple: In order to solve linear equations on matrices

restricted to matrix groups, solve them over the generated

algebras. We name this approach the \\emph{algebraic span method}.

The resulting algorithms are have substantially better performance than those of \\cite{LinCent}.

These algorithms constitute cryptanalyses of the motivating protocols that

cannot be foiled by changing the distributions used in the protocols, and are

practical for most affordable parameter settings.

16:49 [Event][New]

16:17 [Pub][ePrint]

We put forth a lookup-table-based modular reduction method which partitions the binary string of an integer to be reduced into blocks according to its runs. Its complexity depends on the amount of runs in the binary string. We show that the new reduction is almost twice as fast as the popular Barrett\'s reduction, and provide a thorough complexity analysis of the method.

07:05 [PhD][Update]

Name: Serge Vaudenay
Topic: The Security of Cryptographic Primitives
Category:secret-key cryptography

Description: In the early fifties, Claude Shannon initiated the theory of cryptographic primitives. He defined the notion of diffusion and confusion. However, this theory did not developed very much until nowadays. Recently, the differential cryptanalysis and the linear cryptanalysis gave a significant advance in the analysis of the primitives. Security criteria for confusion, essentially nonlinearity criteria, has been proposed. In this thesis, we show how to define a notion of complexity on the graph structure of the primitives and how to study it. This gives security criteria of the computational network. We propose new criteria for diffusion. Finally, we unify the two types of cryptanalysis, getting rid of their linear aspects by a statistical approach.[...]

04:17 [Pub][ePrint]

Since its introduction more than a decade ago the homomorphic properties of the NTRU encryption scheme have gone largely ignored. A variant of NTRU proposed by Stehle and Steinfeld was recently extended into a full fledged multi-key fully homomorphic encryption scheme by Alt-Lopez, Tromer and Vaikuntanathan (ATV). This NTRU based FHE presents a viable alternative to the currently dominant BGV style FHE schemes. While the scheme appears to be more efficient, a full implementation and comparison to BGV style implementations has been missing in the literature. In this work, we develop a customized implementation of the ATV scheme. First parameters are selected to yield an efficient and yet secure ATV instantiation. We present an analysis of the noise growth that allows us to formulate a modulus cutting strategy for arbitrary circuits. Furthermore, we introduce a specialization of the ring structure that allows us to drastically reduce the public key size making evaluation of deep circuits such as the AES block cipher viable on a standard computer with a reasonable amount of memory. Moreover, with the modulus specialization the need for key switching is eliminated. Finally, we present a generic bit-sliced implementation of the ATV scheme that embodies a number of optimizations. To assess the performance of the scheme we homomorphically evaluate the full 10 round AES circuit in 31 hours with 2048 message slots resulting in 55 sec per AES block evaluation time.

2014-01-14
16:17 [Pub][ePrint]

In our previous work, we have proposed a framework which allows tools

that can check standard noninterference properties but a priori

cannot deal with cryptography to establish cryptographic

indistinguishability properties, such as privacy properties, for

Java programs. We refer to this framework as the CVJ framework

(Cryptographic Verification of Java Programs) in this paper.

While so far the CVJ framework directly supports public-key

encryption (without corruption and without a public-key

infrastructure) only, in this work we further instantiate the

framework to support, among others, public-key encryption and

digital signatures, both with corruption and a public-key

infrastructure, as well as (private) symmetric encryption. Since

these cryptographic primitives are very common in security-critical

applications, our extensions make the framework much more widely

applicable.

To illustrate the usefulness and applicability of the extensions

proposed in this paper, we apply the framework along with the tool

Joana, which allows for the fully automatic verification of

noninterference properties of Java programs, to establish

cryptographic privacy properties of a (non-trivial) cloud storage

application, where clients can store private information on a remote

server.

13:17 [Pub][ePrint]

In our previous work, we have proposed a framework which allows tools

that can check standard noninterference properties but a priori

cannot deal with cryptography to establish cryptographic

indistinguishability properties, such as privacy properties, for

Java programs. We refer to this framework as the CVJ framework

(Cryptographic Verification of Java Programs) in this paper.

While so far the CVJ framework directly supports public-key

encryption (without corruption and without a public-key

infrastructure) only, in this work we further instantiate the

framework to support, among others, public-key encryption and

digital signatures, both with corruption and a public-key

infrastructure, as well as (private) symmetric encryption. Since

these cryptographic primitives are very common in security-critical

applications, our extensions make the framework much more widely

applicable.

To illustrate the usefulness and applicability of the extensions

proposed in this paper, we apply the framework along with the tool

Joana, which allows for the fully automatic verification of

noninterference properties of Java programs, to establish

cryptographic privacy properties of a (non-trivial) cloud storage

application, where clients can store private information on a remote

server.

01:17 [Pub][ePrint]

2014-01-13
22:17 [Pub][ePrint]

Mobile text messages are currently vulnerable to inspection, modification, and replay by network operators and those that influence network operators. This paper describes a set of protocols that provide end-to-end message confidentiality, integrity, and authenticity over the high latency, low bandwidth, Short Message Service provided by GSM networks.

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

This paper introduces the use of channel equalization as a method of simplifying side channel analysis attacks, by eeffectively collapsing all points in a power measurement trace into a single random variable. This uses a simple Finite Impulse Response (FIR) linear equalizer, which has been studied extensively in communications systems. In addition the estimation of a channel model is used in developing the Channel Estimation Analysis (CEA), which is a generic attack requiring similar assumptions to the Correlation Power Analysis (CPA) attack. Both channel equalization and the CEA attack are straight-forward to apply to real systems, and Python examples are provided. Results of attacking unprotected AES-128 and protected AES-256RSM on a microcontroller are provided.