Abstract: We will present the BPQS protocol, an extensible hash-based post-quantum signature scheme best suited to blockchain and distributed ledger technologies (DLTs). One of its unique characteristics is that it can take advantage of application-specific 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 hash-based 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 post-quantum blockchains (i.e., IOTA), and why blockchains have not been well-designed 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 post-quantum signatures by just using hash functions and nothing else?

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 privacy-aware 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 end-to-end 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 well-known privacy notions (unobservability, anonymity, unlinkability, etc.), by parameterizing the amount of leakage an ideal-world 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.

Abstract: It is well-known that a Boolean function needs to satisfy specific properties, such as high low-order nonlinearity, in order to provide cryptographic strength. However, there are generally no efficient ways to determine best low-order 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 non-trivial 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.

Abstract: TBA

Abstract: Polynomial Pigeonhole Principle (PPP) is an important subclass of TFNP with profound connections to the complexity of the fundamental cryptographic primitives: collision-resistant hash functions and one-way permutations. In contrast to most of the other subclasses of TFNP, no complete problem is known for PPP. Our work identifies the first PPP-complete 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 constrained-SIS (cSIS), a generalized version of the well-known Short Integer Solution problem (SIS) from lattice-based cryptography, is PPP-complete. In order to give intuition behind our reduction for constrained-SIS, we identify another PPP-complete 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 collision-resistant hash functions, we use our completeness result to construct the first natural hash function family that captures the hardness of all collision-resistant hash functions in a worst-case sense, i.e. it is natural and universal in the worst-case. The close resemblance of our hash function family with SIS, leads us to the first candidate collision-resistant hash function that is both natural and universal in an average-case 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.

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 pairing-based cryptography. In particular the secure and efficient examples of pairings we had in the pre-TNFS 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 TNFS-secure pairing-based applications. Consequently, this work can be viewed as “a glimpse of hope for pairings” (…in a pre-quantum world).

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.