Theory of Cryptography Conference ‘22: Field Notes

Editor’s note: Field notes is a series where we report on the ground at significant industry, research, and other events. In this edition, Miranda Christ, a16z crypto research associate, shares highlights particularly related to blockchains from the Theory of Cryptography Conference, which took place November 7-10 in Chicago. The conference is organized by by the International Association for Cryptologic Research (IACR). 

Invited Talk: Meta-Complexity as a Tool in the Foundations of Cryptography – Rahul Santhanam

Most cryptographic primitives are built using hardness assumptions about specific problems, such as factoring. While these assumptions are standard in cryptography, how they fit into the complexity theory landscape remains unclear. One might instead hope to build cryptographic assumptions using standard complexity assumptions (e.g., P ≠ NP), or even better, to fully characterize primitives by showing necessary and sufficient complexity assumptions. This is where meta-complexity comes in. Meta-complexity problems are problems that are themselves about the complexity of solving problems. For example, in the minimum circuit size problem (MCSP), one is given as input the truth table of a function F and a size parameter s. The goal is to determine whether there exists a circuit of size s implementing F. This talk introduces meta-complexity and  surveys recent results connecting meta-complexity and cryptography and discusses open problems. 

Random-Index Oblivious RAM – Shai Halevi, Eyal Kushilevitz

In oblivious RAM (ORAM), a client accesses data held by an untrusted server through a compiler, which queries the server in such a way that the server doesn’t learn which indices the client accesses. The compiler should use as little space and communication as possible. In this paper, the authors consider a relaxation of this problem where the client specifically wishes to sample a random index. One motivation for this is lotteries, where participants register with the server, and the client chooses a winner uniformly at random in such a way that the server doesn’t know who won. Random-index ORAM (RORAM) is also potentially useful for randomly sampling committees. This paper formally defines RORAM and gives RORAM schemes that achieve better efficiency than those for general ORAM.

Multi-Authority ABE from Lattices without Random Oracles – Brent Waters, Hoeteck Wee, David J. Wu

In attribute-based encryption (ABE), users are allowed to decrypt only if they have certain combinations of desired attributes (e.g., employer, job). Typically, a single authority is in charge of ensuring that each user has the appropriate decryption key for its attributes. This paper considers a multi-authority setting, where different authorities (e.g., corresponding to different employers) manage keys for users with different attributes. The challenge here is ensuring that users at employers A and B respectively cannot collude and combine their keys to decrypt a ciphertext meant for users employed by both A and B simultaneously. The authors succeed in finding such a construction, using a somewhat nonstandard assumption called evasive LWE. 

SCALES: MPC with Small Clients and Larger Ephemeral Servers – Anasuya Acharya, Carmit Hazay, Vladimir Kolesnikov, Manoj Prabhakaran

