Monday, March 14, 2022 (π day)
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.
Speakers:
K. Brazitikos
P. Chatzigiannis
A. Kiayias
E. KokorisKogias
P. Lazos
G. Malavolta
A. Pappa
A. Polychroniadou
T. Samarth
A. P. Stouka
L. Tseng
T. Zacharias
V. Zikas
D. Zindros
E. Vlatakis
Stathis Zachos
Aris Pagourtzis
Aggelos Kiayias
Petros Potikas
Antonis Antonopoulos
Pourandokht Behrouz
Aggeliki Chalki
AtheCrypt 2021
AtheCrypt 2020
AtheCrypt 2019
AtheCrypt 2018
AtheCrypt 2017
AtheCrypt 2016
AtheCrypt 2015
AtheCrypt 2014
AtheCrypt 2013
There are no registration fees. However, participants should register in order to receive the WebEx link:
9:4510:00  Opening 
10:0010:40 
Building Practical and Modular Consensus with DAGs
Lefteris KokkorisKogias
Abstract: We present DAGRider, the first asynchronous Byzantine Atomic Broadcast protocol that achieves optimal resilience, optimal amortized communication complexity, and optimal time complexity. DAGRider is postquantum safe and ensures that all messages proposed by correct processes eventually get decided. We construct DAGRider in two layers: In the first layer, processes reliably broadcast their proposals and build a structured Directed Acyclic Graph (DAG) of the communication among them. In the second layer, processes locally observe their DAGs and totally order all proposals with no extra communication.
Afterwards we propose Narwhal and Tusk. Where we separate the task of reliable transaction dissemination from transaction ordering of DAGRider, to enable highperformance Byzantine faulttolerant quorumbased consensus. We design and evaluate a mempool protocol, Narwhal, specializing in highthroughput reliable dissemination and storage of causal histories of transactions. Narwhal tolerates an asynchronous network and maintains high performance despite failures. Narwhal is designed to easily scaleout using multiple workers at each validator, and we demonstrate that there is no foreseeable limit to the throughput we can achieve.

10:4011:10 
Hide & Seek: PrivacyPreserving Rebalancing on Payment Channel Networks
Tiwari Samarth
Abstract: Payment channels effectively move the transaction load offchain thereby successfully addressing the inherent scalability problem most cryptocurrencies face. A major drawback of payment channels is the need to ``top up'' funds onchain when a channel is depleted. Rebalancing was proposed to alleviate this issue, where parties with depleting channels move their funds along a cycle to replenish their channels offchain. Protocols for rebalancing so far either introduce local solutions or compromise privacy.
In this work, we present an optin rebalancing protocol that is both private and globally optimal, meaning our protocol maximizes the total amount of rebalanced funds. We study rebalancing from the framework of linear programming. To obtain full privacy guarantees, we leverage multiparty computation in solving the linear program, which is executed by selected participants to maintain efficiency. Finally, we efficiently decompose the rebalancing solution into incentivecompatible cycles which conserve user balances when executed atomically.

11:1011:50 
Can we obfuscate quantum circuits?
Giulio Malavolta
Abstract: We study the notion of indistinguishability obfuscation for null quantum circuits (quantum nulliO). We present a construction assuming:
 The quantum hardness of learning with errors (LWE).
 Postquantum indistinguishability obfuscation for classical circuits.
 A notion of ''dualmode'' classical verification of quantum computation (CVQC).
We give evidence that our notion of dualmode CVQC exists by proposing a scheme that is secure assuming LWE in the quantum random oracle model (QROM).
Then we show how quantum nulliO enables a series of new cryptographic primitives that, prior to our work, were unknown to exist even making heuristic assumptions. Among others, we obtain the first witness encryption scheme for QMA, the first publicly verifiable noninteractive zeroknowledge (NIZK) scheme for QMA, and the first attributebased encryption (ABE) scheme for BQP.

