Last year my wife and I suspected we might have gotten each other the same Christmas gift, but didn’t want to spoil the surprise in case we didn’t. So we compared SHA256 hashes... and sure enough they both came out cb17007d (theragun)
But it isn't zero-knowledge. If it was zero-knowledge, you would be able to know what you had the same gift/crush, but it would be impossible to prove to someone else.
Mere hashing doesn't do that. For the crush example (This site), your crush could show everyone the link and their name. For that matter, someone could enter the names of everyone you knew in turn, until you were outed.
Non interactive zero knowledge allows one proof to be checked by many verifiers. I think folks would still consider that to be a zero knowledge proof no?
That said, yeah this hashing example is not zero knowledge because, among other things, the hash is not hiding.
It's been a while since I read about zero-knowledge proofs, so I wasn't aware of the non-interactive kind. But I read up on them, and as I understand, you have to pre-commit to a finite set of participants in the protocol who can verify that you have the proof.
Which makes sense: If the evidence (that you have a mathematical proof) could be convincingly shared with absolutely everyone, it wouldn't be zero-knowledge any longer. The whole point of zero-knowledge proof is that the evidence is only useful for the recipient(s).
My favorite analogy is someone has a Wheres Waldo photo. They can prove to you they know where Waldo is by getting a piece of paper (the size of the photo) with a cut out around Waldo. When they hold it up and show you Waldo through the cutout you have zero knowledge about his location.
If the mask paper is the same size as the waldo photo, one can trivially tell where waldo is by just looking at the location of the cutout
I think for this to work, the piece of paper with the cutout must be much larger than the full waldo photo. The actual cutout would always be in the center of this mask paper. Then the waldo photo can be moved around behind this mask.
But then you cannot prove anymore that you know where Waldo is, no?
Previously, the proof relied on the alignment between the picture and mask being constant, but this is no longer the case. Now wherever Waldo actually is, every mask fits since you can just freely move around the picture.
To align the cutout with Waldo, you need to know where he is. Since the entire picture would be hidden behind the mask, the other person won't know where in the picture that location is, but by aligning the mask cutout you can prove _your_ knowledge about Waldo's location.
As the sibling comment says, neither gp comment nor this post are zero-knowledge.
But in addition to the definition given in sibling comment, here's another necessary condition of a zero-knowledge proof: it must be possible to forge transcripts (i.e., one party writing both sides of the interaction) of a zk proof even without possessing the secret.
There are a couple of science and science fiction authors that started posting hashes or signatures for their predictions for the future, and then post it after events played out.
I think the idea is that unlike pundits predicting the future, you don't want your particularly clever friend speculating out loud ten minutes into the suspense movie what they think is going on because they either guess the ending, or their guess makes you figure out the ending, and then it's 70 minutes of sitting there reading all of the other foreshadowing and not getting to enjoy any of it.
Yeah I'm not sure what's the best protocol that's actually zero-knowledge here, but since we both trusted each other to only want to find out whether or not our gifts were the same, and otherwise to not spoil the surprise, this did the job.
You could just write a script that lets you write an input and your spouse writes an input and then compares the two inputs without showing them - no need for hashing at all.
Sure, but the example is contrived, as it serves to illustrate the point in an easily digestible (heh) way. In real world applications, both the possible messages and the possible hashes would be way too large to brute force.
We both hashed "theragun" in all lowercase. We actually bought each other two different models of Theragun but it was pretty natural to refer to them with that string.
This protocol has some downsides - if you share the link with large adversarial group (e.g. your school) they can brute force your crush name and it’s basically no different then embarrassingly shouting out your crush name in public and it has problems with canonical names.
Instead we can alter it and fix this problems:
Bob will find out his crush’s public key, encrypt "you are my crush" message to it and post it with his own signature to public bulletin (blockchain can be good shelling point). When crush decrypts message they will see proper string, while everyone else will see gibberish.
- to solve problems with key distribution we can use "identity based encryption". it requires trusted third party (e.g. school administrators) but it solves problem for key generation of participants. With identity encryption bob can encrypt message to some canonical identity such as school email. Owner of that email can prove it’s identity to the third party and receive corresponding private key.
I can absolutely guarantee that the school generation would not naturally gravitate to the blockchain as a source for social interaction, since it's not (yet) running social media. I'm assuming TikTok (if it's common to post your own videos and not just consume?) or Snapchat (or whatever came next, that's probably old enough to be uncool by now I guess?)
EDIT: I just saw the suggestion that school administrators be identity providers for a crush-admission website. OK, now I'm _sure_ this must be satire. Well played.
Thanks to other people pointing out, I now see that there is still a fundamental problem — crush can see that you appointed them to be your crush without liking you back, and the solution is that:
1) everobody precommits to your crush set in advance
2) users use mpc protocol that will ensure that your crush reveals if both of you precommitted to each other. (I guess it's similar to "Yao millionaire problem" where two parties calculate "x < y" without revealing x and y. but you calculate "x == y" where x and y is values that you committed to previously and you dont reveal x and y)
Previous variant does not need any blockchain because you can just embed encrypted message to the web page similarly to the original hash variant (really it's the same as sending private message to your crush) but MPC variant probably needs blockhain because that's a perfect way to publicly precommit to something.
Note: there is still the possibility that you can precommit to "x is my crush" without x being your real crash to lure out if you are crush of x.
P.S. I think that's a good illustration of a service that can't be done without crypto and have similar properties.
And then someone will guess that the school administrators password is “StudentsSucks2022” and steal all the private keys they left in their documents folder.
You are correct, but I think "identity based encryption" protocols can run in MPC mode.
Multiple parties will generate distributed secret that will be used to generate private keys. Anyone can easily generate public key for any identity (e.g. email) for the given "key generator" setup using public data of this setup. But for a user to get their private key, they need to assemble secrets by proving their identity to multiple independent parties - you have to hack every one of them to restore the private key of user.
I remember reading a joke research paper about something like this. It explored all currently known methods of confessing your love, their pros and cons, and had a funny acronym for each. It then proposed a newer, secure algorithm for confessing to your crush if the feeling was mutual, and without leaking information to 3rd parties. I'm trying to find it, but I don't have it saved and I haven't found it on Google yet.
I'm really impressed with how readable and how funny that is, but I'm sure I'm missing at least one of the jokes contained within. In particular, they suggest an extension to their protocol called "SENPAI-MTT (More Than Two)", which I'm sure must be a cleverly chosen backronym, but I can't work out why (or if) it is funny.
My initial thought was that it could be a reference to the Japanese verb meaning "to look"[0], such as mite ita ("was looking") but represented in vowelless chatspeak[1]. More logical, though, would be the verb meaning "to notice"[2], but the imperative would be kizuite kudasai ("please notice!")[2], and that doesn't match "MTT" at all.
The paper does discuss such relationships, but "SENPAI-MTT (More Than Two)" is an extension to the protocol to allow a participant to choose from more than two (i.e. Crush / No Crush) possible opinions about someone.
It's in the section titled "Ternary Responses", and covers the use case of a participant wanting to express "Maybe" as an opinion.
Oh, actually, I might have worked it out. It could be that "More Than Two" is designed to be somehow the reverse of "Less Than Three", which represents a heart.
It's my understanding that zero-knowledge concepts can be extended to databases, in a way where I can query a database and get a result without knowing the contents, perhaps to pass on to a trusted system to perform another action.
Depending how you slice it, I either do or don't get to know if the result set is empty. In the latter case, there's a variation of this crush registration system where I don't get to know if Sally has a crush on me, but I do find out if anyone has a crush on me. Of course if the answer is empty set, I don't know if I'm unloved or only loved by people that don't use the app. Which could be pretty heavy.
Love these kind of ideas. Reminded me of once I was trying to allow access to a file with a password. It wasn't any super-secret file or anything, just a CV of a friend hosted on a static file server and she wanted it to "protect" it with a simple password (just didn't want it to be directly available to anyone viewing the homepage. No mission-critical secret of any kind otherwise).
Having no real/strict security requirements and being lazy to go server-side scripting, I simply hashed the password. Noted the hash. Saved the file into a folder like "/${hash}/Proper Name.pdf". Hashed the hash again and embedded it into client-side JS. Wrote a JS function that took the input, hashed it twice, and if second hash of the entered password matches that, download the file "/${first hash}/Proper Name.pdf".
It worked like a charm, but please note that this is prone to attacks so if anyone reading this thinks it's a good idea to implement actual security, DO NOT. It is not. Fun to play with though.
Among other things, it’s almost certainly the case that the web server isn’t implementing a constant-time string comparison for the URL, which enables you to brute-force the value one character at a time.
Fair point, though search engines are aware of special headers that tell them not to publicize the link to the content. Would it be any safer with the key in the GET parameter string? Search engines still usually treat this string as part of the address.
Tinder goes in two directions. This would go in 4 directions. Swipe up to send them to your friends, down to your enemies, left to the void, right to you.
You start with 2048 single people, and have to act as matchmaker to pair them off into married couples who each produce at least one child. A generation later, you take the 1024 first-borns of each couple and have to pair them off too, into 512 new pairings.
Repeat that long process until there is just one couple left, whose first-born you then propose to. Having lived long and healthily enough to complete this game, you must have some very desirable genes and/or wealth, and you'll be good friends with basically all this person's ancestors, so there's a strong chance they'll say yes, despite the age difference.
> Those games only make at least a bit of sense when everybody enters their crush and only when matching both get notified.
Even then, among heterosexuals they will suffer from the same problem as basically every software platform for romance among straight people: the massive asymmetry in interest between men and women. Men would copy and paste virtually every woman they know into the system as a "crush," so they can find which if any of their female acquaintances might be interested, and then they would decide who to pursue.
> Men would copy and paste virtually every woman they know into the system as a "crush," so they can find which if any of their female acquaintances might be interested, and then they would decide who to pursue.
Smart men would, who know their place in the world. Any of them are good enough for you, really. Take the one that you like the most out of the ones who like you. Is this a problem? If it weren't asymmetric, it would be hopeless. Instead, most men get the choice between one or more interested women, and most women get a response from one or more of the men they were interested in.
It's better if one side isn't as picky as the other. The other options are that only a couple of people match up at all, or everyone getting a response from everyone i.e. no signal at all.
I don't follow this, either logically or in practice.
Granted I've never dated as a gay man or as a lesbian, but from what I've observed it seems to me a much smoother and more mutual process than straight dating. I've even heard from bi men about how much easier and less stressful it is to date men than women. AFAICT when both parties are on a level playing field, and there's not a massive asymmetry in power, interest, and investment, there's a lot less grief overall.
> edit: I mean, isn't that Bumble?
Bumble is a valiant attempt to fix this issue but it seems to mostly be a failure. An average man may occasionally get a message (which will usually just say "hi"), but the asymmetry in interest is still there, and it's still mostly men's responsibility to do the real initiating.
You'd want to use asymmetric public key cryptography so that Bob could hash his message with Alice's public key, and it could only be decrypted with Alice's private key.
Seems to me such a system must make it expensive to claim to have a crush on someone. Otherwise Bob can just claim to have a crush on everyone and will find out who crushes on him.
That lets Bob confess semi-deniably to Alice (if Alice is willing to share her private key, she can still show Bob's confession to Carroll and prove that it's authentic). But it still doesn't do any matching; Alice will know about Bob's feelings whether she returns then or not.
Yup, everyone publishes their public keys. No one’s private keys gets published (fake crush created).
I’m not sure if zero-knowledge proofs exist for love outside of action - repeated acts of commitment over time (to reduces the confidence that someone doesn’t love you).
Yeah, it is like hashing a phone number to protect its owner's identity. With a small domain known by the attacker hashing isn't really one-directional.
There's nothing wrong with only wanting to reveal a crush if it's somewhat returned. If it isn't, you're just putting them in an uncomfortable position for no good reason.
that's because it's not zero knowledge, it's password hashing.
a zero knowledge proof would do something like prove a valid attestation of love, but reveal nothing about who (other than maybe membership in some large enough set).
And when everyone is an actual adult, not a manchild or other people without a fully formed prefrontal cortex and thus prone to making ugly, life-changing decisions - for themselves and others - on a dime.
That's most of the demographic for this product. The number of over-25 people, not in a committed relationship, who still haven't figured out how to ask people out, is pretty small.
I dunno. I'm reasonably well adjusted and apparently even decently attractive, and I still have a super hard time with the whole asking people out thing. I've been lucky enough to have people ask me out but otherwise I'm not sure I'd have had much luck dating at all.
This tool doesn't do what I'd want, but a tool that did would be kinda neat :)
Instead of getting your SO's name tattooed on your body that you'll regret in a few years, you'll instead get your names added to the blockchain...that you'll regret in a few years.
Blake2b + Hybrid PoW chain with LOW TRANSACTION FEES and 4 TX/S THROUGHPUT now CONFIRMING COMMITTED RELATIONSHIPS with blockchain technology! Your relationship isn't valid until there are AT LEAST 36 CONFIRMATIONS on $LOVE chain!!1
Also now supporting ON-CHAIN unique NFTs for couples for low fees!!
Similar to how blockchains killer app is delivering pizza.
You deliver the pizza as normal then do something something blockchain and now it is
blockchain.
I believe "zero knowledge" refers to the third party here. That is, you give it A => B, and it tells you if B => A was given previously, without it knowing the actual values of A or B. While you might be able to brute force the system by trying every name you know, the third party can't unless you give the third party a registry of names to try.
Related is the humorous paper "Solving the Dating Problem with the SENPAI Protocol" [1], though the solution in that paper does not rely on a third party.
Yeah zero-knowledge is supposed to give you no usable information, but brute-forcing aside, the fact anyone can learn they are not the target is knowledge, right?
Nice. Kinda along the lines of what made the current generation of dating apps (starting with Tinder) so popular. Take a large group of 1st and 2nd degree friends. People anonymously select who all they'd like to get with. If there's a match, both parties are notified. If not, no one gets to know. It's such a simple concept, and it's odd that someone like Facebook wasn't able to capitalize on it first despite providing all the infrastructure (the social graph) to make a service like this possible in the first place.
> People can enter their names into this unique link to generate the hash of their name. If the generated hash matches, they'll be notified *you* are *their* crush
Don't mean to be pedantic, but shouldn't it be "they'll be notified *they* are *your* crush"?
Well... hactually... This is kind like the opposite of zero-knowledge, where everyone can know your crush just by entering all suspecting names in the link.
Small idea, no idea how useful if at all but maybe it could be a simple page with a list of reasons why the sender likes the recipient, and/or a YouTube playlist of songs that remind them of the recipient etc
Jacques Patarin[1], my cryptography teacher at university introduced us with zero-knowledge proofs with a simple real-life zero knowledge scheme for this exact purpose. All you need is 5 cards, 3 identical red and 2 identical blacks.
You give one black and one red to each person (Alice and Bob), and keep the last red.
The scheme is the following:
Alice will puts her two cards ON TOP of the remaining red card: to say yes, she puts her black card on top of her red card, to say no she does the opposite (red on top of black).
Bob will put his pair of cards BELOW the remaining red card, and to say yes he puts his black card at the bottom, with his red card in between, and to say no he does the opposite.
Then you cut the deck enough times to obfuscate who've done what, and you know that they've both day yes if you have the two blacks cards next to each other (or both at each ends of the deck). If anyone (or both of them) said no, you'd have black cards separated by one red card.
I might be an old timer but there used to be a site where you would put in your email and your crushes email and if they did the same you’d both be notified. I don’t remember the name of the site now though.
I mean, you would want to handle this correctly for a "real" thing, but this is just a cute demo and that's gonna be a close enough approximation to work for this I think.
Quite simple: you don't deal at all. That's zero assumptions about the name. Let them eat cake and enter whatever they want. The user should know their sweetie well enough to guess what they will enter as own name. This is an assumption about their level of mutual knowledge, true, but not one about the naming scheme.
On the contrary, there is a very strong and completely invalid assumption: that Alice will type her name in exactly the way Bob typed her name, and vice versa, that neither will misspell it, that either both will use the official name or both will use the same nickname.
This is a design decision that will very likely lead to missed matches, bold of you to assume it's desirable but even that doesn't answer the entire ordeal. How are they going to enter the name, have you read 11?
> 12. People’s names are case sensitive. 13. People’s names are case insensitive.
You can store this as an attribute
> 14. People’s names sometimes have prefixes or suffixes, but you can safely ignore those.
This can be other fields if you're trying to structure the data, or you can simply store the entire name as a contiguous field.
> 18. People’s names have an order to them. Picking any ordering scheme will automatically result in consistent ordering among all systems, as long as both use the same ordering scheme for the same name.
Don't string compare names as a test for equality.
The obvious response to this is: that's too hard (/impossible to do). But that's just the reality of the situation. These issues are not necessarily possible to solve. #21 in particular makes this application very broken even with very plain vanilla western names.
To stop my friends from using this to guess who my crush is, a fun iteration could be instead of entering the person’s name, you enter the last text you sent, place you met, etc. Something only the two of you would know … and maybe even something romantic :)
It's fascinating to see how far people are willing to go to avoid the awkward feeling of potential rejection.
I mean I have been there.
But as I am older this just feels funny. If you like someone just tell them. Rejection is part of the fun.
Right? I embraced rejection therapy and the results were scary good. A whole new world opened up, not only in romance, but sales, financing, recruitment, etc.
Nice, quick implementation. It's cool that it's all client side. People have pointed out the weaknesses as far as non-crushes brute forcing the answer but still this is interesting. I'll have to digest the implications more. I created https://aytwit.com/thoughter which takes the basic idea here to a much more involved extreme. It got some good traction on hackers news a few years ago and I've improved it a lot since then. I still want to make some improvements as far as moving more of the cryptography client-side so people don't have to trust my server as much, yet not ALL client side like this for more convenience and privacy.
I used a similar technique to obfuscate the answers in a silly TV quiz[0] I wrote a couple of years ago.
I have a terrible habit of looking at the source of web-based puzzles to discover the solutions and wanted to make something where that was impossible.
My solution was to use the given answers as the key to decode a small blob of data. Multiple correct answers (different spellings) were handled by simply encoding the blob multiple times and trying them all.
Everything happens client side but at no time does the client store any information about the answers unless the user proves they know them by typing them in.
The cave parable always confused me. This blog-post made it click. I think the 'secret passage in the cave' is just a very bad stand-in for knowledge. Perhaps a maze would be better. But the parable also focuses to much on 'creating false transcripts' without explaining why being able to fake it makes it 'zero knowledge'.
Fun concept, but quite easy to use with a malicious intent. It would be better if only people who have a crush on you could use the link (meaning the confession would work both ways)
What does this achieve that posting "text me and I'll tell you if I have a crush on you" doesn't?
Or texting your crush directly?
I suppose it's a useful commitment mechanism for proving you aren't telling everyone they're your only crush, but that seems a bit of a niche use case.
1. Since it's an external web site with a little bit of tech behind it that presumably others are using, it might seem less desperate or strange than the post you suggest.
2. The potential crushee can do the check without notifying you they're doing so. They might be too embarrassed/intimidated to actually tell you they're interested in whether you have a crush.
Yeaaahh, but no. It doesn’t need to be mutual. Guess can be correct but the reveal will probably just out you and cause problems. For confessing your love do it openly, they are no short cuts.
Wrapping this in a native app could be a nice little moneymaker. Lots of speed dating events could use this to help match attendees that were interested in each other.
"The essence of zero-knowledge proofs is that it is trivial to prove that one possesses knowledge of certain information by simply revealing it; the challenge is to prove such possession without revealing the information itself or any additional information."
"In cloud computing, the term zero-knowledge (or occasionally no-knowledge or zero access) refers to software services that store, transfer or manipulate data such that it is only accessible to its owner, not to the service provider."
Your quote heavily misspells "bullshit marketing" ;)
For marketing reasons, people try give things fancy names, even if those names are misused and are completely wrong. This is exactly what happened with all those "zero-knowledge encrypted cloud storages" and so on.
My problem is that they started doing this my using "zero knowledge" as a term from cryptography. The trend had started in early 2010s or so, as cryptocurrencies and all things crypto became popular, people realized they could use that vibe for profit.
So cloud storage providers in particular had realized "zero knowledge" sounds cool and fancy and started using it in their marketing despite stealthily assigning it entirely different meaning from where they took it from (well, some had their cryptographic designs all backwards recognizably even to my uneducated brain - false promises when most customers don't have sufficient knowledge and awareness, business as usual). They were critiqued for it, and they just shrugged it off because who gives a fuck about some angry nerds insisting on some correct word usage. And so this shit caught on, and yes, now we have two meanings.
I suppose I got to let it go, but I feel upset about the outcome.
As far as I understand it (and I'm not a cryptographer!), it is not zero knowledge.
Zero knowledge means you can prove you know something without disclosing any additional information about it, at all - that's why it's called "zero". And here, a hash of crush name is exposed, so it's not.
But why impossible? Take this example: https://en.wikipedia.org/wiki/Zero-knowledge_proof#Discrete_... - all parties exchange are essentially random numbers (which doesn't count as "additional information"), yet they establish the fact that Peggy knows x. There's that footnote about how r must be truly random, of course, but as long as everything's done right there is no additional information there whatsoever, only random noise.
Side note: one thing I certainly don't understand are NI-ZK - while I think I have some rough understanding of how interactive ZK proofs work - well, I mean, I've read Quisquater et al.'s "How to explain zero-knowledge protocols to your children" - but I'm pretty clueless how they manage to make such things non-interactive.
Oh, I think I see your point now. But I think it's a weird argument, to be honest.
I suppose the fact that it's Peggy and Victor who are running that protocol is simply irrelevant. They're talking about that value of x after all, and nothing related to that topic is revealed beyond the proof of the fact that Peggy knows it. If she'd appear in person, wherever she wears a red shirt or a white one would be might be considered "information" but it would be completely out of scope.
