8 ms·
Socialist millionaire protocol
- roymurdock 11y agoSee Enigma [1] and homomorphic encryption for a related concept: The key new utility Enigma brings to the table is the ability to run computations on data, without having access to the raw data itself. For example, a group of people can provide access to their salary, and together compute the average wage of the group. Each participant learns their relative position in the group, but learns nothing about other members’ salaries. It should be made clear that this is only a motivating example. In practice, any program can be securely evaluated while maintaining the inputs a secret. [1] http://enigma.media.mit.edu/enigma_full.pdf http://enigma.media.mit.edu/enigma_full.pdf
- morgante 11y agoThat's a rather interesting choice of name for an encryption tool.
- rwmurrayVT 11y agoOTR messaging is commonly used with Pidgin and is considered a requirement for DNM conversations.
- p4bl0 11y agoI have never seen "DNM" before. According to the urban dictionary, it means "deep and meaningful". Is that what you meant?
- VLM 11y agowow, works just as well for dark net markets. Prove you have a working zero day, for example.
- rwmurrayVT 11y agoDarkNetMarket. I apologize for the late reply. I read HN frequently, rarely log in, and have yet to figure out how I can tell if someone has sub-commented me.
- et2o 11y agoI love encountering a seemingly difficult problem that in fact has an easy solution like this.
- emiliobumachar 11y agoEasy to implement once designed. Who knows how much effort went towards designing it.
- jxm262 11y agoHere's another simplistic explanation for this concept - http://twistedoakstudios.com/blog/Post3724_explain-it-like-im-five-the-socialist-millionaire-problem-and-secure-multi-party-computation http://twistedoakstudios.com/blog/Post3724_explain-it-like-i... I've been reading alot about the cryptography (and alot of bitcoin stuff), there's alot of interesting material out there.
- fredsted 11y agoThanks, the Wiki article is complete gibberish to me.
- AMcQuarrie 11y agoI find this about basically every Wikipedia article on a math topic. They are very precise - but basically completely useless for learning anything about the topic.
- peterwwillis 11y agoSometimes there will be a Simple English translation for math articles. Here's an index of articles on Cryptography: https://simple.wikipedia.org/wiki/Category:Cryptography https://simple.wikipedia.org/wiki/Category:Cryptography
- big_youth 11y agoWhile not every wiki page has it enabled I find that the simple english really helps my understanding. For ex: https://en.wikipedia.org/wiki/Probability_theory https://en.wikipedia.org/wiki/Probability_theory https://simple.wikipedia.org/wiki/Probability_theory https://simple.wikipedia.org/wiki/Probability_theory https://en.wikipedia.org/wiki/Advanced_Encryption_Standard https://en.wikipedia.org/wiki/Advanced_Encryption_Standard https://simple.wikipedia.org/wiki/Advanced_Encryption_Standard https://simple.wikipedia.org/wiki/Advanced_Encryption_Standa...
- 3pt14159 11y agoI once edited a Wikipedia article on an Einstein paper to make it much more clear. It was subsequently reverted. I understand the need for brevity, but the domain experts at Wikipedia revert many seemingly irrelevant edits. The edit I made was to explain how Einstein made the leap to E=mc^2 by including the step that showed how E=mv^2 for particles of a given velocity. Of course this is well known to every engineer and physicist, but the article on the proof was so hard to follow without it.
- kazinator 11y ago> Alice and Bob have secret values x and y, respectively. Alice and Bob wish to learn if x = y without allowing either party to learn anything else about the other's secret value. This is better put as: without allowing either party, in the event that the equality is false, to learn even so much as whether x < y or x > y. Of course if the equality is true, each party knows everything about the other's value.
- neogodless 11y agoWell, it says "anything else" which covers exactly that. You don't need to be more explicit, because the entire goal is "learn if x = y"
- kazinator 11y agoIf you learn that x = y, then there isn't any "anything else".
- rwmj 11y agoIs the use of a fixed choice of prime vulnerable to the Weak DH / Logjam attack? (https://weakdh.org/ https://weakdh.org/)
- fryguy 11y agoLogjam works like rainbow tables, but for prime fields. Supposing that a way to reverse the function (a hash in rainbow table case, discrete logarithm in prime fields) in time X for a single case, you can instead pre-compute something in time P, which allows computing a specific instance in time Y. P + Y is longer or equal to X, and Y is significantly less than X. To compute n inversions takes nX for the first case, and P + nY for the second. However, the single instance case X still needs to be solvable. For a large enough prime field, X is still incredibly difficult, so P + Y is going to be incredibly difficult as well. It's much more significant that Logjam changes the field to something weak, than all of the servers use the same prime field.
- rix0r 11y agoCan someone "explain like I'm five" why calculating a hash and comparing those isn't good enough? Is it to protect against bruteforcing? What if the hash is made expensive to compute?
- machinelearning 11y agoThe possibility of collisions renders this approach invalid. If the hashes match, there is a possibility that it is a false positive.
- ademarre 11y agoI accidentally upvoted your comment, but I meant to downvote. Sorry. If fear of collisions is the reason you don't use a crypto hash function, then you are using a broken hash function. A hash doesn't satisfy all the requirements of the problem, but it's not because of collisions.
- alayne 11y agoI don't understand. Aren't collisions why a hash of any kind isn't sufficient for proving equality of inputs?
- optimiz3 11y agoCollisions are when two different inputs hash to the same value, which breaks the security of the hash function. If a hash function is cryptographically secure, it has the property where finding collisions is infeasable, which makes it suitable for evaluating equality. This is why cryptographic hash functions are used as a proxy for passwords in order to avoid storing the plaintext.
- machinelearning 11y ago"Collisions are when two different inputs hash to the same value, which breaks the security of the hash function" This is so wrong. Cryptographically secure hash functions merely claim that the probability of a collision is low. By your definition, it is impossible to find a secure hash function that works on an arbitrary input size. "If a hash function is cryptographically secure, it has the property where finding collisions is infeasable, which makes it suitable for evaluating equality." This is so wrong. It has a high probability of evaluating equality but in no way is it suitable. The primary benefit that cryptographic hash functions offer is that it is impractical to conduct a chosen plaintext attack. "This is why cryptographic hash functions are used as a proxy for passwords in order to avoid storing the plaintext." This is true, and is due to preimage resistance and the infeasibility of a chosen plaintext attack.
- zkhalique 11y agoAre the millionaires able to trust each other's self-reporting? This sounds a bit like mental poker.
- hissworks 11y agoFrom the article: "Even if one of the parties is dishonest and deviates from the protocol, that person cannot learn anything more than if x = y."
- swang 11y agoNo. The two parties trust each other. This is to secure the fact that Alice and Bob are talking to each other and only know that x=y
- baby 11y agono need if the protocol is "fair". He just gave a simplified example on how to solve the millionaire problem. There are many ways to solve it, some are unfair, some are fair. For example you can use fully homomorphic encryption to trivially solve this problem.
- tomasien 11y agoIs anyone familiar with how this differs from a zero knowledge proof, or is this a TYPE of ZKP?
- BrandonY 11y agoI love zero knowledge proofs. My professor in college explained the idea in what I thought was an especially clear way: Say that you and a friend are reading a Where's Waldo book, and you want to prove that you have found Waldo, but you don't want to tell your friend where Waldo is. This seems impossible. However, you could take a large piece of cardboard, cut out a Waldo-shaped hole, and place it over the book. Now you have proven that you can find Waldo. "But wait!" cries your friend. "How do I know the book is even under there? Let me see." But you can't do that, since he knows roughly the spot Waldo would be if you lifted the cardboard. So, you get a second piece of cardboard and put it on top of the first. Now, you play a game. You ask your friend whether you should lift one piece of cardboard (to verify the picture of Waldo) or two pieces (to verify that the book is beneath the second piece). You can play this game as many times as required for your partner to gain a reasonable confidence that you're not cheating. And that's a zero knowledge proof.
- BinaryIdiot 11y agoCorrect me if I'm wrong but that example doesn't seem quite right. If you lift one piece of cardboard the person now sees roughly where Waldo is, right? Sure the cardboard could be HUGE to obscure the size and position of the book but then asking to lift both pieces will show you the position and size of the book making it immediately obvious where Waldo is.
- gbhn 11y agoPerhaps a good intuition pump is this: after every guess the person claiming to have found Waldo gets to position three things: the book, the waldo mask, and the covering cardboard. This then means the subsequent trials don't reveal any side channels about Waldo's location in the book. (And of course in practice the "pieces of cardboard" are big enough to obscure all book information.)
- skj 11y agoThe idea is that some the time, it's not the book, but just a random small picture of Waldo. Since you don't know if it's the book under there or not, you don't know if this example is a "control". The proportion of times that it is the book has to be the same as the odds that you could randomly guess where Waldo is, I think.
- barkingcat 11y agoIs this the one where both millionaires pledge to donate 100% of their wealth to ending world hunger - and in the end seeing who's donated more?
- mathgeek 11y agoIt works for comparing any arbitrary x and y, so long as equality and inequality can be determined.
- azernik 11y agoI find that my interest in algorithms goes up the more outlandish their names get.
- christianmann 11y agoMath works the same way. Have you heard of the Ham Sandwich Theorem[1]? [1]: https://en.wikipedia.org/wiki/Ham_sandwich_theorem https://en.wikipedia.org/wiki/Ham_sandwich_theorem
- Rexxar 11y ago"Hairy ball theorem" is cool too: https://en.wikipedia.org/wiki/Hairy_ball_theorem https://en.wikipedia.org/wiki/Hairy_ball_theorem
- Tinyyy 11y agoChicken Mcnugget Theorem: http://www.artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem http://www.artofproblemsolving.com/wiki/index.php/Chicken_Mc...
- baby 11y agoNote that this explanation is not fair. If Bob stops the protocol when he gets the answer (equal or not) then Alice doesn't learn anything. In cryptography there are ways to make such a protocol "fair". Basically both learn "bit by bit" the answer, if Bob stops early, he only gets one bit of information more than Alice and if he can bruteforce the rest, so can Alice (except if Bob is the NSA).