11:5012:00  Break 
12:0012:30 
Reward Sharing Schemes for Stake Pools
AikateriniPanagiota Stouka
Abstract: I will present reward sharing schemes (RSS) for stake pools, a reward mechanism that we introduced in https://ieeexplore.ieee.org/document/9230398 and is used in the Cardano blockchain platform. Reward sharing schemes promote the fair formation of stake pools in collaborative projects that involve a large number of stakeholders, such as the maintenance of a proofofstake (PoS) blockchain. They are parameterized by a target value k for the desired number of pools, and they make the underlying system stabilize at a Nash equilibrium, where the users are organised in k pools of equal size. Our equilibria exhibit also an efficiency / security tradeoff via a parameter that calibrates between including pools with the smallest cost and providing protection against Sybil attacks, the setting where a single stakeholder creates a large number of pools in the hopes to dominate the collaborative project. Finally, we experimentally demonstrate fast convergence to equilibria in dynamic environments where players react to each other's strategic moves over an indefinite period of interactive play. We also show how simple reward sharing schemes that are seemingly more “fair” converge to centralized equilibria with just one pool.

12:3013:00 
How to establish conference keys anonymously over a quantum network
Anna Pappa
Abstract: In this talk I will examine how to protect the identity of communicating parties in quantum networks. Starting from the two party case, I will show what are the necessary components in order to perform anonymous key distribution. I will then extend this to the multiparty case, and examine what notions of anonymity we can achieve when multiple parties want to establish a common secret key, also known as conference key agreement. I will finally present the outcomes of the first experimental demonstration of anonymous conference key agreement between three parties, using an optical setup.

