ACM Conference on Computer and Communications Security 2022: 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, Valeria Nikolaenko, a16z crypto Research Partner, shares her quick highlights from the ACM CCS conference, which took place November 7-11 in Los Angeles. The conference is one of the largest in computer and communication security. Lera notes: “I highlighted papers and talks you might not want to miss, as well as papers most relevant to blockchain tech. Make sure to also check out the papers that won best paper awards, mentioned below.”

Keynotes

• Shafi Goldwasser, the Director of the Simons Institute at UC Berkeley, gave a talk on planting an undetectable trapdoor in the machine learning models (paper).
• Michelle Mazurek, an Associate Professor in University of Maryland, talked about the general confusion about the guidelines (often 300+) given to non-expert to help them stay safe online, including vague caution to be “careful” when using public WiFi, or the rules around password’s expiry. She argues we, as a community, should make the recommendations more clear, and more importantly find channels to reach the general public.
• Srini Devadas, Professor at MIT, highlighted his recent developments in hardware acceleration of lattice-based fully-homomorphic encryption. On his radar might be accelerations of zero-knowledge provers. Srini’s work is behind the design of Intel SGX.

Core-cryptography

• Reinforced Concrete: A Fast Hash Function for Verifiable Computation
  Is a promising new hash-function that performs better within zk-proofs, as well is very fast when executed natively:

• MatProofs: Maintainable Matrix Commitment with Efficient Aggregation
  A new matrix commitment scheme that allows to open any subset of the matrix entries. It is concise (costans-size commitment), aggregatable (proofs for multiple elements can be aggregated into a succinct proof), easily updatable (the old proofs and commitments can be updated) and maintainable (can update all proofs within time sublinear in the length of the committed vector).

• ROAST: Robust Asynchronous Schnorr Threshold Signatures
  Is a simple wrapper that turns a FROST threshold Schnorr signature protocol into a protocol with robust and asynchronous signing. Robust here means that for a “t-out-of-n” threshold t honest signers will be able to obtain a valid signature even in the presence of malicious signers. This work is especially important in light of recent standardization efforts for FROST with IETF, and interest from NIST for standardizing threshold cryptography.
• STAR: Secret Sharing for Private Threshold Aggregation Reporting
  [BEST PAPER AWARD] STAR improves the state of private data collection, it is easy to implement and cheap to run. At a high level the idea is that each client constructs a ciphertext by encrypting their measurement and sends a k-out-of-n secret share of the randomness used to derive the encryption key. The server learns all the measurements that are shared by at least k clients.
• Threshold Cryptography as a Service (in the Multiserver and YOSO Models)
  Design and implement a novel threshold solution for the recently introduced YOSO (You Only Speak Once) model that works particularly well in systems with dynamic participation – each party only speaks once and then can go offline. The authors show efficient protocols that allow n’ dealers, each with m secrets, to share all their secrets among a set of n shareholders.
• Server-Aided Continuous Group Key Agreement
  CGKA protocol provides E2E secure group management for groups whose properties may change mid-session (e.g., the set of members, the group name, etc.) Any such change initiates an epoch change and the creation of a new symmetric key known to epoch members but not to anyone else. Members will only transit to a new epoch if they agree with the changes to the properties of the group. This work reduces communication complexity to support larger groups.
• On the Adaptive Security of Threshold BLS Signature Scheme
  BLS threshold signatures are an important building block for randomness beacons that are inherent to asynchronous consensus. This paper proves adaptive security of BLS with a tight reduction, and states what security notion is needed for DKG.

• Batching, Aggregation, and Zero-Knowledge Proofs in Bilinear Accumulators
  The scheme allows to succinctly commit to a set of values while proving both membership and non-membership efficiently for multiple values with a constant-size batch-proof. It is faster than the state-of-the-art SNARK-based zero-knowledge batch proofs in the RSA setting.
• AntMan: Interactive Zero-Knowledge Proofs with Sublinear Communication
  Shows a construction of a designated-verifier (thus interactive) zero-knowledge proof that can prove B executions of any circuit C in communication O(B + |C|) field elements (with free addition gates), while the best prior work requires a communication of O(B|C|) field elements.
