Abstract Program verification provides stronger guarantees of correctness than standard testing. The verification process takes a program as input and derives a mathematical formula. Proving that a program is correct then reduces to establishing that this derived formula is unsatisfiable. Traditionally, automated reasoning tools can be used to determine unsatisfiability automatically. Furthermore, modern solvers can also produce a proof of unsatisfiability. However, these techniques typically rely on the proof and the underlying code being publicly available, which may not be desirable for certain applications. This work shows how to address this problem. Our team initially developed a protocol for validating the unsatisfiability of Boolean formulas in privacy-preserving settings. Building on these initial results, we devised ZKSMT, a virtual machine for validating unsatisfiability results produced by SMT solvers in zero-knowledge settings. In this paper we describe the theoretical foundations of such virtual machines and demonstrate how they can be applied to the theories of uninterpreted functions and linear integer arithmetic, two of the most widely used theories in verification. We conclude by outlining how the full formal verification workflow can be adapted to operate in privacy-preserving settings.

Distributed multi-user secret sharing is a cryptographic primitive for secure distributed computing. Khalesi et al. (2021) provided a full information-theoretic characterization of the capacity region under weak privacy and correctness constraints. Their encoding and decoding scheme relied on a randomized Monte-Carlo procedure whose success probability depended on the choice of a very large finite field. A gap remains between their information-theoretic characterization and deterministic design which eliminates random failures and enables reproducible, hardware-efficient implementations. We close this gap by developing a deterministic, polynomial-time algorithm that achieves every integral-rate point in thesamecapacity region over small hardware-friendly fields. The algorithm is asymptotically faster than a single Monte-Carlo run. This work provides the first explicit deterministic realization of the previously known capacity region, advancing the algorithmic foundations of distributed secret sharing.

Zero-knowledge proofs of training (zkPoT) allow a party to prove that a model is trained correctly on a committed dataset without revealing any additional information about the model or the dataset. Existing zkPoT protocols prove the entire training process in zero knowledge; i.e., they prove that the final model was obtained in an iterative fashion starting from the training data and a random seed (and potentially other parameters) and applying the correct algorithm at each iteration. This approach inherently requires the prover to perform work linear to the number of iterations.

Due to the globalization of the semiconductor supply chain, chip fabrication now involves multiple parties, including intellectual property (IP) vendors and Electronic Design Automation (EDA) tool vendors. Involving multiple entities and valuable IP naturally raises security and privacy concerns. Various frameworks and tools, such as the IEEE 1735 standard for IP protection, have been developed to mitigate the risk of theft. However, existing solutions fail to address all the threats envisioned by the zero-trust model. We propose a novel zero-trust formal verification framework that requires only two essential parties: IP users and IP vendors. This framework leverages secure multiparty computation to ensure the security and privacy of the hardware verification process. Our proposed solution allows IP users and IP vendors to independently convert the hardware design and assertions into conjunctive normal form (CNF), and then apply privacy-preserving SAT solving to verify the conformance of the design to the specification. This paper introduces a domain-specific secure decision procedure, hw-ppSAT, designed to overcome the scalability challenges of using SAT solving in hardware design verification. Our approach also leverages property-based hardware optimizations and domain-specific heuristics to enhance the verification process. We showcase the framework's effectiveness through its application to several open-source benchmarks.

A zero-knowledge proof (ZKP) is a powerful cryptographic primitive used in many decentralized or privacy-focused applications. However, the high overhead of ZKPs can restrict their practical applicability. We design a programming language, Ou, aimed at easing the programmer's burden when writing efficient ZKPs, and a compiler framework, Lian, that automates the analysis and distribution of statements to a computing cluster. Ou uses programming language semantics, formal methods, and combinatorial optimization to automatically partition an Ou program into efficiently sized chunks for parallel ZK-proving and/or verification. We contribute: (1) A front-end language where users can write proof statements as imperative programs in a familiar syntax; (2) A compiler architecture and implementation that automatically analyzes the program and compiles it into an optimized IR that can be lifted to a variety of ZKP constructions; and (3) A cutting algorithm, based on Pseudo-Boolean optimization and Integer Linear Programming, that reorders instructions and then partitions the program into efficiently sized chunks for parallel evaluation and efficient state reconciliation.

Illegal construction poses a safety hazard to both cities and people and affects the social stability and long-term stability of the country. Therefore, it is important to detect illegal buildings as early as possible. However, current illegal building detection methods generally suffer from either detection cycles or low detection accuracies. To solve these challenges, this study adopts an unusual method that detects illegal building objects to prevent illegal building behavior. A detection model, CRMNet, which is based on the anchor-free detection model CenterNet, and dataset for illegal building objects are proposed. ResNet50 is selected as the backbone for extracting futures after weighing the computational cost and detection accuracy. Furthermore, Mish, a new activation function, is used to improve the identification accuracy of illegal building objects. Experimental results show that the mean average precision (mAP) of the proposed detector on the illegal building object dataset reached 88.16%, which is higher than that of other popular object detection methods. Additionally, in contrast to mainstream target detection methods, the proposed detection method has fewer parameters and a higher detection accuracy, which can be better applied to mobile devices and smart devices.

Zero-knowledge (ZK) protocols enable one party to prove to others that it knows a fact without revealing any information about the evidence for such knowledge. There exist ZK protocols for all problems in NP, and recent works developed highly efficient protocols for proving knowledge of satisfying assignments to Boolean formulas, circuits and other NP formalisms. This work shows an efficient protocol for the converse: proving formula unsatisfiability in ZK (when the prover posses a non-ZK proof). An immediate practical application is efficiently proving safety of secret programs.

The stable path problem (SPP) is a unified model for analyzing the convergence of distributed routing protocols (e.g., BGP), and a foundation for many network verification tools. Although substantial progress has been made on finding solutions (i.e., stable path assignments) for particular subclasses of SPP instances and analyzing the relation between properties of SPP instances and the convergence of corresponding routing policies, the non-trivial challenge of finding stable path assignments to generic SPP instances still remains. Tackling this challenge is important because it can enable multiple important, novel routing use cases. To fill this gap, in this paper we introduce a novel data structure called solvability digraph, which encodes key properties about stable path assignments in a compact graph representation. Thus SPP is equivalently transformed to the problem of finding in the solvability digraph a maximum independent set (MIS) of size equal to the number of autonomous systems (ASes) in the given SPP instance. We leverage this key finding to develop a heuristic polynomial algorithm GREEDYMIS that solves strictly more SPP instances than state-of-the-art heuristics. We apply GREEDYMIS to designing two important, novel use cases: (1) a centralized interdomain routing system that uses GREEDYMIS to compute paths for ASes and (2) a secure multi-party computation (SMPC) protocol that allows ASes to use GREEDYMIS collaboratively to compute paths without exposing their routing preferences. We demonstrate the benefits and efficiency of these use cases via evaluation using real-world datasets.