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-04
08:48 [Conf]

The 9th IACR Theory of Cryptography Conference (TCC'12) was held at the Hotel "Villa Diodoro" in Taormina, Italy, on March 19-21, 2012. The organizing committee included Rosario Gennaro and Nelly Fazio (General Co-chairs) and Dario Catalano (Local Arrangements Chair).

The technical program featured 36 papers selected from 131 submissions, along with two invited lectures: "Locally Decodable Codes" by Sergey Yekhanin of Microsoft Research and "Non-Interactive Zero-Knowledge" by Jens Groth of the University College of London. The program was assembled by a 20-member Program Committee led by Ronald Cramer as Program Chair.

The conference attracted 108 delegates, including 29 students of which 16 were given financial aid to attend the conference in the form of free registration and free housing.

The generous financial support of the conference sponsors (Bell Labs, IBM Research, Microsoft, AT&T and Oxford University Press) was also an important factor for the success of the event, and is gratefully acknowledged.

This was the first IACR workshop or conference where printed proceedings were optional, and had to be ordered at the time of registration for an extra fee of $50. Conference delegates received an electronic copy of the proceedings stored on a USB stick which was donated by DEShaw. 08:42 [Job][New] The Department of Informatics has a vacancy for 2 research fellows (PhD positions) in computer security for a period of 4 years. The recruited students will work in a new research group, named Simula@UiB, that is headed by Professor Kjell Jørgen Hole. The group is a joint venture between Simula Research Laboratory (http://simula.no) and University of Bergen. It currently consists of two professors, two research scientists, one PhD student and several master students. Candidates must have good analytical skills and be able to generate their own research ideas. They must have good communication skills and be fluent in English. Experience in computer security is an advantage. Candidates with experience from one or more of the areas Cyber Security, Software Security, Network Science, Game Theory, or Information Theory are of special interest. In total, the fellowship period is 4 years. For positions with a 4-year duration 25 pct of the period will be designated to teaching and/or administrative duties. The fellowship period may be reduced if the successful applicant has held previous employment as research fellow or similar. 08:33 [Event][New] Submission: 20 August 2013 Notification: 1 October 2013 From November 22 to November 24 Location: Beijing, People's Republic of China More Information: http://www.pairing-conference.org/ 2013-06-03 15:17 [Pub][ePrint] Obtainment of exact value or high lower bound on the$r$-th order nonlinearity of Boolean function is a very complicated problem (especial if$r > 1$). In a number of papers lower bounds on the$r$-th order nonlinearity of Boolean function via its algebraic immunity were obtain for different$r$. This bounds is rather high for function with maximum near maximum possible algebraic immunity. In this paper we prove theorem, which try to obtain rather high lower bound on the$r\$-th order nonlinearity for many functions with small algebraic immunity.

15:17 [Pub][ePrint]

Digital signatures are often used by trusted authorities to make unique bindings between a subject and a digital object; for example, certificate authorities certify a public key belongs to a domain name, and time-stamping authorities certify that a certain piece of information existed at a certain time. Traditional digital signature schemes however impose no uniqueness conditions, so a malicious or coerced authority can make multiple certifications for the same subject but different objects. We propose the notion of a \\emph{double-authentication-preventing signature}, in which a value to be signed is split into two parts: a \\emph{subject} and a \\emph{message}. If a signer ever signs two different messages for the same subject, enough information is revealed to allow anyone to compute valid signatures on behalf of the signer. This double-signature forgeability property prevents, or at least strongly \\emph{discourages}, signers misbehaving. We give a generic construction using a new type of trapdoor functions with extractability properties, which we show can be instantiated using the group of sign-agnostic quadratic residues modulo a Blum integer.

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.