Hot answers tagged

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


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


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 have written a tutorial on how to write simulation-based proofs. I think that it should be helpful.


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


5

There are many ways of doing this. A very nice read (but with informal presentation) is this paper by Fagin, Naor and Winkler on Comparing Information without Leaking It. A very fast protocol exists which requires a single oblivious transfer for every bit. Let $n$ be a security parameter; say $n=128$, and let $\ell$ be the bit-length of the inputs. For ...


5

What does this mean, exactly? The purpose of the environment is to model "everything else happening in the universe" besides the protocol execution. In the UC model, the adversary is allowed to talk to the environment during the execution of the protocol. So UC security means "security no matter what else is going on in the world, even if other things ...


5

If one-way functions exist, then there is a distribution over graphs (or SAT formulas, or ...) having the property you're asking for. In short, just put the OWF through the Cook-Levin reduction. In a little more detail, Cook-Levin transforms the NP witness-finding question "what is a preimage of $y = f(x)$?" (for random unknown $x$) into the NP ...


5

Even following your edits, there's still some confusion about honest verifier zero knowledge and plain-old (i.e., "possibly malicious verifier") zero knowledge, which is a much stronger property. Your description of HVZK is essentially correct, but with the following clarifications: A 3-move protocol between a prover P and a verifier V for a language ...


5

The question mentions FIPS 140-2 Level 3 compliant. I answer this as if the question had said the intent is to validate the product as FIPS 140-2 Level 3. This may sound like hairsplitting, but there are many modules claiming to be FIPS 140-2 compliant, which factually could not be validated without large changes to functionality. FIPS 140-2 really intends ...


4

I guess you are talking about Figure 5.3? It is said that the Schnorr proof (sigma protocol for discrete log relation) is insecure against cheating verifiers - it is only honest-verifier zero knowledge. Sigma protocols are always only defined in the honest-verifier zero-knowledge setting. To see why a cheating verifier is a problem in Figure 5.3 think ...


4

There is quite a bit of confusion in your question. First, differentiate between the real and ideal models. The adversary in the ideal model sends the adversary's input and gets its output (and can also sometimes determine if the honest party gets output, depending on the model). We often call the ideal adversary a "simulator" since this is how we build the ...


4

One could split both secrets into smaller parts, commit to parts and "gradually" open that commitments to each other, so that no party is better than (ahead of the other) one such part. For example, let secret be a big number split into bits. With an additively homomorphic bit commitment scheme, the other party could verify that bit commitments correspond ...


4

This cannot be done. It is provably impossible. In order to explain this in technical terms, what you are looking for is a FAIR protocol to compute equality of long random strings (I added the latter since it adds a constraint and so in theory could make it easier). In any case, if I had such a protocol, then I could toss a fair unbiased coin. Here is the ...


3

