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
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 4Next

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