Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

cryptography

101 missions · 14 completed

Missions

Open87Completed14All101
🏆Completed
AlgebraInformation Theory·Captain: mikedeng1

Proximity Gaps for Gabidulin Codes and ApplicationsResearch Paper

A verifier checking a large encoded object often sees only a small portion of it. Such a check needs a relation between local consistency and distance from a valid encoding. A proximity gap provides one such relation: along an affine line of received words, sufficiently many points close to a code force a common explanation for the two words defining the…

28 thms2 active usersReviewed
Combinatorics·Captain: mikedeng1

The Authentication Complexity of Byzantine ConsensusResearch Paper

Byzantine agreement (BA) asks nnn parties, each holding an input bit, to output a common bit despite up to ttt parties behaving arbitrarily, with the common output equal to the honest parties' input whenever those inputs coincide. It is a building block of state-machine replication and secure multiparty computation. Its resilience depends on the initial…

25 thms2 active usersReviewed
Quantum Information·Captain: mikedeng1

Anchoring the Security of Invariant Quantum MoneyResearch Paper

A public verifier lets anyone check a quantum banknote, while its security asks whether an efficient algorithm can turn one issued banknote into two accepted registers. For invariant quantum money, the banknote is a superposition of combinatorial objects sharing a public invariant. A classical description of one object therefore supplies useful information…

14 thms2 active usersReviewed
Complexity TheoryQuantum Information·Captain: iris

Unconditional Certified Randomness without StructureResearch Paper

Certified randomness lets a classical user check that the output of an untrusted quantum device is random: if the device passes a classical test, its output must carry entropy that nobody, including the device, could have fixed in advance. Device-independent protocols obtain this from Bell-inequality violations by several non-communicating devices;…

29 thms2 active usersReviewed
Complexity TheoryQuantum Information·Captain: iris

Quantum Advantage has Few Complexity ImplicationsResearch Paper

A proof of quantumness (PoQ) is an interactive protocol in which a classical verifier becomes convinced that its counterpart is quantum: an efficient quantum prover passes, and no efficient classical prover does. Every known construction, starting with Brakerski, Christiano, Mahadev, Vazirani and Vidick (2018), rests on a cryptographic assumption, and all…

75 thms2 active usersReviewed
Information TheoryQuantum Information·Captain: iris

Universally composable privacy amplification against quantum adversaries: two-universal hashing yields a key within 122−(S2−S0−s)/2\frac12 2^{-(S_2-S_0-s)/2}21​2−(S2​−S0​−s)/2 of idealResearch Paper

Two parties who share a partially secret string ZZZ can turn it into a short, highly secret key by privacy amplification: one of them publicly picks a hash function FFF and both compute S=F(Z)S=F(Z)S=F(Z) (Bennett, Brassard, Robert 1988). The step ends almost every quantum key distribution protocol, so the security of those protocols rests on what an adversary who holds a…

30 thms2 active usersReviewed
Information TheoryQuantum Information·Captain: iris

Quantum Key Distribution and String Oblivious Transfer in Noisy Channels: Security of String-QOT Against Bob, I(B;V∣Pass=1,C=1)⋅Pr⁡(Pass=1)≤2−ξnI(B;V\mid Pass=1,C=1)\cdot\Pr(Pass=1)\le 2^{-\xi n}I(B;V∣Pass=1,C=1)⋅Pr(Pass=1)≤2−ξnResearch Paper

Quantum key distribution lets two parties who share no secret agree on one over a public quantum channel, with security resting on physics and not on a computational assumption. The BB84 scheme of Bennett and Brassard is the standard protocol, and the question that drove the field through the 1990s was whether it stays secure when the eavesdropper applies…

26 thms2 active usersReviewed
🏆Completed
Information Theory·Captain: queelius

GBFPlus: disclosure from public occupancyResearch Paper

A data structure can hide each stored share individually while revealing their joint value through its visible layout. This distinction matters when a ledger publishes both a collection of shares and the markers identifying which cells were filled by genuine insertions. The GBFPlus protocol records cross-domain transfers in ledger attestations and uses a…

5 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: iris

Signal-Routed Two-Arm Verification: Statistical Soundness and Threshold AggregationResearch Paper

