13

An interactive or non-interactive protocol is said to be sound for a language $\mathcal{L}$ if it is "hard" for a (malicious) prover $\textsf{P}$ to convince a verifier $\textsf{V}$ of a statement $I\not\in\mathcal{L}$. Depending on how "hard" it actually is for $\textsf{P}$ to cheat, we either get a (interactive or non-interactive) proof ...


5

It would not affect this at all. Note that under reasonable complexity hardness assumptions, it holds that P=BPP. So, even though we don't know how to prove this unconditionally (and in fact seem far away from doing so), it is what we assume to be correct. I am not sure why you would think that this would affect the Fiat-Shamir heuristic. Even if P=BPP it ...


5

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


5

Yes, there are examples of non-constant round interactive protocols that are unsound when the Fiat-Shamir transform is applied even in the random-oracle model. Note that for constant-round protocols soundness in the random oracle model was proved by Pointcheval and Stern [PS00] -- that is, any constant round interactive protocol (that has negligible ...


4

You are correct about the attack, given the way you have defined the Fiat-Shamir-transformed protocol. Since Fiat-Shamir is subtle for multi-round protocols, the standard way to resolve this is to use parallel instead of sequential composition. Start with a protocol that has soundness error 1/2, and run it $k$ times in parallel (not in sequence) to amplify ...


4

In the random-oracle model, it has been shown that the Fiat-Shamir transform preserves the soundness and zero-knowledge of certain families of zero-knowledge (proof of knowledge) protocols (e.g., Sigma protocols) -- see [§5 in BR93,PS00,FKMV12]. Instantiating the random oracle with a concrete hash function is a much harder prospect, but there have been some ...


4

Since there are no answers here yet, I'll write down my own opinion. The Fiat-Shamir heuristic for augmenting Sigma-protocols (or possibly any 3-move honest-verifier ZKPoK?) works as follows: For the problem statement $X$ and first prover message $A$, the prover self-generates the challenge $e = H(X,A)$and uses it to generate its final response $z$. Note ...


3

$\newcommand{\NP}{\mathsf{NP}}\newcommand{\lang}{\mathcal{L}}\newcommand{\rel}{\mathcal{R}}\newcommand{\bin}{\{0,1\}}$ Let $\lang\subseteq\bin^*$ be any $\NP$ language with a corresponding $\NP$ relation $\rel$. Now assume that every statement in $\lang$ has a short witness, i.e. a witness of constant (as in your question) or at most logarithmic length. I.e. ...


3

Knowledge of $p$ and $q$ makes computing square roots modulo $n=pq$ easy. Using the Tonelli-Shanks algorithm, one may determine square roots modulo $p$ and $q$ individually and then combine them to a square root modulo $n$ using the Chinese remainder theorem. Therefore, anyone who knows $p$ and $q$ can compute the prover's private key (which is a square ...


3

The philosophy behind the extractor and knowledge is that if the prover can generate the proof, then it could itself run the extractor. Therefore, if it can prove, then it knows the witness. If the extractor runs in super polynomial time, then the prover itself cannot run the extractor. Note that if you took this to an extreme, then in exponential time it is ...


2

The first problem is, that you calculated $v_i$ wrong right at the start. $$v_i = s_i^2 \mod n$$ This means: $$v_1 = 5^2 = 25 \mod 77$$ $$v_2 = 12^2 = 67 \mod 77$$ $$v_3 = 37^2 = 60 \mod 77$$ Then at the end you have: $$(x \cdot \prod_i v_i^{a_i}) = 67 \cdot 25 \cdot 1 \cdot 1 = 58 \mod 77$$


2

In order to convert a 3-move id-scheme to a digital signature you have to replace the request (or the challenge) by the value of a secure hash function applied to the message (this method is called Fiat-Shamir method). In Sterns's id-scheme you have to choose a random element from the set $\{0,1,2\}$ for your message. That is $H(m)\in \{0,1,2\}.$ For ...


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

If $b$ was always the same value, you could convince the Verifier that you have the private key even though you actually don't! Case $b = 1$: Instead of sending $x = {\text{randNum}}^2 \bmod n$, the false Prover can send $x = {\text{randNum}}^2 / \text{pubKey} \bmod n$. Assuming the Verifier sends $b = 1$, the false Prover can then send $\text{randNum} \...


2

Solution 1 has some weakness when the verifier is malicious. If the prover's private key $a$ is used for decryption, Solution 1 provides the verifier with a decryption oracle, i.e., a malicious verifier can decrypt any ciphertext encrypted with the public key $v$. On the other hand, Solution 2 reveals nothing about the private key $a$ because the random ...


2

Recall that in strong existential unforgeability for digital signatures, we want it to be the case that even after seeing many signatures under different instances, it should still not be possible to create a new signature unless you know the secret key (equivalently witness in a NIZK). So, one can use a NIZK to design a digital signature (of knowledge), ...


2

Pedersen commitments would appear to address your problem. A Pedersen commitment is a value $t = g^w h^r$ (for the witness value $w$ and a random value $r$); someone cannot recover $w$ from that value (actually, even a computationally unbounded adversary cannot do that). This is true even if $w$ is of low entropy. And, it is straight-forward to come up ...


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

These are equivalent. Given that the first challenge is a deterministic function of the statement and $\alpha_1$, it makes no difference. What is crucial is just to include the statement, and the entire transcript to that point. (Note that anything that is deterministically dependent on other things doesn't have to be included in the transcript.)


2

You can find the security proofs for 5-round Fiat-Shamir: Ming-Shing Chen and Andreas Hülsing and Joost Rijneveld and Simona Samardjiska and Peter Schwabe: From 5-pass MQ-based identification to MQ-based signatures. Asiacrypt 2016. https://eprint.iacr.org/2016/708 Özgür Dagdelen, David Galindo, Pascal Véron, Sidi Mohamed El Yousfi Alaoui, and Pierre-Louis ...


2

No. Since 0x1234, 0x4321 is public and thus known ahead of the execution, the prover knows the challenge c before sending t. This violet the requirement of the sigma protocol: c is sent to P after t is received.


2

Quick remarks: the Fiat-Shamir transform is implemented with a standard hash function (e.g. SHA-256 or SHA-3). Random oracles do not exist in the real world: it is only in the security analysis that the real hash function is modeled as a random oracle to get heuristic guarantees about its real-world security. In most $\Sigma$-protocols (Schnorr included), ...


1

The paper by Goldwasser and Tauman is another paper in the series of the failure of the random oracle model; its novelty is applying this principle to the Fiat-Shamir paradigm and interactive protocols. However, an easier place to start is the seminal paper of Canetti, Goldreich and Halevi, called The Random Oracle Methodology, Revisited. This paper shows ...


1

No, sending both parts of the proof together does not create any additional risk. Notice that at the end of the protocol, Victor knows the same set of values, regardless of whether it has been split into two rounds or not. So whatever he would be able to achieve in "one-round" version, he can still achieve after the second round of the two phase protocol.


1

If the challenge is calculated as $H(\Sigma_1)$ the transform is called the weak Fiat-Shamir (wFS) transform. On the other hand, when the challenge is computed as $H(x\mathbin\Vert \Sigma_1)$ the transform is called the strong Fiath-Shamir (sFS) transform. In scenarios where the attacker can choose adaptively the statement she would like to prove, the proof ...


1

I think you have the verification of Fiat Shamir wrong. The proof consists of $(h,r)$ and $y$ which is public anyway and only the relation $h = H(y,g^r y^h)$ is checked. As a result in your first case the proof is trivially valid. Your second case is interesting as it is not secure against an adaptive adversary. There is a paper by David Bernhard, Olivier ...


1

So the corresponding $v_i$ for $s_1$ would be 2. If $n=pq=11∗19=209$, then does this mean that $s_i = \sqrt{2} \bmod n$? What they mean by "square-root of $x$" is the value $y$ that is a solution to $y^2 \equiv x \pmod n$; as there are multiple solutions (in the cases that at least one solution exists), then by a random solution, they mean to pick one ...


1

As Natanael pointed out, if you are willing to make very strong assumptions, SNARGs can be used to give proofs of constant size, independent of the size of the statement to be proven. However, these proof systems are in general not UC-compatible (see e.g. this paper). You have two natural alternatives: 1) use NIZKs with "almost optimal size", i.e., of size $...


1

Man-in-the-Middle attacks are possible for almost all zero-knowledge proofs. Victor can copy everything sent by Alice, the prover, to Bob, the verifier, and reversely to impersonate the Alice. In short, Victor can relay every message. To mitigate this, time limit can be used to prevent the relay. However, this may not be enough. A better solution is first ...


1

Warning: Oversimplified. Most, if not all interactive Zero-Knowledge proofs rely on the randomness of the verifier. Taking the Ali Baba cave example, since Alice cannot predict what path Bob wants her to come out of, it is statistically improbable that she will be able to fake the proof, especially when this "experiment" is done multiple times. In case you ...


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