Proposals by Topic

Every open proposal carries one or more topic tags, StackExchange-style, alongside the paper it comes from. Click a tag below to jump to its group; each entry links back to its full write-up on the main proposals page.

Secure Messaging 9 Blockchain Consensus 6 Formal Verification 4 Quantum Random Oracle Model 4 Subversion Resistance 4 Threshold Signatures 4 Black Box Separations 3 Blockchain Bridges 3 Compressed Oracle 3 Game Theory 3 Indifferentiability 3 Leakage 3 Proof Of Work 3 Quantum Cryptography 3 Sum Of Squares 3 Anonymity 2 Collateral Management 2 Fuzzy Extractors 2 Homomorphic Encryption 2 Incentive Mechanisms 2 Learning With Errors 2 One Way Functions 2 Online Algorithms 2 Physically Uncloneable Functions 2 Searchable Encryption 2 Signature Schemes 2 Tight Reductions 2 Universal Composability 2 Verifiable Delay Functions 2 Voting And Governance 2 Watermarking 2 Average Case Hardness 1 Biometric Security 1 Blind Signatures 1 Byzantine Agreement 1 Collision Resistant Hashing 1 Commitment Schemes 1 Fine Grained Cryptography 1 Generic Group Model 1 K Wise Independent Hashing 1 Key Agreement 1 Mpc In The Head 1 Non Interactive Key Exchange 1 Obfuscation 1 Proof Of Stake 1 Quantum Information 1 Quantum Query Complexity 1 Random Oracle Model 1 Search Trees 1 Secret Sharing 1 Time Lock Puzzles 1

Secure Messaging

Protocols for asynchronous end-to-end secure communication, and the forward-secrecy, post-compromise, and metadata-privacy guarantees they offer.

• Bit-dropping on the encapsulation key – from Triple Ratchet: A Bandwidth Efficient Hybrid-Secure Signal Protocol
• A subversion-resilient post-quantum X3DH – from Guarding the Signal: Secure Messaging with Reverse Firewalls
• Firewall rerandomization under an additional encryption layer – from Guarding the Signal: Secure Messaging with Reverse Firewalls
• Modifying the Double Ratchet directly for anonymity – from Generic Anonymity Wrapper for Messaging Protocols
• Anonymity guarantees beyond message content – from Generic Anonymity Wrapper for Messaging Protocols
• Session-handling in the vulnerable-message-set methodology – from How to Compare Bandwidth Constrained Two-Party Secure Messaging Protocols
• Capturing root-key forward secrecy in the vulnerable-message-set metric – from How to Compare Bandwidth Constrained Two-Party Secure Messaging Protocols
• CGKA security against fully active adversaries – from Fair-Weather No More: Guaranteed Efficiency in Secure Group Messaging
• Per-party storage independent of group size – from Fair-Weather No More: Guaranteed Efficiency in Secure Group Messaging

Blockchain Consensus

Protocols for agreeing on a shared chain or ledger state among mutually distrusting, possibly permissionless, participants.

• Tight consistency analysis for proof-of-stake GHOST – from A Tight Analysis of GHOST Consistency
• Porting DAG-based BFT protocols to the permissionless, adaptive setting – from High-Throughput Permissionless Blockchain Consensus under Realistic Network Assumptions
• A compact, on-chain-postable certificate of ML training work – from Efficient and Proof-of-Useful-Work Friendly Local-Search for Distributed Consensus
• A seeded proof-of-work compatible with distributed samplers – from Permissionless Consensus from a Common Random String
• Sequential composition and dynamic difficulty adjustment – from Permissionless Consensus from a Common Random String
• Removing the CRS and minimizing assumptions – from Permissionless Consensus from a Common Random String

Formal Verification

Machine-checked security proofs and definitions, typically in EasyCrypt or a similar proof assistant, for concrete implementations.

