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

2013-07-22
15:17 [Pub][ePrint]

Flush+Reload is a cache side-channel attack that monitors access to data in shared pages. In this paper we demonstrate how to use the attack to extract private encryption keys from GnuPG. The high resolution and low noise of the Flush+Reload attack enables a spy program to recover over 98% of the bits of the private key in a single decryption or signing round. Unlike previous attacks, the attack targets the last level L3 cache. Consequently, the spy program and the victim do not need to share the execution core of the CPU. The attack is not limited to a traditional OS and can be used in a virtualised environment, where it can attack programs executing in a different VM.

15:17 [Pub][ePrint]

We remark that AKS primality testing algorithm needs about 1,000,000,000 G (gigabyte) storage space for a number of 1024 bits. Such storage requirement is hard to meet in practice. To the best of our knowledge, it is impossible for current operating systems to write and read data in so huge storage space. Thus, the running time for AKS algorithm shuould not be simply estimated as usual in terms of the amount of arithmetic operations.

15:17 [Pub][ePrint]

White-box cryptography aims to protect the secret key of a cipher in an environment in which an adversary has full access to the implementation of the cipher and its execution environment. In 2002, Chow, Eisen, Johnson and van Oorschot proposed a white-box implementation of AES. In 2004, Billet, Gilbert and Ech-Chatbi presented an efficient attack (referred to as the BGE attack) on this implementation, extracting its embedded AES key with a work factor of $2^{30}$. In 2012, Tolhuizen presented an improvement of the most time-consuming phase of the BGE attack. This paper presents several improvements to the other phases of the BGE attack. The paper shows that the overall work factor of the BGE attack is reduced to $2^{22}$ when all improvements are implemented. In 2010, Karroumi presented a white-box AES implementation that is designed to withstand the BGE attack. This paper shows that the implementations of Karroumi and Chow \\emph{et al.} are the same. As a result, Karroumi\'s white-box AES implementation is vulnerable to the attack it was designed to resist.

15:17 [Pub][ePrint]

In this work, we study indistinguishability obfuscation and functional encryption for general circuits:

Indistinguishability obfuscation requires that given any two equivalent circuits C_0 and C_1 of similar size, the obfuscations of C_0 and C_1 should be computationally indistinguishable.

In functional encryption, ciphertexts encrypt inputs x and keys are issued for circuits C. Using the key SK_C to decrypt a ciphertext CT_x = Enc(x), yields the value C(x) but does not reveal anything else about x. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually.

We give constructions for indistinguishability obfuscation and functional encryption that supports all polynomial-size circuits. We accomplish this goal in three steps:

- We describe a candidate construction for indistinguishability obfuscation for NC1 circuits. The security of this construction is based on a new algebraic hardness assumption. The candidate and assumption use a simplified variant of multilinear maps, which we call Multilinear Jigsaw Puzzles.

- We show how to use indistinguishability obfuscation for NC1 together with Fully Homomorphic Encryption (with decryption in NC1) to achieve indistinguishability obfuscation for all circuits.

- Finally, we show how to use indistinguishability obfuscation for circuits, public-key encryption, and non-interactive zero knowledge to achieve functional encryption for all circuits. The functional encryption scheme we construct also enjoys succinct ciphertexts, which enables several other applications.

15:17 [Pub][ePrint]

In this paper, we propose two new frameworks for joint encryption encoding schemes based on polar codes, namely efficient and secure joint secret/public key encryption channel coding schemes. The issue of using new coding structure, i.e. polar codes in McEliece-like and RN-like schemes is addressed. Cryptanalysis methods show that the proposed schemes have an acceptable level of security with a relatively smaller key size in comparison with the previous works. The results indicate that both schemes provide an efficient error performance and benefit from the higher code rate which can approach to the channel capacity for large enough polar codes. The resulted characteristics of the proposed schemes make them suitable for high-speed communications, such as deep space communication systems.

15:17 [Pub][ePrint]

Peris-Lopez et al. recently provides some guidelines that should be followed to

design a secure yoking-proof protocol. In addition, conforming to those guidelines and

EPC C1 G2, they presented a yoking-proof for low-cost RFID tags, named Kazahaya. However,

in this letter, we scrutinize its security showing how an passive adversary can retrieve secret

parameters of patient\'s tag in cost of O(216) o-line PRNG evaluations. Given the tag\'s secret

parameters, any security claims are ruined. Nevertheless, to show other weaknesses of the

