International Association for Cryptologic Research

IACR News Central

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

To receive your credentials via mail again, please click here.

You can also access the full news archive.

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

10:17 [Pub][ePrint] Human Assisted Randomness Generation Using Video Games, by Mohsen Alimomeni and Reihaneh Safavi-Naini

  Random number generators have direct applications in information security, online

gaming, gambling, and computer science in general. True random number generators

need an entropy source which is a physical source with inherent uncertainty, to ensure

unpredictability of the output. In this paper we propose a new indirect approach to

collecting entropy using human errors in the game play of a user against a computer. We

argue that these errors are due to a large set of factors and provide a good source of

randomness. To show the viability of this proposal, we design and implement a game,

conduct a user study in which we collect user input in the game, and extract randomness

from it. We measure the rate and the quality of the resulting randomness that clearly

show effectiveness of the approach. Our work opens a new direction for construction of

entropy sources that can be incorporated into a large class of video games.

10:17 [Pub][ePrint] Crypto-analyses on \"user efficient recoverable off-line e-cashs scheme with fast anonymity revoking\", by Yalin Chen1 and Jue-Sam Chou*2

  Recently, Fan et al. proposed a user efficient recoverable off-line e-cash scheme with fast anonymity revoking. They claimed that their scheme could achieve security requirements of an e-cash system such as, anonymity, unlinkability, double spending checking, anonymity control, and rapid anonymity revoking on double spending. They further formally prove the unlinkability and the un-forgeability security features. However, after crypto-analysis, we found that the scheme cannot attain the two proven security features, anonymity and unlinkability. We, therefore, modify it to comprise the two desired requirements which are very important in an e-cash system.

10:17 [Pub][ePrint] Down the Rabbit Hole: Revisiting the Shrinking Method, by Vivien Dubois

  The paper is about methodology to detect and demonstrate impossible differentials in a block cipher. We were inspired by the shrinking technique proposed by Biham et al. in 1999 which recovered properties of scalable block cipher structures from numerical search on scaled down variants. Attempt to bind all concepts and techniques of impossible differentials together reveals a view of the search for impossible differentials that can benefit from the computational power of a computer. We demonstrate on generalized Feistel networks with internal permutations an additional clustering layer on top of shrinking which let us merge numerical data into relevant human-readable information to be used in an actual proof. After that, we show how initial analysis of scaled down TEA-like schemes leaks the relevant part of the design and the length and ends of the impossible differentials. We use that initial profiling to numerically discover 4 15-round impossible differentials (beating the current 13-round) and thousands of shorter ones.

13:17 [Pub][ePrint] rPIR: Ramp Secret Sharing based Communication Efficient Private Information Retrieval, by Lichun Li and Michael Militzer and Anwitaman Datta

  Even as data and analytics driven applications are becoming increasingly popular, retrieving data from shared databases poses a threat to the privacy of their users. For example, investors/patients retrieving records about interested stocks/diseases from a stock/medical database leaks sensitive information to the database server. PIR (Private Information Retrieval) is a promising security primitive to protect the privacy of users\' interests. PIR allows the retrieval of a data record from a database without letting the database server know which record is being retrieved. The privacy guarantees could either be information theoretic or computational. Ever since the first PIR schemes were proposed, a lot of work has been done to reduce the communication cost in the information-theoretic settings - particularly the question communication cost, i.e., the traffic from the user to the database server. The answer communication cost (the traffic from the database server to the user) has however barely been improved. When question communication cost is much lower than the record length, reducing question communication cost has marginal benefit on lowering overall communication cost. In contrast, reducing answer cost becomes very important. In this paper we propose ramp secret sharing based mechanisms that reduce the answer communication cost in information-theoretic PIR. We have designed four information-theoretic PIR schemes, using three ramp secret sharing approaches, achieving answer communication cost close to the cost of non-private information retrieval. Evaluation shows that our PIR schemes can achieve lower communication cost and the same level of privacy compared with existing schemes. Our PIR schemes\' usages are demonstrated for realistic settings of outsourced data sharing and P2P content delivery scenarios. Thus, our approach makes PIR a viable communication efficient technique to protect user interest privacy.

10:17 [Pub][ePrint] A New Algorithm for Solving the Approximate Common Divisor Problem and Cryptanalysis of the FHE based on GACD, by Jintai Ding, Chengdong Tao

  In this paper, we propose a new algorithm for solving the approximate common divisors problems, which is based on LLL reduction algorithm of certain special lattice and linear equation solving algorithm over integers. Through both theoretical argument and experimental data, we show that our new algorithm is a polynomial time algorithm under reasonable assumptions on the parameters. We use our algorithm to solve concrete problems that no other algorithm could solve before. Further more, we show that our algorithm can break

the fully homomorphic encryption schemes, which are based on the approximate common divisors problem, in polynomial time in terms of the system parameter $\\lambda$.

10:17 [Pub][ePrint] Elligator Squared: Uniform Points on Elliptic Curves of Prime Order as Uniform Random Strings, by Mehdi Tibouchi

  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.

22:17 [Pub][ePrint] Practical polynomial time solutions of several major problems in noncommutative-algebraic cryptography, by Boaz Tsaban

  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] A Fast Modular Reduction Method, by Zhengjun Cao and Ruizhong Wei and Xiaodong Lin

  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] Serge Vaudenay: The Security of Cryptographic Primitives

  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] Homomorphic AES Evaluation using NTRU, by Yarkin Doroz and Yin Hu and Berk Sunar

  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.