• Leakage-freeness for possibly-divergent programs – from Leakage-Free Probabilistic Jasmin Programs
• Applying leakage-freeness definitions to Kyber – from Schnorr Protocol in Jasmin
• A meaningful SPV-style bridge in the paper’s formal model – from Crossing with Confidence: Formal Analysis and Model Checking of Blockchain Bridges
• Further security notions in the same formal framework – from Crossing with Confidence: Formal Analysis and Model Checking of Blockchain Bridges

Quantum Random Oracle Model

Statements set in the quantum random oracle model, where the oracle may be queried in superposition.

• Reusing the quantum heavy-queries learner for other QROM separations – from On the Impossibility of Key Agreements from Quantum Random Oracles
• Communication-complexity lower bounds for QROM key agreement – from On the Impossibility of Key Agreements from Quantum Random Oracles
• Relating the Polynomial Compatibility and Aaronson–Ambainis conjectures – from On the Impossibility of Key Agreements from Quantum Random Oracles
• A tight QROM proof from a search assumption – from Tight Lattice-Based Signatures without Trapdoors from Search LWE

Subversion Resistance

Security that survives a maliciously implemented or backdoored component, such as a subverted random function.

• Multi-stage crooked indifferentiability – from Crooked Indifferentiability of the Feistel Construction
• Broader applications and a practical construction – from Crooked Indifferentiability of the Feistel Construction
• A subversion-resilient post-quantum X3DH – from Guarding the Signal: Secure Messaging with Reverse Firewalls
• Firewall rerandomization under an additional encryption layer – from Guarding the Signal: Secure Messaging with Reverse Firewalls

Threshold Signatures

Signature schemes distributed across multiple signers under a corruption threshold.

• Accountable peg-out – from Cardinal: Bridging Bitcoin with Ownership Preservation
• Direct, specialized constructions for threshold signatures and encryption – from Proactive Secret Sharing without Erasures
• Identifiable abort for Tweed – from Tweed: Adaptively Secure Lattice-Based Two-Round Threshold Signatures
• Grand unification of MPC-in-the-Head and VOLE-in-the-Head – from On Threshold Signatures from MPC-in-the-Head

Black Box Separations

Impossibility or separation results ruling out a fully black-box construction or reduction between two primitives.

• A general non-black-box separation for PKE from OWFs – from Limits on the Power of Garbling Techniques for Public-Key Encryption
• A general theory of monolithic black-box uselessness – from Black-Box Uselessness: Composing Separations in Cryptography
• Reusing the quantum heavy-queries learner for other QROM separations – from On the Impossibility of Key Agreements from Quantum Random Oracles

Blockchain Bridges

Protocols and their formal security models for moving assets or state between separate blockchains.

• Accountable peg-out – from Cardinal: Bridging Bitcoin with Ownership Preservation
• A meaningful SPV-style bridge in the paper’s formal model – from Crossing with Confidence: Formal Analysis and Model Checking of Blockchain Bridges
• Further security notions in the same formal framework – from Crossing with Confidence: Formal Analysis and Model Checking of Blockchain Bridges

Compressed Oracle

Zhandry’s compressed-oracle method for tracking a quantum algorithm’s queries to a random function or permutation.

• Simulator-based proofs for compressed permutation oracles – from Compressed Permutation Oracles (And the Collision-Resistance of Sponge/SHA3)
• A workable decompression operator for permutations – from Towards Compressed Permutation Oracles
• Extending the top-down ansatz to correlated-output oracles – from Towards Compressed Permutation Oracles

Game Theory

Strategic behavior of rational or adversarial participants, analyzed via equilibrium or best-response reasoning.

• Collusion that harms rather than profits – from Incentivizing Geographic Diversity for Decentralized Systems
• A multi-tiered, richer strategy space – from Incentivizing Geographic Diversity for Decentralized Systems
• Modeling monetary stakes and a game-theoretic incentive analysis – from Beyond Blockchain Ballots: UC-Secure Layer-2 Voting and Governance

Indifferentiability

The indifferentiability framework for showing an idealized construction is as good as the random object it is meant to instantiate.

• Multi-stage crooked indifferentiability – from Crooked Indifferentiability of the Feistel Construction
• Broader applications and a practical construction – from Crooked Indifferentiability of the Feistel Construction
• Simulator-based proofs for compressed permutation oracles – from Compressed Permutation Oracles (And the Collision-Resistance of Sponge/SHA3)