This paper considers multi-party computation (MPCº in a blockchain-inspired setting where there are computationally limited clients (like blockchain users) that provide input, and the servers performing the bulk of the computation (like validators) are selected unpredictably from a large server set and are ephemeral (need only send one message before going offline). This is a relaxation of the recently introduced and similarly blockchain-inspired YOSO (“You Only Speak Once”) model of MPC. In SCALES, the clients provide the input and remain online to collect the output, whereas in YOSO all parties send only one message and disappear. This modification allows the authors to achieve greater efficiency compared to YOSO, while still maintaining a practical setting.

Invited Talk: From Practice to Theory: how I learned to stop worrying and love the models – Eran Tromer

Eran Tromer discussed several areas where practical problems have led him to theoretical work. He provided an overview of surprisingly powerful side channel attacks that are possible in practice – for example, using a parabolic microphone an adversary can learn a 4096-bit RSA key by recording and analyzing sound waves emitted by a laptop running a computation. This motivated a new model of leakage-resilient circuits, where at a high level a circuit (representing the computation that the laptop is performing) is leakage-resilient if an adversary cannot learn the input even if it learns some extra low-complexity global information about the circuit (capturing the noise picked up by the microphone). Other topics covered include unclonable polymers (proteins) and their applications to cryptography, anonymous messaging systems, and Zcash.

On the Impossibility of Algebraic Vector Commitments in Pairing-Free Groups – Dario Catalano, Dario Fiore, Rosario Gennaro, Emanuele Giunta

A VC scheme is algebraic if, at a high level, it requires only black-box access to its underlying group (i.e., uses only the group operation), both in generating commitments and verifying openings (proofs of vector components). Algebraic VCs often have constant-sized openings, making them very practical. This paper shows that a natural subclass of algebraic VCs is unrealizable in pairing-free groups.

Poly Onions: Achieving Anonymity in the Presence of Churn – Megumi Ando, Miranda Christ, Anna Lysyanskaya, Tal Malkin

I presented my own recent work, where my coauthors, focused on onion routing in a setting with network churn (where servers might go offline unpredictably). In onion routing, Alice hides the fact that she’s talking to Bob by encrypting her message in layers and routing it to Bob via a path of intermediary servers, each of which decrypts (“peels”) a layer of the onion before relaying it. At each intermediary server, Alice’s onion mixes with many other network participants’ onions, making it appear to an adversary observing all network traffic that Alice could be talking to other participants instead of Bob. However, if one of these intermediary servers is offline, Alice’s onion will not make it to Bob. To solve this problem, we construct a new type of cryptographic onion, called a Poly Onion, which allows the onion to be routed to a different intermediary server in the case that the desired server is offline. We also propose new definitions of anonymity for this setting and show that Poly Onion Encryption can be used to construct a communication protocol achieving anonymity, even when a constant fraction of servers may go offline.

Permissionless Clock Synchronization with Public Setup – Juan Garay, Aggelos Kiayias, Yu Shen

This paper considers the problem of maintaining a clock among a permissionless group of parties that might come and go unpredictably, as is common with blockchains. They specifically want a clock synchronization protocol that uses only public setup and proof-of-work, which they succeed in constructing. This clock synchronization protocol allows them to construct a proof-of-work-based consensus protocol whose block difficulty adjustment does not need an external clock (unlike Bitcoin).

One-Time Programs from Commodity Hardware – Harry Eldridge, Aarushi Goel, Matthew Green, Abhishek Jain, Maximilian Zinkus

A one-time program (OTP) is a piece of code that can be run only once, on a single input. If OTPs existed, they would be useful for applications such as limited-attempt authentication, differentially private data analysis (where the analyst can make only a limited number of queries), and autonomous ransomware. We can’t build one-time programs in theory, since code can always be copied. This work constructs OTPs from counter lockboxes, a common piece of hardware that stores a secret and allows a user to make only a limited number of password guesses to unlock the box and recover the secret. 

Universal Reductions: Reductions Relative to Stateful Oracles – Benjamin Chan, Cody Freitag, Rafael Pass

In cryptography, we usually prove that a protocol is secure by showing that if an adversary A breaks the protocol, another adversary B can run A as a subroutine to break some hardness assumption. However, implicit in many such reductions is the assumption that B can re-run A many times. This paper considers what happens when A might be stateful, allowing B only to query it some limited number of times (possibly only once). This restriction is especially relevant to quantum settings. In addition to defining this new notion of a universal reduction, this paper shows various impossibility and feasibility results in this new model.

***
Miranda Christ is a PhD student in Computer Science at Columbia University, where she is a member of the Theory Group and a Presidential Fellow. She is also a research intern at a16z crypto.

***
The views expressed here are those of the individual AH Capital Management, L.L.C. (“a16z”) personnel quoted and are not the views of a16z or its affiliates. Certain information contained in here has been obtained from third-party sources, including from portfolio companies of funds managed by a16z. While taken from sources believed to be reliable, a16z has not independently verified such information and makes no representations about the enduring accuracy of the information or its appropriateness for a given situation. In addition, this content may include third-party advertisements; a16z has not reviewed such advertisements and does not endorse any advertising content contained therein.

This content is provided for informational purposes only, and should not be relied upon as legal, business, investment, or tax advice. You should consult your own advisers as to those matters. References to any securities or digital assets are for illustrative purposes only, and do not constitute an investment recommendation or offer to provide investment advisory services. Furthermore, this content is not directed at nor intended for use by any investors or prospective investors, and may not under any circumstances be relied upon when making a decision to invest in any fund managed by a16z. (An offering to invest in an a16z fund will be made only by the private placement memorandum, subscription agreement, and other relevant documentation of any such fund and should be read in their entirety.) Any investments or portfolio companies mentioned, referred to, or described are not representative of all investments in vehicles managed by a16z, and there can be no assurance that the investments will be profitable or that other investments made in the future will have similar characteristics or results. A list of investments made by funds managed by Andreessen Horowitz (excluding investments for which the issuer has not provided permission for a16z to disclose publicly as well as unannounced investments in publicly traded digital assets) is available at https://a16z.com/investments/.

Charts and graphs provided within are for informational purposes solely and should not be relied upon when making any investment decision. Past performance is not indicative of future results. The content speaks only as of the date indicated. Any projections, estimates, forecasts, targets, prospects, and/or opinions expressed in these materials are subject to change without notice and may differ or be contrary to opinions expressed by others. Please see https://a16z.com/disclosures for additional important information.