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-08-06
15:17 [Pub][ePrint]

We present a generalization to genus 2 of the probabilistic

algorithm in Sutherland~\\cite{Sutherland} for computing Hilbert class polynomial˻s. The improvement over the algorithm presented

in~\\cite{BGL} for the genus 2 case, is that we do not need to find a

curve in the isogeny class with endomorphism ring which is the maximal

order: rather we present a probabilistic algorithm for going up\'\' to a {\\it

maximal} curve (a curve with maximal endomorphism ring), once we find {\\it

any} curve in the right isogeny class. Then we use the structure of the

Shimura class group and the computation of $(\\ell,\\ell)$-isogenies to

compute all isogenous maximal curves from an initial one.

15:17 [Pub][ePrint]

I provide the details of the factorization of the Mersenne number $2^{1061}-1$ by the Special Number Field Sieve. Although this factorization is easier than the completed factorization of RSA-768, it represents a new milestone for factorization using publicly available software.

15:17 [Pub][ePrint]

Recently, Xiong et al. [H. Xiong, Z. Guan, Z. Chen, F. Li, An Efficient certificateless aggregate signature with constant pairing computations, Information Science, doi: 10.1016/j.ins.2012.07.004, 2012] proposed a certificateless signature (CLS) scheme and used it to construct a certificateless aggregate signature (CLAS) scheme with constant pairing computations. They also demonstrated that both of their schemes are provably secure in the random oracle model under the computational Diffie-Hellman assumption. Unfortunately, by giving concrete attacks, we point out that Xiong et al. schemes are not secure in their security model.

15:17 [Pub][ePrint]

In this paper we present a theoretical analysis of the limits

of the Differential Fault Analysis (DFA) of AES by developing an inter

relationship between conventional cryptanalysis of AES and DFAs. We

show that the existing attacks have not reached these limits and present techniques to reach these. More specifically, we propose optimal DFA on states of AES-128 and AES-256. We also propose attacks on the key schedule of the three versions of AES, and demonstrate that these are some of the most efficient attacks on AES to date. Our attack on AES-128 key schedule is optimal, and the attacks on AES-192 and AES-256 key schedule are very close to optimal. Detailed experimental results have been provided for the developed attacks. The work has been compared to other works and also the optimal limits of Differential Fault Analysis of AES.

15:17 [Pub][ePrint]

We investigate a new class of authenticate codes (A-codes) that support verification

by a group of message recipients in the network coding setting. That is, a sender generates an

A-code over a message such that any intermediate node or recipient can check the authenticity

of the message, typically to detect pollution attacks. We call such an A-code as multi-receiver

homomorphic A-code (MRHA-code). In this paper, we first formally define an MRHA-code.

We then derive some lower bounds on the security parameters and key sizes associated with our

MRHA-codes. Moreover, we give efficient constructions of MRHA-code schemes that can be used

to mitigate pollution attacks on network codes. Unlike prior works on computationally secure

homomorphic signatures and MACs for network coding, our MRHA-codes achieve unconditional

security.

05:51 [Conf][CHES]

CHES 2012 early registration deadline Aug. 5.

2012-08-05
18:38 [News]

The IACR Board is seeking volunteers to assist with the maintenance of the IACR website and to serve as general chair for a future Crypto. If you are interested in these tasks, send a message to president@iacr.org.

18:17 [Pub][ePrint]