• RedShift: Transparent SNARKs from List Polynomial Commitment IOPs
  Builds a SNARK without a trusted setup with polylogarithmic proof size and verifier time, plausibly post-quantum secure.
• Succinct Zero Knowledge for Floating Point Computations
  Instead of proving the computation followed the IEEE-754 floating point standard exactly, the authors propose an alternative method that guarantees approximate correctness. Of independent interest is a new batch range proof system in standard prime order groups that does not rely on bit decomposition.
• VOProof: Efficient zkSNARKs Generation for Algebra Dummies
  This new construction helps zkSNARK-designers focus on the application-specific logics and abstracts away even more cryptographic and algebraic operations than other modern compilers.
• Feta: Efficient Threshold Designated-Verifier Zero-Knowledge Proofs
  Most prover-efficient protocols are in the designated verifier setting, where the proofs can only be verified by a designated party. The Feta protocol distributes the designated prover making it threshold.
• Proving UNSAT in Zero Knowledge
  [BEST PAPER AWARD] This work shows how to prove formula unsatisfiability in ZK in the setting where the prover holds a non-ZK proof. An immediate application is efficiently proving the safety of secret programs for audits, for example.
• Sharp: Short Relaxed Range Proofs
  The authors design short proofs to show that a value behind the commitment or encryption belongs to some public range. Compared to the state of the art Bulletproofs, the authors show significant runtime speed-up.
• Caulk: Position-Hiding Linkability for Vector Commitments with Applications to Lookup Arguments
  This paper builds a vector commitment scheme such that for a commitment C to a vector v = (v_1, … , v_N), it is possible to prove in zero-knowledge the knowledge of a secret mathematically linked to v_i without revealing i.
• Efficient Zero-Knowledge Proofs on Signed Data with Applications to Verifiable Computation on Data Streams
  A new solution to the problem of verifiable computation on data streams.
  The authors Introduce and formalize the notion of homomorphic signatures for NP and propose a generic construction.
• Succinct Zero-Knowledge Batch Proofs for Set Accumulators
  Proposes a new technique to efficiently use zkSNARKs with RSA accumulators to obtain batch membership proofs in zero-knowledge, and prove batch updates.

• Bullshark: DAG BFT Protocols Made Practical
  The first directed acyclic graph (DAG) based asynchronous Byzantine Atomic Broadcast protocol that is optimized for the common synchronous case, i.e. low latency fast-path during periods of synchrony.
• The Generals’ Scuttlebutt: Byzantine-Resilient Gossip Protocols
  Presents a way to construct a Byzantine-resilient network layer for blockchain protocols that allows to build a Byzantine-resilient gossiping protocol. The main idea is to create a stake-weighted random-graph overlay using a VRF function to determine how nodes are being connected.
• Bolt-Dumbo Transformer: Asynchronous Consensus As Fast As the Pipelined BFT
  Builds a practical optimistic asynchronous atomic broadcast with low latency.
• Constant Latency in Sleepy Consensus
  Present the first protocol to simultaneously achieve dynamic participation and constant latency by extending the classic BFT approach from static to dynamic quorum size.
• PACE: Fully Parallelizable BFT from Reproposable Byzantine Agreement
  Propose a new framework for asynchronous BFT (based on reproposable asynchronous binary agreement – RABA), implement several variations of the scheme and show that it outperforms the state of the art.
• Minotaur: Multi-Resource Blockchain Consensus
  A multi-resource blockchain consensus protocol that combines proof-of-work (PoW) and proof-of-stake (PoS), security holds as long as the cumulative adversarial power across all resources is bounded. Demonstrate the simplicity of Minotaur via implementing a full stack client in Rust.
• Dumbo-NG: Fast Asynchronous BFT Consensus with Throughput-Oblivious Latency
  Aims to solve the “remaining practical issues” for asynchronous BFT consensus, experiments demonstrate larger throughput and smaller latency compared to others.

• Foundations of Coin Mixing Services
  Constructs a coin mixing service protocol secure under composition improving on the previous work by strengthening security definitions.
