Speaker: Vincenzo Iovino

Title: Voting with Succinct Verification from bilinear maps

Abstract: We present new verifiable voting schemes that are suitable for Decentralized Autonomous Organisations (DAOs) over the Ethereum network.

Voting procedures for the DAOs are carried out with the purpose of deciding whether or not to transfer funds to some Ethereum address. Currently, this has been done without privacy, that is the voters make public their voting preferences. There are two main types of voting settings: the multisig and the referendum one. In the former, there is a threshold k and the transfer of funds is accepted if there are at least k votes in support of the transfer. In the latter, the transfer is accepted whether there is support from the majority of the voters.

Voting on-chain on the Ethereum network is costly and may consume a huge quantity of GAS. For this reason, some researchers proposed to perform the voting procedure off-chain and to send to a smart contract only a SNARK proof that allows the smart contract to verify that a sufficient number of signatures have been submitted by valid voters. The cost of verifying the SNARK proof is constant, resulting thus in GAS consumption independent from the number of votes. We take a practical stance and propose voting schemes for the DAO in which the election result can be verified efficiently. We do not target the theoretical objective of constant GAS consumption in the verification of the result but we propose schemes whose verification in a smart contract consumes less GAS than current SNARK-based solutions in several use-cases when the number of voters is moderately high.

We put forth a formal model of what we call a Succinct Argument of Voting (SNARV) that also encompasses SNARK-based voting solutions and we present three SNARVs schemes from bilinear groups. All our protocols are provably secure in the random oracle model under the Computational Diffie-Hellman assumption. Unlike SNARK-based solutions, all our protocols do not depend on any CRS or trusted setup, do not require an administrator to setup a census, and have a linear time prover.

Speaker: Naomi Sirkin

Title: Non-Malleable Time-Lock Puzzles and Applications

Abstract: Time-lock puzzles are a mechanism for sending messages "to the future", by allowing a sender to quickly generate a puzzle with an underlying message that remains hidden until a receiver spends a moderately large amount of time solving it. We introduce and construct a variant of a time-lock puzzle which is non-malleable, which roughly guarantees that it is impossible to "maul" a puzzle into one for a related message without solving it.

Using non-malleable time-lock puzzles, we achieve the following applications:

(1) The first fair non-interactive multi-party protocols for coin flipping and auctions in the plain model without setup.

(2) Practically efficient fair multi-party protocols for coin flipping and auctions proven secure in the (auxiliary-input) random oracle model.

As a key step towards proving the security of our protocols, we introduce the notion of functional non-malleability, which protects against tampering attacks that affect a specific function of the related messages. To support an unbounded number of participants in our protocols, our time-lock puzzles satisfy functional non-malleability in the fully concurrent setting. We additionally show that standard (non-functional) non-malleability is impossible to achieve in the concurrent setting (even in the random oracle model).

This is based on joint work with Cody Freitag, Ilan Komargodski, and Rafael Pass.

Speaker: Sri Aravinda Krishnan Thyagarajan

Title: Cryptographic Locks For Cryptocurrency Payments

Abstract: Blockchains and their popular application of cryptocurrencies have revolutionized the payment infrastructure of the world. Users can now make trustless payments among each other without having to worry about extensive fees or hurdles. The technology has also given rise to more complex financial systems, referred to as Decentralized Finance (DeFi) systems. What has followed is the entry of numerous cryptocurrencies or DeFi systems as they are referred to, into the blockchain application space.

A natural question that arises is how do these different systems co-exist with each other. For example, a user of one cryptocurrency may want to make payments to another user who accepts tokens of a different cryptocurrency. Or, a user may want to exchange a token of one cryptocurrency with a token of another cryptocurrency. Such scenarios are trivial with centralized trusts like banks and exchange services, but require complex solutions in the blockchain setting which suffer from numerous security, privacy and cost issues. In this talk, we will see payment protocols to the above two scenarios that instead have better efficiency, sots, scalability, user-privacy and interoperability compared to existing solutions. The protocols make use of new cryptographic techniques in combination with new payment techniques to achieve these guarantees. By doing so, these protocols address several fundamental questions concerning the theoretical foundation and practical development of blockchain-based cryptocurrencies.

Bio: Sri AravindaKrishnan Thyagarajan (Aravind) is currently a Postdoc at NTT Research and was formerly a Postdoc at CMU with Elaine Shi. His primary research interest is in applied cryptography where he works on problems related to "cryptography meets game-theory” in applications like blockchains, security and privacy of payment applications in cryptocurrencies and fairness in multi-party computation. He completed his PhD in Computer Science at University of Erlangen-Nürnberg, Germany with Dominique Schröder in 2021 and Masters at Saarland University, Germany in 2016.

Personal Webpage

Speaker: Harish Karthikeyan

Title: Encapsulated Search Index: Public-Key, Sub-linear, Distributed, and Delegatable

Abstract: We build the first sub-linear (in fact, potentially constant-time) public-key searchable encryption system: − server can publish a public key PK. − anybody can build an encrypted index for document D under PK. − client holding the index can obtain a token zw from the server to check if a keyword w belongs to D. − search using zw is almost as fast (e.g., sub-linear) as the non-private search. − server granting the token does not learn anything about the document D, beyond the keyword w. − yet, the token zw is specific to the pair (D,w): the client does not learn if other keywords w′≠w belong to D, or if w belongs to other, freshly indexed documents D′. − server cannot fool the client by giving a wrong token zw. We call such a primitive Encapsulated Search Index (ESI). Our ESI scheme can be made (t,n)- distributed among n servers in the best possible way: non-interactive, verifiable, and resilient to any coalition of up to (t−1) malicious servers. We also introduce the notion of delegatable ESI and show how to extend our construction to this setting. Our solution — including public indexing, sub-linear search, delegation, and distributed token generation — is deployed as a commercial application by Atakama.

