We present zk-Analytics, a distributed cloud analytics system that enables publicly verifiable analytics without revealing raw logs or relying on trusted hardware in analytics providers' infrastructure. Today's cloud analytics are largely self-assertive: providers collect telemetry, perform aggregation, and report results, leaving external parties unable to verify correctness without access to sensitive data or trusted execution environments. zk-Analytics addresses this gap by augmenting analytics pipelines with lightweight append-only log commitments and verifiable aggregation and query execution using zero-knowledge proofs. The system cleanly separates online log commitment from offline, distributed batch aggregation and query verification, enabling scalability while keeping online overhead low. We implement zk-Analytics using a zkVM-based execution environment and evaluate it on real-world and synthetic workloads, demonstrating that verifiable, privacy-preserving cloud analytics is feasible for real-world cloud workloads. zk-Analytics is open-sourced at https://github.com/Froot-NetSys/zk-Analytics.

Verifiable network telemetry is crucial for ensuring transparency and trust in network measurements. However, telemetry logs (e.g., NetFlow records) often contain sensitive data, making public verification challenging. Recent work has attempted to address this problem using Trusted Execution Environments (TEEs), such as Intel SGX, to provide confidentiality and integrity guarantees. However, TEEs are known to suffer from complex deployment requirements and limited scalability. In this paper, we introduce a software-based approach utilizing the latest advances in Zero-knowledge Proofs (ZKPs) to enable verifiable network telemetry without revealing the underlying sensitive logs or relying on special-purpose hardware. Our system employs a general-purpose ZKP virtual machine (RISC Zero) to generate cryptographic proofs over NetFlow data, enabling operators to securely attest to network flow metrics. Our preliminary results indicate that our ZKP-based design offers a viable path toward overcoming deployment and scalability limitations inherent in the solutions that require special-purpose hardware.

Anonymous Broadcast Channels (ABCs) allow a group of clients to announce messages without revealing the exact author. Modern ABCs operate in a client-server model, where anonymity depends on some threshold (e.g, 1 of 2) of servers being honest. ABCs are an important application in their own right, e.g., for activism and whistleblowing. Recent work on ABCs (Riposte, Blinder) has focused on minimizing the bandwidth cost to clients and servers when supporting large broadcast channels for such applications. But, particularly for low bandwidth settings, they impose large costs on servers, make cover traffic costly, and make volunteer operators unlikely. In this paper, we describe the design, implementation, and evaluation of ZipNet, an anonymous broadcast channel that: 1) scales to hundreds of anytrust servers by minimizing the computational costs of each server, 2) substantially reduces the servers' bandwidth costs by outsourcing the aggregation of client messages to untrusted (for privacy) infrastructure, and 3) supports cover traffic that is both cheap for clients to produce and for servers to handle.

Zero-knowledge Succinct Non-interactive ARguments of Knowledge (zkSNARKs) allow a prover to convince a verifier of the correct execution of a large computation in private and easily-verifiable manner.These properties make zkSNARKs a powerful tool for adding accountability, scalability, and privacy to numerous systems such as blockchains and verifiable key directories.Unfortunately, existing zkSNARKs are unable to scale to large computations due to time and space complexity requirements for the prover algorithm.As a result, they cannot handle real-world instances of the aforementioned applications.In this work, we introduce Hekaton, a zkSNARK that overcomes these barriers and can efficiently handle arbitrarily large computations.We construct Hekaton via a new "distribute-and-aggregate" framework that breaks up large computations into small chunks, proves these chunks in parallel in a distributed system, and then aggregates the resulting chunk proofs into a single succinct proof.Underlying this framework is a new technique for efficiently handling data that is shared between chunks that we believe could be of independent interest.We implement a distributed prover for Hekaton, and evaluate its performance on a compute cluster.Our experiments show that Hekaton achieves strong horizontal scalability (proving time decreases linearly as we increase the number of nodes in the cluster), and is able to prove large computations quickly: it can prove computations of size 2 35 gates in under an hour, which is much faster than prior work.Finally, we also apply Hekaton to two applications of realworld interest: proofs of batched insertion for a verifiable key directory and proving correctness of RAM computations.In both cases, Hekaton is able to scale to handle realistic workloads with better efficiency than prior work.

