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


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.


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

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

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

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

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

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

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.


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

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

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

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


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



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