9:00  9:30 
Registration  Opening 
9:30  10:10 
PostQuantum Signatures from Small Merkle Trees
K. Chalkias, Newcrypt
Abstract:
We will present the BPQS protocol, an extensible hashbased postquantum signature scheme best suited to blockchain and distributed ledger technologies (DLTs). One of its unique characteristics is that it can take advantage of applicationspecific chain/graph structures in order to decrease key generation, signing and verification costs as well as signature size. Compared to recent improvements in the field, BPQS outperforms existing hashbased algorithms when a key is reused for reasonable numbers of signatures, while it supports a fallback mechanism to allow for a practically unlimited number of signatures if required. It’s also very simple to be implemented. If time allows, we will also mention some attacks on existing postquantum blockchains (i.e., IOTA), and why blockchains have not been welldesigned to allow forks.
All in all, we expect to answer the following questions:
Do quantum computers pose a credible threat to blockchains?
Will it happen in 2, 10 or 100 years from now?
Which algorithms are affected?
How to build postquantum signatures by just using hash functions and nothing else?

10:10  10:30 
Break 
10:30  11:10 
A Universally Composable Framework for the Privacy of Email Ecosystems
P. Chaidos, University of Athens
Abstract:
Email communication is amongst the most prominent online
activities, and as such, can put sensitive information at risk. It is thus
of high importance that internet email applications are designed in a
privacyaware manner and analyzed under a rigorous threat model. The
Snowden revelations (2013) suggest that such a model should feature a
global adversary, in light of the observational tools available.
Furthermore, the fact that protecting metadata can be of equal importance
as protecting the communication context implies that endtoend encryption
may be necessary, but it is not sufficient.
With this in mind, we utilize the Universal Composability framework
[Canetti, 2001] to introduce an expressive cryptographic model for email
``ecosystems'' that can formally and precisely capture various wellknown
privacy notions (unobservability, anonymity, unlinkability, etc.), by
parameterizing the amount of leakage an idealworld adversary (simulator)
obtains from the email functionality.
Equipped with our framework, we present and analyze the security of two
email constructions that follow different directions in terms of the
efficiency vs. privacy tradeoff. The first one achieves optimal security
(only the online/offline mode of the users is leaked), but it is mainly of
theoretical interest; the second one is based on parallel mixing [Golle
and Juels, 2004] and is more practical, while it achieves anonymity with
respect to users that have similar amount of sending and receiving
activity.

11:10  11:50 
Exploring relationships between pseudorandomness properties of sequences
and cryptographic properties of Boolean functions
K. Limniotis, University of Athens
Abstract:
It is wellknown that a Boolean function needs to satisfy specific
properties, such as high loworder nonlinearity, in order to provide
cryptographic strength. However, there are generally no efficient ways to
determine best loworder approximations of an arbitrary Boolean function f
or another function g depending on fewer variables than f such that g
approximates f up to a great extent. Therefore, verifying whether a
function behaves well in terms of these cryptographic criteria is a
nontrivial task. In this work, via defining a bijection between periodic
binary sequences and Boolean functions, we show that known algorithms on
assessing some pseudorandomness properties of a sequence may also provide
useful cryptographic information for the corresponding Boolean function in
terms of how well the latter can be approximated by a “simpler” function.

11:50  12:10 
Break 
12:10  12:50 
Shaving moustaches off the blockchain
N. Leonardos, University of Athens
Abstract: TBA

12:50  13:30 
PPPCompleteness with Connections to Cryptography
G. Zirdelis, Northeastern University
Abstract:
Polynomial Pigeonhole Principle (PPP) is an important subclass of TFNP with profound connections to the complexity of the fundamental cryptographic primitives: collisionresistant hash functions and oneway permutations. In contrast to most of the other subclasses of TFNP, no complete problem is known for PPP. Our work identifies the first PPPcomplete problem without any circuit or Turing Machine given explicitly in the input, and thus we answer a longstanding open question from [Papadimitriou1994]. Specifically, we show that constrainedSIS (cSIS), a generalized version of the wellknown Short Integer Solution problem (SIS) from latticebased cryptography, is PPPcomplete.
In order to give intuition behind our reduction for constrainedSIS, we identify another PPPcomplete problem with a circuit in the input but closely related to lattice problems. We call this problem BLICHFELDT and it is the computational problem associated with Blichfeldt's fundamental theorem in the theory of lattices.
Building on the inherent connection of PPP with collisionresistant hash functions, we use our completeness result to construct the first natural hash function family that captures the hardness of all collisionresistant hash functions in a worstcase sense, i.e. it is natural and universal in the worstcase. The close resemblance of our hash function family with SIS, leads us to the first candidate collisionresistant hash function that is both natural and universal in an averagecase sense.
Finally, our results enrich our understanding of the connections between PPP, lattice problems and other concrete cryptographic assumptions, such as the discrete logarithm problem over general groups.
Joint work with Katerina Sotiraki and Manolis Zampetakis.

13:30  15:30 
Lunch Break 
15:30  16:10 
A glimpse of hope for pairings (…in a prequantum world)
G. Fotiadis, University of the Aegean
Abstract:
The recent improvements of the tower number field sieve (TNFS) attacks on the DLP
in finite field extensions of composite degree, have caused serious complications
in pairingbased cryptography. In particular the secure and efficient examples of
pairings we had in the preTNFS period are no longer secure for implementations.
In this joint work with Chloe Martindale we present a comprehensive comparison of
different pairing types on different elliptic curve shapes. Our goal is to provide
a list of pairing choices that can serve as optimal candidates for efficient and
TNFSsecure pairingbased applications. Consequently, this work can be viewed
as “a glimpse of hope for pairings” (…in a prequantum world).

16:10  16:20 
Break 
16:20  17:00 
Circuits, Lower Bounds, and Circuit Analysis Algorithms
D. Myrisiotis, Imperial College London
Abstract:
We survey the connections between circuit lower bounds and circuit analysis algorithms. Circuit analysis algorithms include, for example, satisfiability algorithms, compression algorithms, learning algorithms, or natural properties (which are algorithms that discriminate between functions computable in some specific circuit class and random functions). Recent work has indicated the importance of this direction by providing new intriguing ways of looking at old results as well as guidelines on acquiring new. In this talk, we pose some open problems that pertain to these connections between algorithms and lower bounds and discuss potential ways of approaching them.

17:00 
End 
 