Potential harms of large language models can be mitigated by watermarking model output, i.e., embedding signals into generated text that are invisible to humans but algorithmically detectable from a short span of tokens. We propose a watermarking framework for proprietary language models. The watermark can be embedded with negligible impact on text quality, and can be detected using an efficient open-source algorithm without access to the language model API or parameters. The watermark works by selecting a randomized set of "green" tokens before a word is generated, and then softly promoting use of green tokens during sampling. We propose a statistical test for detecting the watermark with interpretable p-values, and derive an information-theoretic framework for analyzing the sensitivity of the watermark. We test the watermark using a multi-billion parameter model from the Open Pretrained Transformer (OPT) family, and discuss robustness and security.

Cryptographers have long been concerned with secure messaging protocols threatening deniability. Many messaging protocols—including, surprisingly, modern email— contain digital signatures which definitively tie the author to their message. If stolen or leaked, these signatures make it impossible to deny authorship. As illustrated by events surrounding leaks from Hilary Clinton’s 2016 U.S. presidential campaign, this concern has proven well founded. Deniable protocols are meant to avoid this very outcome, letting politicians and dissidents alike safely disavow authorship. Despite being deployed on billions of devices in Signal and WhatsApp, the effectiveness of such protocols in convincing people remains unstudied. While the absence of cryptographic evidence is clearly necessary for an effective denial, is it sufficientƒWe conduct a survey study (n = 1, 200) to understand how people perceive evidence of deniability related to encrypted messaging protocols. Surprisingly, in a world of "fake news" and Photoshop, we find that simple denials of message authorship, when presented in a courtroom setting without supporting evidence, are not effective. In contrast, participants who were given access to a screenshot forgery tool or even told one exists were much more likely to believe a denial. Similarly, but to a lesser degree, we find an expert cryptographer’s assertion that there is no evidence is also effective.

Frequently, users on the web need to show that they are, for example, not a robot, old enough to access an age restricted video, or eligible to download an ebook from their local public library without being tracked. Anonymous credentials were developed to address these concerns. However, existing schemes do not handle the realities of deployment or the complexities of real-world identity. Instead, they implicitly make assumptions such as there being an issuing authority for anonymous credentials that, for real applications, requires the local department of motor vehicles to issue sophisticated cryptographic tokens to show users are over 18. In reality, there are multiple trust sources for a given identity attribute, their credentials have distinctively different formats, and many, if not all, issuers are unwilling to adopt new protocols.We present and build zk-creds, a protocol that uses general-purpose zero-knowledge proofs to 1) remove the need for credential issuers to hold signing keys: credentials can be issued to a bulletin board instantiated as a transparency log, Byzantine system, or even a blockchain; 2) convert existing identity documents into anonymous credentials without modifying documents or coordinating with their issuing authority; 3) allow for flexible, composable, and complex identity statements over multiple credentials. Concretely, identity assertions using zk-creds take less than 150ms in a real-world scenario of using a passport to anonymously access age-restricted videos.

Zero-knowledge blocklists allow cross-platform blocking of users but, counter-intuitively, do not link users identities inter- or intra-platform, or to the fact they were blocked. Unfortunately, existing approaches (Tsang et al. ’10) require that servers do work linear in the size of the blocklist for each verification of a non-membership proof.We design and implement SNARKBLOCK, a new protocol for zero-knowledge blocklisting with server-side verification that is logarithmic in the size of the blocklist. SNARKBLOCK is also the first approach to support ad-hoc, federated blocklisting: websites can mix and match their own blocklists from other blocklists and dynamically choose which identity providers they trust.Our core technical advance, of separate interest, is the HICIAP zero-knowledge proof system, which addresses a common problem in privacy-preserving protocols: using zero-knowledge proofs for repeated but unlinakble interactions. Rerandomzing a Groth16 proof achieves unlinkability without the need to recompute the proof for every interaction. But this technique does not apply to applications where each interaction includes multiple Groth16 proofs over a common hidden input (e.g., the user’s identity). Here, the best known approach is to commit to the hidden input and feed it to each proof, but this creates a persistent identifier, forcing recomputation. HICIAP resolves this problem by aggregating n Groth16 proofs into one $O(\log n) -$sized, $O(\log n) -$verification time proof which also shows that the input proofs share a hidden input. Because HICIAP is zero-knowledge, repeated shows of the same aggregate or an updated aggregate are unlinkable even though the underlying Groth16 proofs are never recomputed.

