*10:17* [Pub][ePrint]
One-Round Key Exchange with Strong Security: An Efficient and Generic Construction in the Standard Model, by Florian Bergsma, Tibor Jager, Jörg Schwenk
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]
Efficient Statically-Secure Large-Universe Multi-Authority Attribute-Based Encryption, by Yannis Rouselakis and Brent Waters
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]
Simple Functional Encryption Schemes for Inner Products, by Michel Abdalla and Florian Bourse and Angelo De Caro and David Pointcheval
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]
A linear attack on Kahrobaei-Lam-Shpilrain key exchange protocol, by Jintai Ding, Alexei Miasnikov, Alexander Ushakov
In this paper we analyze the Kahrobaei-Lam-Shpilrain (KLS) keyexchange 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]
Strongly-Optimal Structure Preserving Signatures from Type II Pairings: Synthesis and Lower Bounds, by Gilles Barthe and Edvard Fagerholm and Dario Fiore and Andre Scedrov and Benedikt Schmidt and Meh
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]
Simpler Efficient Group Signatures from Lattices, by Phong Q. Nguyen and Jiang Zhang and Zhenfeng Zhang
A group signature allows a group member to anonymously sign messages on behalf of the group. In the past few years, new group signaturesbased 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.

*10:17* [Pub][ePrint]
Non-Malleable Condensers for Arbitrary Min-Entropy, and Almost Optimal Protocols for Privacy Amplification, by Xin Li
Recently, the problem of privacy amplification with an active adversary has received a lot of attention. Given a shared $n$-bit weak random source $X$ with min-entropy $k$ and a security parameter $s$, the main goal is to construct an explicit 2-round privacy amplification protocol that achieves entropy loss $O(s)$. Dodis and Wichs \\cite{DW09} showed that optimal protocols can be achieved by constructing explicit \\emph{non-malleable extractors}. However, the best known explicit non-malleable extractor only achieves $k=0.49n$ \\cite{Li12b} and evidence in \\cite{Li12b} suggests that constructing explicit non-malleable extractors for smaller min-entropy may be hard. In an alternative approach, Li \\cite{Li12} introduced the notion of a non-malleable condenser and showed that explicit non-malleable condensers also give optimal privacy amplification protocols.In this paper, we give the first construction of non-malleable condensers for arbitrary min-entropy. Using our construction, we obtain a 2-round privacy amplification protocol with optimal entropy loss for security parameter up to $s=\\Omega(\\sqrt{k})$. This is the first protocol that simultaneously achieves optimal round complexity and optimal entropy loss for arbitrary min-entropy $k$. We also generalize this result to obtain a protocol that runs in $O(s/\\sqrt{k})$ rounds with optimal entropy loss, for security parameter up to $s=\\Omega(k)$. This significantly improves the protocol in \\cite{ckor}. Finally, we give a better non-malleable condenser for linear min-entropy, and in this case obtain a 2-round protocol with optimal entropy loss for security parameter up to $s=\\Omega(k)$, which improves the entropy loss and communication complexity of the protocol in \\cite{Li12b}.