Answering the question in your title (and not addressing your proposed alternative which I don't quite understand) there is a zero knowledge proof of password protocol "SRP" which is fast and effective. SRP does not seem to have been given as wide publicity as it should get. Having implemented it, and being an advocate of its use, I don't really understand ...


3

The simplest example I know of is actually for a pathological case. Namely, it is presented in Chapter 2 of the book of Hazay and Lindell as an example of a two-party MPC protocol which is secure against a malicious adversary but not against a semi-honest one (in the classical sense, for this reason they prefer the notion of augmented semi-honest ...


3

If you use a one-time pad as your encryption function then this simplifies to a proof that Alice knows some $F$ that hashes to $H$. $K$ can be trivially derived from $F$ and $E(K, F)$ by xor-ing. An interactive zero-knowledge proof of this simpler problem - Alice proving she knows a pre-image of $H(F)$ - would go something like this: You need to use a ...


3

Yes, you are right. In a proof, the soundness holds against a computationally unbounded prover and in an argument, the soundness only holds against a polynomially bounded prover. Arguments are thus often called "computationally sound proofs".


2

The objective of the simulator is to make the simulated world (often called the ideal world) indistinguishable from the real world (running the actual protocol). See my write-up on the UC framework here for more detail. In the proof setup, the entity attempting to distinguish between the two worlds is often assumed to provide the inputs to the parties. That ...


2

The probabilistic nature is not specific to special-honest verifier zero-knowledge but that's what zero-knowledge is about. With zero-knowledge you want to formulate that such an interactive proof does not leak any information besides the validity of the claim, as it is efficiently simulatable meaning that real and simulated transcripts are not ...


2

The simulator obtains "client $B$'s input" in the same way the simulator obtains $\:\{\hspace{-0.03 in}0,\hspace{-0.04 in}0\hspace{-0.03 in}\}\;$. Even in the real world, the server computes its response without using any secrets, that response is the only message $B$ receives, and (from your description) no other party gives any output. $\:$ Thus, it ...


2

Yes, it's okay. This is actually mentioned in passing in the SRP 6 design paper. Previous versions used a random $u$ where an attacker who saw (or could predict) it before revealing $A$ could compute $A = g^a v^{-u}$ and use this to effectively cancel out the long term secret. With $u$ derived from a hash, even if the attacker saw $B$, the dependence of $u$ ...


2

Consider a multiplicative group of an order $q$ generated by some $g$. For simplicity, let commitment be $C_1 = g^{L_1}$. Consider a proof of knowledge of $L_1$ committed to at $C_1$. At the first step of an interactive proof, choose some $L_2$ at random and send $C_2 = g^{L_2}$ to the verifying party. Second step, receive a challenge $c$. Third step, send a ...


2

Do you allow Bob to ask all the users having $F$ to encrypt, then to upload the file with a same secret key deriving from $F$ ? Here would be the principle of the tweaked protocol : all the users must encrypt the file with the same key which depends on the file (calculated via another hash). The key would be a kind of shared key, but which can only decrypt ...


2

I figured it out, it's quite simple actually. The $d$ values (and $r$ values) are all exponents and chosen from $\mathbb{Z}_q$. Thus all calculations on them directly take place in $\mathbb{Z}_q$. Applying mod $q$ (not mod $p$) to all of my calculations on $d$ and $r$ fixed any problems with calculations.


2

Sure they can, it's called the socialist millionaires problem. The most common solution is to use Yao's protocol: Alice sends a garbled circuit of the equality function to Bob, and then Alice use oblivious transfers to send the keys necessary for the evaluation of the circuit to Bob. Another option is to rely on additively homomorphic IND-CPA encryption: ...


1

This may look like a homework, so I would not present any complete "Ctrl-C Ctrl-V" -style solution. A proof for equality of logarithms was introduced at Chaum, Evertse and van de Graaf paper, "An Improved Protocol for Demonstrating Possession of Discrete Logarithms and Some Generalizations", Eurocrypt 1987. At the core, Prover shows that the same single ...


1

This is doable by (1) opening all commitments $B_k$ with standard responses $Q_{k}(z)$ that are linear in challenge, (2) proving that all $x_k \in \{0,1\}$ (with at most second-degree polynomials in challenge), and (3) proving $m$ polynomial identities for (at most) third-degree polynomials in challenge $$U_i(z) = T_{i,1}(z) T_{i,2}(z) T_{i,3}(z) $$ where ...


1

Yes it proves that $y \ne 1 \pmod{n}$ is not an $e$-th root. That is, no $x$ exists such that $x^e = y \pmod{n}$. In particular, if $e | \phi(n)$ then for any $x$ it holds that $\left( x^{ \frac{\phi(n)} {e}} \right)^e = 1 \ne y$. This probably means one last final conclusion designed as a homework. Regarding GQ protocol: prover will be unable to pick an ...


1

There are no relation we are currently aware of. The reason is as follows. The map $$k \mapsto (k G).x$$ is assumed to be a good pseudo random number generator. (The NSA infiltration of the Dual EC drgb has nothing to do with that fact). This basically says that k and r can be seen as independant random variables.



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