# Tag Info

16

A non-interactive ZK proof is when you play with yourself. Or, more accurately, with an impartial version of yourself. In a normal ZK proof, the prover first issues a bunch of commitments, then the verifier issues challenges that the prover complies with; this proves anything only as long as the verifier is assumed to issue challenges normally without any ...

16

I assume you are familiar with $P$ and $NP$. Also, my knowledge of SNARKs is based mostly on the work of Parno et al., other work may differ in some fine details. So, a SNARK is a succinct non-interactive argument of knowledge. Leaving the "knowledge" part aside for the moment, let's look at "plain" succinct non-interactive arguments (called SNARGs in the ...

12

If k is a constant, such as 3, it becomes possible to select a pair (N,g) such that the discrete log of k to the base g is known, which would enable the two-for-one guessing attack again.

12

This is a classical example. Here is the proof system… Bob gives two gloves to Alice so that she is holding one in each hand. Bob can see the gloves at this point, but Bob doesn't tell Alice which is which. Alice then puts both hands behind her back. Next, she either switches the gloves between her hands, or leaves them be, with probability $1/2$ each. ...

10

Schnorr can be proven zero knowledge when the challenge $e$ is restricted to a small set (typically $0$ and $1$). Recall that in the Schnorr protocol, the prover knows the logarithm $u$ of $y$ to base $g$. He chooses a random value $r$, computes $a = g^r$ and sends $a$ to the verifier. The verifier chooses a random challenge $e$ from some set and sends it ...

9

I don't believe your protocol meets the standard definition of Zero Knowledge Proof, as a cheating verifier can learn more information about the secret than allowed. In particular, suppose we have a cheating verifier (server) that has a list of one million potential passwords. Then, he can run your protocol with a client that knows the password, run the ...

8

