Intrusion Detection in Zero Knowledge System Using Model Checking Approach
2
Citation
7
Reference
10
Related Paper
Citation Trend
Keywords:
Zero-knowledge proof
Communication source
Gas meter prover
Login
Hacker
The seminal result that every language having an interactive proof also has a zero-knowledge interactive proof assumes the existence of one-way functions. Ostrovsky and Wigderson (ISTCS 1993) proved that this assumption is necessary: if one-way functions do not exist, then only languages in BPP have zero-knowledge interactive proofs. Ben-Or et al. (STOC 1988) proved that, nevertheless, every language having a multi-prover interactive proof also has a zero-knowledge multi-prover interactive proof, unconditionally. Their work led to, among many other things, a line of work studying zero knowledge without intractability assumptions. In this line of work, Kilian, Petrank, and Tardos (STOC 1997) defined and constructed zero-knowledge probabilistically checkable proofs (PCPs). While PCPs with quasilinear-size proof length, but without zero knowledge, are known, no such result is known for zero knowledge PCPs. In this work, we show how to construct “2-round” PCPs that are zero knowledge and of length ~ O(K) where K is the number of queries made by a malicious polynomial time verifier. Previous solutions required PCPs of length at leastK 6 to maintain zero knowledge. In this model, which we call duplex PCP (DPCP), the verifier first receives an oracle string from the prover, then replies with a message, and then receives another oracle string from the prover; a malicious verifier can make up toK queries in total to both oracles. Deviating from previous works, our constructions do not invoke the PCP Theorem as a blackbox but instead rely on certain algebraic properties of a specific family of PCPs. We show that if the PCP has a certain linear algebraic structure — which many central constructions can be shown to possess, including [BFLS91,ALMSS98,BS08] — we can add the zero knowledge property at virtually no cost (up to additive lower order terms) while introducing only minor modifications in the algorithms of the prover and verifier. We believe that our linear-algebraic characterization of PCPs may be of independent interest, as it gives a simplified way to view previous well-studied PCP constructions.
Gas meter prover
Zero-knowledge proof
Zero (linguistics)
Cite
Citations (1)
A zero-knowledge proof system of knowledge is a protocol between two parties called the prover and the verifier. The prover wants to convince the verifier that he 'knows' the proof of a given theorem without revealing any additional information. This is different from a zero-knowledge proof system of membership where the prover convinces the verifier only of the veridicity of the statement. Zero-knowledge proofs of knowledge are very useful tools in the design of secure protocols. Though, the concept of a proof of knowledge is a very subtle one and great care is needed to obtain a satisfying formalization. The authors investigate the concept of a zero-knowledge proof of knowledge with a non-interactive model. Here, the prover and the verifier share a short random string and the only communication allowed is from the prover to the verifier. Although this is a simpler model than the interactive one, still formalizing zero-knowledge proofs of knowledge is a delicate task.< >
Gas meter prover
Zero-knowledge proof
Zero (linguistics)
Statement (logic)
Proof assistant
Cite
Citations (155)
In 2009, Gradwohl, Naor, Pinkas, and Rothblum proposed physical zero-knowledge proof protocols for Sudoku. That is, for a puzzle instance of Sudoku, their excellent protocols allow a prover to convince a verifier that there is a solution to the Sudoku puzzle and that he/she knows it, without revealing any information about the solution. The possible drawback is that the existing protocols have a soundness error with a non-zero probability or need special cards (such as scratch-off cards). Thus, in this study, we propose new protocols to perform zero-knowledge proof for Sudoku that use a normal deck of playing cards and have no soundness error. Our protocols can be easily implemented by humans with a reasonable number of playing cards.
Zero-knowledge proof
Soundness
Gas meter prover
Zero (linguistics)
Proof of concept
Cite
Citations (22)
In 2009, Gradwohl, Naor, Pinkas, and Rothblum proposed physical zero-knowledge proof protocols for Sudoku. That is, for a puzzle instance of Sudoku, their excellent protocols allow a prover to convince a verifier that there is a solution to the Sudoku puzzle and the prover knows it, without revealing any information about the solution. The possible drawback is that the existing protocols have an extractability error with a non-zero probability, or need special cards (such as scratch-off cards). Thus, in this study, we propose new protocols to perform zero-knowledge proof of knowledge for Sudoku using a normal deck of playing cards with no extractability error. Our protocols can be easily implemented by humans with a reasonable number of playing cards.
Gas meter prover
Zero-knowledge proof
Zero (linguistics)
Proof of concept
Cite
Citations (60)
Zero-knowledge proof is one of the techniques implemented in a variety of data security applications. ZKP is a security procedure between two parties, one as the prover and the other as the verifier. The prover and the verifier exchange information without allowing any kind of sensitive information to leak. In this paper, we mention the challenges and limitations that face the zero-knowledge technique when utilized in authentication and privacy protection processes in different environments. We help to produce improvements to the most common zero-knowledge protocol to show many factors that would have greatly contributed to the success of the authentication process.
Zero-knowledge proof
Gas meter prover
Zero (linguistics)
Cite
Citations (0)
The seminal result that every language having an interactive proof also has a zero-knowledge interactive proof assumes the existence of one-way functions. Ostrovsky and Wigderson (ISTCS 1993) proved that this assumption is necessary: if one-way functions do not exist, then only languages in BPP have zero-knowledge interactive proofs. Ben-Or et al. (STOC 1988) proved that, nevertheless, every language having a multi-prover interactive proof also has a zero-knowledge multi-prover interactive proof, unconditionally. Their work led to, among many other things, a line of work studying zero knowledge without intractability assumptions. In this line of work, Kilian, Petrank, and Tardos (STOC 1997) defined and constructed zero-knowledge probabilistically checkable proofs (PCPs). While PCPs with quasilinear-size proof length, but without zero knowledge, are known, no such result is known for zero knowledge PCPs. In this work, we show how to construct “2-round” PCPs that are zero knowledge and of length ~ O(K) where K is the number of queries made by a malicious polynomial time verifier. Previous solutions required PCPs of length at leastK 6 to maintain zero knowledge. In this model, which we call duplex PCP (DPCP), the verifier first receives an oracle string from the prover, then replies with a message, and then receives another oracle string from the prover; a malicious verifier can make up toK queries in total to both oracles. Deviating from previous works, our constructions do not invoke the PCP Theorem as a blackbox but instead rely on certain algebraic properties of a specific family of PCPs. We show that if the PCP has a certain linear algebraic structure — which many central constructions can be shown to possess, including [BFLS91,ALMSS98,BS08] — we can add the zero knowledge property at virtually no cost (up to additive lower order terms) while introducing only minor modifications in the algorithms of the prover and verifier. We believe that our linear-algebraic characterization of PCPs may be of independent interest, as it gives a simplified way to view previous well-studied PCP constructions.
Gas meter prover
Zero-knowledge proof
Zero (linguistics)
Random oracle
Cite
Citations (0)
A zero-knowledge proof system of knowledge is a protocol between two parties called the prover and the verifier. The prover wants to convince the verifier that he “knows” the proof of a given theorem without revealing any additional information. This is different from a zero-knowledge proof system of membership where the prover convinces the verifier only of the veridicity of the statement. Zero-knowledge proofs of knowledge are very useful tools in the design of secure protocols. Though, the concept of a proof of knowledge is a very subtle one and great care is needed to obtain a satisfying formalization. In this paper, we investigate the concept of a zero-knowledge proof of knowledge in the noninteractive model of [5, 61. Here, the prover and the verifier share a short random string and the only communication allowed is from the prover to the verifier. Although this is a simpler model than the interactive one, still formalizing zeroknowledge proofs of knowledge is a delicate task. The main results of the paper are the following e We present formal definitions for the concept of non-interactive zero-knowledge proofs
Gas meter prover
Zero-knowledge proof
Proof assistant
Zero (linguistics)
Cite
Citations (46)
We prove that every problem in NP that has a zero-knowledge proof also has a zero-knowledge proof where the prover can be implemented in probabilistic polynomial time given an NP witness. Moreover, if the original proof system is statistical zero knowledge, so is the resulting efficient-prover proof system. An equivalence of zero knowledge and efficient-prover zero knowledge was previously known only under the assumption that one-way functions exist (whereas our result is unconditional), and no such equivalence was known for statistical zero knowledge. Our results allow us to translate the many general results and characterizations known for zero knowledge with inefficient provers to zero knowledge with efficient provers.
Gas meter prover
Zero-knowledge proof
Zero (linguistics)
Cite
Citations (44)
Cryptography and complexity theory have gained a lot of importance because of zero-knowledge proofs. The motive behind zero-knowledge proofs are to provide an obfuscation to the verifier, so that the verifier will not understand the information sent by the prover. Zero-knowledge proofs are normally used to verify a prover's theorem to a verifier, in such a way that the verifier will not be able to discover any supplementary evidence other than the proof given to him. An enigmatic conception was formalized, that lead to the formation zero-knowledge proof systems. In this paper, we have reviewed different zero-knowledge argument / proof techniques. We have also reviewed the proof system implications in the presence of malicious prover and malicious verifier. Examples related to zero-knowledge argument systems are also given.
Zero-knowledge proof
Gas meter prover
Argument (complex analysis)
Zero (linguistics)
Cite
Citations (2)
Gas meter prover
Zero-knowledge proof
Statement (logic)
Zero (linguistics)
Identification
Realization (probability)
Cite
Citations (14)