*22:17* [Pub][ePrint]
A Note on Bilinear Groups of a Large Composite Order, by Zhengjun Cao and Lihua Liu
We remark that the structure of bilinear groups of a large composite order(at least 1024 bits) could make group operation inefficient and lose the advantages of elliptic curve cryptography which gained mainly from smaller parameter size. As of 2013, the longest parameter recommended by NIST for elliptic curves has 571 bits.From the practical point of view, such an algebraic structure is unlikely applicable to cryptographic schemes.

*22:17* [Pub][ePrint]
Multi-ciphersuite security and the SSH protocol, by Benjamin Dowling and Florian Giesen and Florian Kohlar and Jörg Schwenk and Douglas Stebila
Real-world cryptographic protocols, such as the Transport Layer Security (TLS) and Secure Shell (SSH) protocols, support the negotiation of different combinations of cryptographic algorithms, often known as ciphersuites. An individual ciphersuite can be modelled as an authenticated and confidential channel establishment (ACCE) protocol, and recently all widely deployed TLS ciphersuites have been individually proven ACCE-secure. In practice, users often re-use long-term keys across ciphersuites, for example using the same digital signature key in two different signed Diffie--Hellman (DH) ciphersuites. Recently, a cross-ciphersuite attack on TLS was discovered in which a signed elliptic curve DH structure can be interpreted as a signed finite-field DH structure, breaking authentication. Thus, ACCE security of individual ciphersuites does not generically imply collective security when long-term keys are re-used across ciphersuites.We investigate the security of multi-ciphersuite protocols with re-used long-term keys. We show how to \"open\" the ACCE definition slightly so that, after each ciphersuites has been proven secure individually, they can then be used together in a secure multi-ciphersuite protocol, even when long-term keys are re-used across ciphersuites, provided the ciphersuites\' messages satisfy an independence property. We apply our definitions and composition theorem to the SSH protocol, showing that signed Diffie--Hellman SSH ciphersuites are individually ACCE-secure; they also satisfy the preconditions of our composition theorem, and thus SSH is multi-ciphersuite-secure even with re-use of long-term keys.

*22:17* [Pub][ePrint]
RDAS: A Symmetric Key Scheme for Authenticated Query Processing in Outsourced Databases, by Lil Maria Rodriguez-Henriquez and Debrup Chakraborty
In this paper we address the problem of authenticated query processing in outsourced databases.An authenticated query processing mechanism allows a client to verify the validity of the query responses that it gets from an untrusted and remote server, who stores the client\'s database

on its behalf.

We introduce a general framework called RDAS for the problem of authenticated query processing, and define the

security goals for this task in line with concrete provable security. We propose several schemes which enable

a client to verify both the completeness and correctness of the query responses of a server. All the schemes follow

the proposed framework and are provably secure in terms of the proposed security definition. The novelty of the proposed schemes

is that they use bitmap indexes as a main component for providing authentication. Bitmap indexes have recently seen

lot of applications for accelerated query processing and many commercial databases implement such indexes. Bitmaps have not been

previously used for a security goal. We show that the proposed schemes can match in both

functionality and efficiency compared to the existing schemes. We also implement the schemes on a real database and provide extensive

experimental studies on the schemes

