International Association for Cryptologic Research

# IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. 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).

2015-01-12
11:58 [Event][New]

Submission: 23 January 2015
Notification: 18 February 2015
From May 19 to May 19
Location: Florence, Italy
More Information: http://aspire-fp7.eu/spro/

11:56 [Job][New]

The Department of Computing at the University of Surrey (http://www.surrey.ac.uk/computing/) seeks to recruit a motivated doctoral student to work in the area of Information Security.

The studentship is for three years and includes a stipend of £16,000 per year and tuition fees, and is available to students of UK/EU residency.

The successful candidate will participate in the Formal Methods and Security group (http://www.surrey.ac.uk/computing/research/fms/index.htm), will work in an exciting international environment and will have the opportunity to participate in the development of the recently launched Surrey Centre for Cyber Security (http://www.surrey.ac.uk/sccs/index.htm).

The main tasks of the Ph.D. student will be to develop state-of-the-art techniques for the security analysis of real world protocols. In particular, he/she will work in one of the following areas:

- Formal methods applied to security protocols;

- Applied Cryptography and Provable Security.

The position will remain open until a suitable candidate is found so there is no fixed closing date for applications.

10:17 [Pub][ePrint]

Private Information Retrieval (PIR) protects users\' privacy in outsourced storage applications and can be achieved using additively homomorphic encryption schemes. Several PIR schemes with a \"real world\" level of practicality, both in terms of computational and communication complexity, have been recently studied and implemented. One of the possible building block is a conceptually simple and computationally efficient protocol proposed by Trostle and Parrish at ISC 2010, that relies on an underlying secret-key (somewhat) additively homomorphic encryption scheme, and has been reused in numerous subsequent works in the PIR community (PETS 2012, FC 2013, NDSS 2014, etc.).

In this paper, we show that this encryption scheme is not one-way: we present an attack that decrypts arbitrary ciphertext without the secret key, and is quite efficient: it amounts to applying the LLL algorithm twice on small matrices. Used against existing practical instantiations of PIR protocols, it allows the server to recover the

users\' access pattern in a matter of seconds.

10:17 [Pub][ePrint]

Cryptography based on the Learning Parity with Noise (LPN) problem has several very desirable aspects: Low computational overhead, simple implementation and conjectured post-quantum hardness. Choosing the LPN noise parameter sufficiently low allows for public key cryptography. In this work, we construct the first standard model public key encryption scheme with key dependent message security based solely on the low noise LPN problem. Additionally, we establish a new connection between LPN with a bounded number of samples and LPN with an unbounded number of samples. In essence, we show that if LPN with a small error and a small number of samples is hard, then LPN with a slightly larger error and an unbounded number of samples is also hard. The key technical ingredient to establish both results is a variant of the LPN problem called the extended LPN problem.

10:17 [Pub][ePrint]

We introduce a lattice-based group signature scheme that provides several noticeable improvements over the contemporary ones: simpler construction, weaker hardness assumptions, and shorter sizes of keys and signatures. Moreover, our scheme can be transformed into the ring setting, resulting in a scheme based on ideal lattices, in which the public key and signature both have bit-size soft-O(n log N), for security parameter n, and for group of N users. Towards our goal, we construct a new lattice-based cryptographic tool: a statistical zero-knowledge argument of knowledge of a valid message-signature pair for Boyen\'s signature scheme (Boyen, PKC\'10), which potentially can be used as the building block to design various privacy-enhancing cryptographic constructions.

10:17 [Pub][ePrint]

One-round authenticated key exchange (ORKE) is an established research area, with many prominent protocol constructions like HMQV (Krawczyk, CRYPTO 2005) and Naxos (La Macchia et al., ProvSec 2007), and many slightly different, strong security models. Most constructions combine ephemeral and static Diffie-Hellman Key Exchange (DHKE), in a manner often closely tied to the underlying security model.

We give a generic construction of ORKE protocols from general assumptions, with security in the standard model, and in a strong security model where the attacker is even allowed to learn the randomness or the long-term secret of either party in the target session. The only restriction is that the attacker must not learn both the randomness and the long-term secret of one party of the target session, since this would allow him to recompute all internal states of this party, including the session key.

This is the first such construction that does not rely on random oracles.

The construction is intuitive, relatively simple, and efficient. It uses only standard primitives, namely non-interactive key exchange, a digital signature scheme, and a pseudorandom function, with standard security properties, as building blocks.

10:17 [Pub][ePrint]

We propose an efficient large-universe multi-authority ciphertext - policy attribute-based encryption system. In a large-universe ABE scheme, any string can be used as an attribute of the system, and these attributes are not necessarily enumerated during setup. In a multi-authority ABE scheme, there is no central authority that distributes the keys to users. Instead, there are several authorities, each of which is responsible for the authorized key distribution of a specific set of attributes. Prior to our work, several schemes have been presented that satisfy one of these two properties but not both.

Our construction achieves maximum versatility by allowing multiple authorities to control the key distribution for an exponential number of attributes. In addition, the ciphertext policies of our system are sufficiently expressive and overcome the restriction

that each attribute is used only once\'\' that constrained previous constructions. Besides versatility, another goal of our work is to increase efficiency and practicality. As a result,

we use the significantly faster prime order bilinear groups rather than composite order groups. The construction is non-adaptively secure in the random oracle model under a non-interactive q-type assumption, similar to one used in prior works. Our work

extends existing program-and-cancel\'\' techniques to prove security and introduces two new techniques of independent interest for other ABE constructions. We provide an implementation and some benchmarks of our construction in Charm, a programming framework developed for rapid prototyping of cryptographic primitives.

10:17 [Pub][ePrint]

Functional encryption is a new paradigm in public-key encryption that allows users to finely control the amount of information that is revealed by a ciphertext to a given receiver. Recent papers have focused their attention on constructing schemes for general functionalities at expense of efficiency. Our goal, in this paper, is to construct functional encryption schemes for less general functionalities which are still expressive enough for practical scenarios. We propose a functional encryption scheme for the inner-product functionality, meaning that decrypting an encrypted vector x with a key for a vector y will reveal only and nothing else, whose security is based on the DDH assumption.

Despite the simplicity of this functionality, it is still useful in many contexts like descriptive statistics. In addition, we generalize our approach and present a generic scheme that can be instantiated, in addition, under the LWE assumption and offers various trade-offs in terms of expressiveness and efficiency.

10:17 [Pub][ePrint]

In this paper we analyze the Kahrobaei-Lam-Shpilrain (KLS) key

exchange protocols that use extensions by endomorpisms of matrices over a Galois field

proposed in 2014.

We show that both protocols are vulnerable to a simple linear algebra attack.

10:17 [Pub][ePrint]

Recent work on structure-preserving signatures studies optimality of these schemes in terms of the number of group elements needed in the verification key and the signature, and the number of pairing-product equations in the verification algorithm. While the size of keys and signatures is crucial for many applications, another important aspect to consider for performance is the time it takes to verify a given signature. By far, the most expensive operation during verification is the computation of pairings. However, the concrete number of pairings that one needs to compute is not captured by the number of pairing-product equations considered in earlier work.

To fill this gap, we consider the question of what is the minimal number of pairings that one needs to compute in the verification of structure-preserving signatures. First, we prove lower bounds for schemes in the Type~II setting that are secure under chosen message attacks in the generic group model, and we show that three pairings are necessary and that at most one of these pairings can be precomputed. We also extend our lower bound proof to schemes secure under random message attacks and show that in this case two pairings are still necessary. Second, we build an automated tool to search for schemes matching our lower bounds. The tool can generate automatically and exhaustively all valid structure-preserving signatures within a user-specified search space, and analyze their (bounded) security in the generic group model. Interestingly, using this tool, we find a new randomizable structure-preserving signature scheme in the Type~II setting that is optimal with respect to the lower bound on the number of pairings, and also minimal with respect to the number of group operations that have to be computed during verification.

10:17 [Pub][ePrint]

A group signature allows a group member to anonymously sign messages on behalf of the group. In the past few years, new group signatures

based on lattice problems have appeared: the most efficient lattice-based constructions are due to Laguillaumie {\\it et al.} (Asiacrypt \'13)

and Langlois {\\it et al.} (PKC \'14). Both have at least $O(n^2\\log^2 n \\log N)$-bit group public key and $O(n\\log^3 n\\log N)$-bit signature,

where $n$ is the security parameter and $N$ is the maximum number of group members. In this paper, we present a simpler lattice-based group signature, which is more efficient by a $O(\\log N)$ factor in both the group public key and the signature size. We achieve this by using a new non-interactive zero-knowledge (NIZK) proof corresponding to a simple identity-encoding function.

The security of our group signature can be reduced to the hardness of SIS and LWE in the random oracle model.