Anonymity Days is a workshop series for disseminating recent advances in anonymity research. It will occur twice a year at Brown University, Tufts University, or Columbia University, rotating between the three venues. Our target audience is theory and security researchers/graduate students interested in sharing and learning the newest anonymity results, but everyone is welcome!
This is open to all, but you must register by April 1, 2025 midnight EST to attend since you will not be able to access the building without a valid QR code. Click here to register.
9:30-10 Intro / Coffee / Opening remarks by Tal Malkin (Columbia)
10-11 "Anonymity in Decentralized Settings" by Ghada Almashaqbeh (UCONN)
11:15-12:15 "Perpetual Encryption" by Yevgeniy Dodis (New York University)
12:30 -- Lunch served --
1:00-2:00 "How to Prove False Statements: Practical Attacks on Fiat-Shamir" by Ron Rothblum (Succinct)
-- Move to CEPSR 414; the remainder of the workshop will be held in CEPSR 414 --
2:30 - 3:15 "Are we finally getting anonymous credentials?" by Eysa Lee (Brown)
3:30 -- Social break and mini art exhibit --
Blockchain technology provides an innovative model that led to new research frontiers in distributed systems and cryptography. This ignited a movement towards a decentralized version of the Internet under the term Web 3.0. At the same time, innovations in AI and machine learning systems led to a long line of research targeting their privacy issues as they deal with sensitive user data. Both of these are instances of large-scale distributed systems, which is a challenging setting. This talk explores the anonymity issue in Web 3.0 applications and federated learning. In particular, I will present RelaySchnorr—an anonymous proxy signature scheme that supports timed delegation, revocability, and policy enforcement in a non-interactive and fully-decentralized way; and AnoFel—a framework that supports private and anonymous dynamic participation in federated learning inspired by recent advances on private cryptocurrencies. Based on joint works with Anca Nitulescu and Zahra Ghodsi.
The Fiat-Shamir (FS) transform is a prolific and powerful technique for compiling public-coin interactive protocols into non-interactive ones. Roughly speaking, the idea is to replace the random coins of the verifier with the evaluations of a complex hash function. The FS transform is known to be sound in the random oracle model (i.e., when the hash function is modeled as a totally random function). However, when instantiating the random oracle using a concrete hash function, there are examples of protocols in which the transformation is not sound. So far all of these examples have been contrived protocols that were specifically designed to fail. In this work we show such an attack for a standard and popular interactive succinct argument, based on the GKR protocol, for verifying the correctness of a non-determinstic bounded-depth computation. For every choice of FS hash function, we show that a corresponding instantiation of this protocol, which was been widely studied in the literature and used also in practice, is not (adaptively) sound when compiled with the FS transform. Specifically, we construct an explicit circuit for which we can generate an accepting proof for a false statement. We further extend our attack and show that for every circuit and desired output , we can construct a functionally equivalent circuit , for which we can produce an accepting proof that outputs (regardless of whether or not this statement is true). This demonstrates that any security guarantee (if such exists) would have to depend on the specific implementation of the circuit , rather than just its functionality. Lastly, we also demonstrate versions of the attack that violate non-adaptive soundness of the protocol -- that is, we generate an attacking circuit that is independent of the underlying cryptographic objects. However, these versions are either less practical (as the attacking circuit has very large depth) or make some additional (reasonable) assumptions on the underlying cryptographic primitives.
We consider the problem of building a private blockchain (BC) on top of a public one. This has the advantage that users of the private BC do not need to build expensive consensus protocol, while still maintaining privacy. When building this object, we realize the need for a novel encryption scheme we call perpetual encryption (PE), which is a new primitive of independent interest.
Very roughly, PE schemes support dynamically changing keys sk_1, sk_2, ... in a way that ciphertext c_n for epoch n:
(1) can be efficiently decrypted using any future key sk_n, sk_{n+1},...
(2) looks random even given all past keys sk_1,..,sk_{n-1}.
We also show how to build an efficient PE from any public-key encryption, hashing and other standard symmetric primitives.
Organized by Megumi Ando (Tufts), Anna Lysyanskaya (Brown), Tal Malkin (Columbia), and Eli Upfal (Brown).
Supported by NSF grants CCF-2312241, CCF-2312242, and CCF-2312243.