AtheCrypt 2021
Athens Cryptography Days

Athens Cryptography Days 2021

Saturday, January 16, 2021 9:45 - 14:15 & 16:00 - 20:15
Saturday, January 23, 2021 9:45 - 14:15 & 16:00 - 20:15
virtually, via Webex.

The link for participating will be sent to you via mail after registering!

Athens Cryptography Day is an annual event.
Its purpose is to give the opportunity to students and scientists in Greece and abroad to observe talks from renowned and promising researchers working in all areas of Cryptography.

List of Speakers:
Z. Avarikioti
P. Chaidos
K. Chalkias
P. Chatzigiannis
I. Demertzis
E. Diamanti
T. Dimitriou
J. Garay
A. Kiayias
L. Kokoris-Kogias
E. Kornaropoulos
V. Koutsos
S. Leonardos
P. Louridas
P. Papakonstantinou
Q. Tang
N. Triandopoulos
L. Tseng
M. Yung
M. Zambetakis
B. Zhang
V. Zikas
D. Zindros

Organization

Stathis Zachos
Aris Pagourtzis
Aggelos Kiayias
Petros Potikas
Antonis Antonopoulos
Pourandokht Behrouz
Aggeliki Chalki
Giannis Papaioannou

Register

There are no registration fees. However, participants should register in order to receive the WebEx link (in case of any difficulties please contact the organizers):

Registration is closed.

Hello

Program

PDF

Saturday 16/1

 9:45 Opening 10:00 Manolis Zampetakis: Complexity of Total Search Problems with connections to Cryptographic Hardness 11:00 Orfeas Thyfronitis-Litos, Nikos Papadis: short presentations 11:25 Dionysis Zindros: Soft Power: Changing Blockchain Macroeconomic Policy through Soft Forks 11:50 Break 12:00 Aggelos Kiayias: Tight Consistency Bounds for Bitcoin 13:00 Lefteris Kokoris-Kogias: Bootstrapping Consensus and MPC in an Asynchronous Network 13:25 Vlasis Koutsos: Agora: A Privacy-Aware Data Marketplace 13:50 Stefanos Leonardos: Ethereum's Transaction Fee Market Reform of EIP 1559 14:15 Long Break 16:00 Moti Yung: Why and How to Deploy “Secure Computations” in Daily Business? 17:00 Zeta Avarikioti: Divide and Scale: Formalization of Distributed Ledger Sharding Protocols 17:30 Nikos Triandopoulos: Private Hierarchical Clustering and Efficient Approximation 18:10 Panos Chatzigiannis: MiniLedger: Compact-sized Anonymous and Auditable Distributed Payments 18:40 Free discussion 19:15 Vasilis Zikas: Broadcast-Optimal Two-Round MPC 20:15 End of Day 1

Saturday 23/1

 9:50 Qiang Tang: Dumbo Protocols: Making Asynchronous (Permissioned) Consensus Real 10:50 Pyrros Chaidos: Weighted Multi-Signatures for Blockchain Bootstrapping 11:15 Periklis Papakonstantinou - The 20 minutes guide to  blackbox separations (and maybe non-blackbox constructions) (if time permits) 11:35 Break 11:45 Tassos Dimitriou: Decentralized Reputation 12:10 Panos Louridas: The Next Generation of the Zeus e-Voting System 12:35 Marios Adamoudis: Attacking (EC)DSA with partially known multiples of nonces 13:00 Long Break 14:40 Eleni Diamanti - Practical challenges in quantum cryptography 15:40 Antigoni Polychroniadou - Differential Privacy for Inventory Obfuscation 16:40 Ioannis Demertzis - Dynamic Searchable Encryption with Small Client Storage 17:05 Lewis Tseng - Fundamental Properties of Cryptocurrency in Distributed Systems 18:05 Break 18:20 Juan Garay: Cryptography in the Proof-of-Work Era 19:20 Kostas Chalkias: ToothBoard: teeth and tongue authentication 19:45 Evgenios Kornaropoulos: Demystifying Leakage in Encrypted Systems 20:10 Closing Remarks - End of AtheCrypt 2021