Leakage

What an implementation or protocol execution reveals beyond its specified output, and how to define or eliminate it.

• Leakage from tree rearrangement – from Optimizing Trees for Static Searchable Encryption
• Leakage-freeness for possibly-divergent programs – from Leakage-Free Probabilistic Jasmin Programs
• Applying leakage-freeness definitions to Kyber – from Schnorr Protocol in Jasmin

Proof Of Work

Consensus and incentive mechanisms built on costly, verifiable computational work.

• A compact, on-chain-postable certificate of ML training work – from Efficient and Proof-of-Useful-Work Friendly Local-Search for Distributed Consensus
• A seeded proof-of-work compatible with distributed samplers – from Permissionless Consensus from a Common Random String
• Sequential composition and dynamic difficulty adjustment – from Permissionless Consensus from a Common Random String

Quantum Cryptography

General security notions, constructions, and separations involving quantum adversaries or quantum information.

• A meaningful collapse-binding property for non-interactive commitments – from How to Base Security on the Perfect/Statistical Binding Property of Quantum Bit Commitment?
• Post-quantum security of permutation-based hashing – from Towards Compressed Permutation Oracles
• Post-quantum minimality for other primitives – from A Note on the Minimality of One-Way Functions in Post-Quantum Cryptography

Sum Of Squares

The sum-of-squares semidefinite-programming hierarchy, and its use for rounding algorithms and hardness arguments.

• Strengthening and transplanting the sum-of-squares entanglement-detection technique – from Quantum Entanglement, Sum of Squares, and the Log Rank Conjecture
• A general theory of computational hardness – from The Complexity of Public-Key Cryptography
• Classifying hard distributions of low-degree polynomials – from Sum-of-Squares Meets Program Obfuscation, Revisited

Anonymity

Hiding a message’s, party’s, or transaction’s identity or relationships, beyond hiding its content alone.

• Modifying the Double Ratchet directly for anonymity – from Generic Anonymity Wrapper for Messaging Protocols
• Anonymity guarantees beyond message content – from Generic Anonymity Wrapper for Messaging Protocols

Collateral Management

Policies for sizing and maintaining the collateral or liquidity backing a stream of transactions.

• Competitive collateral policies under condition-dependent settlement – from Competitive Policies for Online Collateral Maintenance
• Adaptive, dynamic wallet and collateral policies – from Competitive Policies for Online Collateral Maintenance

Fuzzy Extractors

Extracting a stable cryptographic key from a noisy secret such as a biometric reading or a PUF response.

• Generalizing beyond the iris, and beyond the lab – from Fuzzy Extractors are Practical: Cryptographic Strength Key Derivation from the Iris
• ζ-sampling for PUF-based fuzzy extractors – from Fuzzy Extractors are Practical: Cryptographic Strength Key Derivation from the Iris

Homomorphic Encryption

Computing on encrypted data, and the compression, packing, and bootstrapping techniques that make it practical.

• Rescaling before truncation for BGV, BFV, and CKKS – from Downlink (T)FHE Ciphertexts Compression
• Compression for partially-filled RLWE ciphertexts – from Downlink (T)FHE Ciphertexts Compression

Incentive Mechanisms

Reward and penalty designs meant to make honest behavior the rational choice for participants.

• Collusion that harms rather than profits – from Incentivizing Geographic Diversity for Decentralized Systems
• A multi-tiered, richer strategy space – from Incentivizing Geographic Diversity for Decentralized Systems

Learning With Errors

Ring- or Module-LWE-specific hardness questions and the constructions built on them.

• Identifiable abort for Tweed – from Tweed: Adaptively Secure Lattice-Based Two-Round Threshold Signatures
• Bit-dropping on the encapsulation key – from Triple Ratchet: A Bandwidth Efficient Hybrid-Secure Signal Protocol

One Way Functions

The minimal cryptographic assumption, and what it does or does not imply in a black-box sense.

