How to prove you know a secret without giving it away
quantamagazine.org
quantamagazine.org
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!
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.
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".
In this case, I would say you have two bugs. First, that you aren't evaluating the actual input data and second, that your error checking code is not running correctly but just defaulting to the same value all the time. Bugs are distinct problems with your code, not problems that the user encounters and you have two distinct problems with your code.
Let's say you are not working on a "number box" (whatever that is) but a drone airplane. Your costumer reports that the drone become unresponsive and crashed.
You investigate and find that there is a buffer overflow which sometimes gets triggered in the navigation system which trashed the memory and lead to the loss of the drone. You develop a patch, and additional testing etc etc and you deploy the fix.
A year later a drone crashes again. You do the investigation and this time you find in the engine control there is an edge case which causes it to shut down the engine under rare circumstances.
Was the first fix not a fix? If I correctly interpret you it wasn't because the "drone becoming unresponsive and crashing" problem still persist. Obviously that is not a useful way to look at the work if you actually have to develop the fixes.
Obviously there was two different problems, and they both need fixing separately (often by different teams). Just because you are not aware of the second bug when you deploy the first fix doesn't make the first fix not a fix.
Of course you might say in this hypothetical the "problem was not the same" but you only know that after you have investigated. If there are no reasons to suspect the second bug, and during the testing of the first fix things appear to be working you have no way of knowing that.
The problem was fixed after the two bugs were fixed:
fix(problem) <= fix(bug1) & fix(bug2)Zero-knowledge proofs let others perform that verification before the full answer is revealed (and it might never be).
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.
These were not the proofs they were looking for.
https://www.researchgate.net/publication/221355016_How_to_Ex...
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?
> After a very uncomfortable wait he saw a thief arrive who, *sensing he was pursued by his victim*, whispered the magic words, “Open sesame.”
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 ..."
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/tra...
How does the interactivity exactly work with the maze example?
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.
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.
Now imagine the maze has a large number of exits, all hard to find by luck, and the verifier tells you before you go in which exit they want to see you come out of. You don't know in advance which exit they will ask for. After you come out, they ask you for another one, and again you don't know in advance which one. These rounds are the interactivity.
Each time through, you have a soundness error's probability of finding the requested path by luck, i.e. winning the lottery kind of odds. The probability that you found all the exits the verifier asked for, is like winning the lottery multiple times in a row. Because you don't know which the verifier will ask for in advance, you can't take advantage of patterns in those requests to skew the combined probability in your favour. They are like independent random events: The probabilities multiply.
After N rounds, your probability of finding all the requested exits by luck is lottery kind of odds raised to the power of N. Pick a sufficiently large N and you have extreme probabilities like those used in other cryptography, numbers like 2⁻¹⁰⁰ or 2⁻²⁵⁶, which are so infeasibly unlikely they are similar to the probability of guessing someone's private key or guessing a SHA-256 hash preimage. We trust this demonstrates you know the maze, even though there's an astronomically unlikely possibility that you guessed right every time.
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".
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?
Even Schneier himself wouldn't make the claim you just did.
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.
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.
I'm sure it's a massive simplification of the way it's actually used.
People use the similar concept in geocaching when they forget to bring a pen... take a photo of a geocache against a neutral background (asphalt, grass,...) thus proving they found it, but not revealing/spoiling the location to other geocachers.
Imagine having a where's waldo book, looking for waldo with a friend, and your friend says he's found him... you don't believe him, but he won't show it to you, because then you'll know the location of waldo too. How can he prove, that he found it, without showing the location to you? By taking this punctured-foil approach, he can prove it to you, that he actually did find it, and do it in a way, where you know he really found it, but you still don't know where it is.
Moving the foil randomly enough might work with a book, but this is just an example of a mathematical principle. An rsa key might be between 1 and 2^4096, randomly guessing the number is practically impossible (atleast with current computing power and without waiting literally millions of years). But if the owner uses the key and signs a number you gave him, you verify the signature with his public key, you know that he actually has the private key, but you dont know the actual key.
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.
They don't know the path you took and they can be reasonably sure you didn't brute-force it in that time.
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.
That's a whole other kettle of fish.
There's no way the small efficiency gain from automation is worth that cost.
Which raises the question- why do we use the really awkward, blackbox and sometimes networked machines that we do, manufactured by weird companies rather than whoever makes scantron machines or whatever?
And this isn’t just about “dumb Republicans” or what have you. Here’s Scott Aaronson [1] in 2016:
> For that matter, if Russia or some other power hacked the trivially-hackable electronic voting machines that lack paper trails—machines that something like a third of American voters still used this election—there’s an excellent chance we’d never find out.
“Antivirus on voting machines? You’re doing it wrong.” [2]
The thing that really gets me is, even if you wanted to use machines, you wouldn’t use the weird machines made by shady companies that we do. Different counties would buy standard scantron machines used to grade high school finals off the shelf, and verify it in ways that are obvious to all of us.
Because they’re cheap, states have to fund their own elections, and no governor will ever fund an election over schools or infrastructure.
The real question is why elections are not federally funded. The answer is that states are afraid election funds will be withheld over speciously related issues, just as highway funds are withheld over drinking ages. IMHO the correct change is a constitutional amendment guaranteeing federal funding for all state elections that can’t be withheld for any reason.
At most you could make an argument that federal elections should be federally funded. But I don't even know whether the US actually has any federal elections that the wider public participates in?
Eg the election for president is officially an election for some state officials that then go off and participate in the real federal election for president. (Of course, this is oversimplified.)
It is just that we choose not to do this. A provably convincing election isn’t actually some hard, unsolved problem. (And yes- if you mention zero knowledge proofs in your story of why the election is safe, people will look askance because an observably valid election is a solved problem, and many countries manage it)
And by this I mean an election where, somehow, an individual would be able to see their individual ballot make it from wherever they cast it, to the counter, and could see how their specific ballot impacted/didn't impact the broader vote, and where (again, somehow) there was proof that no artificial or false votes were cast in the name of citizens who either don't exist or didn't participate.
Even if there was a livestrem of the vote counting, that would mean nothing if we didn't see every step of transportation for every single vote from the ballot box to the counters office.
A truly observably fair election is practically impossible if you mean to have any significant number of voters.
Our ballots go into a transparent urn, you need to be registered in a voting office and show an ID paper to vote, and people counting the votes are typically a mix of local state employees and volunteers citizens (and given that most people don't want to spend their Sunday evening counting ballots, it's quite easy to get a place).
Now I guess it moves the trust onto the ID system and the aggregation of local counts into national results.
> A truly observably fair election is practically impossible if you mean to have any significant number of voters.
Just broadcast the counting live.
In some countries people would like to have undisputably valid elections, but can't, so I wouldn't call this a solved problem.
But I have a feeling you knew that already.
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.
And I mean a ballot stub that is separated at the time it is cast is tied to a voter.
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.
How do you reliably identify them without an ID card (which, as I understand it, the US doesn't have), or without an election-related "ID card" (which is pretty much the same thing)?
Trying to use SSNs will of course result in economically disadvantaged people having no right to vote, the same goes, more or less, if trying to rely on driver's licenses.
On the other you have a narcissist who actually tried to overthrow democracy to stay in power and throws around utterly baseless claims of an organised conspiracy of direct vote subversion and interference in the election mechanism itself, who was also caught trying to coerce others to do that for him over the phone.
These situations are not really comparable.
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 a mob. A person who continues to attack the election result and throw accusations of vast, entirely unevidenced illegal conspiracies.
These are not the same. It's a ridiculous false equivalence. I'm not American, I have no particular love for Hilary Clinton, but I saw the footage of January 6th and I know how out of the ordinary that is. Trump's conduct is far more than someone mithering about a loss they perceived as unfair, and to attempt to put these on a level is disingenuous at best.
More context: https://www.politifact.com/factchecks/2022/oct/05/glenn-youn...
She was talking about voter suppression and other tactics rather than the election results being tampered with.
This is important to point out, because the GOP is hellbent on messing with future elections and want an air of whataboutism regarding election integrity.
What Clinton (and I would bet most other folks that you're alluding to from the years prior) had meant by "stolen" elections or "illegitimate" president was emphatically not the same as Trump's wild allegations. She was not claiming "people cast fraudulent ballots" or "the votes were counted incorrectly" or the like. She was not denying what actually happened. Rather, she was using "stolen" to refer to things like "you can get the most votes but still lose the electoral vote, and thus the presidency", or "they make it difficult for your supporters to vote", or things like that. It's unfortunate she used the word "stealing" to refer to that, given that that apparently gave some people a very convenient opportunity to paint a false equivalency between both sides, when in reality she was using that word to make a factual statement about how votes are cast and counted in the system, whereas her opponent was using that word to to hurl unsupported (and "unsupported" is incredibly generous here) allegations of fraud.
Imagine if you were about to get a heart transplant. Someone grabs the donated heart sitting in the operating room and runs. "She stole my heart!", you panic. "Oh don't worry honey, my wife stole my heart too. It's pretty common! It happens to all of us." Imagine the sheer exasperation when you're on life support and now have to spend the remainder of your energy replying to that as a serious comment.
But you’re giving Clinton too much credit.
For one thing, neither Clinton nor Trump received over 50% if the popular vote. It’s tempting to think the Green and Libertarian voters wanted Clinton more than Trump - but third party voters have weird ideas.
Winning the presidency by getting the majority of the electoral college isn’t a steal.
If there were concerns about disenfranchised voters, maybe she would have a something.
But it was low turn out, plain and simple.
The election wasn’t stolen in any way shape or form. Nothing fishy happened. It wasn’t insanely close like in 2000.
She simply lost.
Not as bad as Trumps insanity. But not innocent either.
If you "understand [as you admit; emphasis mine] the big difference" between what Trump and Clinton were referring to and merely intended to argue "Clinton is not innocent", then by all means, go ahead and say that directly, instead of casually leaving an incredibly misleading comment claiming Trump's allegations were "not a unique claim" because Clinton and others have been making "similar" claims. "Big difference" and "similar" are not only dissimilar, they're about as diametrically opposite as you can go.
Like doing an HMAC reveals a tiny piece of information every time…
It is shocking
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.
For decades, every long page had a progress bar. Then, nonsense design fads dictated that the scroll bar should become invisible on some browsers.
Adding a progress bar seems redundant to me.
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.
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."
Yes, it works, but it doesn't because we'll all be dead when your computer has the answer.
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...)
https://www.prb.org/articles/how-many-people-have-ever-lived...
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.
This part gives it away. Also his username which is probably misspelled deliberately.
Thanks for this grandiose piece of satire.
Very ironic usage of this quote, imho. Almost like - "even a broken clock is correct 2 times a day"
I thought the joke would continue that now with blockchain, I don't have a girlfriend anymore.
You missed the "without giving it away" part.
You could just send an encrypted document to all the relevant people, and later on give them the key. At best the blockchain would prove that you actually send it to them (or everyone in that case), but nothing else.