Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Confess your love with zero-knowledge

zkcrush.xyz

Post reply on HN
Print view View original

191–200 of 205 posts

Re: Confess your love with zero-knowledge

#191

Post by imagin8or »

random314 wrote: post #6
Tomte wrote: post #2

This is some strange notion of zero-knowledge. If Bob publishes his link, and I want to know who his crush is, I can simply try all our classmates' names and quickly find out that it's Alice. Those games only make at least a bit of sense when everybody enters their crush and only when matching both get notified. Also brute-forceable, but at least it's quadratic (if you suspect nothing about crushes, which is unrealis…

Or just tell your crush, without sharing URLs with everyone

I feel like this could be a good implementation.

"Find out if your crush fancies you, just choose them from your contacts:"

...

"Message 'hey there, I like you' sent"

Re: Confess your love with zero-knowledge

#192

Post by rocqua »

hinkley wrote: post #146
baby wrote: post #135

This has nothing to do with zero-knowledge crypto. Here's some intuition about what zero-knowledge is actually about: https://minaprotocol.com/blog/kimchi-the-latest-update-to-mi...

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…

This system is not zero knowledge, because publishing the link actually leaks info to non-intended recipients.

Suppose I share a link, and you suspect I am trying to steal your partner. You could easily check whether my crush is your partner.

Re: Confess your love with zero-knowledge

#193

Post by rocqua »

I found this blog post a great explanation: https://blog.cryptographyengineering.com/2014/11/27/zero-kno...

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'.

Re: Confess your love with zero-knowledge

#194

Post by vintermann »

sangel wrote: post #118
vintermann wrote: post #96

Earlier quoted context omitted.

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).

Re: Confess your love with zero-knowledge

#195

Post by [deleted] »

motohagiography wrote: post #168
ghayes wrote: post #92

Earlier quoted context omitted.

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?

> the fact anyone can learn they are not the target is knowledge, right? To a point, however, you've also described a Bloom filter reasonably well. That is it would show whether their hash is not in the set.

[deleted]

Re: Confess your love with zero-knowledge

#196

Post by baby »

hinkley wrote: post #146
baby wrote: post #135

This has nothing to do with zero-knowledge crypto. Here's some intuition about what zero-knowledge is actually about: https://minaprotocol.com/blog/kimchi-the-latest-update-to-mi...

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…

What you’re describing is more like MPC to me

Re: Confess your love with zero-knowledge

#197

Post by baby »

totetsu wrote: post #149
baby wrote: post #135

This has nothing to do with zero-knowledge crypto. Here's some intuition about what zero-knowledge is actually about: https://minaprotocol.com/blog/kimchi-the-latest-update-to-mi...

Crypto like cryptography or crypto like cryptocurrency?

As in cryptography, although the link I posted also explains how it can be applied to smart contracts

Re: Confess your love with zero-knowledge

#198

Post by drog »

drog wrote: post #167

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 wit…

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 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.

Re: Confess your love with zero-knowledge

#199

Post by drog »

Godel_unicode wrote: post #184
drog wrote: post #167

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 wit…

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.

Re: Confess your love with zero-knowledge

#200

Post by Leherenn »

arcastroe wrote: post #178
MaxLeiter wrote: post #174

Earlier quoted context omitted.

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.

Post reply on HN