• A general non-black-box separation for PKE from OWFs – from Limits on the Power of Garbling Techniques for Public-Key Encryption
• Post-quantum minimality for other primitives – from A Note on the Minimality of One-Way Functions in Post-Quantum Cryptography

Online Algorithms

Algorithms that commit to each decision as it arrives, analyzed by their competitive ratio against an optimal offline policy.

• Competitive collateral policies under condition-dependent settlement – from Competitive Policies for Online Collateral Maintenance
• Adaptive, dynamic wallet and collateral policies – from Competitive Policies for Online Collateral Maintenance

Physically Uncloneable Functions

Protocols built from hardware tokens whose physical structure cannot be efficiently cloned.

• ζ-sampling for PUF-based fuzzy extractors – from Fuzzy Extractors are Practical: Cryptographic Strength Key Derivation from the Iris
• Adaptive corruptions for everlasting UC commitment from malicious PUFs – from Everlasting UC Commitments from Fully Malicious PUFs

Searchable Encryption

Encrypted search schemes and the tradeoffs among their efficiency, leakage, and index structure.

• Other matching heuristics for tree construction – from Optimizing Trees for Static Searchable Encryption
• Leakage from tree rearrangement – from Optimizing Trees for Static Searchable Encryption

Signature Schemes

Digital signature constructions and the tightness of their security reductions.

• A tight QROM proof from a search assumption – from Tight Lattice-Based Signatures without Trapdoors from Search LWE
• Extending tightness to the multi-user setting – from Tight Lattice-Based Signatures without Trapdoors from Search LWE

Tight Reductions

Security reductions whose loss is a constant rather than growing with the adversary’s resources.

• A tight QROM proof from a search assumption – from Tight Lattice-Based Signatures without Trapdoors from Search LWE
• Extending tightness to the multi-user setting – from Tight Lattice-Based Signatures without Trapdoors from Search LWE

Universal Composability

Security definitions and realizations in the UC framework, including under adaptive or malicious setup corruption.

• Adaptive corruptions for everlasting UC commitment from malicious PUFs – from Everlasting UC Commitments from Fully Malicious PUFs
• UC realizations with many bulletin-board managers – from Beyond Blockchain Ballots: UC-Secure Layer-2 Voting and Governance

Verifiable Delay Functions

Functions that take a prescribed amount of sequential time to evaluate but are quickly verifiable, and their (un)computational uniqueness.

• Escaping the perfect-uniqueness impossibility for VDFs – from Can Verifiable Delay Functions be Based on Random Oracles?
• Extending QROM time-lock-puzzle impossibility to VDFs – from On the (Im)possibility of Time-Lock Puzzles in the Quantum Random Oracle Model

Voting And Governance

Protocols for casting, tallying, or governing collective decisions with strong composable security guarantees.

• UC realizations with many bulletin-board managers – from Beyond Blockchain Ballots: UC-Secure Layer-2 Voting and Governance
• Modeling monetary stakes and a game-theoretic incentive analysis – from Beyond Blockchain Ballots: UC-Secure Layer-2 Voting and Governance

Watermarking

Embedding a detectable, ideally robust and hard-to-remove, mark into a model’s or program’s output.

• The theoretical limits of publicly-detectable watermarking – from Publicly-Detectable Watermarking for Language Models
• New robustness notions for publicly-detectable watermarks – from Publicly-Detectable Watermarking for Language Models

Average Case Hardness

Hardness of a computational problem on a natural random input distribution, as opposed to worst-case hardness.

• A general theory of computational hardness – from The Complexity of Public-Key Cryptography

Biometric Security

Security and reliability of key derivation from a specific biometric modality, and how it holds up outside curated lab conditions.

• Generalizing beyond the iris, and beyond the lab – from Fuzzy Extractors are Practical: Cryptographic Strength Key Derivation from the Iris

Blind Signatures

Signature schemes that let a signer sign a message without seeing it, and round-complexity lower bounds for them.

• Bypassing the round-optimality barrier with a non-group assumption – from On the Impossibility of Round-Optimal Pairing-Free Blind Signatures in the ROM