13:0014:00 
Mixnet cryptoeconomics
Aggelos Kiayias
Abstract: Applying cryptographic operations in a distributed and collaborative fashion has been for more than four decades a dominant paradigm in the design of privacypreserving communications systems and specifically mixnets. The design of such systems present to the end user a guarantee that typically involves a threshold condition. For instance, such condition could have the form “as long as x out of a certain set of y cryptographic keys remain uncompromised then privacy is maintained.” Enforcing the condition is typically out of scope for the system design and the enduser has no tools whatsoever to assess whether the condition holds. As a result, it is typically taken at face value. This is unfortunate as it may lead to deployments where privacy fails – and to make matters worse, noone may even be aware of it.
In this talk, I will present ongoing work (in collaboration with Claudia Diaz and Harry Halpin) that is pursued in the context of Nym (https://nymtech.net/), an incentivised mixnetwork system. The design is based on new techniques in the context of mixnets as well as it suitably adapts concepts first developed in the context of blockchain protocols, and offers an incentivedriven privacy preserving communication infrastructure that aims to provide privacy via a novel “cryptoeconomic” mechanism.

14:0014:30 
General Adversary Structures in Byzantine Agreement and MultiParty Computation with Omission and Byzantine Faults
Konstantinos Brazitikos
Abstract: The vast majority of the literature on faulttolerant distributed computing and multiparty computation (in short, MPC) considers threshold adversaries  up to a certain number of faults are assumed  corrupting parties actively (byzantine faults) and/or failstop (crash failures). Arguably, the above fault types are inadequate for capturing correct parties/processes that might suffer temporary network failures and/or localized faultsthese are particularly relevant for (secure) distributed computation over large, global scale networks. Omission faults and general adversary structures have been proposed as more suitable alternatives. However, to date, there is no characterization of the faulttolerance landscape combining the above ramifications of fault types and patterns.In this work we provide a tight characterization of feasibility of synchronous Byzantine agreement tolerating general adversary structures with (adversaries that combine) omission and byzantine faults. We also initiate the investigation of informationtheoretic MPC against such adversaries: First, we show the common techniques used in the threshold MPC literature do not work in this setting, not even for proving bounds that would appear trivial, such as sufficiency of the well known $Q^3$ condition on omissiononly general adversaries. We then prove the first feasibility and necessity result for MPC tolerating such an adversary, under a mild atomicity assumption on the omission faults.

14:3015:00 
Mechanism Design for Transaction Fees
Philip Lazos
Abstract: Prominent blockchain systems such as Bitcoin and Ethereum have experienced explosive growth in transaction volume, leading to frequent surges in demand for limited block space, causing transaction fees to fluctuate by orders of magnitude. Many approaches have been proposed, each with different goals such as to keep the prices down or make the choice easier for the user. However, so far none have been particularly effective in practice; often, even the target objective is unclear. In this talk we will go over the current literature (including the most prominent mechanisms used), formulate a more sophisticated model for transaction fees and discuss alternative solutions.

15:0016:00  Lunch Break 
16:0016:40 (10:0010:40 EDT) 
Prime Match: A Privacy Preserving Inventory Matching System
Antigoni Polychroniadou
Abstract: In this talk we are going to present our multiparty Prime Match solution for matching orders in a stock exchange while maintaining the privacy of the orders. Information is revealed only if there is a match. To achieve our solution, we present a new protocol for secure comparison with malicious security which can be of independent interest. Prime Match has been running in production since September 2021.

16:4017:25 (10:4011:25 EDT) 
Gus: Strongly Consistent Object Storageacross Global Data Centers with Optimal Commit Latency
Lewis Tseng
Abstract: Georedundancy protects customer data and provides high availability in cloud storage systems. This paper presents the design, implementation and evaluation of Gus, a strongly consistent object storage system that supports high performance atomic read, write, and remove operations, while preserving low tail latency. Gus achieves that through the following three properties. (i) Leaderless design: operations can be ordered in a decentralized way, without relying on a single leader. (ii) Optimal commit latency: all three operations can be completed in 1 RTT, by contacting a simple majority, in the common case (when there is no conflicting write). (iii) Instant execution:whenever the operation is committed, the operation can be executed. It was demonstrated that leaderless systems often suffer from long tail latency owing to delayed execution of some operations. To the best of our knowledge, Gus is the first protocol to achieve all three properties. Our evaluation shows that Gus provides lower tail latency and higher throughput than EPaxos, Gryff, and Giza, under various workloads.
In addition, I will sketch some highlevel ideas of making Gus Byzantinetolerant and how Gus could be applied to Blockchain applications.

17:2517:55 
Optimal Private Median Estimation under Minimal Distributional Assumptions
Emmanouil Vlatakis
Abstract: We study the fundamental task of estimating the median of an underlying distribution from a finite number of samples, under pure differential privacy constraints. We focus on distributions satisfying the minimal assumption that they have a positive density at a small neighborhood around the median. In particular, the distribution is allowed to output unbounded values and is not required to have finite moments. We compute the exact, uptoconstant terms, statistical rate of estimation for the median by providing nearlytight upper and lower bounds. Furthermore, we design a polynomialtime differentially private algorithm which provably achieves the optimal performance. At a technical level, our results leverage a Lipschitz Extension Lemma which allows us to design and analyze differentially private algorithms solely on appropriately defined "typical" instances of the samples.
Joint work with Christos Tzamos and Ilias Zadik. 
17:5518:05  Break 
18:0518:50 
A Rational Protocol Treatment of 51% Attacks
Vasillis Zikas
Abstract: Gametheoretic analyses of cryptocurrencies andmore generallyblockchainbased decentralized ledgers offer insight on their economic robustness and behavior when even their underpinning cryptographic assumptions fail. In this work we utilize the recently proposed blockchain adaptation of the rational protocol design (RPD) framework [EUROCRYPT'18] to analyze 51% doublespending attacks against Nakamotostyle proofofwork based cryptocurrencies. We first observe a property of the originally proposed utility class that yields an unnatural conclusion against such attacks, and show how to devise a utility that avoids this pitfall and makes predictions that match the observable behaviori.e., that renders attacking a dominant strategy in settings where an attack was indeed observed in reality. We then propose a generic remedy to the underlying protocol parameters that provably deter adversaries controlling a majority of the system's resources from attacks on blockchain con!
sistency, including the 51% doublespending attack. This can be used as guidance to patch systems that have suffered such attacks, e.g., Ethereum Classic and Bitcoin Cash, and serves as a demonstration of the power of gametheoretic analyses.
This is joint work wit Christian Badertscher and Yun Lu. 
18:5019:20 
Astrolabous: A Universally Composable TimeLock Encryption Scheme
Thomas Zacharias
Abstract: In this presentation, we explore the TimeLock Encryption (TLE) cryptographic primitive. The concept of TLE involves a party initiating the encryption of a message that everyone can decrypt, only after a certain amount of time has elapsed. Following the Universal Composability (UC) paradigm introduced by Canetti [IEEE FOCS 2001], we formally abstract the concept of TLE into an ideal functionality. In addition, we provide a standalone definition for secure TLE schemes in a gamebased style and we devise a hybrid UC protocol that relies on such a secure TLE scheme. The hybrid functionalities we consider are (i) a global clock, (ii) a random oracle, (iii) a broadcast channel, and (iv) a wrapper that models the limited resources of each party. We show that if the underlying TLE scheme satisfies the standalone gamebased security definition, then our hybrid protocol UC realises the TLE functionality. Finally, we present Astrolabous, a TLE construction that satisfies our security definition, leading to the first UC realisation of the TLE functionality.

19:2019:50 
gOTzilla: Efficient Disjunctive ZeroKnowledge Proofs from MPC in the Head, with Application to Proofs of Assets in Cryptocurrencies
Panos Chatzigiannis
Abstract: We present gOTzilla, a protocol for interactive zeroknowledge proofs for large disjunctive statements of the following format: given publicly known circuit $C$, and set of values $Y = \{y_1, \ldots, y_n\}$, prove knowledge of a witness $x$ such that $C(x) = y_1 \lor C(x) = y_2 \lor \cdots \lor C(x) = y_n$. These type of statements are extremely important for the proof of assets (PoA) problem in cryptocurrencies where a prover wants to prove the knowledge of a secret key $sk$ that associates with the hash of a public key $H(pk)$ posted on the ledger.
gOTzilla is based on the MPC in the head (MPCitH) paradigm and is based on the observation that if we restructure the proof statement to an equivalent of proving knowledge of $(x,y)$ such that $(C(x) = y) \land (y = y_1 \lor \cdots \lor y = y_n))$, then we can reduce the disjunction of equalities to 1outofN oblivious transfer (OT). We additionally provide a concrete, efficient extension of our protocol for the case where $C$ combines algebraic and nonalgebraic statements (which is the case in the PoA application). We achieve an asymptotic communication cost of $O(\log n)$ plus the proof size of the underlying MPCitH protocol. While related work has similar asymptotic complexity, our approach results in concrete performance improvements. We implement our protocol and provide benchmarks. Concretely, for a set of size 1 million entries, the total runtime of our protocol is 14.89 seconds using 48 threads, with 6.18 MB total communication, which is about 4x faster compared to the state of the art when considering a disjunctive statement with algebraic and nonalgebraic elements. 
19:5020:20 
Hours of Horus: Keyless Cryptocurrency Wallets
Dionysis Zindros
Abstract: We put forth a keyless wallet, a cryptocurrency wallet in which money can be spent using a password alone, and no private keys are required. It requires a smart contract blockchain. We propose two schemes. In the first, the user sets a short wallet password and can spend their money at a prespecified maturity date using the password alone. Using this as a stepping stone, we propose a second scheme, in which the user uses an OTP authenticator seed to generate a long series of timebased OTP passwords for the foreseeable future. These are encrypted and organized in a Merkle tree whose root is stored in a smart contract. The user can spend funds at any time by simply visually providing the current OTP password from an air gapped device. These OTPs can be relatively short: Just 6 alphanumeric characters suffice. Our OTP scheme can work in proofofstake as well as static and variable difficulty proofofwork blockchains. The lowentropy in the passwords and OTPs in our scheme is protected from brute force attempts by requiring that an adversary accompany any brute force attempt by a transaction on the chain. This quickly incurs enormous economic costs for the adversary. Thus, we develop the first decentralized rate limiting scheme. We use Witness Encryption (WE) to construct a timelock encryption scheme in which passwords are encrypted from past into future blocks by leveraging the NPlanguage expressing proofofwork or proofofstake performed as the witness. Witness Encryption is a currently impractical cryptographic primitive, but our scheme may become practical as these primitives are further developed.

20:20  Closing remarks  End of Athecrypt 2022 