• i-TiRE: Incremental Timed-Release Encryption or How to use Timed-Release Encryption on Blockchains?
  Builds a new time-release encryption protocol for blockchains (TiRE). In TiRE  a message can be encrypted to a certain epoch’s number. In this scheme, compared to previous ones, the decryption key of a certain epoch (the key is logarithmic in size) can be used to decrypt all ciphertext created for prior epochs. The construction is based on bilinear pairings.
• Empirical Analysis of EIP-1559: Transaction Fees, Waiting Time, and Consensus Security
  Experimental study on the effects of EIP-1559 shows improved users’ waiting times and overall experience, however only a small effect on gas fee levels and consensus security.
• Understanding Security Issues in the NFT Ecosystem
  The authors perform an in-depth analysis of the top 8 marketplaces (ranked by transaction volume) to discover potential issues. Among many of the issues discussed, one of the most surprising perhaps is the amount of NFTs that are actually inaccessible at the NFT’s specified URL.

• PEReDi: Privacy-Enhanced, Regulated and Distributed Central Bank Digital Currencies
  The authors define a formal model for the central-bank digital currency, capturing the regulatory compliance requirements (KYC, AML, CFT, auditing, etc.). And provide a distributed construction that realizes the model.
• Practical Settlement Bounds for Proof-of-Work Blockchains
  Give an efficient method for computing explicit upper bounds on settlement time for PoW blockchains (e.g., Bitcoin) as a function of primary system parameters: honest and adversarial computational power and a bound on network delays.
• Sleepy Channels: Bi-directional Payment Channels without Watchtowers
• GearBox: Optimal-size Shard Committees by Leveraging the Safety-Liveness Dichotomy
  Propose a novel approach to sharding: rely on a single chain that is assumed to always be life and safe, and if shards are detected to be not live, they are resampled with increased shard size and liveness tolerance.
• VRust: Automated Vulnerability Detection for Solana Smart Contracts
  Developed an automated tool to detect one of eight different vulnerability types in Solana smart contracts. The tool has been used to find some critical previously unknown vulnerabilities.
• Thora: Atomic And Privacy-Preserving Multi-Channel Updates
  This work improves upon the Bitcoin Lightning network. In the Lightning network, a collateral lock time is linear in the path length, and it requires special scripting features. In contrast, Thora requires only constant collateral and no specific scripting functionalities thus being potentially applicable more widely beyond Bitcoin.
• Platypus: A Central Bank Digital Currency with Unlinkable Transactions and Privacy-Preserving Regulation
  Adapts techniques similar to those used by Zcash to fit the account-based model and applies them to building an e-cash system.
• Zapper: Smart Contracts with Data and Identity Privacy
  [BEST PAPER AWARD] Hides both the identity of its users as well as the objects that they access within the transactions. Zapper builds a zero-knowledge processor that hides accessed objects by an oblivious Merkle tree construction.
• ENGRAFT: Enclave-guarded Raft on Byzantine Faulty Nodes
  Propose a concrete way to put RAFT protocol (resilient to crash faults, not byzantine faults) in the SGX secure enclave, while also taking into account a wide range of attack vectors on SGX. The system overall achieves security properties similar to BFT under certain assumptions on the behavior of the hardware.
• zkBridge: Trustless Cross-chain Bridges Made Practical
  An efficient cross-chain bridge with succinct proofs and small verification cost based on a novel distributed zero-knowledge proof protocol deVirgo.
• VeRSA: Verifiable Registries with Efficient Client Audits from RSA Authenticated Dictionaries
  Verifiable registries allow clients to securely access a key-value mapping maintained by an untrusted server, such as look-up a public key of a person using their public identifier (phone number or email address). The scheme is based on RSA accumulators with constant-size proofs showing that certain invariants hold (e.g., update counts).

***

Valeria Nikolaenko is a Research Partner at a16z crypto. Her research focuses on cryptography and blockchain security. She has also worked on topics such as long-range attacks in PoS consensus protocols, signature schemes, post-quantum security, and multi-party computation. She holds a PhD in Cryptography from Stanford University, and worked on the Diem blockchain as part of the core research team.

***

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.