13 ms·
How to prove you know a secret without giving it away
- ihm 4y agoIf you want to play around with zero-knowledge proofs, I work on a typescript DSL called SnarkyJS. It’s easy to pick up and runs in the browser. https://github.com/o1-labs/snarkyjs https://github.com/o1-labs/snarkyjs
- jettblu 4y agoI haven't used SnarkyJs, but I've heard good things! Big props.
- Blackthorn 4y agoThere's a pretty good section on this in Applied Cryptography. Still an incredible book for a field that supposedly moves pretty fast.
- adastra22 4y agoFor explaining the concepts, maybe. Please don’t implement any protocols from that book!
- tptacek 4y agoIt's pretty bad on the concepts, too. There are good books on the concepts that won't blow your head off; two of them are JP Aumasson's "Serious Cryptography" and David Wong's "Real World Cryptography".
- unnouinceput 4y agoCan you give an example of such a bad concept explained in Applied Cryptography vs Serious Cryptography? Because, out of curiosity, I just downloaded both books, skimmed on both of them (having read in the past Applied Cryptography it took me less time for it of course) through first chapters (classic crypto, randomness and RSA chapters) and found that they are very similar. So, again, do you have a proof of your statement or are you just another Schneier hater?
- adastra22 4y agoI don't remember there being anything downright wrong in Applied Cryptography, at least at the time it was published, although it doesn't convey a lot of the nuance that is required in implementing secure systems. But it now 30 years out of date.
- tptacek 4y agohttps://sockpuppet.org/blog/2013/07/22/applied-practical-cryptography/ https://sockpuppet.org/blog/2013/07/22/applied-practical-cry... Even Schneier himself wouldn't make the claim you just did.
- tptacek 4y agoIt's a good almanac. It's never been a good reference. It's extremely outdated now, and has been for at least a decade and a half.
- pGuitar 4y agozero-knowledge proof is very nice... and could be used to prove election results: https://eprint.iacr.org/2018/466.pdf https://eprint.iacr.org/2018/466.pdf
- defrost 4y agoAs demonstrated in central north america recently the real challenge isn't in proving election results .. it's in the greater social challenge of propagating belief and trust in the results in the face of concerted efforts to widely undermine such. That's a whole other kettle of fish.
- ehnto 4y agoThe technobabble would probably erode confidence more than help the situation in the US, no matter how demonstrably true it is.
- avmich 4y agoUS can probably run two parallel simultaneous systems of record - the technobabble one and regular one, with regular one being the authoritative. After some practice is accumulated working with the other one, they can decide what to do next.
- pc86 4y ago"Central north america" is a really weird way of saying "the US."
- yazzku 4y agoSide topic, but why does something relatively respectable like Quanta Magazine need a reading progress bar? These odd decisions truly amaze me sometimes.
- muppetman 4y agoWhy does the web need half the chaff it has these days? That's why I love YComb, it's a simple text site. Marketing ruined the Internet.
- pexabit 4y agoCheckout Healthline today. Then do WaybackMachine of Healtine in like 2009. It is shocking
- titzer 4y agoThanks iPad
- aargh_aargh 4y agoLooks just fine: https://anon.healthline.com/17-effective-ways-to-lower-your-blood-pressure/ https://anon.healthline.com/17-effective-ways-to-lower-your-...
- vidyesh 4y agoMaybe because it can then also cater to audiences who do not generally visit such sites or reading long-er articles. or maybe it recapture reader's attention, there recently (or always have been) this idea that if you don't like what you are reading you can move on and not waste your time especially with books. But most people generally want to know how that thing ends. So they make a quick decision how little time they have to spend based on the percentage of the reading material remaining. Either way a reading progress bar is a UX improvement and has nothing to do with the intellect of the reader.
- alanbernstein 4y agoI’m glad it’s there. For decades, every long page had a progress bar. Then, nonsense design fads dictated that the scroll bar should become invisible on some browsers.
- seaourfreed 4y ago
- deleted 4y ago[deleted]
- coderintherye 4y agoIf interested in playing around with zero-knowledge proofs, recently was at a workshop with Ying Tong who has an exercise (and long associated slide deck) to walk through them using halo2 ( https://electriccoin.co/blog/explaining-halo-2/ https://electriccoin.co/blog/explaining-halo-2/ ) to build your own zero knowledge proof https://github.com/therealyingtong/halo2-hope https://github.com/therealyingtong/halo2-hope
- ranger_danger 4y ago"How do you let go of a secret without telling the wrong person? You tell everyone at once."
- unnouinceput 4y agoThen that's not a secret anymore.
- psychoslave 4y agoYou just enlarged the number of people in the confidence. Most people in the universe will still be completely uninformed about it, even if you spent tremendous resources on making it readily publicly available. Just considering human beings, most people are already dead anyway. https://www.prb.org/articles/how-many-people-have-ever-lived-on-earth/ https://www.prb.org/articles/how-many-people-have-ever-lived...
- AtlasBarfed 4y ago...... share a hash?
- CobrastanJorji 4y agoSure, but that only works if you both know the answer. Zero knowledge proofs are neat because you can prove you know the answer to somebody who doesn't know it.
- praptak 4y agoHashing parts of the problem works for interactive proofs. I know a graph colouring, so I hash the {color, random salt} pair for every node. The other party chooses two connected nodes at random at asks me to reveal the {color, salt} pairs and checks if colors are different.
- orthecreedence 4y agoThat can reveal the secret. If I know one value out of a known set of values then by sharing a hash anybody can hash the known values until they arrive at my hash, revealing my "secret."
- blueflow 4y agoOne can also iterate over all primes and brute-force them to break RSA. Yes, it works, but it doesn't because we'll all be dead when your computer has the answer.
- orthecreedence 4y ago> known set of values
- rogers18445 4y agoThis is false. When doing a hash commitment you include some randomness along with the value.
- 4y ago
- seewhydee 4y agoScientists used to use anagrams to register scientific discoveries without revealing them. Hooke registered his law of elastic extension using the letters "ceiiinosssttuv”, which he later revealed to unscramble into "ut tensio, sic vis" ("as the tension, so the force"). People did try to brute-force the anagrams. On two occasions, Kepler unscrambled analgrams from Galileo into the statements that (i) Mars has two moons and (ii) Jupiter has red spots. Bizaarely, both turned out to be true facts, but not what Galileo's anagrams were about!
- ALittleLight 4y agoThis reminds me of fixing a bug that causes your problem but then you discover the problem persists after the fix and that you actually had two independent bugs causing the same problem.
- unnouinceput 4y agoErm, if you do a fix and the problem still exists then how is that a fix? For example, if I have a number box and I punch letters in it and the problem is <string "CARTER" is not a number> error is still poping up, then my fix is not a fix, is it? Regardless of how many bugs I have that cause the problem, a fix, in my opinion, is the sum of all those bugs going away.
- galaxyLogic 4y agoI see your point which is semantically valid. But there is something more to it. Consider it from the other direction: You can introduce a bug by making some modification to the code. Then you add another modification which produces the same erroneous behavior. Either one alone would be enough to cause the problem. And two of them together does not cause any more problems than each of them alone. But now to "fix" the problem you have to undo both of your modifications. You have 2 bugs and you have to "fix" them both. "Fix a bug" as in "Kill a bug". So "Fix a bug" can mean "remove a cause of the problem". Or it can mean "remove the problem".
- bockchain 4y ago> How to prove you know a secret without giving it away This is the best use case for blockchain. Put the secret on the blockchain and show others that transaction. Since it's on blockchain, no one can deny your claim about knowing the secret. This is why blockchain was invented. Before blockchain, I was miserable. There was no way for me to prove to my girlfriends that I knew a secret, without telling the secret. Now with blockchain, my life is so easy - I just show them the blockchain transaction and they know that I know.
- SV_BubbleTime 4y agoI assume this is excellent satire, but you never really can tell.
- fortuna86 4y agoYou really can't..
- nayaketo 4y ago> Before blockchain, I was miserable. This part gives it away. Also his username which is probably misspelled deliberately.
- nikau 4y agoBockchain - human centipede but with chickens
- MonkeyMalarky 4y agoBockchain - digital pecking order
- rzzzt 4y agoStoutchain
- sexy_seedbox 4y ago
- porcuquine 4y agoI recently published a fairly detailed blog post about how to formulate expressive provable programs in Lurk (https://github.com/lurk-lang/lurk-rs https://github.com/lurk-lang/lurk-rs). Although this post goes into no details about the underlying proving mechanism, it does build to some pretty powerful ideas. If you haven't thought about the implications of being able to prove correctness of a computation without revealing some or all details of what the computation actually was, you might enjoy it. https://blog.lurk-lang.org/posts/prog-intro/ https://blog.lurk-lang.org/posts/prog-intro/
- dmichulke 4y agoAs a functional programmer it's easy for me to understand the code, so I actually made it until the end where a neat example is given. In general though I think the example problem might be worth mentioning in the beginning: "by the end of this article you will understand how to ..."
- porcuquine 4y agoThanks, that's a good point — and I had originally intended exactly that. Any suggestion for how the … should be completed?
- kayson 4y agoHow can you use zero knowledge proofs to show that your nuclear weapons are inactive? Also... couldn't you just reactivate them after?
- cyclotron3k 4y agoI would like to know this too
- deleted 4y ago[deleted]
- pmx 4y agoIsn't this the point of the article? You wouldn't prove if they're active or not, only that YOU know if they're active or not?
- barsonme 4y agoZK proofs let you (the prover) prove a fact to somebody else (the verifier).
- barsonme 4y agoFWIW the linked paper on nuclear warheads is fairly accessible. You don’t need to understand nuclear physics to grok the algorithm. ZK proofs only demonstrate knowledge of some fact. So, you could prove that you know the way through the maze, but then immediately forget it afterward. Maybe the nuclear inspectors inspect the warheads frequently enough that rearming them would be detected? Or perhaps there is just some level of trust and you have to rely on the country to play by the rules.
- redrobein 4y agoYup, this would only work if some central authority had exclusive control to activate/deactivate the warheads.
- can16358p 4y agoI'm confused about the maze example in the article: I can "prove" that I know the path to exit as I traverse the maze in limited time, okay. But interactive proofs have many iterations to sufficiently convince the verifier, however if I found the exit by luck in first try, I've already found it and I can simply follow the same path in the next iterations. How does the interactivity exactly work with the maze example?
- barsonme 4y agoThe “magic door in a cave” game might’ve been a better example of interactivity.
- PeeMcGee 4y agoYeah, this article tries too hard to appeal to all audiences in a way that ends up making it confusing for everyone. Starts off with the clumsy maze example, then hops over into graph theory and NP-complete proofs, then hand waves something about sharing bits and quantum computing... But enough about that, it turns out blockchain will prevent nuclear war!
- elondaits 4y agoAnd they lost me with the graph example… because both graphs are the same! How are you not leaking information about the solution if you’re showing the path in the exact same graph! If they consider two graphs drawn differently as different graphs, they should clarify it from the start … and maybe not pose it as a graph problem.
- junofan 4y agoImagine the graphs are really, really big. Graph isomorphism is NP-hard. Alice gives Bob a graph. Bob can ask Alice to show the bijection (hard) or show a path (hard) but not both. Say Alice and Bob do this 40 times. Can you see how Bob should be convinced that Alice is giving him isomorphic graphs and that she knows a path through the graph? Otherwise Alice would have failed to answer one of his questions along the way.
- toolslive 4y agoBest intro paper on the subject (IMNSHO) How to Explain Zero-Knowledge Protocols to Your Children https://www.researchgate.net/publication/221355016_How_to_Explain_Zero-Knowledge_Protocols_to_Your_Children https://www.researchgate.net/publication/221355016_How_to_Ex...
- dhartmei 4y agoAt the beginning, where the hidden passage is explained, isn't there a "race condition", where Ali Baba would eventually (across 40 repetitions) run into the thief? The thief picks one branch, Ali Baba the other. The thief uses the passage, then walks right into Ali Baba? I don't understand how the thief can be sure to never walk into Ali Baba coming down the other path at some time. What am I missing?
- bdunks 4y agoThe thief waits in his own passage until he knows the victim has followed him down that passage. He does not pass through the door if the victim is in the other passage. The authors briefly mention this: > After a very uncomfortable wait he saw a thief arrive who, *sensing he was pursued by his victim*, whispered the magic words, “Open sesame.”
- lljk_kennedy 4y agoI guess the thief can observe / hear Ali Baba's approach and decide on using the secret passage to go to the other path (if Ali Baba is approaching his way) or just run out the current passage if Ali Baba chose the other one.
- amenghra 4y agoThis tweet illustrates the idea of showing that you know where is Waldo without revealing Waldo's position: https://twitter.com/cronokirby/status/1571824060513796099 https://twitter.com/cronokirby/status/1571824060513796099
- moffkalast 4y agoThat's just giving Waldo's coordinates with extra steps
- amenghra 4y agoHow so? You don't reveal any coordinates if the foil covering the page is 3x the size of the page.
- moffkalast 4y agoWell whoever's doing the verifying would need to have a way to align that piece of foil in a way that shows the position, and unless both people know that process it's useless anyway. If there's infinite possible alignments then you've given no data, but a piece of foil with a random hole in it. Like giving you two random numbers and you coming up with a function that maps them to waldo's position.
- amenghra 4y agoYou might not have understood how this works. The prover shows the fact that they know Waldo's position by showing the page covered in foil to the verifier in person (or by taking a picture). The verifier does not manipulate anything. Obviously, there's no way to verify that the page under the foil is the page you think it is. This is more of an analogy / tool to explain things vs an actual secure protocol.
- moffkalast 4y agoThinking again, I may have read too much into the foil thing. A better example would be a just a cut-out of Waldo, separate from everything else. I'm sure it's a massive simplification of the way it's actually used.
- moffkalast 4y agoAccording to school professors, the only way to prove that a person knows something is to lock them in a room for an hour or two and have them write down the entire thing on a piece of paper while being watched intently.
- vestrigi 4y agoWell, most of the time I attempted a zero-knowledge proof in school I couldn’t convince the teacher ;) I think the difference is that the teacher already has the full knowledge and learning isn’t as easy as telling a secret once and then the learner can quickly parse it and keep it forever. Despite that, I’d also prefer to proof I know a topic by writing an essay at home rather than under pressure within an hour under supervision.
- Tangurena2 4y agoI was usually successful in proving to teachers that I had zero knowledge. :) These were not the proofs they were looking for.
- draw_down 4y ago
- AkshatJ27 4y ago> For a simple way to understand this idea, let’s suppose you want to show your friend that you know how to get through a maze, without divulging any details about the path. You could simply traverse the maze within a time limit, while your friend was forbidden from watching. (The time limit is necessary because given enough time, anyone can eventually find their way out through trial and error.) Your friend would know you could do it, but they wouldn’t know how. How would your friend know you solved it though? Does he have to take your word for it? Doesn't that defeat the purpose? This analogy seems flawed, correct me if I'm wrong Edit: I misunderstood the kind of maze the article is talking about. Apparently it's not the pen and paper version.
- edent 4y agoThe friend sees you enter the maze at the entrance. They don't watch you traverse the maze, instead they run around the outside of the maze to the exit. They see you leave by the exit 2 minutes later. They don't know the path you took and they can be reasonably sure you didn't brute-force it in that time.
- aryamaan 4y agoIf it's a big maze where you can pass through, you can enter and exit in that time limit
- AkshatJ27 4y agoOh, I was thinking of a pen-and-paper maze, not a real life maze
- pas 4y agoa hypothetical real life maze (eg. in a fancy park), not the paper version?
- EGreg 4y agoIs it true that given enough such proofs, I can reconstruct the original thing, so I do leak something? Like doing an HMAC reveals a tiny piece of information every time…
- marcodiego 4y agoIsn't it enough no show a hash?
- JanisErdmanis 4y agoIt would be a random string for the verifier as he does not know the secret. It’s much like one can sign a document without revealing a secret key. In fact signatures are proofs of g^sk=pk where the document hash is a verifier challenge.
- Double_a_92 4y agoA hash of what exactly though? This would only work as a timestamp, if you ever plan to publicly release your secret. But it wouldn't work if you e.g. want to find other people that also know what you know, without ever telling anyone. (Because they wouldn't have your exact text or document to hash...)
- xrd 4y agoThere was a recent podcast by ZK Knowledge about homomorphic encryption and how this is different and complementary to ZK proofs. The founder of Zama had some surprising things to say (from my perspective) about how ZK is not something that can be used to guarantee privacy when used with blockchain tech. I'm sure that will be exciting news to everyone on HN. :) https://zeroknowledge.fm/248-2/ https://zeroknowledge.fm/248-2/ Transcript, look for the timestamp with 28:55 to see that discussion: https://assets.fireside.fm/file/fireside-images/podcasts/transcripts/6/66a36787-cf18-4f96-ba6b-d00e9f507731/episodes/4/4b115ca6-7ea7-4849-a93a-12a769eae970/transcript.txt https://assets.fireside.fm/file/fireside-images/podcasts/tra...