Many privacy-preserving protocols employ a primitive that allows a sender to "flag" a message to a recipient's public key, such that only the recipient (who possesses the corresponding secret key) can detect that the message is intended for their use. Examples of such protocols include anonymous messaging, privacy-preserving payments, and anonymous tracing. A limitation of the existing techniques is that recipients cannot easily outsource the detection of messages to a remote server, without revealing to the server the exact set of matching messages. In this work we propose a new class of cryptographic primitives called \em fuzzy message detection schemes. These schemes allow a recipient to derive a specialized message detection key that can identify correct messages, while also incorrectly identifying non-matching messages with a specific and chosen false positive rate p. This allows recipients to outsource detection work to an untrustworthy server, without revealing precisely which messages belong to the receiver. We show how to construct these schemes under a variety of assumptions; describe several applications of the new technique; and show that our schemes are efficient enough to use in real applications.

Ledger-based systems that support rich applications often suffer from two limitations. First, validating a transaction requires re-executing the state transition that it attests to. Second, transactions not only reveal which application had a state transition but also reveal the application's internal state.We design, implement, and evaluate ZEXE, a ledger-based system where users can execute offline computations and subsequently produce transactions, attesting to the correctness of these computations, that satisfy two main properties. First, transactions hide all information about the offline computations. Second, transactions can be validated in constant time by anyone, regardless of the offline computation.The core of ZEXE is a construction for a new cryptographic primitive that we introduce, decentralized private computation (DPC) schemes. In order to achieve an efficient implementation of our construction, we leverage tools in the area of cryptographic proofs, including succinct zero knowledge proofs and recursive proof composition. Overall, transactions in ZEXE are 968 bytes regardless of the offline computation, and generating them takes less than 1min plus a time that grows with the offline computation.We demonstrate how to use ZEXE to realize privacy-preserving analogues of popular applications: private user-defined assets and private decentralized exchanges for these assets.

The growing adoption of digital assets---including but not limited to cryptocurrencies, tokens, and even identities---calls for secure and robust digital assets custody. A common way to distribute the ownership of a digital asset is (M, N)-threshold access structures. However, traditional access structures leave users with a painful choice. Setting M = N seems attractive as it offers maximum resistance to share compromise, but it also causes maximum brittleness: A single lost share renders the asset permanently frozen, inducing paralysis. Lowering M improves availability, but degrades security.

We present a new primitive supporting file replication in distributed storage networks (DSNs) called a Public Incompressible Encoding (PIE). PIEs operate in the challenging public DSN setting where files must be encoded and decoded with public randomness-i.e., without encryption-and retention of redundant data must be publicly verifiable. They prevent undetectable data compression, allowing DSNs to use monetary rewards or penalties in incentivizing economically rational servers to properly replicate data. Their definition also precludes critical, demonstrated attacks involving parallelism via ASICs and other custom hardware. Our PIE construction is the first to achieve experimentally validated near-optimal performance-within a factor of 4 of optimal by one metric. It also allows decoding orders of magnitude faster than encoding, unlike other comparable constructions. We achieve this high security and performance using a graph construction called a Dagwood Sandwich Graph (DSaG), built from a novel interleaving of depth-robust graphs and superconcentrators. PIEs' performance makes them appealing for DSNs, such as the proposed Filecoin system and Ethereum data sharding. Conversely, their near-optimality establishes concerning bounds on the practical financial and energy costs of DSNs allowing arbitrary data.

Bitcoin owes its success to the fact that transactions are transparently recorded in the blockchain, a global public ledger that removes the need for trusted parties. Unfortunately, recording every transaction in the blockchain causes privacy, latency, and scalability issues. Building on recent proposals for "micropayment channels" --- two party associations that use the ledger only for dispute resolution --- we introduce techniques for constructing anonymous payment channels. Our proposals allow for secure, instantaneous and private payments that substantially reduce the storage burden on the payment network. Specifically, we introduce three channel proposals, including a technique that allows payments via untrusted intermediaries. We build a concrete implementation of our scheme and show that it can be deployed via a soft fork to existing anonymous currencies such as ZCash.