Recording: https://umass-amherst.zoom.us/rec/share/Bc35ofwjYYai-qV_n5kJGvSnS9Txte5GRkBHeVEzk7ncllZ7QoDr87MsvYU7AD8K.UXMNnB3HTfJDN60X?startTime=1651251822000

Speaker: Saeed Mahloujifar (Princeton)

Title: Is Private Learning Possible with Instance Encoding?

Abstract: In this work, we study whether a non-private learning algorithm can be made private by relying on an instance-encoding mechanism that modifies the training inputs before feeding them to a normal learner. We formalize the notion of instance encoding and its privacy by providing attack models. We first prove impossibility results for achieving these notions of privacy. Next, we demonstrate an attack on InstaHide, a recent proposal by Huang, Song, Li and Arora [ICML'20] that aims to use instance encoding for privacy.

Speaker: Wei Dai (UCSD)

Title: Concrete Security of Schnorr Signature and Schnorr-type Multi-Signature Schemes

Abstract: Schnorr signature and Schnorr-type multi-signatures have seen wide practical adoption in recent years due to their efficiency. However, current proofs of security for these signature schemes from the discrete-logarithm problem (DL) rely on the forking lemma and yield bounds on adversary advantage that are loose, failing to match the indications of cryptanalysis, and failing to justify security of implementations of the schemes in the 256-bit groups that are widely deployed in practice. In this talk, we present techniques to bridge this gap and conclude results that justify the instantiation of these schemes in 256-bit groups. We analyze the security of these signature schemes, as well as relations between their security, by giving modular reductions from shared starting points. We discuss the tight equivalence between the security of Schnorr signature, Bellare-Neven multi-signature, and the hardness of the identification discrete-logarithm problem (IDL). We discuss how to bypass the square-root loss in security in the hardness justification of IDL from DL by introducing the multi-base discrete-logarithm problem (MBDL). We then introduce the random-target identification discrete-logarithm problem (XIDL), justify its hardness from IDL, and demonstrate the equivalence between its hardness and the security of MuSig multi-signature scheme. Finally, we give construction of a two-round multi-signature scheme called HBMS and prove it secure using XIDL, resulting in the first efficient two-round multi-signature scheme whose qualitative security holds assuming only DL and whose quantitative security are justified to hold in 256-bit groups.

Speaker: Romain Gay (IBM Research Zürich)

Title: Dynamic Decentralized Functional Encryption

Abstract: We introduce Dynamic Decentralized Functional Encryption (DDFE), a generalization of Functional Encryption which allows multiple users to join the system dynamically, without relying on a trusted third party or on expensive and interactive Multi-Party Computation protocols. This notion subsumes existing multi-user extensions of Functional Encryption, such as Multi-Input, Multi-Client, and Ad Hoc Multi-Input Functional Encryption. We define and construct schemes for various functionalities which serve as building-blocks for latter primitives and may be useful in their own right, such as a scheme for dynamically computing sums in any Abelian group. These constructions build upon simple primitives in a modular way, and have instantiations from well-studied assumptions, such as DDH or LWE. Our constructions culminate in an Inner-Product scheme for computing weighted sums on aggregated encrypted data, from standard assumptions in prime-order groups in the Random Oracle Model.

Joint work with Jérémy Chotard and Edouard Dufour-Sans and Duong Hieu Phan and David Pointcheval. eprint: https://eprint.iacr.org/2020/197

Speaker: Dov Gordon (GMU)

Title: Secure Computation with Differentially Private Access Patterns

Abstract: Secure computation allows multiple parties, each with private input, to engage in some agreed upon computation while revealing nothing about the inputs beyond the result of the computation. Differential privacy provides a framework for anonymizing the output of such computations, given each contributing party a formal privacy guarantee. These tools serve orthogonal purposes: the first protects the process of computing, while the latter protects the result. In this talk, we will leverage differential privacy to create a security relaxation in secure computation. Specifically, we explore a new trade-off between efficiency and privacy in secure computation, by allowing some bounded amount of leakage to be observed by the computing servers, in the form of access patterns to memory. However, we give provable guarantees about what is revealed, demonstrating that what is leaked in the process of computing preserves the differential privacy of the users that have contributed data. The leakage allows us to improve on the run-time of existing protocols for a wide class of computations.

Speaker: Sogol Mazaheri (TU Darmstadt)

Title: On Defeating Backdoors in Hash Functions

Abstract: Cryptosystems are vulnerable to being sabotaged by big brother adversaries. Therefore, it is of utmost necessity to rigorously study such sabotage and to develop resilient cryptosystems. Considering that the anticipated adversary is an extremely powerful one, finding solutions to this problem requires not only tailoring the existing approaches from various areas in cryptography and other closely related disciplines to new scenarios but at times also entirely new design and proof techniques. In this talk I will focus on the security of cryptographic hash functions. In particular I will talk about an extension of the random oracle model, called backdoored random oracle model, whereby a big brother designs a good hash function, but can also see arbitrary functions of its table via backdoor capabilities. Then I will explain how we can re-establish security properties by combing two or more independently designed hash functions even if they are all backdoored.

Speaker: Aloni Cohen

Title: Bridging the Divide Between Computer Science and Law

Abstract: Seriously engaging with law and policy exposes new computer science research directions that also have policy consequences. My work aims to understand and resolve the tensions between the theory of privacy and cryptography on the one hand and the privacy laws that govern its eventual real-world context. In this talk, I'll describe work that tackles three broad questions: How can we bridge the basic concepts of data privacy in computer science and law? How can privacy theory have a positive impact on policy? How can we incorporate legal powers and constraints into our cryptographic threat models for better cryptography?