This project implements interactive and non interactive zero knowledge proof protocols based on current Wolfram's cryptography framework. Zero knowledge proofs are communication protocols by which one person called the Prover can convince another person called Verifier that it posses a solution to a given public problem without revealing the content of the solution. This project implements two main applications of zero knowledge proofs; online zero knowledge authentication that provides protection against "man in the middle" impersonation attacks; and the most impressive, a Verifier can be convinced that a computation was executed correctly without executing it and without knowing what was executed.
Interactive zero knowledge proofs
Interactive zero knowledge proofs
Discussion
Discussion
Zero knowledge proofs are communication protocols by which a person P that has a PrivateSolution to a PublicProblem of complexity class NP, is be able to convince another person V that it posses the solution without revealing the content of the solution (the verifier gains zero knowledge).
In the common (non zero knowledge) case, to prove that such solution exists P will simply share the solution’s content with V and then V will run the polynomial time verifier of the NP problem solution. In order to achieve zero knowledge, the prover will transform the public problem into several equivalent problems for which person V will send repeated challenges to P that can be solved efficiently if and only if P posses such solution (or is extremely lucky).
At the end of the interactive transmission of queries and responses V is convinced of the existence (or lack) of the solution. This is described in the following protocol
In the common (non zero knowledge) case, to prove that such solution exists P will simply share the solution’s content with V and then V will run the polynomial time verifier of the NP problem solution. In order to achieve zero knowledge, the prover will transform the public problem into several equivalent problems for which person V will send repeated challenges to P that can be solved efficiently if and only if P posses such solution (or is extremely lucky).
At the end of the interactive transmission of queries and responses V is convinced of the existence (or lack) of the solution. This is described in the following protocol
1
.P generates an isomorphism that ciphers the PublicProblem into another computationally hard NP problem called PublicCipherProblem, such isomorphism must meet that the PrivateSolution to the original problem is also ciphered into a solution to the PublicCipherProblem problem. The isomorphism must be computationally hard to find. Both the isomorphism and the cipher solution constitute what is called the PrivateCipherSolution. Finally the PublicCipherProblem is shared with V as Witness.
2
.To verify the Witness’s PublicCipherProblem, V makes a Query to P to show either the isomorphism that ciphered the PublicProblem, or the solution to the PublicCipherProblem. V can only ask for one of the isomorphism or the ciphered solution since having both will give V all the information needed to recreate the original PrivateSolution making this protocol non zero knowledge.
Notice that having only the isomorphism, V cannot come up with the PrivateCipherSolution since it would have solve the PublicCipherProblem; and having the solution, V cannot come up with the isomorphism since its a computationally hard problem to find.
Notice that having only the isomorphism, V cannot come up with the PrivateCipherSolution since it would have solve the PublicCipherProblem; and having the solution, V cannot come up with the isomorphism since its a computationally hard problem to find.
3
.If P gives an incorrect Response, V can be sure that P doesn’t have the claimed solution and rejects the proofs. On the other hand if the Response is valid, then either P has the PrivateCipherSolution, or it was lucky and V asked for a forged response, the latter case has a 50% probability of success, and decreases exponentially with the number of rounds this interaction is repeated.
The PublicProblem definition and the way the problems and solutions are ciphered defines a specific type of zero knowledge interactive protocol.
The paclet has implementation for the following interactive protocols
The paclet has implementation for the following interactive protocols
"Isomorphism" | Thepublicproblemistofindanisomorphismbetweentwographs;Theprivatesolutionisthegraphisomorphism;Ciphersaregraphisomorphisms |
"HamiltonianCycle" | Thepublicproblemistofindahmiltoniancycleinagivengraphs;Theprivatesolutionisthehamiltoniancycle;Ciphersaregraphisomorphisms |
"SAT" | Thepublicproblemisabooleanfunctiononnvariables;Thesolutionisabooleanvectorthatsatisfiesthebooleanfunction;Ciphersarepermutationofthenvariablesandtheirsigns |
Needs["ArmandoCruz`ZeroKnowledgeProofs`"]
Online Authentication
Online Authentication
If P is able to easily generate a computationally hard PublicProblem and its PrivateSolution, then P is the only person in the world that knows the answer, and this PublicProblem can be used to authenticate P in a network. If a verifier V is convinced that person X has a solution to P’s PublicProblem, then X must be P.
This authentication protocol provides protection against a man in the middle impersonation attack, in which a third untrusted party ask for your password impersonating the verifier, the password is then copied and used with the actual verifier. In zero knowledge authentication this cannot happen since no knowledge about the password is shared with any verifier.
This authentication protocol provides protection against a man in the middle impersonation attack, in which a third untrusted party ask for your password impersonating the verifier, the password is then copied and used with the actual verifier. In zero knowledge authentication this cannot happen since no knowledge about the password is shared with any verifier.
Example
Example
Zero knowledge authentication protocol is carried out in the following way
P generates a computationally hard NP PublicProblem and its PrivateSolution (E.g. using the Isomorphism protocol).
In[]:=
zkProof=GenerateZeroKnowledgeProof["Isomorphism"]privateSolution=zkProof["ZeroKnowledgePrivateSolution"];publicProblem=zkProof["ZeroKnowledgePublicProblem"];
Out[]=
ZeroKnowledgePrivateSolutionZeroKnowledgePrivateSolution,ZeroKnowledgePublicProblemZeroKnowledgePublicProblem
[PublicProblem and PrivateSolution]
In[]:=
publicProblem["PublicProblem"]privateSolution["PrivateSolution"]
Out[]=
,
Out[]=
{124,27,35,49,519,630,71,829,911,1015,1122,1220,1313,1418,1517,1614,1723,1826,1927,2012,212,224,2316,246,2510,2625,2728,2821,293,308}
The PublicProblem is shared with V. When P wants authenticate with V as the solver of the PublicProblem, it will prove it with a ZKP. V makes a VerificationRequest to P, asking for a fixed number of PublicCipherProblems. Suppose V requests for 5 CipheredKeys.
P gets the VerificationRequest and generates a ZeroKnowledgeProver object, that contains the PublicWitness with the 5 PublicCipherProblems, and a PrivateOracle with the PrivateCipherSolutions, the Witness is shared with Β.
In[]:=
prover=GenerateZeroKnowledgeProver[privateSolution,5]cipher=prover["ZeroKnowledgePrivateCipher"];witness=prover["ZeroKnowledgePublicWitness"];
Out[]=
ZeroKnowledgePrivateCipherZeroKnowledgePrivateCipher,ZeroKnowledgePublicWitnessZeroKnowledgePublicWitness
[PublicCipherProblem contained in the PublicWitness]
In[]:=
witness["PublicCipherProblems"][[1]]
Out[]=
[PrivateCipherSolution contained in the PrivateCipher]
In[]:=
cipher["PrivateCipherSolutions"][[1]]
Out[]=
Cipher{124,227,323,48,511,61,721,825,96,1012,1110,1226,1317,1422,1530,163,175,1828,1914,204,212,2216,237,2429,2518,269,2713,2815,2919,3020},Solution{16,228,316,429,522,624,72,810,930,1020,1115,1225,1323,144,158,165,1719,1821,1918,209,217,2214,231,243,2526,2611,2713,2817,2927,3012}
For each PublicCipherProblem, V request for the isomorphism to the original problem (the isomorphism to the first graph) or the solution of the PublicCipherProblem (the isomorphism to the second graph), and sends the Query to P.
In[]:=
query=GenerateZeroKnowledgeQuery[witness]
Out[]=
ZeroKnowledgeQuery
[Queries contained in the ZeroKnowledgeQuery]
In[]:=
query["Queries"]
Out[]=
{Cipher,Cipher,Cipher,Cipher,Cipher}
P then makes use of the PrivateOracle to answer the Query from V and share the answers.
In[]:=
response=GenerateZeroKnowledgeResponse[cipher,query]
Out[]=
ZeroKnowledgeResponse
[Response contained in the ZeroKnowledgeResponse]
In[]:=
response["Responses"][[1]]
Out[]=
{124,227,323,48,511,61,721,825,96,1012,1110,1226,1317,1422,1530,163,175,1828,1914,204,212,2216,237,2429,2518,269,2713,2815,2919,3020}
Finally V verifies the answers provided by P are correct.
In[]:=
VerifyZeroKnowledgeProof[publicProblem,witness,query,response]
Out[]=
True
Suppose a third person E tries to impersonate P in a communication with V, when V asks for the PublicWitness E must generate 4 fake CipheredKeys hoping to deceive V. It’s easy for E to generate an isomorphic problem to the original problem with no solution, or to generate a solution to a non isomorphic problem, but it cannot produce a solution to an isomorphic problem.
Since V will ask for either the isomorphism or the solution randomly, E has a 2^(-4) probability of trick the verifier, and this probability decreases exponentially with the number of requested rounds from the verifier.
Since V will ask for either the isomorphism or the solution randomly, E has a 2^(-4) probability of trick the verifier, and this probability decreases exponentially with the number of requested rounds from the verifier.
Zero knowledge proofs for NP complete problems
Zero knowledge proofs for NP complete problems
The complexity class NP-complete is composed of problems of class NP for which any other problem of class NP can be reduced into an instance of this NP-complete problem. Cook-Levin Theorem states that the Boolean satisfiability problem (SAT) is of class NP-complete.
This means that a zero knowledge protocol for NP-complete problems (like SAT) can be extended to any given NP problem, since there’s an algorithm to compile it into a boolean function that satisfies that solutions of the original NP problem are compiled into n-dimensional boolean vectors that satisfies the boolean function. One way to compile the problem is to look at the boolean expression of the circuit of the NP problem’s verifier.
This means that a zero knowledge protocol for NP-complete problems (like SAT) can be extended to any given NP problem, since there’s an algorithm to compile it into a boolean function that satisfies that solutions of the original NP problem are compiled into n-dimensional boolean vectors that satisfies the boolean function. One way to compile the problem is to look at the boolean expression of the circuit of the NP problem’s verifier.
Example
Example
For example suppose P wants to prove V that 3 divides 12, that is that P knows a number x such that 3 x = 12, in this case x equals 4. This can be compiled to a boolean expression using the adder circuit of two 4 bit numbers .
[Circuit compilation functions]
In[]:=
binaryAdder1bit[x_,y_,c_]:=<|"sum"->Xor[Xor[x,y],c],"carry"->(x&&y)||(c&&Xor[x,y])|>
In[]:=
nextSum[sum_,x_,y_]:=Append[binaryAdder1bit[x[[sum["n"]]],y[[sum["n"]]],sum["carry"]],<|"n"->sum["n"]+1|>]
In[]:=
binaryAdder4bits[x_,y_]:=Rest@NestList[nextSum[#,x,y]&,<|"sum"->False,"carry"->False,"n"->1|>,4][[All,"sum"]]
In[]:=
booleanVector={x[1],x[2],x[3],x[4]};digits=binaryAdder4bits[binaryAdder4bits[booleanVector,booleanVector],booleanVector];
[Compiled NP verifier]
In[]:=
result={False,False,True,True};(*12inbinary*)
compilation=And@@(Array[If[result[[#]],digits[[#]],Not[digits[[#]]]]&,Length[result]])
Out[]=
!x[1]&&!((x[1]&&x[1])⊻x[2])&&((x[2]&&x[2])⊻(x[1]&&x[1]&&x[2])⊻x[3])&&((x[3]&&x[3])⊻((x[2]&&x[2]&&x[3])||(x[1]&&x[1]&&x[2]&&((x[2]&&x[2])⊻x[3])))⊻x[4])
Out[]=
booleanCompilation/.{x[1]#1,x[2]#2,x[3]#3,x[4]#4}&
[Boolean vectors that satisfy the result]
Once the problem and solutions are compiled into an equivalent NP-complete problem like SAT, it will be straight forward to generate a zero knowledge proof following the previously mentioned interaction, using an interactive zero knowledge protocol of type “SAT”.
Notice the cipher solutions are permuted version of the original PrivateSolution, unless V knows the permutation the PrivateSolution will remain ciphered and V will gain zero knowledge. But if there’s an easy way to break the cipher then the zero knowledge property will not hold. This is something to have in mind at the definition of a new type of protocol.
Notice the cipher solutions are permuted version of the original PrivateSolution, unless V knows the permutation the PrivateSolution will remain ciphered and V will gain zero knowledge. But if there’s an easy way to break the cipher then the zero knowledge property will not hold. This is something to have in mind at the definition of a new type of protocol.
zkSNARK
zkSNARK
Discussion
Discussion
The main disadvantage with interactive proofs, are the witness size and the verification time (for non trivial problems the compilation might be , that make this protocols non scalable for multi verification systems. zkSNARK is short for zero knowledge succinct non-interactive arguments of knowledge, a noninteractive zero knowledge proof protocol having the “public verifier” property, that is that anyone can verify the proof without
interacting with the prover anew. Another advantage of zkZNARKs are small sizes of witness compared to the length of the verification computation.
interacting with the prover anew. Another advantage of zkZNARKs are small sizes of witness compared to the length of the verification computation.
The principle that makes zkSNARKS possible is the same described in the “Zero knowledge proofs for NP complete problems” section. Gennaro, Gentry, Parno and Raykova [1] introduced a new NP-complete problem called Quadratic Span
Programs (QSPs), that are well suited for the zkSNARK protocol. Again the first step would be to compile a given NP problem into a QSP. A compiler of circuits into QSP and the implementation of the zkSNARK protocol as described in [2] is visualized as future work.
Programs (QSPs), that are well suited for the zkSNARK protocol. Again the first step would be to compile a given NP problem into a QSP. A compiler of circuits into QSP and the implementation of the zkSNARK protocol as described in [2] is visualized as future work.
Concluding remarks
Concluding remarks
In this project a paclet with definition of 3 interactive zero knowledge proof protocols, based on a common structure of PrivateSolution, PublicProblem, PrivateCipher and PublicWitness objects. The exploration of secure NP-complete zero knowledge proofs like zkSNARK protocol, has huge implications to privacy in decentralized networks and technology like blockchain in which the correctness of the creation of new blocks must be verified by the network, usually done by inspecting the transactions in the block (non zero knowledge).
Implementation of an interactive protocol for the NP-complete 3SAT (the satisfiability of a formula in conjunctive normal form where each clause is limited to at most three literals) and a Quadratic Span Problem compiler are visualized as future work of this project.
Implementation of an interactive protocol for the NP-complete 3SAT (the satisfiability of a formula in conjunctive normal form where each clause is limited to at most three literals) and a Quadratic Span Problem compiler are visualized as future work of this project.
Keywords
Keywords
◼
Zero knowledge proof
◼
zkSNARK
◼
Authentication
◼
NP-complete
Acknowledgment
Acknowledgment
The author would like to thank Stephen Wolfram, for proposing the project’s topic and providing the state of the art of the problem and his input on the future of this technology, that helped the author shape the content of this project.
The author would like to express his gratitude towards his mentor Christopher Wolfram for sharing his knowledge in cryptography and the Wolfram language cryptography framework, with his support this project achieved an professional interface based on Wolfram’s cryptography functions. Also the help and support of TAs Faizon Zaman (Fez), Swastik Banerjee and Connor Gray that helped him understand the problem and give him technical insight to implement the paclet.
The author would like to finish by thanking Emily Carter and Mads Bahrami, organizers of the Wolfram Summer School 2022, with their help and guidance in the application process attending the summer school was possible for him.
The author would like to express his gratitude towards his mentor Christopher Wolfram for sharing his knowledge in cryptography and the Wolfram language cryptography framework, with his support this project achieved an professional interface based on Wolfram’s cryptography functions. Also the help and support of TAs Faizon Zaman (Fez), Swastik Banerjee and Connor Gray that helped him understand the problem and give him technical insight to implement the paclet.
The author would like to finish by thanking Emily Carter and Mads Bahrami, organizers of the Wolfram Summer School 2022, with their help and guidance in the application process attending the summer school was possible for him.
References
References
◼
[1] Gennaro, R., Gentry, C., Parno, B., Raykova, M. (2013). Quadratic Span Programs and Succinct NIZKs without PCPs. In: Johansson, T., Nguyen, P.Q. (eds) Advances in Cryptology – EUROCRYPT 2013. EUROCRYPT 2013. Lecture Notes in Computer Science, vol 7881. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38348-9_ 37
◼
[3] Foundation, E., 2022. zkSNARKs in a nutshell. [online] Blog.ethereum.org. Available at: https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/ [Accessed 19 July 2022].
◼
[4] Company, E., 2022. What are zk-SNARKs? | Zcash. [online] Zcash. Available at: https://z.cash/technology/zksnarks/ [Accessed 19 July 2022].
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Implementation of Interactive Zero Knowledge proofs paclet
by Armando Benjamín Cruz Hinojosa
Wolfram Community, STAFF PICKS, July 19, 2022
https://community.wolfram.com/groups/-/m/t/2575404
by Armando Benjamín Cruz Hinojosa
Wolfram Community, STAFF PICKS, July 19, 2022
https://community.wolfram.com/groups/-/m/t/2575404