Titles & Abstracts

Title: Attacking (EC)DSA with partially known multiples of nonces

Abstract: DSA (Digital Signature Algorithm) is a public-key signature scheme developed by NSA (the U.S. National Security Agency). It was proposed by NIST (the U.S. National Institute of Standards and Technology) back in 1991 and has become a FIPS 186 (U.S.Federal Information Processing Standard) called DSS (Digital Signature Standard). In 1998, an elliptic curve analogue called Elliptic Curve Digital Signature Algorithm (ECDSA) was proposed and standarized. The security of these system is based on Discrete Logarithm Problem. We present some lattice attacks to these systems which under some conditions permit us to find the private key.

Slides Video

Title: Divide and Scale: Formalization of Distributed Ledger Sharding Protocols

Speaker: Zeta Avarikioti (ETH Zurich)

Abstract: Sharding distributed ledgers is the most promising on-chain solution for scaling blockchain technology. In this work, we define and analyze the properties a sharded distributed ledger should fulfill. More specifically, we show that a sharded blockchain cannot be scalable under a fully adaptive adversary, but it can scale up to $O(n/logn)$ under an epoch-adaptive adversary. This is possible only if the distributed ledger creates succinct proofs of the valid state updates at the end of each epoch. Our model builds upon and extends the Bitcoin backbone protocol by defining consistency and scalability. Consistency encompasses the need for atomic execution of cross-shard transactions to preserve safety, whereas scalability encapsulates the speedup a sharded system can gain in comparison to a non-sharded system. In order to show the power of our framework, we analyze the most prominent sharded blockchains and either prove their correctness (OmniLedger, RapidChain) under our model or pinpoint where they fail to balance the consistency and scalability requirements (Elastico, Monoxide).

Video

Title: Weighted Multi-Signatures for Blockchain Bootstrapping

Speaker: Pyrros Chaidos

Abstract: Proof of Stake Blockchains operate by having participants demonstrate that they control a certain piece of stake, chosen by some selection mechanism. In contrast, proof of work blockchains require that participants provide a solution to some computational problem with restrictions indicated by the context. Such solutions can usually be verified in isolation and at low computational cost. In many current Proof of Stake implementations, verifying a claim of stake either requires a large context or a somewhat complex proof. These costs are exacerbated when a new user wishes to participate for the first time, as verifying the current state will often require replaying operations since the genesis. We introduce the primitive of weighted multi-signatures and use it to offer a simple solution to speed up bootstrapping: we produce an aggregate signature for verifying a succinct checkpoint for each epoch. Our approach minimizes computational costs to small stakeholders and is compatible with recent advances such as key-evolving signatures and delegation.

Video

Title: ToothBoard: teeth and tongue authentication

Speaker: Kostas Chalkias (Facebook / Novi Research)

Abstract: Unlike textual and graphical passwords, humans can take advantage of their embedded keyboard, their "teeth". Using small IoT sensors and smart encoding, we can securely communicate by using our tongue to type. The main advantage of Toothboard is its shoulder-surfing resistance due to our skull providing a physical protection to side channel attacks. Potential applications include a) secure password typing b) unnoticed secret communication c) assistive device for people with speech disorders d) simulating a hands free remote control. This work focuses on the desired cryptographic properties of an ideal system rather than technical implementation details.
Joint work with Sam Blackshear and Evan Cheng.

Video

Title: MiniLedger: Compact-sized Anonymous and Auditable Distributed Payments

Speaker: Panos Chatzigiannis

Abstract: While privacy preserving distributed payment schemes manage to drastically improve user privacy, they come at the cost of generating new regulatory concerns: in a private ledger the transactions cannot be subject to any level of auditing, and thus are not compatible with tracing illegal behaviors. In this work we present MiniLedger, a distributed payment system which not only guarantees the privacy of transactions, but also offers built-in functionalities for various types of audits by any external authority. MiniLedger is the first private and auditable payment system with storage costs independent of the number of transactions. To achieve such a storage improvement, we introduce pruning functionalities for the transaction history while maintaining integrity and auditing. We provide formal security definitions and a number of extensions for various auditing levels. Our evaluation results show that MiniLedger is practical in terms of storage requiring as low as 70KB per participant for 128 bits of security, and depending on the implementation choices, can prune 1 million transactions in less than a second.

