Function-hiding functional commitment schemes allow one party to commit to a private function f and later prove f(x)=y for public x and y without revealing additional information about the function. We construct efficient function-hiding functional commitment schemes for arithmetic circuits of bounded size that achieve proof sizes below 1.6 kBâover an order of magnitude smaller than previous constructionsâwhile simultaneously reducing proving and verification times. We achieve these results by introducing a novel information-theoretic interactive proof system called Polynomial Interactive Oracle Proofs with Randomized Indexer (rPHPs). By compiling rPHPs with commit-and-prove zkSNARKs, we are able to leverage relaxed zero-knowledge notions for our building blocks. This approach eliminates the overhead of strict privacy requirements of prior work, directly translating into improved efficiency in both communication and computation.
Open access
Cryptography and Data Security
Complexity and Algorithms in Graphs
Physical Unclonable Functions (PUFs) and Hardware Security
Ilango (FOCS 2025) invented effectively zero-knowledge proofs, a new variant of zero-knowledge. We reformulate it in the language of logic and give simple proofs (under the same assumptions as Ilango (FOCS 2025)) of its existence and of the key property defined in Ilango (FOCS 2025) that it is "indistinguishable from true" (that property is in Ilango (FOCS 2025) a part of the definition of the prover, not its consequence). Using the theory of proof complexity generators we show that the concept can be turned it into a genuinely zero-knowledge proofs, assuming a conjecture from the theory about the existence of a hard generator and allowing the parties to share a common random string.
Rohan Goyal, Venkatesan Guruswami, Yihang Sun, Mary Wootters
Proximity gaps are a property of error correcting codes that arise in the study of Interactive Oracle Proofs (IOPs) and Succinct Non-interactive Arguments of Zero Knowledge (SNARKs). Recent work of Goyal and Guruswami has established near-optimal proximity gaps for many families of codes, including subspace design codes, as well as random ensembles like random linear codes, Reed-Solomon codes with random evaluation points, and Gallager's ensemble of LDPC codes (Goyal & Guruswami, 2025). However, the parameters for these latter randomized ensembles are worse than the parameters for subspace design codes, and degrade as the degree ell increases. In this work, we obtain improved proximity gaps for random ensembles of codes, including random linear codes, Reed-Solomon codes with random evaluation points, and Gallager's ensemble. Quantitatively, our results for these random ensembles match the results that Goyal and Guruswami attained for subspace design codes. In fact, our techniques are a black-box transference from subspace design codes: any progress on subspace design codes will automatically lead to analogous progress for these random ensembles. To obtain our results, we extend the Local Coordinate-wise Linear (LCL) property framework developed by Levi, Mosheiff, and Shagrithaya and by Brakensiek, Chen, Dhar, and Zhang to a \textit{row-span constrained} version (Levi, Mosheiff & Shagrithaya, 2025; Brakensiek, Chen, Dhar & Zhang, 2025). This allows us to cast \textit{curve-decodability} -- a property that implies proximity gaps -- directly as a row-span constrained LCL property, and make use of that machinery. In contrast, because curve-decodability is not obviously a vanilla LCL property, prior work had worked with a proxy property instead, leading to the aforementioned parameter losses.
We present Aggios, a scalable and privacy preserving proxy voting system designed for frequent and large-scale elections such as Decentralized Autonomous Organizations (DAO), when storing votes on the bulletin board is expensive. To this end, Aggios introduces âaggregatorsâ: entities to which voters delegate their votes, and who then post their batched proofs on the public ledger. Aggios achieves strong integrity guarantees: only authorized voters can vote, votes are counted correctly, voters are assured their vote is counted.
We study distributed zero-knowledge proofs, introduced by Bick, Kol, and Oshman (SODA 2022). While distributed interactive proofs have advanced rapidly, general-purpose techniques for distributed zero-knowledge remain limited and mostly problem-specific. We address this gap by introducing distributed statistical zero-knowledge, requiring that each node's view be simulatable within negligible statistical distance, and by lifting the classical Sumcheck protocol (Lund, Fortnow, Karloff, and Nisan, FOCS 1990) into a modular primitive for distributed zero-knowledge proofs. Our main contribution is a distributed zero-knowledge implementation of Sumcheck. Given oracle access to a polynomial F over a finite field $\mathbb{F}$ with N variables, we design a protocol verifying claims of the form $\sum_{x\in\mathbb{F}} F(x)=a$ using $O(N)$ rounds of $O(\log |\mathbb{F}|)$-bit messages, while achieving statistical zero-knowledge and small soundness error. We apply this primitive to two problems. For non-k-colorability, we obtain an $O(n)$-round distributed statistical zero-knowledge proof deciding whether a graph is not k-colorable, for any constant k, using $O(log^{1+o(1)} n)$-bit messages. This is the first nontrivial distributed interactive proof for this problem, even without zero-knowledge guarantees. For Subgraph Counting, we obtain an $O(k \log n)$-round, $O(k \log n)$-bit distributed statistical zero-knowledge proof for counting copies of a given k-node pattern, improving previous distributed interactive proofs while additionally providing statistical zero-knowledge. Finally, we show that additional round compression of Sumcheck is problem-dependent: for non-3-colorability on constant-degree graphs, we prove a lower bound excluding $o(n/\log n)$ rounds under polynomial-time local computation.
Self-contained, Mathlib-free Lean 4 library implementing the Rei-AIOS D-FUMT8 eight-valued logic {TRUE, FALSE, BOTH, NEITHER, INFINITY, ZERO, FLOWING, SELF}. 29 zero-sorry theorems via decide / native_decide on the finite type. Three classical-logic bridges (toBool, toTernary, asProp with Decidable instance). Builds in ~5 seconds on a fresh clone â two orders of magnitude faster than Mathlib-dependent projects. Apache-2.0 licensed at github.com/fc0web/lean-d-fumt8 (v1.0.0). Library-only strategy (purely additive, no kernel changes, full Mathlib compatibility). Completes the proof-theoretic anchor for D-FUMT8, complementing the Schnorr-randomness ceiling (Paper 69) and the QuTiP quantum-operational floor (Papers 75â76). To our knowledge, this is the first publicly released eight-valued-logic library for Lean 4.
We prove that for planted k-SAT instances with k >= 7 at clause density alpha/alpha_s >= 0.21, a positive fraction of variables are frozen directly in the planted model---without requiring transfer from the random model via quiet planting. The expected number of "support clauses" per variable (clauses in which that variable is the unique satisfying literal) exceeds 1 at remarkably low density: alpha/alpha_s ~ 0.20 for k = 7, compared to the random-model freezing threshold at alpha_f/alpha_s ~ 0.90. We prove that the resulting frozen-core structure implies topological disconnection of the solution subgraph across cluster boundaries, with a cycle-robustness argument showing that short cycles in the factor graph cannot quench the supercritical repair cascade. As an immediate corollary, the Hilbert space spanned by satisfying assignments decomposes into orthogonal sectors preserved by any unitary generated by the adjacency matrix---blocking quantum walks, QAOA at all depths, and quantum annealing. We construct a post-quantum commitment scheme whose binding property reduces to the hardness of solving planted k-SAT, provide formal proofs of completeness, soundness, and zero-knowledge, and derive a digital signature scheme with existential unforgeability via the Fiat-Shamir transform. We present a six-vector quantum attack analysis with proved barriers against five algorithmic families. We give concrete parameter recommendations at NIST security levels 1, 3, and 5, and position the scheme within the landscape of SAT-based and CSP-based cryptographic constructions. We prove that the Grover query complexity for breaking the binding property is Omega(2^{fn/2}); empirical cryptanalysis of Glucose and MiniSat CDCL solvers on our exact distribution yields a classical attack cost of 2^{0.234n} operations, enabling concrete parameter selection at NIST security levels 1, 3, and 5. Empirical validation across 100 random seeds at n = 16 confirms complete cluster isolation at every instance tested.
We present COMET-MPC (Commitment-Oriented Multi-Party Computation with Equality Testing), a novel MPC framework that fundamentally reimagines multi-party computation as a commitment verification problem rather than a traditional secret-sharing problem. COMET-MPC achieves dealerless, one-round setup by reducing all MPC coordination tasksâinput binding, consistency verification, and replay preventionâto homomorphic equality testing over elliptic-curve commitments. Unlike classical MPC protocols (Shamirâs secret sharing, FROST) that require multi-round polynomial verification or interactive zero-knowledge proofs, COMET-MPC performs verification through a single algebraic check: testing whether a group element equals the identity. This zero-detection paradigm exploits the structural identity between EC-Pedersen commitments and EC-ElGamal ciphertexts, enabling decrypt-free verification with perfect correctness and computational hiding under the Decisional Diffie-Hellman (DDH) assumption. We provide complete algorithmic specifications, formal security proofs including binding, hiding, replay resistance, and a rigorous security level analysis demonstrating â 128-bit security for standard 256-bit elliptic curves. COMET-MPC is particularly suited for real-world ledger systems, authentication protocols, confidential databases, and privacy-preserving regulatory compliance where minimal interaction, minimal trust, and minimal leakage are paramount.
Dense retrieval services increasingly underpin semantic search, recommendation, and retrieval-augmented generation, yet clients typically receive only a top-$k$ list with no auditable evidence of how it was produced. We present V3DB, a verifiable, versioned vector-search service that enables audit-on-demand correctness checks for approximate nearest-neighbour (ANN) retrieval executed by a potentially untrusted service provider. V3DB commits to each corpus snapshot and standardises an IVF-PQ search pipeline into a fixed-shape, five-step query semantics. Given a public snapshot commitment and a query embedding, the service returns the top-$k$ payloads and, when challenged, produces a succinct zero-knowledge proof that the output is exactly the result of executing the published semantics on the committed snapshot -- without revealing the embedding corpus or private index contents. To make proving practical, V3DB avoids costly in-circuit sorting and random access by combining multiset equality/inclusion checks with lightweight boundary conditions. Our prototype implementation based on Plonky2 achieves up to $22\times$ faster proving and up to $40\%$ lower peak memory consumption than the circuit-only baseline, with millisecond-level verification time. Github Repo at https://github.com/TabibitoQZP/zk-IVF-PQ.
Stochastic Bit-Parallel Maximum Clique Solver (1024-bit Virtual Register) We introduce a stochastic bit-parallel solver for the Maximum Clique Problem (MCP) based on a 1024-bit virtual register architecture implemented as 16 contiguous uint64_t words in standard C++17, ensuring full portability across 64-bit platforms (x86-64, ARM, RISC-V). Core operationsâcandidate intersection, population count, and leading-zero detectionâexecute in exactly 16 instructions per 1024-bit operation. The solver integrates three key components: (i) a co-neighborhood heuristic that identifies high-coreness nodes via O(NÂČ) pairwise popcount over 1024-bit adjacency rows; (ii) a stochastic swarm of independent worker threads; and (iii) greedy clique expansion through iterative bitwise intersection. Exact branch-and-bound solvers (MaxCliqueDyn, MCQ) become computationally intractable on dense random graphs such as G(1024, 0.5), where chromatic coloring bounds lose effectiveness and the search tree grows exponentially, requiring hours of computation on commodity hardware. The proposed method operates specifically within this hard regime, achieving 100% recovery of all 28 planted clique vertices in 153 millisecondsâa setting where exact state-of-the-art methods cannot remain competitive regardless of hardware scaling. Experimental validation was performed on a Qualcomm Snapdragon 8 Gen 2 (8-core ARM) and independently reproduced on Linux x86-64 server hardware. The solver requires no cloud infrastructure and no GPU acceleration. STATEMENT OF PRIOR ART AND LICENSE TERMS (PolyForm Noncommercial Framework) 1. Statement of Prior Art This document constitutes a public disclosure of the stochastic bit-parallel Maximum Clique methodology, including its virtual register architecture, heuristic structure, and execution model.The mathematical and algorithmic concepts are released solely to establish Prior Art and prevent third-party patent claims under 35 U.S.C. § 102 and international equivalents. 2. Software License While the conceptual methods are disclosed defensively, all source code, implementations, binaries, and hardware realizations are not in the public domain and are licensed under the PolyForm Noncommercial License 1.0.0. Permitted (Non-Commercial)âą Academic research and experimentationâą Peer review and independent verificationâą Educational and non-profit useâą Non-commercial open-source research implementations Condition: Publications must cite the canonical DOI or primary reference. Prohibited (Commercial)âą Integration into proprietary software or hardwareâą Deployment in commercial systems, services, or productsâą Use in paid tools, platforms, or consulting workflowsâą Sublicensing or sale of the code or derivatives 3. Commercial Licensing Any commercial use requires explicit written authorization from the author. 4. No Code-Size Threshold (No De Minimis) The PolyForm Noncommercial License imposes no exemptions based on code length, fragment size, or proportion of reuse. Any useâpartial or completeâremains fully subject to the license. 5. Anti-Snippet Laundering and Anti-Circumvention Extraction, paraphrasing, refactoring, translation, or reimplementation of any algorithmic componentâincluding bit-parallel structures, heuristics, or execution logicâshall be considered derivative use.Attempts to evade the license through minimal reuse, language changes, functional replication, or modular embedding do not limit its applicability.This interpretation aligns with international good-faith and anti-abuse principles. 6. Presumption of Derivation Any system exhibiting substantial functional or structural similarity, developed after exposure to this work, shall be presumed derivative.The burden of proof for independent creation rests on the alleged infringing party. 7. Knowledge Contamination Exposure to the code, documentation, or technical description constitutes knowledge contamination.Subsequent implementations by exposed parties are not considered clean-room unless supported by contemporaneous evidence of prior independent development. 8. Waiver of Jury Trial To the fullest extent permitted by law, all parties waive the right to a jury trial in disputes arising from this license or related use. 9. Severability and Survival If any provision is deemed unenforceable, the remaining provisions remain in effect.The following provisions survive termination: license scope, noncommercial restrictions, anti-circumvention, presumption of derivation, knowledge contamination, intellectual property ownership, waiver of jury trial, and remedies. 10. Academic Use and Research Freedom The author expressly encourages academic and scientific use of this work. The following activities are permitted on a non-commercial basis: âą Research, benchmarking, and experimental validationâą Publication of scientific analyses, comparisons, or extensionsâą Use in university courses, laboratories, and academic projectsâą Inclusion in research solver portfoliosâą Independent theoretical or empirical study All academic use must include proper citation to the original work.
Suvradip Chakraborty, James Hulett, Dakshita Khurana, Kabir Tomer
A recent breakthrough [Hirahara and Nanashima, STOC'2024] established that if $\mathsf{NP} \not \subseteq \mathsf{ioP/poly}$, the existence of zero-knowledge with negligible errors for $\mathsf{NP}$ implies the existence of one-way functions (OWFs). In this work, we obtain a characterization of one-way functions from the worst-case complexity of zero-knowledge {\em in the high-error regime}. We say that a zero-knowledge argument is {\em non-trivial} if the sum of its completeness, soundness and zero-knowledge errors is bounded away from $1$. Our results are as follows, assuming $\mathsf{NP} \not \subseteq \mathsf{ioP/poly}$: 1. {\em Non-trivial} Non-Interactive ZK (NIZK) arguments for $\mathsf{NP}$ imply the existence of OWFs. Using known amplification techniques, this result also provides an unconditional transformation from weak to standard NIZK proofs for all meaningful error parameters. 2. We also generalize to the interactive setting: {\em Non-trivial} constant-round public-coin zero-knowledge arguments for $\mathsf{NP}$ imply the existence of OWFs, and therefore also (standard) four-message zero-knowledge arguments for $\mathsf{NP}$. Prior to this work, one-way functions could be obtained from NIZKs that had constant zero-knowledge error $Δ_{zk}$ and soundness error $Δ_{s}$ satisfying $Δ_{zk} + \sqrt{Δ_{s}} < 1$ [Chakraborty, Hulett and Khurana, CRYPTO'2025]. However, the regime where $Δ_{zk} + \sqrt{Δ_{s}} \geq 1$ remained open. This work closes the gap, and obtains new implications in the interactive setting. Our results and techniques could be useful stepping stones in the quest to construct one-way functions from worst-case hardness.
We study the implications of the existence of weak Zero-Knowledge (ZK) protocols for worst-case hard languages. These are protocols that have completeness, soundness, and zero-knowledge errors (denoted $Δ_c$, $Δ_s$, and $Δ_z$, respectively) that might not be negligible. Under the assumption that there are worst-case hard languages in NP, we show the following: 1. If all languages in NP have NIZK proofs or arguments satisfying $ Δ_c+Δ_s+ Δ_z < 1 $, then One-Way Functions (OWFs) exist. This covers all possible non-trivial values for these error rates. It additionally implies that if all languages in NP have such NIZK proofs and $Δ_c$ is negligible, then they also have NIZK proofs where all errors are negligible. Previously, these results were known under the more restrictive condition $ Δ_c+\sqrt{Δ_s}+Δ_z < 1 $ [Chakraborty et al., CRYPTO 2025]. 2. If all languages in NP have $k$-round public-coin ZK proofs or arguments satisfying $ Δ_c+Δ_s+(2k-1).Δ_z < 1 $, then OWFs exist. 3. If, for some constant $k$, all languages in NP have $k$-round public-coin ZK proofs or arguments satisfying $ Δ_c+Δ_s+k.Δ_z < 1 $, then infinitely-often OWFs exist.
This is an extended appendix for an unpublished paper. It covers the use of a framework defined in that paper to prove the zero-knowledge of a few zero-knowledge proofs. The first example, covering 3-colourability, is justified and explained. The second, covering boolean circuit satisfiability, is simply given.
We show that a decidable promise problem has a non-interactive statistical zero-knowledge proof system if and only if it is randomly reducible via an honest polynomial-time reduction to a promise problem for Kolmogorov-random strings, with a superlogarithmic additive approximation term. This extends work by Saks and Santhanam (CCC 2022). (Saks and Santhanam showed that promise problems that can be reduced in this way to such an approximation of the Kolmogorov-random strings have (possibly interactive) zero-knowledge proof systems, and they did not address the converse implication.) We build on this to give new characterizations of Statistical Zero Knowledge SZK , as well as the related classes NISZK L and SZK L .
Modern cryptographic primitives have evolved from supporting basic to more advanced functionalities, and such schemes are now getting more practical. In this thesis, we identify and rectify some limitations of such cryptographic constructions and their proofs of security. Specifically, we work with functional encryption, secure aggregation, and threshold signature schemes, and observe key functional or security limitations in prior work. Our first focus is functional encryption (FE), which enables function evaluation on encrypted messages using a functional secret key. A different primitive named function-revealing encryption (FRE) allows one to compute a fixed function of the underlying messages using their ciphertexts only. We give formal definitions and construct an inner-product FRE scheme. We also analyze the relationship between FE and FRE. Our second contribution considers secure aggregation, a classic problem that has numerous applications in privacy preserving machine learning. Secure aggregation lets many clients contribute data for aggregation without revealing their individual data. Existing practical protocols either have multiple rounds of interaction between clients and the server or rely on heavyweight cryptographic primitives. We build a non-interactive secure aggregation protocol using a novel combination of inner-product FE and a fully-linear probabilistically checkable proof (FLPCP) system. For this protocol, we use an existing FLPCP system [BBCGIâ19] that we prove satisfies soundness and zero-knowledge properties even when reused for multiple proof instances. Finally, we address a pressing open question: achieving fully adaptive security for the Sparkle+ [CKMâ23] threshold signature scheme. Threshold schemes require t signers to provide partial signatures to form a valid one. Fully adaptive security prevents adversaries from forging signatures even when corrupting up to t-1 signers. While Sparkle+ is secure against static corruption and a limited number of adaptive corruptions, a previous proof of fully adaptive security was shown to be incorrect. We propose a novel hardness assumption under which Sparkle+ satisfies this notion with a tight reduction. We establish hardness of this assumption in the elliptic-curve generic-group model. Our contributions close important gaps in prior work and push advanced cryptographic primitives closer to practice.
Secure Multi-Party Computation (MPC) is a widely acknowledged framework enabling the design of multi-party protocols that preserve the privacy of parties' inputs while ensuring the correct evaluation of the desired functionality. Crucially, these security guarantees should hold even in the presence of external entities who are empowered with some adversarial capabilities, such as controlling the communication channels used throughout the protocol run or forcing a subset of the parties to behave arbitrarily (so-called ``malicious" or ``byzantine" corruptions). Concretely, a user can instantiate secure MPC protocols on a device to carry out computations involving sensitive information with other untrusted parties. Despite capturing very general classes of real-world threats, one limitation of ``traditional" MPC lies in assuming at least one ``honest" party who, throughout the protocol run, behaves exactly as per the theoretical specification of the protocol itself. For several practical settings this may be unrealistic, as the devices used to run the protocol are themselves exposed to a plethora of threats, such as attacks on software or hardware components. Moreover, the security guarantees provided by secure MPC could be voided if a protocol is found to be faulty, be it from cryptographic assumptions falling short or from an incorrect formalization of the protocol itself. In this composition, we explore more expressive frameworks that enable the design of secure MPC protocols and cryptographic primitives even in the presence of untrusted devices. We first consider cryptographic reverse firewalls: lightweight devices that sanitize a party's traffic while preserving the correctness of the protocol. These objects were originally introduced by Mironov and Stephens-Davidowitz (EUROCRYPT'15) and later embedded in the framework of subversion-resilient Universal Composability (srUC) due to Chakraborty et al. (EUROCRYPT'22). Under the srUC framework, it is possible to design protocols that provide meaningful security guarantees even if the devices of honest parties have been tampered with in an undetectable manner with the goal of exfiltrating information (so-called ``specious subversion attacks"). In particular, we focus on the design of protocols for Password-Authenticated Key Exchange (PAKE): a cryptographic primitive that enables two parties to mutually authenticate by establishing a shared high-entropy key leveraging exclusively some (possibly low-entropy) pre-shared password. (1) Our first contribution focuses on sanitizing the PAKE protocol from Oblivious Transfer (OT) due to Canetti et al. (PKC'12). For that, we design and instantiate novel cryptographic primitives with sanitation-friendly properties that may be of independent interest, including sanitizable variants of oblivious transfer, dual-mode cryptosystems, and signature schemes. As an additional contribution, we formalize the unauthenticated setting in the srUC framework by extending the framework of split-authentication due to Barak et al. (CRYPTO'05, JoC'07). This is the first PAKE protocol ever designed in the srUC framework. (2) Our second contribution consists of sanitizing the PAKE protocol from trapdoor smooth-projective hashing due to Benhamouda and Pointcheval (CRYPTO'13). The sanitation requires non-trivial modifications to the original protocol, whose security relies on a CCA-secure encryption scheme - an inherently non-malleable primitive. Along the way, we bring advances to the field of malleable smooth-projective hash functions, originally introduced by Chen et al. (ASIACRYPT'16), and coin the notion of malleable trapdoor smooth-projective hashing. Our resulting PAKE protocol has better communication and round complexity compared to the aforementioned PAKE-from-OT. We then shift our attention to t-out-of-n robust combiners: constructions that take as input n candidate instantiations of some cryptographic primitive to securely realize the same primitive, as long as at least t of the candidates are secure. These objects were first formalized by Harnik et al. (EUROCRYPT'05), where robustness is characterized by explicitly forbidding combiners from re-implementing the desired primitive from scratch. Here, we focus on Non-Interactive Zero-Knowledge (NIZK): a cryptographic primitive that allows a prover to convince a verifier of the veracity of some NP-statement by using a single message (commonly referred to as a ``proof"). (3) Our third contribution provides a comprehensive characterization of robust combiners for NIZK. We show the first formal definition of these objects, and prove that no robust NIZK combiner exists for t †n/2 unless the polynomial hierarchy collapses. To complement our negative results, we provide three incomparable constructions: (i) A black-box combiner for {\em homomorphic} NP languages, where n,t are polynomial and t > n/2; (ii) A non-black-box combiner for any NP language, where n,t are constant and t > n/2; (iii) A non-black-box combiner for any NP language, where n,t are polynomial and t > 2n/3.
Secret Sharing Schemes are cryptographic tools for securely distributing a secret among participants, ensuring that only authorized subsets can reconstruct it while unauthorized coalitions cannot, a property known as information-theoretic security. A key challenge in designing such schemes is reducing share size, which impacts efficiency and scalability in distributed systems. This thesis studies this problem in structured access structures. After reviewing threshold schemes and their ideality, it focuses on weighted threshold access structures, analyzing classical constructions and methods, including approximation techniques, to reduce share size. Their relevance is illustrated in Proof-of-Stake blockchain protocols, where influence is proportional to staked resources. Ideal hierarchical access structures are then characterized using matroid theory, Boolean polymatroids, and lattice path matroids, and related to applications in multi-level blockchain networks such as Polkadot.