Timeline for Minimizing exchanges for ZK proof of a message with given SHA-256
Current License: CC BY-SA 4.0
25 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Jan 18, 2020 at 12:04 | history | bounty ended | fgrieu♦ | ||
| S Jan 18, 2020 at 12:04 | history | notice removed | fgrieu♦ | ||
| Jan 18, 2020 at 12:04 | vote | accept | fgrieu♦ | ||
| Jan 14, 2020 at 7:47 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jan 13, 2020 at 10:08 | answer | added | Geoffroy Couteau | timeline score: 11 | |
| Jan 13, 2020 at 8:05 | comment | added | Meir Maor | If we take the classical proof of graph coloring we send commitments for all edges, if we use a tree hash for commitments, sending the commitment is as large as our security parameter, and revealing an edge is our security parameter times log of the number of edges. in the other direction we only select an edge number, this should be repeated to reduce epsilon. Asymptotically this doesn't look bad, though we might be able to improve. I don't know how big the reduction from SHA-256 to any such problem comes out. | |
| Jan 13, 2020 at 7:41 | comment | added | fgrieu♦ | @Meir Maor: I understand how we can reduce the problem of proving knowledge of $m$ to proving knowledge of a solution to a boolean SAT problem. I could evaluate how many 3-SAT equations that requires. But I don't know the communication cost for proving a 3-SAT problem, nor if state-of-the-art techniques would go this route (perhaps they use fewer larger equations, or non-boolean SAT to represent 32-bit addition). | |
| Jan 13, 2020 at 5:40 | comment | added | Meir Maor | We can reduce anything NP to SAT and then if we can prove a SAT problem is satisfiable we can do anything. | |
| Jan 12, 2020 at 22:24 | comment | added | kodlu | @MeirMaor, Ignorant question, this is far from my expertise. Are boolean circuits used here essentially because no lower bounds are known in any other setting? | |
| Jan 12, 2020 at 18:55 | comment | added | fgrieu♦ | @Meir Maor: I have no application in mind, but from practice yes it is useful to minimize the number of round trips. Say that's a (secondary?) objective, with no precise weighting with the (primary?) of minimizing total information flow, and minimizing $\epsilon$. | |
| Jan 12, 2020 at 18:26 | comment | added | Meir Maor | Are you trying to minimize information flow or round trips. I vaguely remember Interactive proofs (for anything in Pspace) with 3 bits per exchanging and a 50% chance of false of successful forgery in each(but that wasn't in a ZK setting, not sure it makes a difference) | |
| Jan 12, 2020 at 18:06 | comment | added | yacovm | yeah... it wasn't there before :) Honestly I don't know of any theoretical work on bounds of these kind of proofs, and I think it's rather hard to come up with something, since it depends on the implementation of the circuit. For instance, if you want to prove you know a witness $x$ for $f(x)$ instead of computing the $f$ it might be cheaper to pre-compute the stages of the computation, secret share them among the parties and then "validate" in the MPC circuit that the stages in the computation of $f$ are correct. I didn't answer because I have nothing really smart to say on this. | |
| Jan 12, 2020 at 18:03 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jan 12, 2020 at 17:57 | comment | added | fgrieu♦ | @yacovm: does the addition of "and probability of reaching a wrong conclusion" adress your comment? | |
| Jan 12, 2020 at 17:53 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Clarify
|
| Jan 12, 2020 at 17:53 | comment | added | yacovm | "Are there firm lower bounds on the necessary information flow in both directions, and number of exchanges" - well at least in the ZKBoo which is based on MPC-In-The-Head, if I understand correctly, the soundness depends on the number of transcripts of the protocol that you want to simulate, so better soundness means bigger proofs. | |
| Jan 12, 2020 at 17:51 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Clarify
|
| Jan 12, 2020 at 17:48 | comment | added | fgrieu♦ | @Meir Maor: yes, I understand that limitation. That why I had put "whoever made it". I tried to further clarify. | |
| Jan 12, 2020 at 16:59 | comment | added | Meir Maor | Obviously a non interactive proof of knowledge is limited as it can be copied and repeated. Without a challenge you can't tell the difference between original and copier. | |
| Jan 12, 2020 at 12:00 | history | tweeted | twitter.com/StackCrypto/status/1216329114753343488 | ||
| S Jan 12, 2020 at 11:27 | history | bounty started | fgrieu♦ | ||
| S Jan 12, 2020 at 11:27 | history | notice added | fgrieu♦ | Draw attention | |
| Jan 10, 2020 at 8:16 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jan 10, 2020 at 7:18 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Polish
|
| Jan 10, 2020 at 7:09 | history | asked | fgrieu♦ | CC BY-SA 4.0 |