A verifier of an interactive proof or succinct argument ends with one bit, but its view carries graded evidence: how many local consistency tests passed, whether the messages were well formed. A verifier that processes many statements under a budget would like to spend little effort on rounds that look clean and more on rounds that look suspicious. Any such…

16 thms1 active userReviewed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Optimal Subcubic Byzantine Agreement with Plain PKIResearch Paper

Byzantine agreement (BA) asks nnn parties, up to ttt of which are malicious (byzantine), to agree on a common bit. It is the basic primitive behind replicated state machines and blockchains. In the synchronous model without any setup it is solvable only for t<n/3t<n/3t<n/3 (Pease–Shostak–Lamport 1980). With a public-key infrastructure (PKI), where every party can sign…

23 thms1 active userReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: Shuze Chen

Algorithms for Sparse LWE and LPN with Small SecretsResearch Paper

Learning with errors (LWE) asks to tell noisy linear equations b=As+e mod qb = As + e \bmod qb=As+emodq apart from uniformly random right-hand sides; its hardness underlies most lattice-based cryptography (Regev 2005). Sparse LWE, where every row of AAA has only kkk nonzero entries, was introduced by Jain, Lin and Saha (2024) as a source of efficient primitives, and the modulus-qqq ana…

21 thms1 active userReviewed
Theoretical Computer Science·Captain: Shuze Chen

Fresh Signatures without Fresh KeysResearch Paper

Digital signatures are transferable: a party for which a signature verifies can pass it on, and it verifies for every other party too. This is what lets authenticated Byzantine agreement and broadcast tolerate a third or more faulty parties, which pairwise authentication cannot do (Lamport, Shostak, Pease 1982; Dolev, Strong 1983). Transient faults break…

7 thms1 active userReviewed
ProbabilityTheoretical Computer Science·Captain: Shuze Chen

Minimizing Key Schedules for Key-Alternating CiphersResearch Paper

A key-alternating cipher (KAC) encrypts a block mmm of a finite abelian group GGG by alternately adding round keys and applying fixed public permutations: x0=k0−mx_0=k_0-mx0​=k0​−m, xj=kj−πj(xj−1)x_j=k_j-\pi_j(x_{j-1})xj​=kj​−πj​(xj−1​). Its provable security in the random permutation model is well understood when the t+1t+1t+1 round keys are independent and uniform (Hoang–Tessaro 2016), but real ciphers derive…

13 thms1 active userReviewed
Information TheoryProbabilityTheoretical Computer Science·Captain: Shuze Chen

The Information-Theoretic Limits of Hiding Among Decoys in the Shuffle ModelResearch Paper

Hiding a genuine secret among plausible decoys is a recurring pattern in security and privacy. A honeyword system stores a user's real password together with n−1n-1n−1 fake ones and raises an alarm when a fake one is used (Juels–Rivest 2013). A computationally unbounded adversary who decrypts a ciphertext under every key of a small key space obtains one genuine…

16 thms1 active userReviewed
Captain: mikedeng1

Optimal Early-Stopping Broadcast via Exponential Information GatheringResearch Paper

A Byzantine broadcast protocol lets a designated sender distribute an input despite parties that can lie, omit messages or send different reports to different recipients. Honest parties must eventually output a common value, and that value must equal the sender’s input when the sender is honest. These requirements give distributed protocols a common value…

30 thms1 active userReviewed
Graph TheoryInformation Theory·Captain: mikedeng1

Non-Interactive Network Sum-Secure ComputationResearch Paper

Several users may need a server to compute an aggregate while protecting the aggregate from an observer of the communication network. Here the confidential object is the sum itself. The users' individual inputs are arbitrary deterministic values; there is no prescribed probability distribution on those inputs. Bai, Guang and Wang formulate this task with…

14 thms1 active userReviewed
Markov ChainProbability·Captain: mikedeng1

Comparison is All You Need: Settling the ttt-wise independence of AESResearch Paper

A block cipher maps fixed-length plaintext blocks to ciphertext blocks using a secret key. One way to study its statistical behavior is to fix several distinct plaintexts and ask whether their ciphertexts resemble the outputs of a uniformly random permutation. This is approximate t-wise independence: it controls every test of the joint outputs at those…

21 thms1 active userReviewed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: iris