Slides Video

Title: Dynamic Searchable Encryption with Small Client Storage

Speaker: Ioannis Demertzis

Abstract: We study the problem of dynamic searchable encryption (DSE) with forward-and-backward privacy. Many DSE schemes have been proposed recently but the most efficient ones have one limitation: they require maintaining one operation counter for each unique keyword, either stored locally at the client or stored encrypted at the server and accessed obliviously (e.g., with an oblivious map) during every operation. We propose three new schemes that overcome the above limitation and achieve constant permanent client storage with improved performance, both asymptotically and experimentally, compared to prior state-of-the-art works. In particular, our first two schemes adopt a “static-to-dynamic” transformation which eliminates the need for oblivious accesses during searches. Due to this, they are the first practical schemes with minimal client storage and non-interactive search. Our third scheme is the first quasi-optimal forward-and- backward DSE scheme with only a logarithmic overhead for retrieving the query result (independently of previous deletions). While it does require an oblivious access during search in order to keep permanent client storage minimal, its practical performance is up to four orders of magnitude better than the best existing scheme with quasi-optimal search.

Video

Title: Practical challenges in quantum cryptography

Speaker: Eleni Diamanti

Abstract: In this talk, we discuss the current landscape in quantum cryptography in the context of future quantum-safe communications and describe the state-of-the-art and practical challenges in this field. To illustrate these challenges, we focus in particular on recent practical photonic implementations, using encodings in discrete or continuous variables of light, of central quantum network protocols, enabling secret key distribution, quantum coin flipping, verification of entangled resources and transactions with quantum money, with maximal security guarantees.

Slides Video

Title: Decentralized Reputation

Speaker: Tassos Dimitriou (Kuwait University)