Yes. Such proofs are possible for El Gamal. It involves a zero knowledge proof of equality of a discrete log, together with the homomorphic property of El Gamal encryption. Recall that given $E(a)$ and $E(b)$, anyone can form $E(a/b)$ using the homomorphic property of El Gamal. Suppose $E(a/b)=(r,s)=(g^k,h^k a/b)$ (where $g$ is the generator and $h$ is ...

7

The security goal behind SRP is that an attacker that could either pretend to be a client (and attempt to log into a server that knows the key), pretend to be a server (and allow clients that know the key to attempt to log in), or actively monitor (and modify) the communications between a valid client and a valid server, would learn nothing from an exchange, ...

7

Verifiable to someone who already has the correct answer Verifiable to whom? Someone else with the correct answer? Then you may be able to get away with a salted bcrypt hash; e.g., you can easily say make a cryptographically strong one-way hash of an answer: >>> import bcrypt #using py-bcrypt python module >>> hashed_answer = bcrypt....

7

Here's what can happen if you don't do this verification: Suppose Alice, Bob and company generate their public key shares honestly, $h_2, h_3, ..., h_n$ Now, Snidely Whiplash (who is also a trustee) is the last to contribute his share, he selects a private key $x_{evil}$ and computes $h_{evil} = g^{x_{evil}}$. However, instead of sharing $h_{evil}$ as his ...

7

The GQ identification scheme is essentially a zero-knowledge proof of a value $x$ such that $x^\mu \equiv J \pmod N$ where $N$ is an RSA modulus and $(\mu,N)$ are system parameters and $J$ is known to the verifier and $x$ only known to the prover. Now your question is not directly concerned with the aforementioned proof where a user shows the possession of ...

7

By Theorem 3 on page 15 of this paper, no secure-with-abort protocol for equality of long strings can be within 1/5 of fair. If there is a protocol for equality on a domain of size at least 3 which is secure against honest-but-curious adversaries, then oblivious transfer protocols exist. If oblivious transfer protocols exist, then there are protocols for ...

7

I have written a tutorial on how to write simulation-based proofs. I think that it should be helpful.

7

Sigma protocols as-is are secure only for honest verifiers. However, they can be easily compiled into full-blown zero knowledge protocols. If you don't want interaction, then the Fiat-Shamir transform suffices, with security in the random oracle model. With interaction, you can do the transform at little cost using commitments based on DDH. For more ...

6

In the other answers, you'll find how to simulate a proof if you know $e$. This answer is meant to provide some "color commentary" on the other answers. It is a companion piece. Notation In step 1, Alice sends $g^r$. Call this value $a=g^r$. In step 3, Alice sends $r+se$. Call this value $b=r+se$. In step 1-3, one value is sent in each step: {$a,e,b$}. ...

6

Let me attack if you (the verifier) always select $b = 1$ as a random challenge. The zero-knowledge proof for QR. Let us recall the zero-knowledge proof for QR. The common inputs are $y$ and $x$ and the prover possesses a witness $w$ which satisfies $w^2 \equiv y \pmod{x}$. The prover generates a randomness $r \gets \mathbb{Z}_x$ and sends $a = r^2 \bmod{... 6 Alice can prove that the decryption of$C$is$M$. This can be done using zero knowledge proofs. Simple example: Suppose$C = (x,w)$is an ElGamal encryption of$M$under public key$y$, that is$(x,w) = (g^r, y^r M)$for some$r$. Suppose that the decryption key is$a$, that is,$y=g^a$. Then we know that$M = wx^{-a}$, or$x^a = w/M$. That is, the ... 6 Formally, this is all very complicated, but informally: An interactive proof is a conversation between a prover and a verifier that ends with the verifier either accepting or rejecting. The interactive proof can be zero knowledge, in which case a cheating verifier does not learn anything new by talking to the honest prover. The interactive proof can be a ... 6 The description of this "kid zero knowledge" example follows the strucure of how interactive proofs that are zero-knowledge usually work: The prover sends a commitment (walks into one of the two sides) The verifier challenges the prover (tosses the coin to decide which side the prover should walk out) The prover gives a response (walks out the side the ... 6 Use the exponential variant of ElGamal, where the plaintext is encoded in the exponent. Elliptic curve ElGamal is fine. In fact, any public key cryptosystem which allows raising ciphertexts to a power such that this operation corresponds homomorphically to multiplication for the plaintext. Your commitments are$c_x = \mathsf{E}(x)$;$c_y = \mathsf{E}(y)$; ... 6 Guillou and Quisquater (link) present a zero-knowledge proof of an RSA signature. Basically, the scheme is as follows: Public knowledge: RSA modulus$n$, public RSA exponent$v$, preimage$X$. Secret knowledge for prover:$A$, such that$A^v = X \mod n$.$$\begin{matrix} \mathcal{P} & & \mathcal{V} \\ r \xleftarrow{\$} \mathbb{Z}_n^* \phantom{\...

6

Yes. The easiest way is if $K$ is an RSA private key, and Bob has the public key. Then, here's how it works; we'll call the ciphertext that Bob has $C$: Bob selects a random number $r$, and computes both $C \cdot r^e \bmod N$ and $r^{-1} \bmod N$ (where $e$ and $N$ are the public exponent and the modulus from the public key) Bob sends $C \cdot r^e \bmod ... 6 SRP does DH key exchange with authentication, and has the capability to also authenticate the server as well (though usually the server is authenticated by keeping the verifier secret). If the key is generated strictly from a password and salt, with the salt stored on the server, you can do a dictionary attack on the verifier (e.g. if the server is ... 6 This does seem to be zero knowledge; as you say, you don't actually commit to the adjacency list. Rather, you commit to a series of edges, in random order. Regarding the question: First, your assumption is that$n^2$commitments, each to a single bit, is more expensive than$|E|$commitments, each to$2\log n$bits (to encode two numbers for the edge). This ... 6 I'm no FIPS expert but I strongly suspect the answer is no. FIPS is incredibly restrictive and laughably behind the times. To evaluate those algorithms that don't appear in FIPS, first make sure their component parts are secure (maybe even built with FIPS algorithms as subroutines). Then, if there are known answer tests anywhere, maybe from the authors of ... 6 There are certainly ZK proof systems which are not known to be POK, and for which no knowledge extractor is known. For example, take the Goldreich-Kahan 4-round ZK proof system. However, do we know of a non-trivial proof system that is provably not a proof of knowledge? Not that I know of. 5 Let$\#G$denote the number of elements in the group. In your particular case,$\#G = \varphi{}(n)$(and even$\#G = n-1$if$n$is prime). Let$\xleftarrow{\$}$ denote a uniformly random sampling from a finite set of elements. Furthermore, $\mathbb{Z}_m$ denotes the set of non-negative integers smaller than $m$ and $\stackrel{?}{=}$ denotes a equality test ...

5

Protocols for selecting uninfluenced random numbers typically fall into two camps: random beacons and coin-tossing protocols. A random beacon is a source of randomness that is agreed by everyone to be unpredictable. For example, you can funnel a large amount of financial data into a small random number. While you cannot prove you didn't know what the ...

5

If Alice guesses $e$ then she chooses a random value $x$ and computes $h = g^x v^{-e}$, a value which she sends to Bob at step 1. At step 3, Alice sends $x$. When Bob does step 4, he recomputes $g^x v^{-e}$ and finds $h$, and he is happy. However, Alice does not know $s$. The "commitment" at step 1 is a way for Alice to say: "I know a $r$ corresponding to ...

5

Suppose that we have Eve, that knows what $e$ is going to be, and does not need to know the prover's private key $a$, just the public one $v$. She then sends $g^k \cdot v^{-e}$ as her first "move", where she can choose her own $k$ (you can modify the $k$ in different plays to make it all look nice and random...). The verifier sends $e$ as expected, of ...

Only top voted, non community-wiki answers of a minimum length are eligible