Recent Forum Posts
From categories:
page 1123...next »
Re: HW 5
nbitanskynbitansky 28 Jun 2019 00:37
in discussion Forum / Course Forum, Spring 2019 » HW 5

2.b. In an expected number of 10 rounds the attacker will be the leader. At this point, it can adaptively resample the seed S to guarantee that it is also the leader in the next round. This way the attacker will always be the leader and propose all the blocks (it can also gain control of the committee, and create forks etc, but that wasn't necessary for a satisfying answer).

3.a When generating an anonymous coin, generate also OTS keys $pk,sk$, then commit to both the serial number $S$ and to $pk$ (we don't publish in the clear either one). When paying a coin to some node $i$ publish both $S$ and a signature on $i$ with $sk$ and provide a ZK proof that there exists a commitment among all the anonymous coins to $S$ and a verification key $pk$ that such that the signature on $i$ is valid with respect to that key.

Re: HW 5 by nbitanskynbitansky, 28 Jun 2019 00:37
nbitanskynbitansky 27 Jun 2019 13:34
in discussion Forum / Course Forum, Spring 2019 » NIZK

- $3$-message protocols (without any repetition) has soundness $1/2$. Doesn't have FS. (This is what I call the basic protocol)
- $n$-sequential repetitions have soundness error $2^{-n}$ and is malicious ZK. Doesn't have FS.
- $3$-parallel repetition also has soundness error $2^{-n}$ but is not known to be malicious ZK, and is believed not to be. has FS under reasonable assumptions.

by nbitanskynbitansky, 27 Jun 2019 13:34
HW 5
daniel (guest) 27 Jun 2019 11:23
in discussion Forum / Course Forum, Spring 2019 » HW 5

Hi, can you please give us an answer sketch for HW 5 Q2 section b, and for Q3 section a?
I asked around and I don't think anyone got full points for this.

HW 5 by daniel (guest), 27 Jun 2019 11:23
daniel (guest) 26 Jun 2019 14:49
in discussion Forum / Course Forum, Spring 2019 » NIZK

When you say the repeated protocol, do you mean the basic protocol repeated in a sequential order?
I thought we said in class it is malicious ZK, but the version where you try to parallelize it, it is no longer malicious ZK.

If you do mean that the repeated protocol sequential protocol is not malicious ZK, then the basic protocol only gives us soundness error of 1/2, are there other known ways to reduce this error to be negligible and still preserving malicious ZK?

by daniel (guest), 26 Jun 2019 14:49
Re: NIZK
nbitanskynbitansky 26 Jun 2019 13:58
in discussion Forum / Course Forum, Spring 2019 » NIZK

Re Hamiltonicity, the basic, non-repeated protocol, is malicious ZK (in particular, it cannot have an FS function).
The repeated protocol is not known to be ZK, and in fact it is believed (and proved under reasonable assumptions) that it does have FS functions, and thus cannot be malicious ZK.

Re: NIZK by nbitanskynbitansky, 26 Jun 2019 13:58
Re: NIZK
eliadtsfeliadtsf 26 Jun 2019 06:41
in discussion Forum / Course Forum, Spring 2019 » NIZK

1. "Fiat-Shamir hash functions are believed to exists" means that we believe there exists a family of hash functions that if the hash is sampled at random from it, then the Fiat-Shamir version of any protocol remains sound. But if this is the case, then zero-knowledge against malicious verifiers cannot be preserved. In other words, Fiat-Shamir cannot preserve both soundness and malicious ZK.

2. Yes, the meaning is for x not in L.

Re: NIZK by eliadtsfeliadtsf, 26 Jun 2019 06:41
NIZK
daniel (guest) 25 Jun 2019 15:16
in discussion Forum / Course Forum, Spring 2019 » NIZK

I have some questions regarding lecture 10 and NIZK.
1. We proved that the Hamiltonicity protocl is HVZK, and it is mentioned on the first page that it is not hard to show that it is also malicious verifier ZK.

Corollary 4.3 states that If there exists a hash function H such that the Fiat-Shamir transform of, say, the Hamiltonicity protocol sound, the Hamiltonicity protocol cannot be ZK against malicious verifiers
and then you say that Fiat-Shamir hash functions are believed to exist.

So I don't understsnd how is this possible?

2. I'm not sure I understand claim 4.1, from the claim "make the verifier accept with probability at most (Q + 1)s"
Do you actually mean "make the verifier accept with probability at most (Q + 1)s for x not in L"
because if x is in L we want to make the verifier exist with probability 1, right?

Thanks.

NIZK by daniel (guest), 25 Jun 2019 15:16
eliadtsfeliadtsf 24 Jun 2019 05:42
in discussion Forum / Course Forum, Spring 2019 » Example Exam 2b

For both there is a solution (the solutions are different).

by eliadtsfeliadtsf, 24 Jun 2019 05:42
Nitzan P (guest) 23 Jun 2019 18:52
in discussion Forum / Course Forum, Spring 2019 » Example Exam 2b

A solution y=x−H(x)(modN) or to H(x+y)=x(modN)

by Nitzan P (guest), 23 Jun 2019 18:52

The revisited example exam can be found here.
The example exam with the solutions can be found here.

think why for each such y there is a solution.

Re: Example Exam 2b by eliadtsfeliadtsf, 22 Jun 2019 17:14

The question is indeed not well defined, I'll upload a fix tomorrow.
Given a collision resistant function H : {0,1}^{n} -> {0,1}^{n-1}, then for any t>= n, you need to show how to construct from it a collision resistant function H':{0,1}^{t} -> {0,1}^{n-1}. You right that the collision resistant is a property of a family of functions. So we can think of it as families (where n is the security level), but for the purpose of this question just show that from any collision for H' you can extract a collision for H.

Re: Example Exam 1a by eliadtsfeliadtsf, 22 Jun 2019 17:12
Example Exam 2b
Nitzan P (guest) 22 Jun 2019 14:41
in discussion Forum / Course Forum, Spring 2019 » Example Exam 2b

Hi

Q2b seems inconsistent. If the puzzle is defined by $y=x'-H(x') (mod N)$, then where did the $H(x+y)$ come from in the next line?

Thanks

Example Exam 2b by Nitzan P (guest), 22 Jun 2019 14:41
Example Exam 1a
Nitzan P (guest) 22 Jun 2019 14:11
in discussion Forum / Course Forum, Spring 2019 » Example Exam 1a

Hi

Can you be more formal? It is unclear what properties does this n->n-1 function has? Is n a predetermined parameter or we have such a function for any n? What does arbitrary compression means? (n->1 probably not so good) etc.
Also the definition from class about collision resistant hashes was about function families and not single functions. Shouldn't the question be formulated using that notation?

Thanks

Example Exam 1a by Nitzan P (guest), 22 Jun 2019 14:11

You can find the exam here.

Example Exam by nbitanskynbitansky, 20 Jun 2019 19:09

1) We assume that the function $N(r)$ is known to all. In particular, you can assume that it is known before the user joins (this is just for simplicity, in reality you can at most get an estimate).
2) Condition changes for both leader/committee election. This should have been explicit.
3) Any reasonable interpretation here is accepted. Most naturally it means the attacker gets to decide exactly which blocks go into the blockchain. You can show with probability one (in expected constant number of rounds) or with very high probability either is accepted.