Abstract: In this work, we develop a privacy-preserving reputation scheme for collaborative systems such as P2P networks in which peers can represent themselves with different pseudonyms when interacting with others. All these pseudonyms, however, are bound to the same reputation token, allowing honest peers to maintain their good record even when switching to a new pseudonym while preventing malicious ones from making a fresh start. Our system is truly decentralized. Using an append-only distributed ledger such as Bitcoin’s blockchain, we show how participants can make anonymous yet verifiable assertions about their own reputation. The system maintains soundness, peer-pseudonym unlinkability as well as unlinkability among pseudonyms of the same peer. We formally prove these properties and we evaluate the efficiency of the various operations, demonstrating the viability of the approach. [To appear in the The 11th ACM Conference on Data and Application Security and Privacy, April 26-28, 2021, http://www.codaspy.org/2021]

Video

Title: Cryptography in the Proof-of-Work Era

Speaker: Juan Garay (Texas A&M University)

Abstract: For over 20 years the term "proof of work" (PoW) has been used liberally in the cryptography and security literature to describe a cryptographic primitive that has been applied in a variety of settings, including spam mitigation, sybil attacks, and denial of service protection. Arguably, the most impactful application of PoWs, however, is in the design of blockchain-based protocols such as Bitcoin. At a high level, the way PoWs enable such protocols is by slowing message passing for all parties indiscriminately, thus generating opportunities for honest parties' views to converge, under the assumption that their aggregate computational power exceeds that of the adversary. This talk comprises two parts. First, despite the evolution of our understanding of the PoW primitive, pinning down the exact properties sufficient to prove the security of Bitcoin and related protocols has been elusive, as all previous analyses of blockchain protocols have been performed in the random oracle model. In this talk we identify such properties, and then construct a protocol whose security can be reduced to them in the standard model, assuming a common reference string (CRS). Second, regarding the realizability of two important problems in the area of cryptographic protocols -- Byzantine agreement (BA) and secure multiparty computation (MPC) -- recall that they require that in the absence of a private correlated-randomness setup, such as a public-key infrastructure (PKI), protocols can only tolerate up to $t < n/3$ of the parties being malicious. On the other hand, the main application PoW blockchains enable, “Nakamoto style” consensus, shows that even a minority (i.e., $t < n/2$) of corrupted parties can be tolerated as long as the majority of the computation resources remain in honest hands. The above apparent contradiction begs the question of whether the mismatch is due to different goals and models, or whether the "resource-restricting" paradigm can be generically used to circumvent the n/3 lower bound. We formally demonstrate how the above paradigm -- which we call " Resource-Restricted Cryptography" -- changes the rules of the game in cryptographic definitions and protocol constructions, and present BA and MPC protocols that tolerate $t < n/2$ corruptions *without* assuming a private correlated randomness setup, thus answering the above question. That's the main focus of the talk's second part; time permitting, we will also mention other lower bounds that can be circumvented in the new framework. The talk is based on joint work with Aggelos Kiayias, Rafail Ostrovsky, Giorgos Panagiotakos and Vassilis Zikas.

Video

Title: Tight Consistency Bounds for Bitcoin

Speaker: Aggelos Kiayias (Univeristy of Edinburgh & IOHK)

Abstract: We establish the optimal security threshold for the Bitcoin protocol in terms of adversarial hashing power, honest hashing power, and network delays. Our analysis immediately applies to any Nakamoto-style proof- of-work protocol (with static difficulty); we also present the adaptations needed to apply it in the proof-of-stake setting, establishing a similar threshold there.
Joint work with Peter Gazi and Alexander Russell.

Video

Title: Bootstrapping Consensus and MPC in an Asynchronous Network.

Speaker: Lefteris Kokoris-Kogias (Novi, Facebook and IST Austria)

Abstract: We present the first Asynchronous Distributed Key Generation (ADKG) algorithm which is also the first algorithm that generates cryptographic keys with a dual $(f, 2f+1)$-threshold. ADKG removes the trusted setup that efficient consensus and MPC protocols need.

Video

Title: Demystifying Leakage in Encrypted Systems

Speaker: Evgenios Kornaropoulos

Abstract: The growing area of encrypted systems combines cryptographic advancements with system designs so that the end product can compute directly on ciphertexts without decrypting. One of the more prominent and practical approaches is using cryptographic primitives that reveal some formally-defined information, known as leakage, during computations on encrypted data. In this talk, I present new findings from my research that show a foundational approach to understanding leakage in encrypted databases. I will use the insights from my previous leakage-abuse attacks towards a new framework of principled and practical defenses with provable guarantees. This result contributes to a holistic understanding of encrypted databases, one that bridges the gap between attacks and defenses.

Video

Title: Agora: A Privacy-Aware Data Marketplace

Speaker: Vlasis Koutsos (HKUST)

Abstract: We propose Agora, the first blockchain-based data marketplace that enables multiple privacy-concerned parties to get compensated for contributing and exchanging data, without relying on a trusted third-party during the exchange. Agora achieves data privacy, output verifiability, and atomicity of payments by leveraging cryptographic techniques, and is designed as a decentralized application via smart contracts. Particularly, data generators provide encrypted data to data brokers who use a functional secret key to learn nothing but the output of a specific, agreed upon, function over the raw data. Data consumers can purchase decrypted outputs from the brokers, accompanied by corresponding proofs of correctness. We implement a working prototype of Agora on Ethereum and experimentally evaluate its performance and deployment costs. As a core building block of Agora, we propose a new functional encryption scheme with additional public parameters that operate as a trust anchor for verifying decrypted results.

Video

Title: Ethereum's Transaction Fee Market Reform of EIP 1559

Speaker: Stefanos Leonardos

Abstract: The scarcity of resources to process transactions on the Ethereum blockchain gives rise to a transaction fee market between miners and users. In a process which closely resembles a generalized first price auction, users bid the fees that they are willing to pay and miners decide which transactions to include. Along with the well-known inefficiencies of generalized first price auctions, users' guesswork on the right fee causes unreasonable delays, extreme variability of fees even among transactions within a block and strategic behavior that threatens the stability of the blockchain. In the present paper, we study Ethereum's Improvement Proposal 1559 (EIP 1559) which aims to address these issues. At the core of the proposal lies a floating basefee which stipulates a minimum fee that each user needs to burn for their transaction to be processed. The basefee is dynamically adjusted between blocks to account for prevailing market conditions. Users' bids comprise a maximum fee (feecap) and a maximum tip (premium) that they are willing to pay to the miner that will (eventually) include their transaction. Our preliminary results (both analytic and experimental) suggest that the basefee quickly settles to a stationary level. We test the robustness of this property under different market conditions (demand distributions) and assumptions on users' strategic behavior and find that the proposed mechanism leads to a more efficient fee market that generates higher social welfare under various scenarios. We conclude with open questions and a roadmap for ongoing work.

Slides Video

Title: The Next Generation of the Zeus e-Voting System

Speaker: Panos Louridas

Abstract: The Zeus e-voting system has been in continuous operation for several years now; more than 2000 electronic elections with more than 260,000 voters have been carried out successfully, in Greece and around the world. Building on this success, we are now planning the next generation of Zeus that will improve significantly the election process. This will require the incorporation of new cryptographic protocols, the re-engineering of Zeus to a pluggable mixnet architecture, lockstep evolution of backend and frontend code, refactoring, and paying down technical debt.

Video

Title: The 20 minutes guide to blackbox separations and maybe non-blackbox constructions (if time permits)

Speaker: Periklis A. Papakonstantinou, Rutgers University

Abstract: This is an introductory tutorial to black-box separations and non-blackbox constructions in cryptography. Most cryptographic primitives are constructed by making black-box use of other crypto-primitives. One observation is that the vast majority (99.9% of them) these constructions do not rely in any way on the code of the smaller primitives they use (just the input/output relations). This observation opened up more than 30 years ago the field of blackbox separations, where one aims to show that a specific assumption or cryptographic primitive cannot be used to build another. To complement these results the somewhat new area of non-blackbox constructions emerged. Non-blackbox constructions make explicit use of the code one is using to compute a cryptographic primitive in order to construct another. For example, one can show that assuming that Factoring is hard we can do cryptography using constant-time parallel computers. The interesting observation is that although it is impossible to compute in constant time the product of two integers, we can still do cryptography by relying on the fact that their factorization is a hard problem.

Video

Title: Differential Privacy for Inventory Obfuscation

Abstract: New differential privacy techniques under continual observation and their application to Finance.

Video

Title: Dumbo Protocols: Making Asynchronous (Permissioned) Consensus Real

Speaker: Qiang Tang

Abstract: Asynchronous consensus has been considered the most robust, yet the most system-friendly consensus in the open network. Unfortunately, all existing protocols suffer from low efficiency thus essentially none has been deployed. In this talk, we will introduce our recent progress on how to make asynchronous permissioned consensus really fast, and finally, real.

Video

Title: Private Hierarchical Clustering and Efficient Approximation

Speaker: Nikos Triandopoulos (Boston University)

Abstract: In collaborative learning, multiple entities contribute their datasets to jointly deduce global, and better, machine learning models for numerous predictive tasks. Yet, privacy risks often limit entities to individually train models using only their own datasets, especially so in application domains that involve highly sensitive data, such as healthcare and security analytics. In this work, we study privacy-preserving collaborative hierarchical clustering, proposing scalable cryptographic protocols that allow two parties to perform cluster analysis over their combined sensitive datasets. We introduce a formal security definition that achieves the necessary balance between utility and privacy, and present two-party hierarchical clustering protocols that provably guarantee privacy under our definition. Our solution employs modular design and judicious use of cryptography to achieve high degrees of efficiency and extensibility; specifically, our core protocol lends itself to a highly scalable, yet highly accurate, approximation variant.

Video

Title: Fundamental Properties of Cryptocurrency in Distributed Systems

Speaker: Lewis Tseng (Boston College)

Abstract: In this talk, I will answer the following fundamental questions in distributed computing:
1. Is consensus necessary for cryptocurrency?
2. Is a total order necessary for cryptocurrency?
3. How to analyze cryptocurrency in the CAP framework?
Concretely, I will share a decomposition and a formulation of cryptocurrency so that we can answer these questions. The talk will be self-contained, as I do not assume any background knowledge of distributed computing. The first part of the talk will be based on this work: The Consensus Number of a Cryptocurrency by Rachid Guerraoui et al. (PODC 2019). The second part of the talk is my unpublished work.

Slides Video

Title: Why and How to Deploy “Secure Computations” in Daily Business?

Speaker: Moti Yung (Google/ Columbia University)

Abstract: In this talk I will describe the analysis of needs and development behind Google development of the private data exchange, a secure computation protocol employed nowadays for a number of applications. The interplay of theory, business, systems, and deployment will be discussed. (Secure computation protocols started with Mental Poker in the Late 70s, and now 40 years later it seems it can actually say its applications begging to be known to actual industry with actual security and privacy needs).

Video

Title: Complexity of Total Search Problems with connections to Cryptographic Hardness

Speaker: Manolis Zambetakis (MIT)

Abstract: The complexity landscape of Total Search Problems has profound connections to Cryptography. For instance, it describes the complexity of fundamental cryptographic primitives, such as collision-resistant hash functions and one-way permutations. In this talk, I will explain these connections through the following works.
- We identify the first natural PPP-complete problem: constrained-SIS (cSIS), which is a generalization of the well-studied SIS problem and shows a connection between PPP and the hardness of lattice problems that lie in the intersection of NP and co-NP. Building on the inherent connection of PPP with collision-resistant hash functions, we also 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 universal in the worst-case.
- We identify the first natural complete problems for the classes PPA_p, which are generalizations of the classical PPA class. We also show that for specific range of parameters SIS belongs to these classes, showing that the existence of SIS solutions can be proven through a "modulo q argument".
This talk is based on works with Mika Göös, Pritish Kamath, Katerina Sotiraki and Giorgos Zirdelis

Video

Title: Broadcast-Optimal Two-Round MPC

Speaker: Vassilis Zikas (Purdue University)

Abstract: An intensive effort by the cryptographic community to minimize the round complexity of secure multi-party computation (MPC) has recently led to optimal two-round protocols from minimal assumptions. Most of the proposed solutions, however, make use of a broadcast channel in every round, and it is unclear if the broadcast channel can be replaced by standard point-to-point communication in a round-preserving manner, and if so, at what cost on the resulting security. In this work, we provide a complete characterization of the trade-off between number of broadcast rounds and achievable security level for two-round MPC tolerating arbitrarily many active corruptions. Specifically, we consider all possible combinations of broadcast and point-to-point rounds against the three standard levels of security for maliciously secure MPC protocols, namely, security with identifiable, unanimous, and selective abort. For each of these notions and each combination of broadcast and point-to-point rounds, we provide either a tight feasibility or an infeasibility result of two-round MPC. Our feasibility results hold assuming two-round OT in the CRS model, whereas our impossibility results hold given any correlated randomness. This is joint work with Ran Cohen (Northeastern) and Juan Garay (Texas A&M) that appeared at EUROCRYPT 2020.

Video

Title: Soft Power: Changing Blockchain Macroeconomic Policy through Soft Forks

Speaker: Dionysis Zindros

Abstract: Blockchain macroeconomic policy concerns the amounts, distributions, beneficiaries and conditions required for money supply payments to participants by the system. Folklore wisdom suggests that any changes to macroeconomics require a hard fork, as backwards compatibility with unupgraded verifier nodes cannot be ensured. In this paper, we challenge this notion. We present a generic smart contract construction that allows any macroeconomic policy upgrade to be made using a soft fork, as long as the new supply is on average bounded by the old supply over long periods of time. Our construction works for Ethereum, but can in principle be extended to any chain with smart contract support. We discuss examples of upgrades that our mechanism can be used for, such as incentivizing superblocks, introducing difficulty bombs, or incentivizing miners to remain online and provide availability.

Slides Video

Venue

AtheCrypt will take place virtually, via the WebEx platform, due to the Covid 19 pandemic.
The WebEx link will be sent in your e-mail, after registering (free). If you face any difficulties please contact the organizers.