Tag Info

Hot answers tagged

12

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 ...


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 ...


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 ...


5

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)$; ...


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

Assumption: the normal user can read the message, which is displayed on his screen. Generic attack: the user uses a camera to take a snapshot of the screen when the message is displayed. And voila! What you seek is demonstrated to be impossible.


4

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 ...


4

She can generate a key-pair and include the public key in the book. Having the private counterpart she can at any time proove that she wrote the book by signing an arbitrary statament.


4

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^* ...


4

More generally, any encryption that is commutative can be used because then: $$(D_k \circ D_K \circ E_k \circ E_K)(m) = m$$ I.e. Bob can encrypt the ciphertext $E_K(m)$ with a new key $k$, then gives that to Alice for decoding with $K$ and finally decodes it himself with $k$. Stream ciphers are commutative, as is exponentiation modulo $n$ (used in RSA) ...


3

Zero-knowledge proofs of knowledge basically allow Alice to convince someone beyond a reasonable doubt that she knows a certain piece of information (i.e., the answer to a certain question), without revealing what exactly that information is. One simple example involves the discrete logarithm problem, which you might be familiar with: given a (large) prime ...


3

Short answer: YES. (Though see the note on "hashed" below.) Intro The remote authentication protocols where server does not know the plaintext password are generally known as augmented password authenticated key agreement (PAKE). You can see this wikipedia article for details of PAKE algorithms (augmented and non-augmented). You may find this reference ...


3

If they don't trust the server they sure shouldn't send any money. The "trusted" third party is used to solve the problem of participants who don't trust each other. So by definition, your problem can only be somewhat mitigated, not solved completely. I'm not sure what you mean by "provably fair". If the server can't prove he cannot cheat, it's not provably ...


3

The problem is one of notation for modular arithmetic, at the point of the question reading if y^2 equals (x * v^e) % n then.. Likely the textbook is about if $y^2\equiv x\cdot v^e\pmod n$ then.. By definition of $a\equiv b\pmod n$, that holds if and only if $n$ divides $a-b$ (or equivalently: $|b-a|$ is a multiple of $n$). In the question, 437 ...


3

In very simplified terms, a NI-ZK proof works in 2 stages: First, you run the protocol with a simulator (who is just a verifier, but the random choices are done differently), and then you can give the transcript of the protocol to anyone and convince them that the proof is real. The most important ways to achieve this are: In the random oracle model ...


3

You said in the comments, that $H$ can be a random oracle, but in this case it needs to be a random oracle. Basically your protocol is a Schnorr protocol in disguise, and you throw in the Fiat Shamir heuristic to make it noninteractive. But considering your questions: Well, the basic Schnorr protocol is not zero-knowledge. There exists no simulator for ...


3

The motivation, to me, is that in reality you can consider any router on the internet to be successfully executing an "intruder-in-the-middle" attack just by forwarding messages unchanged. After a successful execution of the identification scheme, Bob knows that someone on the channel is Alice, which is all the protocol was hoping to achieve. It was ...


3

A zero-knowledge proof is a protocol by which the Prover demonstrate to the Verifier that he knows the solution to a given problem, without giving to the Verifier any additional information about the solution -- that is, no information that the Verifier could not already obtain alone. In the case of the discrete logarithm, the y value is not part of what the ...


2

A homomorphic cryptosystem has some operation $*$ on ciphertexts that correspond to some other operation $\circ$ on plaintexts, that is $$\mathcal{D}(c_1 * c_2) = \mathcal{D}(c_1) \circ \mathcal{D}(c_2).$$ Typically, the ciphertexts you get by applying $*$ look like ciphertexts that are produced by the encryption algorithm. For Damgård-Jurik, $*$ is ...


2

First, before I answer your questions: Money rewards are not forbidden, as far as I know, but that's not how it goes here. Feel free to check out the according question on crypto-meta. I think, there are few conceptual misunderstandings in your scenario. First, a signature scheme uses the private key (also called signing key) to sign messages, and it uses ...


2

There are a couple of problems with this zero knowledge proof; it isn't explained very well it gives the verifier more information than it claims to Lets go through them in order: It isn't explained very well The problem is that the terminology it uses in the proof statement differs from the terminology they use in the protocol description; for ...


2

The original question was: Alice knows: $a,b$ and $x$ such that $a^{(x\cdot x)} = b$ Bob knows: $a,b$ and DrLecter referenced this paper (fixed the link), which covers the question. Now, the question was changed to Alice knows: $b$ and $x$ such that $x^x=b$; Bob knows: $b$. The given structure was: ... multiplicative group $G$ ...


2

Below is one possibility, but for a large set of values not a really efficient one as the work and the size is linear in the number of values. I additionally added a variant where the work and proof size is constant. Standard OR Proof Say we are working in a cyclic multiplicative group $G$ of prime order $p$ with generators $g$ and $h$ (such that the ...


2

Alice generates a signature key-pair and puts $\;$ the fact that she's using this identity-proving construction $\;\;\;\;$ and $\;$ the digital signature scheme $\;\;\;\;$ and $\;$ the prefix-free code $\;\;\;\;$ and $\;$ the verification key into the book, and keeps the signing key. (Let "||" denote concatenation.) For interactive verification, the ...


2

Proving uniqueness You can prove that the elements are unique in $O(m)$ time and space by pre-sorting them and then giving a zero-knowledge proof that they are in sorted order. Details follow. Assume the elements of $\Sigma$ are integers in the range $[0,K-1]$, where $K$ is a constant chosen in advance and made public. Pick a large prime $p$ and a group ...


2

You can use the techniques in the paper you have linked to show that a list of commitments $C_1,\ldots,C_m$ to the elements in $\Sigma$ are elements in $\Psi$ (the commitment scheme of choice are information-theoretically hiding Pedersen commitments, which are also used in the linked paper) . Basically, this works by the "owner" of the set $\Psi$ publishing ...


2

Let $q$ be given by $\:$ for all $n$, $\: q(n) = 1 \;\;$. $\;\;\;\;\;$ For every $P^*\hspace{-0.05 in}$, every $\: x\in L_R \:$, $\frac{p-\kappa(|x|)}{q(|x|)} = \frac{p-\kappa(|x|)}1 = \:p\hspace{-0.04 in}-\hspace{-0.04 in}\kappa(|x|) \: \leq \: p\hspace{-0.04 in}-\hspace{-0.04 in}0 \: = \: p \: \leq \: 1 \;\;$. For every $P^*\hspace{-0.05 in}$, every $\: ...


2

A just has to calculate $y=(x*v^e)^{\frac{1}{2}}$ and send it to B. Yes, if that was easy, the protocol would be breakable. However, finding square roots modulo a composite number is as difficult as factoring that number. See: Quadratic residue problem on composite integers


2

Yes, it is possible. Actually, any statement in NP can be proven in zero knowledge. This means that if something can be proven by releasing some information, it is possible to prove the same without releasing any information, i.e. in zero knowledge.


2

In context of interactive proof systems (including zero-knowledge proofs) completeness means the same as the term correctness as used for many other (interactive) cryptographic schemes or protocols. I guess that's mainly due to historical reasons (there are even some people that use correctness instead of completeness in context of zero-knowledge proofs). ...



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