*22:17* [Pub][ePrint]
Iterated group products and leakage resilience against NC^1, by Eric Miles
We show that if NC^1 \\neq L, then for every element g of the alternating group A_t, circuits of depth O(log t) cannot distinguish between a uniform vector over (A_t)^t with product = g and one with product = identity. Combined with a recent construction by the author and Viola in the setting of leakage-resilient cryptography [STOC \'13], this gives a compiler that produces circuits withstanding leakage from NC^1 (assuming NC^1 \\neq L). For context, leakage from NC^1 breaks nearly all previous constructions, and security against leakage from P is impossible.We build on work by Cook and McKenzie [J.\\ Algorithms \'87] establishing the relationship between L = logarithmic space and the symmetric group S_t. Our techniques include a novel algorithmic use of commutators to manipulate the cycle structure of permutations in A_t.

*22:17* [Pub][ePrint]
Interactive Encryption, Message Authentication, and Anonymous Key Exchange, by Yevgeniy Dodis and Dario Fiore
Public-Key Encryption (PKE) and Message Authentication (PKMA, aka as digital signatures) are fundamental cryptographic primitives. Traditionally, both notions are defined as non-interactive (i.e., single-message). In this work, we initiate rigorous study of (possibly) {\\em interactive} PKE and PKMA schemes. We obtain the following results demonstrating the power of interaction to resolve questions which are either open or impossible in the non-interactive setting.Efficiency/Assumptions.

One of the most well known open questions in the area of PKE is to build, in a ``black-box way\'\', so called chosen ciphertext attack (CCA-) secure PKE from chosen plaintext attack (CPA-) secure PKE. In contrast, we show a simple $2$-round CCA-secure PKE from any (non-interactive) CPA-secure PKE (in fact, these primitives turn out to be equivalent). Similarly, although non-interactive PKMA schemes can be inefficiently built from any one-way function, no efficient signature schemes are known from many popular number-theoretic assumptions, such as factoring, CDH or DDH. In contrast, we show an efficient $2$-round PKMA from most popular assumptions, including factoring, CDH and DDH.

Advanced Properties.

It is well known that no non-interactive signature (resp. encryption) scheme can be {\\em deniable} (resp. {\\em forward-secure}), since the signature (resp. ciphertext) can later ``serve as an evidence of the sender\'s consent\'\' (resp. ``be decrypted if the receiver\'s key is compromised\'\'). We also formalize a related notion of {\\em replay-secure} (necessarily) interactive PKMA (resp. PKE) schemes, where the verifier (resp. encryptor) is assured that the ``current\'\' message can only be authenticated (resp. decrypted) by the secret key owner {\\em now}, as opposed to some time in the past (resp. future). We observe that our 2-round PKMA scheme is both replay-secure and (passively) deniable, and our 2-round PKE scheme is both replay- and forward-secure. We also define and construct stronger forms of necessarily interactive PKE/PKMA schemes, called {\\em confirmed encryption} and {\\em confidential authentication}.

Anonymous Key Exchange.

We extend our definitional framework for interactive PKE and PKMA schemes to give definitions and constructions of (necessarily interactive) {\\em anonymous key exchange} (1-KE), where an anonymous (unkeyed) party establishes a key with an authenticated (keyed) party. Unlike the prior work, defining 1-KE by ``downgrading\'\' the hairy and complex definition of {\\em mutually authenticated} key exchange (2-KE), our definition is very ``short\'\' and easy to understand. We also show simple and general connections between anonymous KE and (interactive) confirmed PKE/confidential PKMA schemes. As a result, we obtain old and new schemes for anonymous KE in a clean and modular manner. For example, we obtain the first $2$-round anonymous KE which is both (passively) deniable and forward-secure.

*22:17* [Pub][ePrint]
On the Relation of Random Grid, Probabilistic and Deterministic Visual Cryptography, by Roberto De Prisco and Alfredo De Santis
Visual cryptography is a special type of secret sharing. Two models of visual cryptography have been independently studied: deterministic visual cryptography, introduced by Naor and Shamir, and random grid visual cryptography, introduced by Kafri and Keren. In the context of the deterministic model, Yang has introduced a third model, the probabilistic visual cryptography model. The connection between the probabilistic and the deterministic models have been explored.In this paper we show that there is a strict relation between the random grid model and the deterministic model. More specically we show that to any random grid scheme corresponds a deterministic scheme and viceversa. This allows us to use results known in a model also in the other model. In fact, the random grid model is equivalent to the probabilistic model with no pixel expansion. Exploiting the (many) results known in the deterministic model we are able to improve several schemes and to provide many upper bounds for the random grid model. Exploiting some results known for the random grid model, we are also able to provide new schemes for the deterministic model. A side eect of this paper is that future new results for any one of the two models (random grid and deterministic) should not ignore, and in fact be compared to, the results known in the other model.

*22:17* [Pub][ePrint]
Safe enclosures: towards cryptographic techniques for server protection, by Sergiu Bursuc and Julian P. Murphy
Cryptography is generally used to protect sensitive data from an untrusted server. In this paper, we investigate the converse question: can we use cryptography to protect a trusted server from untrusted data? As a first step in this direction, we propose the notion of safe enclosures. Intuitively, a safe enclosure is a cryptographic primitive that encapsulates data in a way that allows to perform some computation on it, while at the same time protecting the server from malicious data. Furthermore, a safe enclosure should come equipped with a dedicated protocol that implements the enclosing function with unconditional integrity. Otherwise, unguarded data may reach the server. We discuss the novelty of these concepts, propose their formal definition and show several realizations.

*22:17* [Pub][ePrint]
Errorless Smooth Projective Hash Function based on LWE, by Olivier Blazy and Céline Chevalier and Léo Ducas and Jiaxin Pan
Smooth Projective Hash Functions are one of the base tools to build interactive protocols; and this notion has lead to the construction of numerous protocols enjoying strong security notions, such as the security in the Bellare-Pointcheval-Rogaway (BPR) model or even Universal Composability (UC).

Yet, the construction of SPHF has been almost limited to discrete-logarithm or pairing type assumptions up to now. This stands in contrast with domains such as homomorphic encryption or functional encryption, where Lattice Based Cryptography has already caught up and overtook discrete-log/pairing based cryptography. So far, work in the direction of UC based on lattices is almost restricted to a paper from Peikert, Vaikuntanathan, and Waters (Crypto 2008) dealing with Oblivious Transfer in the UC framework, and work in the direction of password-authenticated key exchange protocols (PAKE) to one from

Katz and Vaikuntanathan (Asiacrypt 2009) on a 3-round Password-Authenticated Key Exchange, but restraining itself to the BPR model. It seems that dealing with errors in those contexts is not as easy as it is for encryption.

In this work, we identify the problem at its source, namely, the lattice version of Diffie-Hellman key exchange protocol: the key greement is only approximate. We explicit a simple folklore trick to obtain true, errorless, one-round key exchange from LWE. We then show that this trick can be adapted to various lattice encryption schemes, leading, with some technicalities, to errorless SPHF\'s. From there, we derive three new results, namely the first lattice-based following protocols: a one-round PAKE secure in the BPR model, a 3-round PAKE secure in the UC model, and a UC commitment scheme, all of them based on SIS and LWE assumptions.