Towards Asymptotically Optimal Pseudorandom Functions: Linear-Size Circuits with Exponentially Small BiasResearch Paper

A keyed function family FK:{0,1}n→{0,1}nF_K:\{0,1\}^n\to\{0,1\}^nFK​:{0,1}n→{0,1}n is the basic object of symmetric cryptography. Two goals pull against each other: the function should be cheap to evaluate, ideally by a circuit of size O(n)O(n)O(n), and it should resist attacks running in time 2Ω(n)2^{\Omega(n)}2Ω(n). Whether both are possible at once is open in general. Dinur and Ishai settle the half that…

27 thms1 active userReviewed
Computational ComplexityMathematical LogicTheoretical Computer Science·Captain: Shuze Chen

Fine-Grained Proof Complexity for Elementary Arithmetic in Extended FregeResearch Paper

Extended Frege (EF) is the propositional proof system obtained from the textbook Frege system by adding the extension rule, which names a fresh variable as an abbreviation of a short formula (Cook–Reckhow 1979). Recent cryptographic constructions rely on EF proofs of correctness of concrete circuits, and the efficiency of those constructions is governed by…

18 thms1 active userReviewed
ProbabilityTheoretical Computer Science·Captain: Shuze Chen

Optimal Semi-Honest Information-Theoretic Secure Multi-Party Computation with Servers and ErasuresResearch Paper

Secure multi-party computation lets parties compute a joint function of private inputs while revealing nothing beyond the output. In the client–server setting, a few clients with inputs delegate the work to nnn servers that have no inputs, and an adversary may corrupt one client and a fraction α\alphaα of the servers. Oblivious transfer (OT) is the basic…

24 thms1 active userReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Near-Optimal One-Way Functions, Direct Product Hardness and Hash Functions from iO and NP versus coNPResearch Paper

A one-way function is an efficiently computable function f:{0,1}n→{0,1}mf : \{0,1\}^n \to \{0,1\}^mf:{0,1}n→{0,1}m that no efficient algorithm can invert on a random image: given y=f(x)y = f(x)y=f(x) for uniform xxx, it is hard to find any x′x'x′ with f(x′)=yf(x') = yf(x′)=y. One-way functions are the minimal assumption of private-key cryptography, and their quantitative strength, the best inversion probability an…

65 thms1 active userReviewed
Theoretical Computer Science·Captain: mikedeng1

Byzantine Broadcast in O~(n2)\widetilde{O}(n^2)O(n2) CommunicationResearch Paper

A replicated service needs a precise rule for turning one participant's proposed bit into a common decision. Byzantine broadcast asks for such a rule even when faulty participants can send inconsistent messages, omit messages, or change their behavior after being corrupted. The receiver of a message cannot infer that other parties received the same message.…

26 thms1 active userReviewed
Computational Complexity·Captain: mikedeng1

On ZLIP: Combinatorial Structures and Reduction to √n-ZSVPResearch Paper

A lattice is the set of integer combinations of a finite collection of linearly independent vectors. Its geometry can be simple while its given coordinates conceal that simplicity. The lattices considered here are Euclidean rotations of the integer grid: they have an orthonormal basis, but the input supplies an arbitrary integer change of that basis.…

26 thms1 active userReviewed
Computational ComplexityQuantum Information·Captain: mikedeng1

Relativistic Zero KnowledgeResearch Paper

A zero-knowledge proof convinces a verifier that a statement is true without revealing anything else. That "nothing else" is defined by simulation: whatever a verifier sees in a real interaction with the provers, a simulator that does not know the secret must be able to produce on its own. In multi-prover interactive proofs (MIPs), introduced by Ben-Or,…

18 thms1 active userReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

From Degree Three to Degree Two: Statistical Randomized Encodings for All FunctionsResearch Paper

A randomized encoding of a function fff replaces f(x)f(x)f(x) by a randomized value f^(x;r)\hat f(x;r)f^​(x;r) from which f(x)f(x)f(x) can be decoded and which reveals nothing else about xxx. Encodings are useful when f^\hat ff^​ is much simpler than fff, and in secure multiparty computation the relevant measure of simplicity is the algebraic degree of f^\hat ff^​ over F2\mathbb F_2F2​, jointly in the input…

31 thms1 active userReviewed
PreviousPage 4 of 5Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me