Secure multiparty computation allows mutually distrusting parties to compute a function on their private inputs such that nothing but the function output is revealed. Achieving fairness --- that all parties learn the output or no one does -- is a long studied problem with known impossibility results in the standard model if a majority of parties are dishonest. We present a new model for achieving fairness in MPC against dishonest majority by using public bulletin boards implemented via existing infrastructure such as blockchains or Google's certificate transparency logs. We present both theoretical and practical constructions using either witness encryption or trusted hardware (such as Intel SGX). Unlike previous works that either penalize an aborting party or achieve weaker notions such as $\Delta$-fairness, we achieve complete fairness using existing infrastructure.

We present a protocol to enable privacy preserving advertising reporting at scale. Unlike previous systems, our work scales to millions of users and tens of thousands of distinct ads. Our approach builds on the homomorphic encryption approach proposed by Adnostic, but uses new cryptographic proof techniques to efficiently report billions of ad impressions a day using an additively homomorphic voting schemes. Most importantly, our protocol scales without imposing high loads on trusted third parties. Finally, we investigate a cost effective method to privately deliver ads with computational private information retrieval.

In this paper we investigate new mechanisms for achieving forward secure encryption in store and forward messaging systems such as email and SMS. In a forward secure encryption scheme, a user periodically updates her secret key so that past messages remain confidential in the event that her key is compromised. A primary contribution of our work is to introduce a new form of encryption that we name puncturable encryption. Using a puncturable encryption scheme, recipients may repeatedly update their decryption keys to revoke decryption capability for selected messages, recipients or time periods. Most importantly, this update process does not require the recipients to communicate with or distribute new key material to senders. We show how to combine puncturable encryption with the forward-secure public key encryption proposal of Canetti et al. To achieve practical forward-secure messaging with low overhead. We implement our schemes and provide experimental evidence that the new constructions are practical.

Abstract A common approach to demands for lawful access to encrypted data is to allow a trusted third party (TTP) to gain access to private data. However, there is no way to verify that this trust is well placed as the TTP may open all messages indiscriminately. Moreover, existing approaches do not scale well when, in addition to the content of the conversation, one wishes to hide one’s identity. Given the importance of metadata this is a major problem. We propose a new approach in which users can retroactively verify cryptographically whether they were wiretapped. As a case study, we propose a new signature scheme that can act as an accountable replacement for group signatures, accountable forward and backward tracing signatures.

Bit coin is the first digital currency to see widespread adoption. While payments are conducted between pseudonyms, Bit coin cannot offer strong privacy guarantees: payment transactions are recorded in a public decentralized ledger, from which much information can be deduced. Zero coin (Miers et al., IEEE S&P 2013) tackles some of these privacy issues by unlinking transactions from the payment's origin. Yet, it still reveals payments' destinations and amounts, and is limited in functionality. In this paper, we construct a full-fledged ledger-based digital currency with strong privacy guarantees. Our results leverage recent advances in zero-knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARKs). First, we formulate and construct decentralized anonymous payment schemes (DAP schemes). A DAP scheme enables users to directly pay each other privately: the corresponding transaction hides the payment's origin, destination, and transferred amount. We provide formal definitions and proofs of the construction's security. Second, we build Zero cash, a practical instantiation of our DAP scheme construction. In Zero cash, transactions are less than 1 kB and take under 6 ms to verify - orders of magnitude more efficient than the less-anonymous Zero coin and competitive with plain Bit coin.

Bitcoin is the first e-cash system to see widespread adoption. While Bitcoin offers the potential for new types of financial interaction, it has significant limitations regarding privacy. Specifically, because the Bitcoin transaction log is completely public, users' privacy is protected only through the use of pseudonyms. In this paper we propose Zerocoin, a cryptographic extension to Bitcoin that augments the protocol to allow for fully anonymous currency transactions. Our system uses standard cryptographic assumptions and does not introduce new trusted parties or otherwise change the security model of Bitcoin. We detail Zerocoin's cryptographic construction, its integration into Bitcoin, and examine its performance both in terms of computation and impact on the Bitcoin protocol.