Athecrypt

Name: Foteini Baldimtsi
Title: Anonymous Credentials Light
Abstract
We define and propose an efficient and provably secure construction of blind signatures with attributes. Prior notions of blind signatures did not yield themselves to the construction of anonymous credential systems, not even if we drop the unlinkability requirement of anonymous credentials. Our new notion in contrast is a convenient building block for anonymous credential systems. The construction we propose is efficient: it requires just a few exponentiations in a prime-order group in which the decisional Diffie-Hellman problem is hard. Thus, for the first time, we give a provably secure construction of anonymous credentials that can work in the elliptic group setting without bilinear pairings and is based on the DDH assumption. In contrast, prior provably secure constructions were based on the RSA group or on groups with pairings, which made them prohibitively inefficient for mobile devices, RFIDs and smartcards. The only prior efficient construction that could work in such elliptic curve groups, due to Brands, does not have a proof of security.
Joint work with Anna Lysyanskaya

Name: Petros Mol
Title: Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions
Abstract
We study under what conditions the conjectured uninvertibility of the knapsack function (with polynomially bounded inputs) over an arbitrary finite abelian group implies that the output of the function is pseudorandom, i.e., computationally indistinguishable from a uniformly chosen group element. Previous work of Impagliazzo and Naor (J. Cryptology 9(4):199-216, 1996) considers only specific families of finite abelian groups and uniformly chosen random binary inputs. Our work substantially extends previous results and provides a much more general reduction that applies to arbitrary finite abelian groups and input distributions with polynomially bounded coefficients. As an application of the new result, we give sample preserving search-to-decision reductions for the Learning With Errors (LWE) problem, introduced by Regev (J. ACM 56(6):34, 2009) and widely used in lattice-based cryptography.

Name: Vassilis Zikas
Title: Universally Composable Synchronous Computation
Abstract
In synchronous networks, protocols can achieve security guarantees that are not possible in an asynchronous world: they can simultaneously achieve input completeness (all honest parties' inputs are included in the computation) and guaranteed termination (honest parties do not ``hang'' indefinitely). In practice truly synchronous networks rarely exist, but synchrony can be emulated if channels have (known) latency and parties have loosely synchronized clocks.
The widely-used framework of universal composability (UC) is inherently asynchronous, but several approaches for adding synchrony to the framework have been proposed. In this talk I will give a high-level overview of the UC security definitions and discuss how to use it for arguing the security of synchronous protocols. I will show that existing proposals do not provide the expected guarantees and propose a novel approach to defining synchrony in the UC framework by introducing functionalities exactly meant to model, respectively, bounded-delay networks and loosely synchronized clocks. I will further show that the expected guarantees of synchronous computation can be realized given these functionalities, and argue that previous models can all be expressed within this new framework.

Name: Nikos Karvelas
Title: Proofs of Secure Erasure
Abstract
We investigate the problem of verifying the internal state of a remote embedded device (remote attestation), using what was by Tsudik and Perito introduced as Proofs of Secure Erasure. This is a procedure that has to take place in many cases, ranging from wireless sensor networks to any device running a software update: One has to make sure that even a compromised device will erase all of its memory contents when asked to, leaving no part of it left unaltered, possibly running malicious software. The protocols proposed thus far demand either very high communication complexity or very high time complexity that renders them ineffective for most practical applications.

Name: Dimitris Sakavalas
Title: Secure Broadcast in generic and wireless networks
Abstract
In the context of designing distributed systems in an adversarial environment, it is widely accepted that mechanisms for reaching "agreement" between all non-corrupted parts, constitute an integral part of the system. One of the major variations of the agreement problem is the Broadcast problem. The problem has been extensively studied in the standard model in which the communication network is complete.
We study the Broadcast problem in generic and wireless networks considering the existence of an active adversary. We develop efficient protocols under the assumption that the underlying communication network is of known topology. Moreover, we investigate the topological restrictions, that are necessary and sufficient for the existence of solution for the Broadcast problem in ad-hoc networks, mainly under the t-locally bounded adversarial model, in which an upper bound on the number of corrupted players in each player's neighborhood is considered.
Joint work with Aris Pagourtzis and Christos Litsas

Name: Aris Tentes
Title: The Learning Parity with Noise assumption and applications
Abstract
The hardness of the Learning Parity with Noise (LPN) problem is an assumption which has gained a lot of popularity lately. Cryptographic schemes whose security is based on LPN are very appealing mainly because of the two following reasons. Firstly, the problem on its own has been extensively studied and it is widely believed that it provides strong guarantees. Secondly, because of that and the nature of the problem, such schemes usually have a very simple structure and are very efficient.
In this talk we will formally define the LPN problem, mention known LPN-based cryptographic schemes and focus on the results of JKPT'12. In this paper we showed how to construct a perfectly binding string commitment scheme with some nice zero-knowledge proof of knowledge protocols. In particular, our scheme not only allows for a simple and efficient zero-knowledge proof of knowledge for committed values, but also for such proofs showing any kind of relation amongst committed values, i.e., proving that messages m0,...,mt, are such that m0 = C(m1,...,mt) for any circuit C.

Name: Dimitris Papadopoulos
Title: Super-Efficient and Parallelizable Authenticated Pattern Matching and XML Search
Authors: D. Papadopoulos, C. Papamanthou, R. Tamassia, E. Tremel, N. Triandopoulos
Abstract
In this paper, we present an authenticated suffix tree and an authenticated XML tree data structure -namely two cryptographic constructions based on the strong-RSA assumption, supporting verifiable pattern matching and verifiable exact path queries on text or semi-structured data that is outsourced to an untrusted cloud server. Our authenticated data structures are the first to simultaneously achieve the following properties: (a) Super efficiency, i.e., the answer verification time is faster asymptotically than the answer generation time using an associated proof of optimal size; (b) Parallelism, allowing construction in parallel logarithmic time using a sublinear number of processors that execute an optimal amount of work; and (c) Outsourcing optimality, incurring storage overhead proportional to the text size. Moreover, we describe extensions of our authenticated XML tree scheme to additionally support: (a) super-efficient verification of exact path queries with attribute predicates (e.g., queries returning XML elements of a particular attribute value that are reachable by a particular label path) and (b) efficient updates over associated objects (e.g., XML elements) in optimal update cost at the expense of producing proofs that are proportional only to the answer size.