In this work we revisit the question of basing cryptography on imperfect randomness. Bosley and Dodis (TCC\'07) showed that if a source of randomness R is \"good enough\" to generate a secret key capable of encrypting k bits, then one can deterministically extract nearly k almost uniform bits from R, suggesting that traditional privacy notions (namely, indistinguishability of encryption) requires an \"extractable\" source of randomness. Other, even stronger impossibility results are known for achieving privacy under specific \"non-extractable\" sources of randomness, such as the gamma-Santha-Vazirani (SV) source, where each next bit has fresh entropy, but is allowed to have a small bias gamma< 1\$ (possibly depending on prior bits).

We ask whether similar negative results also hold for a more recent notion of privacy called differential privacy (Dwork et al., TCC\'06), concentrating, in particular, on achieving differential privacy with the Santha-Vazirani source. We show that the answer is no. Specifically, we give a differentially private mechanism for approximating arbitrary \"low sensitivity\" functions that works even with randomness coming from a gamma-Santha-Vazirani source, for any gamma

18:17 [Pub][ePrint]

In this work we focus on a simple database commitment functionality where besides the standard security properties, one would like to hide the size of the input of the sender. Hiding the size of the input of a player is a critical requirement in some applications, and relatively few works have considered it. Notable exceptions are the work on zero-knowledge sets introduced in~\\cite{MRK03}, and recent work on size-hiding private set intersection~\\cite{ADT11}. However, neither of these achieves a secure computation (i.e., a reduction of a real-world attack of a malicious adversary into an ideal-world attack) of the proposed functionality.

The first result of this submission consists in defining secure\'\' database commitment and in observing that previous constructions do not satisfy this definition. This leaves open the question of whether there is any way this functionality can be achieved.

We then provide an affirmative answer to this question by using new techniques that combined together achieve secure\'\' database commitment. Our construction is in particular optimized to require only a constant number of rounds, to provide non-interactive proofs on the content of the database, and to rely only on the existence of a family of CRHFs. This is the first result where input-size hiding secure computation is achieved for an interesting functionality and moreover we obtain this result with standard security (i.e., simulation in expected polynomial time against fully malicious adversaries, without random oracles, non-black-box extraction assumptions, hardness assumptions against super-polynomial time adversaries, or other controversial/strong assumptions).

A key building block in our construction is a universal argument enjoying an improved proof of knowledge property, that we call quasi-knowledge. This property is significantly closer to the standard proof of knowledge property than the weak proof of knowledge property satisfied by previous constructions.

18:17 [Pub][ePrint]

Motivated by the question of access control in cloud storage, we consider the problem using Attribute-Based Encryption (ABE) in a setting where users\' credentials may change and ciphertexts may be stored by a third party. We find that a comprehensive solution to our problem must simultaneously allow for the revocation of ABE private keys as well as allow for the ability to update ciphertexts to reflect the most recent updates. Our main result is obtained by pairing two contributions:

- Revocable Storage. We ask how a third party can process a ciphertext to disqualify revoked users from accessing data that was encrypted in the past, while the user still had access. In applications, such storage may be with an untrusted entity and as such, we require that the ciphertext management operations can be done without access to any sensitive data (which rules out decryption and re-encryption). We define the problem of revocable storage and provide a fully secure construction. Our core tool is a new procedure that we call ciphertext delegation. One can apply ciphertext delegation on a ciphertext encrypted under a certain access policy to `re-encrypt\' it to a more restrictive policy using only public information. We provide a full analysis of the types of delegation possible in a number of existing ABE schemes.

- Protecting Newly Encrypted Data. We consider the problem of ensuring that newly encrypted data is not decryptable by a user\'s key if that user\'s access has been revoked. We give the first method for obtaining this revocation property in a fully secure ABE scheme. We provide a new and simpler approach to this problem that has minimal modications to standard ABE. We identify and define a simple property called piecewise key generation which gives rise to efficient revocation. We build such solutions for Key-Policy and Ciphertext-Policy Attribute-Based Encryption by modifying an existing ABE scheme due to Lewko et al. to satisfy our piecewise property and prove security in the standard model.

It is the combination of our two results that gives an approach for revocation. A storage server can update stored ciphertexts to disqualify revoked users from accessing data that was encrypted before the user\'s access was revoked. This is the full version of the Crypto 2012 paper.

18:17 [Pub][ePrint]

In this paper, we study the security proofs of GCM (Galois/Counter Mode of Operation). We first point out that a lemma, which is related to the upper bound on the probability of a counter collision, is invalid. Both the original privacy and authenticity proofs by the designers are based on the lemma. We further show that the observation can be translated into a distinguishing attack that invalidates the main part of the privacy proof. It turns out that the original security proofs of GCM contain a flaw, and hence the claimed security bounds are not justified. A very natural question is then whether the proofs can be repaired. We give an affirmative answer to the question by presenting new security bounds, both for privacy and authenticity. As a result, although the security bounds are larger than what were previously claimed, GCM maintains its provable security. We also show that, when the nonce length is restricted to 96 bits, GCM has better security bounds than a general case of variable length nonces.