Cryptography and Policy
The Digital Currency Initiative is interested in cryptography research beyond digital currency and blockchains. The DCI and its collaborators conduct research on cryptographic primitives that may be used in conjunction with blockchain technologies — such as zero-knowledge proofs and digital signatures — and on cryptographic tools and theories related to goals advanced by blockchain-based digital currency — such as anonymity, accountability/transparency, tamper-proofness, and free and secure communication.
The DCI is also interested in technology policy, especially policy issues related to cryptography and digital currency. On one hand, how does or should modern technology policy impact use and development of cryptography and blockchain-based technologies? On the other hand, when and how can cryptographic tools efficiently promote specific policy goals — and when is cryptography or blockchain technology the wrong tool to achieve a given goal?
This page features some recent DCI work on cryptography beyond blockchains and on cryptography and policy.
Papers
Abstract
This paper shows several connections between data structure problems and cryptography against preprocessing attacks. Our results span data structure upper bounds, cryptographic applications, and data structure lower bounds, as summarized next.
First, we apply Fiat–Naor inversion, a technique with cryptographic origins, to obtain a data structure upper bound. In particular, our technique yields a suite of algorithms with space S and (online) time T for a preprocessing version of the N-input 3SUM problem where S3 ·T = O(N6). This disproves a strong conjecture (Goldstein et al., WADS 2017) that there is no data structure that solves this problem for S = N2−δ and T = N1−δ for any constant δ > 0.
Secondly, we show equivalence between lower bounds for a broad class of (static) data struc- ture problems and one-way functions in the random oracle model that resist a very strong form of preprocessing attack. Concretely, given a random function F : [N] → [N] (accessed as an oracle) we show how to compile it into a function GF : [N2] → [N2] which resists S-bit prepro- cessing attacks that run in query time T where ST = O(N2−ε) (assuming a corresponding data structure lower bound on 3SUM). In contrast, a classical result of Hellman tells us that F itself can be more easily inverted, say with N2/3-bit preprocessing in N2/3 time. We also show that much stronger lower bounds follow from the hardness of kSUM. Our results can be equivalently interpreted as security against adversaries that are very non-uniform, or have large auxiliary input, or as security in the face of a powerfully backdoored random oracle.
Thirdly, we give lower bounds for 3SUM which match the best known lower bounds for static data structure problems (Larsen, FOCS 2012). Moreover, we show that our lower bound generalizes to a range of geometric problems, such as three points on a line, polygon containment, and others.
by Sunoo Park (MIT Media Lab) and Adam Sealfon (MIT CSAIL)
To appear in the International Cryptology Conference (CRYPTO 2019).
By Thibaut Horel, Sunoo Park, Silas Richelson, and Vinod Vaikuntanathan. Published in the Innovations in Theoretical Computer Science conference (ITCS 2019).
By Aloni Cohen and Sunoo Park. Published in the Harvard Journal of Law and Technology (JOLT), Fall 2018 issue.
By Jonathan Frankle, Sunoo Park, Daniel Shaar, Shafi Goldwasser, and Daniel J. Weitzner. Published in the 27th USENIX Security Symposium (USENIX Security 2018).
By Sunoo Park, Albert Kwon, Georg Fuchsbauer, Peter Gaži, Joël Alwen, and Krzysztof Pietrzak. Published in the 22nd International Conference on Financial Cryptography and Data Security (Financial Crypto 2018)
By Thaddeus Dryja, Quanquan C. Liu and Sunoo Park
Static-Memory-Hard Functions, and Modeling the Cost of Space vs. Time was presented at the Cryptography Conference 2019, which is organized by the International Association for Cryptologic Research (IACR).
Media
DCI’s Director Neha Narula commented on ‘Gemini Trust ad campaign calling for new regulations’ in an article for The Wall Street Journal
