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

Speaker: Marios Adamoudis

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.

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).

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.

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.

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.

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.

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.

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]

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.

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.

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.

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.

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.

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.

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.

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.

Title: Differential Privacy for Inventory Obfuscation

Speaker: Antigoni Polychroniadou

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

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.

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.

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.

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).

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

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.

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.