Re: HW5 question 2 by nbitanskynbitansky, 12 Jun 2019 05:24
HW5 question 2
Gal (guest) 11 Jun 2019 20:56
in discussion Forum / Course Forum, Spring 2019 » HW5 question 2

Hi,

1) I'm a bit confused with the terminology. When an attacker joins before round r, is it possible that he already knows N(r) (with probability of atleast 99%) by the time he joins? For example, can we assume that if he publishes his pk just before the beginning of round r, with probability of atleast 99%, no more than m new nodes join after him before round r (where m is constant)?
2) In section b, is the leader chosen according to the original Algorand's consensus, or does the condition change for the leader as well?
3) Also in section b. What does "takes control of the entire system" mean? Does it mean that the attacker is able to control who becomes leader and which nodes will be on the committee for all future rounds? Does it have to be with probability 1?

HW5 question 2 by Gal (guest), 11 Jun 2019 20:56

The header of the exam can be found here.

Exam header by nbitanskynbitansky, 11 Jun 2019 18:45
Re: HW5 Q2
nbitanskynbitansky 11 Jun 2019 18:39
in discussion Forum / Course Forum, Spring 2019 » HW5 Q2

$N(r)$ may change as a function of $r$. All parties have equal stake, whether the stake of parties grows or not makes no difference for this question.

Re: HW5 Q2 by nbitanskynbitansky, 11 Jun 2019 18:39
HW5 Q2
Guy Oren (guest) 11 Jun 2019 09:39
in discussion Forum / Course Forum, Spring 2019 » HW5 Q2

Hi,

I am trying to parse the sentence: "at the beginning of round r there are N(r) nodes in the system, each with equal stake".
When new party join the system (and therefore create new node), what is the stake of that party? is N(r) does not change?

Thanks,
Guy Oren

HW5 Q2 by Guy Oren (guest), 11 Jun 2019 09:39
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License