The Deflated Sharpe Ratio (Bailey and LĂłpez de Prado, 2014) corrects an observed Sharpe ratio for the number of trials N behind it, separating genuine skill from the selection bias of a large backtest search. Its practical weakness is structural: N is supplied by the same researcher whose result it constrains. A search over a thousand configurations, reported as a single trial, satisfies the formula while defeating its purpose. The correction is sound; its input is self-reported. We present a construction that removes the researcher's discretion over that input. The trial set is committed to a Merkle tree before evaluation; the trial count N is the leaf count of the tree, not a reported scalar; and the winning strategy is bound, inside a zero-knowledge proof (a STARK), to be the maximum over the committed leaves. The deflation is then recomputed in-circuit on Merkle-pinned prices, net of a cost model the credential discloses, so the figure an allocator reads is derived by the circuit rather than asserted by the manager. The output is a credential, checkable by anyone, in seconds, without disclosure of the strategy, whose anti-overfitting correction cannot be understated within the committed search. We give the commitment scheme and its in-circuit binding; state precisely the manipulation it eliminates (understating N, cherry-picking a non-maximal winner, softening the cost model) and the residual trust it does not (off-ledger trials, closed only by forward pre-registration); and report a live implementation that additionally computes, in-circuit, the Probability of Backtest Overfitting over all C(16,8) = 12,870 combinatorially-symmetric splits (via recursive proof composition), together with the Probabilistic Sharpe Ratio and Hansen's Superior Predictive Ability. We demonstrate the system on its own flagship strategy, which it rules not significant (DSR 0.68, below the 0.95 bar), and publish that failure as the reference credential.
A set of multivariate polynomials is algebraically independent if they exhibit no non-trivial algebraic relations, and this notion is fundamental in algebra. When these polynomials are given as algebraic circuits, deciding algebraic independence has several applications in algebraic complexity theory. Over fields of zero (or exponentially large) characteristic, this problem is known to have an efficient randomized algorithm. Over finite fields of small characteristic, a sequence of works has culminated in showing that algebraic independence admits Arthur-Merlin proofs, in particular giving the complexity bound of AMâŠcoAM ([Guo et al., 2019]). We improve the complexity of deciding algebraic independence over finite fields by showing that it admits zero-knowledge proofs, in particular giving the upper bound of NISZK â AMâŠcoAM, the class of problems admitting non-interactive statistical zero-knowledge proofs. This is achieved by arguing that algebraically independent polynomials yield maps whose output distribution has high-entropy, while algebraically dependent polynomials yield maps with low-entropy. We can then reduce to the question of approximating entropy, which is a known NISZK-complete problem. We also more generally show that transcendence degree, which quantifies the independence of a set of possibly dependent polynomials, can be computed in NISZK.
Large-scale privacy-preserving computation is essential for cross-domain data collaboration, making correctness auditing and accountability crucial for practical deployment. Existing auditing schemes typically use zero-knowledge proofs (ZKPs) to verify computation correctness and blockchain-based stake or reputation mechanisms to constrain dishonest participants. However, ZKP approaches often verify computation tasks or circuit constraints independently, causing high communication and verification overhead in large-scale task scenarios. Meanwhile, existing blockchain-based accountability mechanisms are weakly coupled with cryptographic audit results and lack sufficient adaptability in dynamic environments. In this paper, we propose MTBA, a batch auditing framework for privacy-preserving computation that leverages VOLE correlation to support polynomial proof generation and integrates blockchain-based reputation feedback. MTBA transforms arithmetic-circuit computations into auditable polynomial tasks by encoding multiplication-gate consistency as polynomial relations, converts these tasks into compact polynomial proofs, and introduces polynomial proof aggregation at multi-task for batch auditing. It further records signed audit outcomes on blockchain to support adaptive reputation feedback and malicious party accountability. Experimental results on circuits with up to $10^{7}$ multiplication gates show that MTBA improves auditing throughput by up to 2.7 times faster than conventional independent auditing schemes. These results indicate that MTBA provides a scalable and accountable auditing mechanism for large-scale privacy-preserving computation.
Guilin Guan, Zhou Wg, Hongtao Xie, Yang Cao ¡ 6 authors
The rapid advancement of big data and cloud computing technologies has elevated the importance of data transmission consistency verification in scenarios such as distributed storage, data backup, and content delivery networks. Traditional verification methods, including hash-based checks and digital signatures, inherently require access to raw data for computation and comparison. This dependency introduces risks of original data leakage and imposes substantial computational overhead in high-concurrency or large-scale data environments. Zero-knowledge proof (ZKP) technology offers a promising alternative by enabling a prover to demonstrate the validity of a statement to a verifier without disclosing any supplementary information. However, conventional ZKP schemes, particularly interactive ones, often suffer from complex communication rounds and significant computational burdens, rendering them unsuitable for data transmission scenarios demanding high real-time performance. This paper proposes a Lightweight Non-interactive Zero-Knowledge Proof (L-NIZK) protocol specifically designed for secure and efficient data transmission consistency verification. The protocol employs a data-blocking strategy combined with a Merkle tree structure and integrates an enhanced Pedersen commitment scheme with elliptic curve cryptography to achieve non-interactive and computationally efficient consistency proofs. A formal security analysis demonstrates that the proposed scheme satisfies completeness, soundness, and zero-knowledge properties under the random oracle model. Comprehensive performance evaluations indicate that the L-NIZK protocol surpasses existing mainstream solutions in proof generation time, verification time, and communication overhead, establishing its suitability for large-scale, high-concurrency data transmission environments.
A zero-knowledge proof demonstrates that a fact (like that a Sudoku puzzle has a solution) is true while, counterintuitively, revealing nothing else (like what the solution actually is). This remarkable guarantee is extremely useful in cryptographic applications, but it comes at a cost. A classical impossibility result by Goldreich and Oren [J. Cryptol. â94] shows that zeroknowledge proofs must necessarily sacrifice basic properties of traditional mathematical proofs - namely perfect soundness (that no proof of a false statement exists) and non-interactivity (that a proof can be transmitted in a single message). Contrary to this impossibility, we show that zero-knowledge with perfect soundness and no interaction is effectively possible. We do so by defining and constructing a powerful new relaxation of zero-knowledge. Intuitively, while the classical zero-knowledge definition requires that an object called a simulator actually exists, our new definition only requires that one cannot rule out that a simulator exists (in a particular logical sense). Using this, we show that every falsifiable security property of (classical) zero-knowledge can be achieved with no interaction, no setup, and perfect soundness. This enables us to remove interaction and setup from (classical) zero-knowledge in essentially all of its applications in the literature, at the relatively mild cost that such applications now have security that is âgame-basedâ instead of âsimulation-based.â Our construction builds on the work of Kuykendall and Zhandry [TCC â20] and relies on two central, longstanding, and well-studied assumptions that we show are also necessary. The first is the existence of non-interactive witness indistinguishable proofs, which follows from standard assumptions in cryptography. The second is KrajĂÄek and PudlĂĄkâs 1989 conjecture that no optimal proof system exists. This is one of the main conjectures in the field of proof complexity and is the natural finitistic analogue of the impossibility of Hilbertâs second problem (and, hence, also GĂśdelâs incompleteness theorem). Our highlevel idea is to use these assumptions to construct a prover and verifier where no simulator exists, but the non-existence of a simulator is independent (in the logical sense of unprovability) of an arbitrarily strong logical system. One such logical system is the standard axioms of mathematics: ZFC.
The complexity class Quantum Statistical Zero-Knowledge ($\mathsf{QSZK}$), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound $\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}$, which was simplified following the inclusion $\mathsf{QIP(2)} \subseteq \mathsf{PSPACE}$ established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, $\mathsf{QIP(2)}$ denotes the class of promise problems that admit two-message quantum interactive proof systems in which the honest prover is typically computationally unbounded, and $\text{co-}\mathsf{QIP(2)}$ denotes the complement of $\mathsf{QIP(2)}$. We slightly improve this upper bound to $\mathsf{QIP(2)} \cap \text{co-}\mathsf{QIP(2)}$ with a quantum linear-space honest prover. Specifically, the honest prover uses space linear in the size of the transcript of the original $\mathsf{QSZK}$ proof system. A similar improvement also applies to the upper bound for the non-interactive variant $\mathsf{NIQSZK}$. Our main techniques are algorithmic versions of the Holevo-Helstrom measurement and the Uhlmann transform, both implementable in quantum linear space, implying polynomial-time complexity in the state dimension, using the recent space-efficient quantum singular value transformation of Le Gall, Liu, and Wang (CC, to appear).
We introduce the notion of committed vector oblivious linear evaluation (C-VOLE), which allows a party holding a pre-committed vector to generate VOLE correlations with multiple parties on the committed value. It is a unifying tool that can be found useful in zero-knowledge proofs (ZKPs) of committed values, actively secure multi-party computation, private set intersection (PSI), etc.
Secure Multi-party Computation (MPC) considers the problem where a set of mutually distrusting parties want to jointly compute a function over their private inputs, without revealing any extra information about these inputs other than what it can be inferred from the output of the function. This setting is well-motivated, and it has many real-world applications such as auction, voting, etc. MPC can be also seen as a generalization of many natural cryptographic primitives. For example, zero-knowledge (ZK) can be viewed as a special case of two-party secure computation. In ZK, a party, called prover aims to convince a second party, called verifier, that the proverâs private input witness w and a public input statement x belong to a relation R. An important research direction in secure computation is to find the trade-off between the required setup (e.g., the use of the broadcast channel, the use of common reference string (CRS) / public key infrastructure (PKI), the upper bound of the parties that can be corrupted, etc.), and the security guarantees that can be achieved. The setups can be viewed as some general assumptions that the protocol needs to satisfy, and they influence the usability of the protocol in real-world scenarios. In principle, having simpler (or no) setups mean that the protocol is more general and can be more useful in real-world scenarios. At the same time, having simpler setups may lead to weaker security guarantees. Therefore, finding the trade-off between setup and security guarantees is important and meaningful. In this thesis, we target MPC and ZK, and we focus on how to minimize the setup for MPC and ZK while still providing meaningful levels of security. More specifically: Regarding MPC, we focus on the dishonest majority (i.e., the adversary can corrupt all but one party), and we aim at 1) minimizing the use of broadcast channels. 2) studying the MPC with pre-processing when no setup is available. ⢠Informally, a broadcast channel guarantees that when a message is sent, this reaches all the parties, without ambiguity. It also guarantees that if an honest party receives a message from a corrupted party, then it is guaranteed that all the honest parties have received the message. To realize broadcast, parties in the protocol could run the broadcast protocol, which may require many rounds of peer-to-peer communications. An alternative way is to rely on physical or external infrastructure such as blockchain. In both cases, broadcast is expensive, as such, we want to minimize its use. In particular, this thesis presents the following results: â When assuming no setup, we give a complete characterization with respect to the use of broadcast channels, and we obtain the optimal results. â We consider the same problem for the case that we only want to allow the black-box use (i.e., do not have access to the code of the algorithm) of the oblivious transfer protocol. We also give a characterization. ⢠In the standard definition of MPC, the partiesâ private inputs are fixed before the start of the protocol. However, there is another type of MPC named MPC with pre-processing, where the protocol can pre-compute some messages without using partiesâ inputs, and these messages can accelerate computations in the online phase (i.e., other computations that require partiesâ inputs). Since some expensive computations can be pre-computed, the online phase could be more lightweight. Therefore, we want to remove the dependency of the input from as many rounds as possible, so that we can do some pre-processing. In this direction, we explore the protocol with no setup. We provide a compiler that can turn a big class of MPC protocol that may require the inputs already to compute the first round, into a new protocol that needs the inputs only in the last two rounds. We also propose new MPC definitions that capture this delayed-input features. Regarding ZK, we do the following: ⢠In standard single-theorem ZK definition, the security of the ZK protocol is guaranteed to hold only when one proof is issued. In the case where multiple zero-knowledge proofs need to be issued (i.e., to prove multiple NP statements), each new zero-knowledge proof requires a freshly generated setup. In the multi-theorem ZK definition, instead, one setup is sufficient for generating multiple zero-knowledge proofs for multiple instances. We propose a multi-theorem protocol (in the format of a compiler) that follows the Fiat-Shamir paradigm and relies on correlation intractable hash functions. Moreover, our protocol remains zero-knowledge and sound even against adversaries that choose the statement to be proven (and the witness for the case of zero-knowledge) adaptively on the key of the hash function. Prior works could achieve this adaptive security only inefficiently via NP reductions. ⢠ZK protocols are secure only when all setups are correctly generated, but in real-world scenarios, some of the setups may not be correctly generated. For instance, to run a non-interactive zero-knowledge (NIZK) protocol, the setup CRS could be chosen with bias. In this case, the security of the NIZK protocol does not hold anymore. Instead of finding a secure ZK candidate, one alternative solution is to have multiple instantiations of ZK candidates and assume that only for a subset of them the setup is generated correctly. More formally, we consider the case where only a subset of the instances are secure. In more detail, given access to n candidate instantiations of a NIZK for some language, we want to have a construction that itself implements a NIZK for the same language without relying on any additional computational assumptions. We refer to this type of construction as combiner, and the combiner is secure assuming at least t of the given candidates are secure. In this work, we provide three different constructions of robust NIZK combiners and show that combiners are impossible to realize unless the majority of the input candidates are secure.
A polynomial commitment scheme (PCS) enables a prover to commit to a polynomial and later prove the correctness of its evaluation without revealing the polynomial. Although discrete logarithm-based PCSs offer succinct proofs, they are not quantum-safe. Lattice-based PCSs provide post-quantum security and additive homomorphism, making them suitable for applications such as zero-knowledge proofs and secure multiparty computation. In this article, we review two recent lattice-based PCSs, Greyhound and HyperWolf, both relying on the Module-SIS assumption but differing in target polynomial classes and proof techniques. In particular, Greyhound achieves a smaller proof size O(log log N) through folding and LaBRADOR proofs, while HyperWolf supports univariate and multilinear polynomials with lower verifier cost O(log N) using hypercube evaluation.
Computer-aided cryptography, with particular emphasis on formal verification, promises an interesting avenue to establish strong guarantees about cryptographic primitives. The appeal of formal verification is to replace the error-prone pen-and-paper proofs with a proof that was checked by a computer and, therefore, does not need to be checked by a human. In this paper, we ask the question of how reliable are these machine-checked proofs by analyzing a formally verified implementation of the Line-Point Zero-Knowledge (LPZK) protocol (Dittmer, Eldefrawy, Graham-Lengrand, Lu, Ostrovsky and Pereira, CCS 2023). The implementation was developed in EasyCrypt and compiled into OCaml code that was claimed to be high-assurance, i.e., that offers the formal guarantees of guarantees of completeness, soundness, and zero knowledge. We show that despite these formal claims, the EasyCrypt model was flawed, and the implementation (supposed to be high-assurance) had critical security vulnerabilities. Concretely, we demonstrate that: 1) the EasyCrypt soundness proof was incorrectly done, allowing an attack on the scheme that leads honest verifiers into accepting false statements; and 2) the EasyCrypt formalization inherited a deficient model of zero knowledge for a class of non-interactive zero knowledge protocols that also allows the verifier to recover the witness. In addition, we demonstrate 3) a gap in the proof of the perfect zero knowledge property of the LPZK variant of Dittmer, Ishai, Lu and Ostrovsky (CCS 2022) that the EasyCrypt proof is based, which, depending on the interpretation of the protocol and security claim, could allow a malicious verifier to learn the witness. Our findings highlight the importance of scrutinizing machine-checked proofs, including their models and assumptions. We offer lessons learned for both users and reviewers of tools like EasyCrypt, aimed at improving the transparency, rigor, and accessibility of machine-checked proofs. By sharing our methodology and challenges, we hope to foster a culture of deeper engagement with formal verification in the cryptographic community.
We introduce zkMaP (Zero-Knowledge Succinct Non-Interactive Matrix Multiplication Proofs), a novel non-interactive zero-knowledge proof system for verifying matrix multiplication with significant improvements in efficiency and scalability. Our protocol leverages KZG polynomial commitments and an innovative inner-product reduction technique to reduce the verification of n x n matrix multiplication to a single pairing equation, thereby enabling constant-time verification independent of the matrix size. In particular, zkMaP requires only two pairing operations and produces proofs as small as 320 bytes, yielding a 96 percent reduction in proof size compared to prior schemes. Furthermore, the prover's computational complexity follows the state-of-the-art at O(n^2), with experimental results demonstrating that proofs for 1024 x 1024 matrices can be generated in approximately 12.21 seconds, offering a 16.14x speedup over previous methods. Our implementation also exhibits better memory efficiency, using only 24.58 MB of prover-side RAM for 1024 x 1024 matrices, and supports scalable batch processing, achieving per-proof generation times of 46.79 milliseconds for 1024 instances while maintaining a constant verification time of 3.6 ms.
Many of the new quantum-resistant digital signature algorithms being evaluated and standardized by NIST rely on the Fiat-Shamir transform for security. This transformation takes a zero-knowledge (or negligible-knowledge) proof of identity and a hash function, and produces an algorithm for a digital signature. Luckily, none of these concepts are very hard to explain! I will give quick introductions to zero-knowledge proofs and hash functions, followed by two examples of digital signature algorithms based on Fiat-Shamir which you could use in an undergraduate classroom. The first one involves a lot of audience participation, and gives opportunities for drawing and decoration if you are so inclined. The second has been fairly well-known since the early days of public-key cryptography, and is likely to at least remind you of systems you have seen before. We wrap up with an overview of how Fiat-Shamir is used in post-quantum cryptography and in blockchains.
Yang Xu, Qixin Wang, Yufei Ren, Ying Hu ¡ 7 authors
ABSTRACT Transitive signatures are a special type of homomorphic signature proposed by Turing Award winners Micali and Rivest, which are highly suitable for authenticating dynamically growing graphâbased data systems. In such a signature scheme, anyone with the signer's public key is allowed to generate a signature for a composed edge , from two signatures on adjacent edges and . To prevent the problem of malicious dissemination of signatures by verifiers leading to data privacy leakage, researchers have proposed a series of universal designated verifier transitive signature (UDVTS) schemes. However, existing work requires that the designated verifier create its own secretâpublic key pair using the public key parameters provided by the signer. Besides, these schemes suffer from significant performance defects due to expensive pairing or exponentiation operations. In this work, we design a pairingâfree and exponentiationâfree UDVTS proof scheme based on the SM2 digital signature algorithm and a zeroâknowledge proof scheme. We prove the security of our construction based on rigorous cryptographic assumptions. The performance comparison with related work shows that our UDVTS proof scheme has an optimal computational cost and desirable communication cost. For example, compared to the stateâofâtheâart work, we reduce the signing cost by and the designated verification cost by .