Tag Info

Hot answers tagged

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


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


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

Rough scetch, assuming Bob is standing next to you in the same room: Prepare cards with the correct numbers on them Lay down the cards according to the setup, face up Lay down the remaining cards with the correct solution, face down, so that Bob can't see them. Now you let Bob choose one column, row or sector. You pick up the cards in that row, column ...


3

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


3

$ax^2+bx+c=0$ is the general expression of a quadratic equation in one variable. Here, there are more than one. You may want to look into how the degree of a multivariate polynomial is defined.


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


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

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

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


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

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

Without a sign the verifier learns that the number he received is a QR modulo n. Whether a number is a QR is a hard problem as he does not know the factors of n.


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


2

Having a client (ex. your web browser) use zero-knowledge proofs to authenticate itself to a server only makes sense if the server knows about the client's public key in advance, and if the client keeps the same private key forever. So you could have the client-side generate a keypair when you register your account, and the server records your public key ...


2

You are on the right track. However, as Ricky Demer points out in the comments, your suggestion would not work because the input is encrypted with different public keys. To fix this you need to use the properties of the threshold-encryption scheme. In a threshold-encryption scheme the players run a key-generation protocol in order to generate a common ...


2

The common reference string in NIZK does not have to be uniformly distributed. It is to be sampled from whatever distribution the NIZK protocol specifies. However, the common random string in NIZK does have to be uniformly distributed, and the setup strings in NIZK also have to be uniformly distributed.


2

I believe a zero knowledge proof that $-1$ is a quadratric nonresidue would accomplish that. If we know that $n$ has two prime factors, and that $n \equiv 1 \pmod{4}$, then $n$ is either a product of two primes both $1 \bmod 4$, or two primes both $3 \bmod 4$. If it were the former, then $-1$ is a QR modulo $p$, and $-1$ is a QR modulo $q$, and hence $-1$ ...


2

This has some issues, with both soundness and zero-knowledge. The issue with zero-knowledge is that an eavesdropper who knows $L$ and overhears legitimate traffic can compromise the secret quite easily. While factoring is hard, taking a GCD is very efficient. That means that given $M=pr$ and $L=pq$, an eavesdropper Eve can efficiently compute $\gcd(M,L)=p$. ...


2

There are two answers. One, go non-interactive with the Fiat-Shamir transform. This requires the Random Oracle Model (ROM) to analyse, but the ROM is standard enough in cryptography and ROM proofs have been used in practice for long enough that this shouldn't worry you. It gets you full ZK, curiously enough for the exact same reason that plain Schnorr is ...


1

Soundness usually means "you can't prove a false statement". There are different ways to formalise this but usually the probability of an efficient algorithm coming up with a false statement and a proof that verifies is negligible in some parameter (such as the length of the statement). Soundness can be defined for any proof scheme, including ones that are ...


1

The initial idea of Fiat and Shamir was to eliminate the interaction in public coin protocols (note that public coin means that the random choices of the verifier are made public) and was used to convert three move public coin identification scheme into conceptually simple signature schemes (it has later been proven by Pointcheval and Stern that under the ...


1

U-Prove TokenID is a hash output, so it may be not the best way to prove "not the same" statement. One would also consider inequality proof for a subset of user attributes instead. For each such attribute pair, "not the same" would mean an inverse exists for attribute difference, modulo group order. One would prove knowledge of such inverses while keeping ...


1

To prove that product holds over integers, one would start from commitments with groups of a hidden order. That is, proving party should not know order of the group, which is the case with RSA-like multiplicative group. Consider Prover responses $\rho_x = tx + \alpha_x$, $\rho_y = ty + \alpha_y$, $\rho_z = tz + \alpha_z$ to Verifier challenge $t$ with ...


1

A straightforward way to prove this when you can prove AND as well as OR statements about discrete logarithms is to take all the $K=\binom{M}{N}$ subsets $A_i=\{A_{i_1},\ldots,A_{i_N}\}$ with $N$ elements of points from the set of your $M$ points and prove the statement $$PK\{(\alpha_1,\ldots,\alpha_N): \bigvee_{j\in K} \big( \bigwedge_{A_{j_i}\in A_j} ...


1

You may be aware of the fact that zero-knowledge proofs for any language in $NP$ can be constructed if you have a zero-knowlege proof for any $NP$-complete language. Then you can reduce your original language to the $NP$-complete one in polynomial time and you are done (more precisely you reduce the instance and the corresponding witness). As the ...


1

Firstly, note that Groth-Sahai framework doesn't provide proofs of knowledge of exponents, because all commitments to exponents in it are computationally irreversible. It only provides proofs that show that such exponents exist. That is, a prover can claim to know $x$ but actually only know $\mathcal{A}^x$ for some $\mathcal{A}$, and still be able to produce ...


1

Because we are working modulo $n$. There's not much more to say. There's no reason why any honest user would ever want to use a larger value. You might want to review modular arithmetic and its use in cryptography.



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