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

15:17 [Pub][ePrint]

Searchable symmetric encryption (SSE) enables a client to outsource a collection of encrypted documents in the cloud and retain the ability to perform keyword searches without revealing information about the contents of the documents and queries. Although efficient SSE constructions are known, previous solutions are highly sequential. This is mainly due to the fact that, currently, the only method for achieving sub-linear time search is the inverted index approach (Curtmola, Garay, Kamara and Ostrovsky, CCS \'06) which requires the search algorithm to access a sequence of memory locations, each of which is unpredictable and stored at the previous location in the

sequence.

Motivated by advances in multi-core architectures, we present a new method for constructing sub-linear SSE schemes. Our approach is highly parallelizable and dynamic. With roughly a logarithmic number of cores in place, searches for a keyword w in our scheme execute in o(r) parallel time, where r is the number of documents containing keyword w (with more cores, this bound can go down to O(log n), i.e., independent of the result size r). Such time complexity outperforms the optimal \\theta(r) sequential search time--a similar bound holds for the updates.

Our scheme also achieves the following important properties: (a) it enjoys a strong notion of security, namely security against adaptive chosen-keyword attacks; (b) compared to existing sub-linear dynamic SSE schemes (e.g., Kamara, Papamanthou, Roeder, CCS \'12), updates in our scheme do not leak any information, apart from information that can be inferred from previous search tokens; (c) it can be implemented efficiently in external memory (with logarithmic I/O overhead). Our technique is simple and uses a red-black tree data structure; its security is proven in the random oracle model.

15:17 [Pub][ePrint]

In this paper, we focus on a novel technique called cube-linear attack, which is obtained by combining the cube and linear attacks together, is first proposed to deal with the probabilistic polynomial, aiming to furthermore mine the available secret information. Based on different combination ways of the two attacks, moreover, two cube-linear schemes are discussed. Naturally, we can use cube-linear attack as an unordinary trick in linear cryptanalysis, which has never been considered by the previous linear cryptanalysis yet. As a new contribution to linear cryptanalysis, it is beneficial to allow for a reduction in the amount of data required for a successful attack in specific circumstances. Applying our method to a reduced-round Trivium, as an example, we get better linear cryptanalysis results. More importantly, we believe that the novel linear cryptanalysis technique introduced in this paper can be extended to other ciphers. In other words, it is worth considering for our method in linear cryptanalysis.

15:17 [Pub][ePrint]

In an attribute-based encryption (ABE) scheme, a ciphertext is associated with

an L-bit public index IND and a message m, and

a secret key

is associated with a

Boolean predicate P. The secret key allows to decrypt the ciphertext and learn m iff P(IND)=1. Moreover, the scheme should be secure against collusions of users, namely,

given secret keys for polynomially many predicates, an adversary

if none of the secret keys can individually decrypt the ciphertext.

We present

attribute-based encryption schemes for circuits

of any arbitrary polynomial size, where the public parameters and

the ciphertext grow linearly with the depth of the circuit. Our construction

is secure under the standard learning with errors (LWE) assumption. Previous

constructions of attribute-based encryption were for Boolean formulas, captured

by the complexity class NC1.

In the course of our construction, we

present a new framework for constructing ABE schemes.

As a by-product of our framework, we obtain ABE schemes

for polynomial-size branching programs,

corresponding to the complexity class LOGSPACE, under

quantitatively better assumptions.

15:17 [Pub][ePrint]

A pseudo-random number generator (PRNG) is a deterministic algorithm that produces numbers whose distribution is indistinguishable from uniform. A formal security model for PRNGs with input was proposed in 2005 by Barak and Halevi (BH). This model involves an internal state that is refreshed with a (potentially biased) external random source, and a cryptographic function that outputs random numbers from the continually internal state. In this work we extend the BH model to also include a new security property capturing how it should accumulate the entropy of the input data into the internal state after state compromise. This property states that a good PRNG should be able to eventually recover from compromise even if the entropy is injected into the system at a very slow pace, and expresses the real-life expected behavior of existing PRNG designs.

Unfortunately, we show that neither the model nor the specific PRNG construction proposed by Barak and Halevi meet this new property, despite meeting a weaker robustness notion introduced by BH. From a practical side, we also give a precise assessment of the security of the two Linux PRNGs, /dev/random and /dev/urandom. In particular, we show several attacks proving that these PRNGs are not robust according to our definition, and do not accumulate entropy properly. These attacks are due to the vulnerabilities of the entropy estimator and the internal mixing function of the Linux PRNGs. These attacks against the Linux PRNG show that it does not satisfy the \"robustness\" notion of security, but it remains unclear if these attacks lead to actual exploitable vulnerabilities in practice. Finally, we propose a simple and very efficient PRNG construction that is provably robust in our new and stronger adversarial model.

We therefore recommend to use this construction whenever a PRNG with input is used for cryptography.

2013-06-02
18:17 [Pub][ePrint]

We present the design, security proof, and implementation of an anonymous subscription service. Users register for the service by providing some form of identity, which might or might not be linked to a real-world identity such as a credit card, a web login, or a public key. A user logs on to the system by presenting a credential derived from information received at registration. Each credential allows only a single login in any authentication window, or epoch. Logins are anonymous in the sense that the service cannot distinguish which user is logging in any better than random guessing. This implies unlinkability of a user across different logins.

We find that a central tension in an anonymous subscription service is the service provider\'s desire for a long epoch (to reduce server-side computation) versus users\' desire for a short epoch (so they can repeatedly \"re-anonymize\" their sessions). We balance this tension by having short epochs, but adding an efficient operation for clients who do not need unlinkability to cheaply re-authenticate themselves for the next time period.

We measure performance of a research prototype of our pro- tocol that allows an independent service to offer anonymous access to existing services. We implement a music service, an Android-based subway-pass application, and a web proxy, and show that adding anonymity adds minimal client latency and only requires 33 KB of server memory per active user.

18:17 [Pub][ePrint]

In this paper, we introduce a general notion of functional proxy-re-encryption (F-PRE), where a wide class of functional encryption (FE) is combined with proxy-re-encryption (PRE) mechanism. The PRE encryption system should reveal minimal information to a proxy, in particular, hiding parameters of re-encryption keys and of original ciphertexts which he manipulate is highly desirable. We first formulate such a fully-anonymous security notion of F-PRE including usual payload-hiding properties. We then propose the first fully-anonymous inner-product PRE (IP-PRE) scheme, whose security is proven under the DLIN assumption and the existence of a strongly unforgeable one-time signature scheme in the standard model. Also, we propose the first ciphertext-policy F-PRE scheme with the access structures of Okamoto-Takashima (CRYPTO 2010), which also has an anonymity property for re-encryption keys as well as payload-hiding for original and re-encrypted ciphertexts. The security is proven under the same assumptions as the above IP-PRE scheme in the standard model. For these results, we develop novel blind delegation and new hidden subspace generation techniques on the dual system encryption (DSE) technique and the dual pairing vector spaces (DPVS). These techniques seem difficult to be realized by a composite-order bilinear group DSE approach.

18:17 [Pub][ePrint]

In this paper, we present a new approach to stream ciphers. This method draws its strength from public key algorithms such as RSA and the development in continued fractions of certain irrational numbers to produce a pseudo-random stream. Although the encryption scheme proposed in this paper is based on a hard mathematical problem, its use is fast.

18:17 [Pub][ePrint]

This paper investigated the use of instantaneous frequency (IF)

instead of power amplitude and power spectrum in side-channel analysis.

By opposition to the constant frequency used in Fourier Transform, instantaneous frequency reflects local phase differences and allows detecting frequency variations. These variations reflect the processed binary data and are hence cryptanalytically useful. IF exploits the fact that after higher power drops more time is required to restore power back to its nominal value. Whilst our experiments reveal IF does not bring specific benefits over usual power attacks when applied to unprotected designs, IF allows to obtain much better results in the presence of amplitude modification

countermeasures.

18:17 [Pub][ePrint]

For searching keywords against encrypted data, the public key encryption scheme with keyword search (PEKS), and its an extension called secure-channel free PEKS (SCF-PEKS) have been proposed.

In SCF-PEKS, a receiver makes a trapdoor for a keyword, and uploads it on a server. A sender computes an encrypted keyword, and sends it to the server. The server executes the searching procedure (called the test algorithm, which takes as inputs an encrypted keyword, trapdoor, and secret key of the server).

In this paper, we extend the security of SCF-PEKS, calling it adaptive SCF-PEKS, wherein an adversary (modeled as a malicious-but-legitimate\" receiver) is allowed to issue test queries \\emph{adaptively}, and show that adaptive SCF-PEKS can be generically constructed by anonymous identity-based encryption (anonymous IBE) only. That is, for constructing adaptive SCF-PEKS we need not require any additional cryptographic primitive when compared to the Abdalla et al. PEKS construction (J. Cryptology 2008), even though adaptive SCF-PEKS requires additional functionalities. Note that our generic construction needs to apply the KEM/DEM framework (a.k.a. hybrid encryption), where KEM stands for key encapsulation mechanism, and DEM stands for data encapsulation mechanism. We also show that there is a class of anonymous IBE that can be applied for constructing adaptive SCF-PEKS without using hybrid encryption, and propose an adaptive SCF-PEKS construction based on this IBE. Although our second construction is not fully generic, it is efficient compared to the first, since we can exclude the DEM part. Finally, we instantiate an adaptive SCF-PEKS scheme (via our second construction) that achieves a similar level of efficiency for the costs of the test procedure and encryption, compared to the (non-adaptive secure) SCF-PEKS scheme by Fang et al. (CANS2009).

18:17 [Pub][ePrint]

We present the hash function BLAKE2, an improved version of the SHA-3 finalist BLAKE optimized for speed in software. Target applications include cloud storage, intrusion detection, or version control systems. BLAKE2 comes in two main flavors: BLAKE2b is optimized for 64-bit platforms, and BLAKE2s for smaller architectures. On 64-bit platforms, BLAKE2 is often faster than MD5, yet provides security similar to that of SHA-3: up to 256-bit collision resistance, immunity to length extension, indifferentiability from a random oracle, etc. We specify parallel versions BLAKE2bp and BLAKE2sp that are up to 4 and 8 times faster, by taking advantage of SIMD and/or multiple cores. BLAKE2 reduces the RAM requirements of BLAKE down to 168 bytes, making it smaller than any of the five SHA-3 finalists, and 32% smaller than BLAKE. Finally, BLAKE2 provides a comprehensive support for tree-hashing as well as keyed hashing (be it in sequential or tree mode).