There are times when the highest levels of privacy and security are required to protect a piece of information, but there is still a need to prove the information’s existence and accuracy. For the Department of Defense (DoD), the proof could be the verification of a relevant capability. How can one verify this capability without revealing any sensitive details about it? In the commercial world, this struggle manifests itself across banking transactions, cybersecurity threat disclosure, and beyond. One approach to addressing this challenge in cryptography is with zero-knowledge proofs. A zero-knowledge proof is a method where one party can prove to another party that they know a certain fact without revealing any sensitive information needed to demonstrate that the fact is true.
The Defense Advanced Research Projects Agency (DARPA) in July 2019 detailed a program seeking research proposals for to help the Defense Department (DoD) understand zero-knowledge proofs. In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that they know a value x, without conveying any information apart from the fact that they know the value x. The essence of zero-knowledge proofs is that it is trivial to prove that one possesses knowledge of certain information by simply revealing it; the challenge is to prove such possession without revealing the information itself or any additional information.
The Securing Information for Encrypted Verification and Evaluation (SIEVE) program aims to increase the efficiency and technology behind zero-knowledge proofs, or a method by which one party can prove to another that they know specific knowledge without revealing sensitive information. Zero Knowledge Protocol (or Zero Knowledge Password Proof, ZKP) is a way of doing authentication where no passwords are exchanged, which means they cannot be stolen. This is cool because it makes your communication so secure and protected that nobody else can find out what you’re communicating about or what files you are sharing with each other.
A protocol implementing zero-knowledge proofs of knowledge must necessarily require interactive input from the verifier. This interactive input is usually in the form of one or more challenges such that the responses from the prover will convince the verifier if and only if the statement is true, i.e., if the prover does possess the claimed knowledge. If this were not the case, the verifier could record the execution of the protocol and replay it to convince someone else that they possess the secret information. The new party’s acceptance is either justified since the replayer does possess the information (which implies that the protocol leaked information, and thus, is not proved in zero-knowledge), or the acceptance is spurious, i.e., was accepted from someone who does not actually possess the information.
“A zero-knowledge proof involves a statement of fact and the underlying proof of its accuracy,” said Dr. Josh Baron, program manager in DARPA’s Information Innovation Office (I2O). “The holder of the fact does not want to reveal the underlying information to convince its audience that the fact is accurate. Take, for example, a bank withdrawal. You may want a system that allows you to make a withdrawal without also having to share your bank balance. The system would need some way of verifying that there are sufficient funds to draw from without having to know the exact amount of money sitting within your account.”
Zero-knowledge proofs in blockchains
DARPA cited that zero-knowledge proof use has seen an uptick in use and efficiency in recent years, particularly in cryptocurrency, but the agency added that it initiated SIEVE to help DoD adopt zero-knowledge proof strategies in its mission.
In recent years, there has been a marked increase in the efficiency and real-world use of zero-knowledge proofs. Most of these uses have been within the cryptocurrency domain where there is a need to provide certain verifiable data without revealing personal or other sensitive information. While useful in this context, the zero-knowledge proofs created are specialized for this task. They prioritize communication and verification efficiency but do not necessarily scale for transactions that are more complex. For highly complex proof statements like those that the DoD may wish to employ, novel and more efficient approaches are needed. Blockchain is based on open, global infrastructure, decentralized public ledger of transactions that no one person or company owns or controls, ensures security of transfer of funds through public and private cryptology and third parties to verify that they shook, digitally, on an agreement.
The same technology used for virtual currencies is now being researched by the Department of Defense to create tamper-proof military computer systems, including those systems used to control America’s nuclear weapons. The Department of Defense also looking to blockchain for development of a secure messaging system that would use the standard encryption and security features of current messaging apps such as WhatsApp, Signal, or Ricochet, but also use a decentralized Blockchain-like backbone structure that would be more resilient to surveillance and cyberattacks.
Zero-knowledge protocols enable the transfer of assets across a distributed, peer-to-peer blockchain network with complete privacy. In regular blockchain transactions, when an asset is sent from one party to another, the details of that transaction are visible to every other party in the network. By contrast, in a zero knowledge transaction, the others only know that a valid transaction has taken place, but nothing about the sender, recipient, asset class and quantity. The identity and amount being spent can remain hidden, and problems such as “front-running” can be avoided.
The most prominent blockchain-based system using zero-knowledge proofs is ZCash, which was also the first cryptocurrency to implement zk-SNARKs. Other blockchain-based systems have since also incorporate zero-knowledge proofs into their solutions to allow for transactions to be verified while protecting user/transaction privacy. Probably the best known of which is Ethereum, which implemented zk-SNARKS as part of the Byzantium upgrade.
zk-SNARKs are a novel form of zero-knowledge cryptography that is intended to enhance the privacy of users transacting on the Zcash blockchain. With cryptocurrencies such as Bitcoin, an individual can identify user addresses and track the movement of value between transacting parties on the blockchain. In this case, Bitcoin only provides users with pseudonymous protection, rather than complete anonymity. zk-SNARKs are designed to solve this problem, by completely encrypting user transaction information on the Zcash blockchain. The generation of zero-knowledge proofs rely on a set of public parameters that allow users to construct and verify private transactions. These parameters are constructed by sampling some random numbers, which are known as ‘toxic waste’. zk-SNARK is an acronym for ‘Zero-Knowledge Succint Non-Interactive Argument of Knowledge’.
By contrast, SIEVE will focus on realistic scenarios for the creation of ZK proofs of relevance to public demonstration of DoD capabilities; this setting may not look anything like a cryptocurrency transaction, and therefore may not require the kinds of assumptions necessary for noninteractivity and/or succinctness. Additionally, in order to ensure the relevance of ZK proofs for the foreseeable future, including the case where a cryptographically-relevant quantum computer were to exist, SIEVE will focus on substantially decreasing the asymptotic complexity of post-quantum ZK proof techniques, specifically ZK proofs that 1) rely on post-quantum hardness assumptions for their security and/or 2) reason about statements of relevance to post-quantum cryptography.
The SIEVE program will advance the state of the art in ZK proofs to enable complex, DoD-relevant applications. While proposers may propose applications, exemplar applications include proving statements about software, computation more generally, and the interaction of technology within society. SIEVE is particularly motivated to provide ZK proofs for statements about capabilities associated with cybersecurity and cyberspace operations, which have historically been difficult for the United States Government to communicate about in a verifiable fashion without the release of sensitive information. SIEVE will demonstrate the feasibility of encoding complex, DoD-relevant statements into intermediate representations (IRs) that can then be used to create efficient ZK
proofs for those statements.
“SIEVE aims to develop computer science theory and software that can generate mathematically verifiable statements that can be shared publicly [sic] without giving sensitive information away. Under the program, researchers will explore the creation of verifiable public statements about software, general computations, as well as social-technical interactions,” DARPA said. Particularly, DARPA said proposed research “should investigate innovative approaches that enable revolutionary advances in science, devices, or systems.”
The Defense Advanced Research Projects Agency is looking for research proposals on verification methods that can enable data validation while keeping sensitive information hidden from verifiers. According to a FedBizOpps notice, the Securing Information for Encrypted Verification and Evaluation program aims to deploy the zero-knowledge proof concept used in cryptocurrency transactions to allow the verification of Department of Defense-relevant capabilities without exposing their classified details.
Proposals may address some, all, or none of the below classes.
- Statements about software: prove that software is vulnerable to an exploit without revealing details of the specific exploit; prove that encrypted software is secure, or performs certain functionalities, without revealing the underlying code.
- Statements about computation: prove that specific computations have been correctly performed without revealing inputs, e.g., that a machine learning classifier was generated from allowable data without revealing that data; prove that specific outputs were derived without revealing the computation, e.g., that digital media was correctly generated from a class of allowable transforms without revealing the original media or the actual transforms used.
- Statements about sociotechnical interactions: prove that a cyber attack was attributable to a particular actor given public, yet encrypted, threat actor information; prove that a set of computations follow a set of “plain English” policy specification, e.g., that a specific computation is General Data Protection Regulation (GDPR) compliant without revealing the computation.
The three-phase SIEVE project will focus on developing, integrating and scaling the verification technologies which must be able to handle cybersecurity operations and “large, complex proof statements.” DARPA expects the first and second phases to run for 18 months and the last phase to conclude within a year. A proposer’s day will be held on July 17. Interested parties may submit proposals through Sept. 20.
Galois seeks to advance trusted computing and cryptography technologies using zero-knowledge proofs
Officials of the U.S. Defense Advanced Research Projects Agency (DARPA) in Arlington, Va., announced a $12.6 million contract to Galois in April 2020 for the Securing Information for Encrypted Verification and Evaluation (SIEVE) project. Galois trusted computing experts will seek to advance the state of the art in zero-knowledge proofs to enable complex military applications. A zero-knowledge proof in cryptography enables one party to prove that he knows a particular without conveying any secret information; the challenge is proving possession of sensitive information without revealing the information itself.
Company engineers will use zero knowledge proofs to verify military capabilities without revealing the sensitive details. They also will focus on increasing the efficiency of zero knowledge proof technology to enable large, complex proof statements — such as billions of gates or more — where the statement consists of probabilistic and indeterminate-branching conditions.
University of California, Berkeley
Professor Omkant Pandey of the Department of Computer Science, along with Sanjam Garg of the University of California, Berkeley, have been awarded a $1 million grant from the Defense Advanced Research Projects Agency (DARPA) to develop safe and secure verification methods for sensitive processes.
Verification is a critical part of our everyday lives. Governments and businesses put various regulations and verification processes in place to detect and prevent fraud (for example, when we go to a bank, the bank must verify who we are before providing access to our money). In many cases, the verification is carried out by computer programs over highly sensitive data associated with these applications.
Pandey and Garg’s research looks at how to prove that a verification was done correctly by the computer without sharing sensitive details, such as the actual data. To do this, they will use a technique called Zero-Knowledge Proofs from cryptography, which proves that a mathematical statement is true but reveals nothing except the validity of the statement. Samir Das, Chair of the Computer Science Department, said: “Professor Pandey’s research in this award will advance the security of future computer systems more efficiently and significantly contribute to the nation’s cyberdefense. Professor Pandey is a key member of our highly visible cybersecurity group.”
The research, titled “EPCC: Efficient Proofs for Cryptographic Code,” focuses on how efficiently zero-knowledge proofs can be constructed for different kinds of procedures. Current technology for these proofs requires the full details of the verification procedure to be known to all parties. Some procedures involve cryptographic algorithms such as encryption, which makes the proofs very inefficient. The researchers will develop more efficient proofs by reducing the need for sharing full code of the cryptographic parts of the verification procedures.
References and Resources also include: