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

How to prove you know a secret without giving it away

quantamagazine.org

Post reply on HN
Print view View original

161–170 of 171 posts

Re: How to prove you know a secret without giving it away

#161

Post by yencabulator »

Double_a_92 wrote: post #147
amenghra wrote: post #112

Earlier quoted context omitted.

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

But then what is the point of the foil? Just take a very zoomed in photo of Waldo?

It's a real-world application of cropping the visible area, for a kid to show to another kid, ELI5 style.

Re: How to prove you know a secret without giving it away

#162

Post by HWR_14 »

pexabit wrote: post #124
HWR_14 wrote: post #75

Earlier quoted context omitted.

> Identified electors cast ballots on paper counted under recorded and public observation. You mean that the vote is tied to the voter, so everyone can tell X voted for Y? That sounds horrible. If you mean that paper votes are simply counted under recorded observation (and observation by representatives of all parties) I would point out that didn't help in the US.

Paper ballots weren’t cast and counted under general public observation in the US. And I mean a ballot stub that is separated at the time it is cast is tied to a voter.

I have no idea what you mean by ballot stub, and no idea if that means that you are eliminating the secret ballot. It sounds like you want everyone to have a receipt tied to their vote, which doesn't even sound helpful.

And I have no idea in what way your system differs from the status quo in the US. Most states use paper receipts and those were recounted. All that stuff about "bamboo fibers" was because of the paper ballots.

Re: How to prove you know a secret without giving it away

#163

Post by pyuser583 »

Nursie wrote: post #79
pyuser583 wrote: post #54

Earlier quoted context omitted.

I’m pretty sure the multiple reports on electoral interference said the outcome of the election wasn’t affected.

And? Again we have one person who thinks that the (proven) Russian interference might have taken the election away from her. She's probably wrong, so? We have a second who has actually tried to have a democratic result overturned and tries his best to undermine it at every turn, through 'soft' pressure by cajoling officials, through many failed court cases, through inflammatory rhetoric and eventually through raising…

I’m glad we agree!

Re: How to prove you know a secret without giving it away

#164

Post by 1-more »

elliekelly wrote: post #136
unnouinceput wrote: post #56

Earlier quoted context omitted.

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

Have you ever had allergies and a cold at the same time?

https://en.wikipedia.org/wiki/Hickam%27s_dictum "A patient can have as many diseases as they damn well please."

Re: How to prove you know a secret without giving it away

#165

Post by thehappypm »

can16358p wrote: post #78

I'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?

If you complete the maze by luck and can repeat yourself, then you have gained the information you claimed to have!

Re: How to prove you know a secret without giving it away

#166

Post by elondaits »

PeeMcGee wrote: post #98
can16358p wrote: post #78

I'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?

Yeah, 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!

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

Re: How to prove you know a secret without giving it away

#167

Post by fritolaid »

seewhydee wrote: post #40

Scientists 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 moo…

you said "analgrams"

Re: How to prove you know a secret without giving it away

#168

Post by junofan »

elondaits wrote: post #166
PeeMcGee wrote: post #98

Earlier quoted context omitted.

Yeah, 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!

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

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

Re: How to prove you know a secret without giving it away

#169

Post by kazinator »

seewhydee wrote: post #40

Scientists 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 moo…

Today, you'd register a SHA256 sum of a sentence, or public-key encrypted sentence, etc.

Re: How to prove you know a secret without giving it away

#170

Post by eru »

getcrunk wrote: post #51
bockchain wrote: post #38

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

I bet $1000 that this is an ai bot. Hn should have a bot that bans bots

I would like to take the other side of that bet.
Post reply on HN