tag:blogger.com,1999:blog-4341554630550651649.comments2014-12-19T01:39:24.444-05:00A Few Thoughts on Cryptographic EngineeringMatthew Greenhttp://www.blogger.com/profile/05041984203678598124noreply@blogger.comBlogger1547125tag:blogger.com,1999:blog-4341554630550651649.post-50928551713278742132014-12-18T07:56:03.978-05:002014-12-18T07:56:03.978-05:00That's known as a covert timing channel. Goog...That's known as a covert timing channel. Google would be smart enough to close it. It's one of the basic things security folks look for.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-74002080601655247862014-12-17T04:40:15.387-05:002014-12-17T04:40:15.387-05:00Your comment system is broken. I write something, ...Your comment system is broken. I write something, I click publish and get back an empty form and nothing "published". <br /><br />You should insert a short note about the non-zero-knowledge version where google doesn't change the coloring between "edge probes". rewhttp://www.blogger.com/profile/14721567792463503445noreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-44308831765127162762014-12-16T19:13:47.291-05:002014-12-16T19:13:47.291-05:00...now that you mention commitment schemas, you sh......now that you mention commitment schemas, you should take a look and look at https://bitcommit.net/Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-51909272772641101942014-12-16T13:59:09.941-05:002014-12-16T13:59:09.941-05:00I believe you are incorrect here, since you're...I believe you are incorrect here, since you're assuming a difference in time between real and fake inputs (assuming no time machine, in which case time can be rewound in just the same way and execution duration is not detectible). Any "lying" prover worth its salt is generating in constant time when compared to a true prover. Just like you should always verify two hashes are the same by checking all characters one at a time, rather than short circuiting on the first incorrect character, thus allowing statistical extrapolation of the secret.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-59378225320910231472014-12-16T06:05:04.909-05:002014-12-16T06:05:04.909-05:00Or wait... The salt is not the same for all nodes...Or wait... The salt is not the same for all nodes. Brennen Chuahttp://www.blogger.com/profile/11614639301908792423noreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-20858689318959662082014-12-16T06:03:52.353-05:002014-12-16T06:03:52.353-05:00Thanks!
Looking forward to the next part.
Stupi...Thanks!<br /><br />Looking forward to the next part. <br /><br />Stupid question(?) <br />What's preventing the verifier from brute forcing the commitments for other nodes once the prover reveals c and salt for 2 nodes? Brennen Chuahttp://www.blogger.com/profile/11614639301908792423noreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-47664545612792201072014-12-10T11:01:37.167-05:002014-12-10T11:01:37.167-05:00Great introduction. I would like to emphasize one ...Great introduction. I would like to emphasize one point that helped me in the past.<br /><br />The structure of the protocol you describe applies generically to all zero-knowledge protocols (that I know):<br />1. The Prover sets up a situation based upon his knowledge.<br />2. The Verifier challenges the Prover in some unpredictable way.<br />3. The Prover has to complete the Verifier's challenge to convince him a little more of his knowledge.<br /><br />This structure is not there by accident: it enables the zero-knowledge nature of the protocol.<br /><br />Also, any introduction on zero-knowledge protocols needs a reference to the paper 'Applied Kid Cryptography' by Naor, Naor and Goldreich: http://www.wisdom.weizmann.ac.il/~naor/PAPERS/waldo.pdf.Pieternoreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-69419925971278895942014-12-08T01:13:43.817-05:002014-12-08T01:13:43.817-05:00Great post Matthew. Since i saw that you are plann...Great post Matthew. Since i saw that you are planning on making this a series of post on ZK, i thought i would point you to the JKO paper "Zero-knowledge using garbled circuits: how to prove non-algebraic statements efficiently". Its a neat application of GC and removes the need to convert the proof into a NP statement.Peter Byerley Rindalhttp://www.blogger.com/profile/02461359107946750714noreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-37582516381654480092014-12-08T00:52:50.408-05:002014-12-08T00:52:50.408-05:00You aren't completely wrong ;). If the prover ...You aren't completely wrong ;). If the prover can rewind the verifier, the protocol doesn't prove anything. But in the real(non-simulated) world the prover can't rewind the verifier... The whole point of the time machine argument was to prove the zero-knowedgeness.<br /><br />Matthew even pointed this out "The soundness argument holds in any situation where we know that nobody is fiddling with time -- that is, the Verifier is running normally and nobody is rewinding its execution."<br /><br />If someone can rewind you computer, you have bigger problems then the soundness of the protocol...Peter Byerley Rindalhttp://www.blogger.com/profile/02461359107946750714noreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-32425367770180600322014-12-08T00:48:46.516-05:002014-12-08T00:48:46.516-05:00This comment has been removed by the author.Peter Byerley Rindalhttp://www.blogger.com/profile/02461359107946750714noreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-31422648139534437862014-12-01T07:10:06.334-05:002014-12-01T07:10:06.334-05:00Thank you Mr Green for another important piece.Thank you Mr Green for another important piece.Anton Prusshttps://twitter.com/AntonPrussnoreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-71350860633094592862014-11-29T17:01:09.119-05:002014-11-29T17:01:09.119-05:00Very nice.
The time travel thought experiment / p...Very nice.<br /><br />The time travel thought experiment / proof reminds me of Philosophy 101.<br /><br />Thank you.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-19235981802301772792014-11-29T02:42:58.736-05:002014-11-29T02:42:58.736-05:00I'm a math and cryptography n00b (& that&#...I'm a math and cryptography n00b (& that's being generous) but greatly enjoyed your post. I *think* I grasped some measure of understanding. If anything, I greatly respect the creativity and rigour that sort of work calls upon. If only a modicum of that could make its way into the field of medicine/nutrition/exercise physiology, the world would be a slightly cooler place to inhabit.<br /><br />Thanks again!raphihttp://www.blogger.com/profile/08992252569979714724noreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-1576217245540020052014-11-29T02:17:46.526-05:002014-11-29T02:17:46.526-05:00Thanks as always for a great post, Matthew Green!
...Thanks as always for a great post, Matthew Green!<br /><br />FYI - "obviouy" looks like a typo for "obviously"hblanksnoreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-28222898480637838952014-11-28T13:06:12.345-05:002014-11-28T13:06:12.345-05:00+1+1Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-28579392805055104732014-11-28T11:11:34.885-05:002014-11-28T11:11:34.885-05:00Hey,
Can you provide a link to the proof of the ...Hey,<br /><br /> Can you provide a link to the proof of the randomized algorithm and the zero-knowledge of this protocol ?<br /><br />ThanksAbishek Sankararamanhttp://abishek90.github.io/noreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-37035310593666050122014-11-28T09:00:39.871-05:002014-11-28T09:00:39.871-05:00Better make sure that the encoding of salt || x is...Better make sure that the encoding of salt || x is unique in C = Hash(salt || x). In other words, there should be no possibility to transfer bytes between salt and x.<br /><br />Best regards! SDLAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-13452467889241432142014-11-28T08:01:31.456-05:002014-11-28T08:01:31.456-05:00For the zero knowledge constraint, with any trick ...For the zero knowledge constraint, with any trick at least one information is extracted, time execution. the modified protocole (with time machine) will run longer then the supposed one, so if I have to challenge google I will try to understand how long it take them to reveal the two edge in the first place, now we are in the situation (never cheated, or always cheating) but in the case of (not cheated at least one time) the difference in time execution of the two version of the protocole (tricked and not) will be the information to extract. so here the zero knowledge isn't verified and at least I will know that google cheat on me for sure .Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-40807317839167666922014-11-28T06:53:16.350-05:002014-11-28T06:53:16.350-05:00If prover and verifier are running on a VM, what h...If prover and verifier are running on a VM, what happens if the choice of the verifier is saved to an external disc during transmission to the prover, then the VM is rewinded to the point before the decision and the prover already knows the decision because he can access the externally stored value, then recolors the graph (or the part in question) and successfully fools the verifier every time without actually having a valid solution? While the verifier indeed doesn't learn anything in the process, how is that actually a "proof"? It merely proofs the zero-knowledgeness, not the solution. This process could be applied easily all the time, making this kind of handshake pointless. <br />There is no restriction on 4 and a half minutes either, the prover could submit all of his solution and still go back in time to change the whole submission. frevdnoreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-67695657314755520512014-11-28T06:41:45.767-05:002014-11-28T06:41:45.767-05:00Hi, any chance of dealing with non-interactive ZK ...Hi, any chance of dealing with non-interactive ZK proofs the next time?izabelahttp://www.blogger.com/profile/12101105514494480901noreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-25632461406720380452014-11-28T05:01:34.708-05:002014-11-28T05:01:34.708-05:00Unreferenced footnote error!Unreferenced footnote error!Philhttp://www.blogger.com/profile/15334261621479728021noreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-19856565863964096892014-11-28T04:33:24.243-05:002014-11-28T04:33:24.243-05:00Uhm...where are the dachshund pictures?Uhm...where are the dachshund pictures?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-48444311356853359262014-11-27T22:04:53.069-05:002014-11-27T22:04:53.069-05:00This is a great post, I've tried a few times i...This is a great post, I've tried a few times in the past to get my head around how Zero Knowledge Proofs work and how they could be applied in practical situations and now I think I get it.<br /><br />I struggled a bit with the time machine thought experiment but once I got down to the part about VM Snapshots and rolling back code it all kind of clicked into place.HybridAUnoreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-54483493563768858542014-11-26T23:13:56.609-05:002014-11-26T23:13:56.609-05:00The reason is that everything else is broken or pr...The reason is that everything else is broken or proprietary - see the attached to understand the requirements:<br /><br />https://dl.dropboxusercontent.com/u/41736374/UnpickingReport%20V1.pdf<br /> <br /><br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-4341554630550651649.post-8317591807722551812014-11-26T23:12:18.110-05:002014-11-26T23:12:18.110-05:00See:
https://dl.dropboxusercontent.com/u/41736374...See:<br /><br />https://dl.dropboxusercontent.com/u/41736374/UnpickingReport%20V1.pdf<br />Anonymousnoreply@blogger.com