protocol and rule out any possible improvement by increasing the length of the used PRNG,

we presented a forgery attack that shows that a proof generated at time tn can be used to

forge a valid proof for any desired time tj . The success probability of this attack is `1\' and the

complexity is negligible.

14:28 [Job][New]

We are looking for a post-doc researcher to join a vibrant and growing team of security researchers at the Centre for Cybercrime and Computer Security (CCCS) at Newcastle University, UK. Newcastle University is recognized by EPSRC/GCHQ as one of the 11 Academic Centres of Excellence in Cyber Security Research in the country.

The post is supported by a five-year ERC Starting Grant on \\\"Self-enforcing Electronic Voting: Trustworthy Elections in the Presence of Corrupt Authorities\\\". The candidate should have a PhD in Computer Science, engineering or a related discipline, with a solid background in security. Previous research experience on e-voting is desirable but not required.

An ideal candidate would be the one who 1) has good understanding of theory; 2) has good practical skills; 3) has a keen interest to tackle real-world problems.

08:48 [Event][New]

Submission: 12 November 2013
From March 3 to March 5
Location: London, United Kingdom

2013-07-19
00:17 [Pub][ePrint]

We study various classical secure computation problems in the context of fairness, and relate them with each other. We also systematically study fair sampling problems (i.e., inputless functionalities) and discover three levels of complexity for them.

Our results include the following:

-Fair exchange cannot be securely reduced to the problem of fair coin-tossing by an r-round protocol, except with an error that is $\\Omega(1/r)$.

-Finite fair {\\em sampling} problems with rational probabilities can all be reduced to fair coin-tossing and unfair 2-party computation (or equivalently, under computational assumptions). Thus, for this class of functionalities, fair coin-tossing is complete.

-Only sampling problems which have fair protocols without any fair setup are the trivial ones in which the two parties can sample their outputs independently. Others all have an $\\Omega(1/r)$ error, roughly matching an upper bound for fair sampling from Moran et al.(TCC 2009).

-We study communication-less protocols for sampling, given another sampling problem as setup, since such protocols are inherently fair. We use spectral graph theoretic tools to show that it is impossible to reduce a sampling problem with {\\em common information} (like fair coin-tossing) to a sampling problem without (like \'noisy\' coin-tossing, which has a small probability of disagreement).

The last result above is a slightly sharper version of a classical result by Witsenhausen from 1975. Our proof reveals the connection between the tool used by Witsenhausen, namely \'maximal correlation\', and spectral graph theoretic tools like Cheeger inequality.

00:17 [Pub][ePrint]

Transferable conditional electronic-cash (e-cash) allows a payer to spend an e-cash based on the outcome not known in advance. It also allows a payee to spend the e-cash to others, or deposit the e-cash to a bank based on the future outcome. Among security properties, the anonymity of the payer has been widely studied. However, the payer is linkable in the existing conditional e-cash schemes. This paper presents the first optimally anonymous and transferable conditional electronic-cash (e-cash) system based on two recent cryptographic primitives, i.e., the Groth-Sahai(GS) proof system

and the commuting signatures, to obtain the user\'s unlinkability and optimal anonymity. A publisher is introduced to publish the conditions, and is firstly formalized. By dividing the deposit protocol into two parts, the anonymity of the user is obtained in the deposit protocol. Compared with the existing conditional e-cash schemes, this scheme has the constant size for the computation and communication. Finally, we give the security proof in the standard model.

2013-07-18
21:17 [Pub][ePrint]

Most implementations of public key cryptography employ exponentiation algorithms. Side-channel attacks on secret exponents are typically bound to the leakage of single executions because of cryptographic protocols or side-channel countermeasures such as blinding. We propose a new class of algorithms, i.e. unsupervised cluster classification algorithms, to attack cryptographic exponentiations and recover secret exponents without any prior profiling or heuristic leakage models. Not requiring profiling is a significant advantage to attackers. In fact, the proposed non-profiled single-execution attack is able to exploit any available single-execution leakage and provides a straight-forward option to combine simultaneous measurements to improve the signal-to-noise ratio of available leakage. We present empirical results from attacking an elliptic curve scalar multiplication and exploit location-based leakage from high-resolution electromagnetic field measurements without prior profiling. Individual measurements lead to a sufficiently low remaining brute-force complexity of the secret exponent. An errorless recovery of the exponent is achieved after a combination of few measurements.