Byzantine Agreement

Consensus protocols tolerating malicious parties, and their resilience bounds.

• Porting DAG-based BFT protocols to the permissionless, adaptive setting – from High-Throughput Permissionless Blockchain Consensus under Realistic Network Assumptions

Collision Resistant Hashing

Collision-resistant hash functions as a primitive, and their relations to other assumptions.

• Post-quantum security of permutation-based hashing – from Towards Compressed Permutation Oracles

Commitment Schemes

Commitment protocols and their binding and hiding properties, including in composable or setup-free settings.

• A meaningful collapse-binding property for non-interactive commitments – from How to Base Security on the Perfect/Statistical Binding Property of Quantum Bit Commitment?

Fine Grained Cryptography

Cryptographic constructions based on worst-case, fine-grained hardness assumptions rather than average-case ones.

• 3-party NIKE from non-pairing algebraic assumptions – from Fine-Grained Non-Interactive Key-Exchange: Constructions and Lower Bounds

Generic Group Model

Statements set in a generic group model (Shoup’s or Maurer’s), where the adversary accesses group operations only through an oracle.

• Bypassing the round-optimality barrier with a non-group assumption – from On the Impossibility of Round-Optimal Pairing-Free Blind Signatures in the ROM

K Wise Independent Hashing

Hash function families whose outputs on any k inputs look independent, and the key-size and locality trade-offs such families admit.

• Unifying bit-local and word-local hash constructions – from Locally Computable High Independence Hashing

Key Agreement

Two-party protocols for agreeing on a shared secret, and their black-box (im)possibility from weaker primitives.

• Communication-complexity lower bounds for QROM key agreement – from On the Impossibility of Key Agreements from Quantum Random Oracles

Mpc In The Head

Signature and proof constructions built by simulating a multi-party protocol’s execution in one’s head, and the frameworks unifying them.

• Grand unification of MPC-in-the-Head and VOLE-in-the-Head – from On Threshold Signatures from MPC-in-the-Head

Non Interactive Key Exchange

Multi-party key exchange with no interaction, typically analyzed in a generic group model.

• 3-party NIKE from non-pairing algebraic assumptions – from Fine-Grained Non-Interactive Key-Exchange: Constructions and Lower Bounds

Obfuscation

Techniques and hardness assumptions for program obfuscation, including candidates built from low-degree polynomials.

• Classifying hard distributions of low-degree polynomials – from Sum-of-Squares Meets Program Obfuscation, Revisited

Proof Of Stake

Consensus protocols where influence over block production is weighted by stake rather than computational work.

• Tight consistency analysis for proof-of-stake GHOST – from A Tight Analysis of GHOST Consistency

Quantum Information

Entanglement, separability, and other problems studied within quantum information theory.

• Strengthening and transplanting the sum-of-squares entanglement-detection technique – from Quantum Entanglement, Sum of Squares, and the Log Rank Conjecture

Quantum Query Complexity

Upper and lower bounds on the number of quantum queries needed against an oracle-based primitive.

• Relating the Polynomial Compatibility and Aaronson–Ambainis conjectures – from On the Impossibility of Key Agreements from Quantum Random Oracles

Random Oracle Model

Statements set in the classical (non-quantum) random oracle model.

• Escaping the perfect-uniqueness impossibility for VDFs – from Can Verifiable Delay Functions be Based on Random Oracles?

Search Trees

Optimal construction of search trees over structured query distributions.

• Other matching heuristics for tree construction – from Optimizing Trees for Static Searchable Encryption

Secret Sharing

Schemes splitting a secret among parties so that only qualified subsets can reconstruct it, including under proactive refresh.

• Direct, specialized constructions for threshold signatures and encryption – from Proactive Secret Sharing without Erasures

Time Lock Puzzles

Puzzles that hide a value for a controlled, only sequentially reducible, amount of time.

• Extending QROM time-lock-puzzle impossibility to VDFs – from On the (Im)possibility of Time-Lock Puzzles in the Quantum Random Oracle Model