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 moons and (ii) Jupiter has red spots. Bizaarely, both turned out to be true facts, but not what Galileo's anagrams were about!
This reminds me of fixing a bug that causes your problem but then you discover the problem persists after the fix and that you actually had two independent bugs causing the same problem.
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 <string "CARTER" is not a number> 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.
That is a very project managery view of things. And in a simple system you might be right. In a complex system multiple different things can cause same looking problems.
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.
I see your point which is semantically valid. But there is something more to it. Consider it from the other direction: You can introduce a bug by making some modification to the code. Then you add another modification which produces the same erroneous behavior. Either one alone would be enough to cause the problem. And two of them together does not cause any more problems than each of them alone.
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".
Obviously it'll be a bit contrived for this example, but... Suppose the logic that checked whether the input was a number used the hardcoded string "CARTER" rather than the value from the input. And, totally independent from that, your error display code just displayed the hard coded "example" value '"CARTER" is not a number' regardless of whether the state was correct or not.
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.
I used to play a social deduction game on IRC, and this was one method to reveal things without revealing them.... but it was too powerful so was banned sort of.
There is also spyfall (https://boardgamegeek.com/boardgame/166384/spyfall) which is about one person not knowing what everyone else knows and trying to pretend otherwise. Very popular among my friends.
Excellent party/social game. An additional variant we play with is to create an "Oops, All Spies" deck to throw in the random selection. Everyone believing that they are the only one who doesn't know the location inevitably leads to hilarity.
Sounds like a regular game of mafia or werewolves, which basically just requires someone to run it and some means of communication, whether it be in-person, IRC, forum, or some other chat application (there are more 'formal' versions of it in the form of board games or video games, like town of salem, as well).
Picked up Town of Salem recently. Quite a fun game. Have been pleasantly surprised with a good experience even with random other people most of the time
According to school professors, the only way to prove that a person knows something is to lock them in a room for an hour or two and have them write down the entire thing on a piece of paper while being watched intently.
Well, most of the time I attempted a zero-knowledge proof in school I couldn’t convince the teacher ;)
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.
At the beginning, where the hidden passage is explained, isn't there a "race condition", where Ali Baba would eventually (across 40 repetitions) run into the thief? The thief picks one branch, Ali Baba the other. The thief uses the passage, then walks right into Ali Baba?
I don't understand how the thief can be sure to never walk into Ali Baba coming down the other path at some time.
The thief waits in his own passage until he knows the victim has followed him down that passage. He does not pass through the door if the victim is in the other passage. The authors briefly mention this:
> After a very uncomfortable wait he saw a thief arrive who, *sensing he was pursued by his victim*, whispered the magic words, “Open sesame.”
I guess the thief can observe / hear Ali Baba's approach and decide on using the secret passage to go to the other path (if Ali Baba is approaching his way) or just run out the current passage if Ali Baba chose the other one.
I recently published a fairly detailed blog post about how to formulate expressive provable programs in Lurk (https://github.com/lurk-lang/lurk-rs). Although this post goes into no details about the underlying proving mechanism, it does build to some pretty powerful ideas. If you haven't thought about the implications of being able to prove correctness of a computation without revealing some or all details of what the computation actually was, you might enjoy it. https://blog.lurk-lang.org/posts/prog-intro/
There was a recent podcast by ZK Knowledge about homomorphic encryption and how this is different and complementary to ZK proofs. The founder of Zama had some surprising things to say (from my perspective) about how ZK is not something that can be used to guarantee privacy when used with blockchain tech. I'm sure that will be exciting news to everyone on HN. :)
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?
Imagine the maze is large and complicated, so that it would be very unlikely you could find the exit by luck. Not impossible, but like winning the lottery odds. You could brute force the search but you don't have time. The probability of finding a path by luck is called "soundness error". When the verifier sees you appear at the exit, they know you either knew the path, or with a soundness error probability, you were just lucky.
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.
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.
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".
Can you give an example of such a bad concept explained in Applied Cryptography vs Serious 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?
I don't remember there being anything downright wrong in Applied Cryptography, at least at the time it was published, although it doesn't convey a lot of the nuance that is required in implementing secure systems. But it now 30 years out of date.
If you don't know the books position under the foil, and the hole is just big enougn to show it's waldo, you cannot get the coordinates, but you know that the person who covered the book with a punctured foil knows where waldo is.
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.
But if you don't know the position of the foil, what does it prove? The other person could just move the foil around arbitrarily until it randomly fits.
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.
Well whoever's doing the verifying would need to have a way to align that piece of foil in a way that shows the position, and unless both people know that process it's useless anyway.
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.
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.
> For a simple way to understand this idea, let’s suppose you want to show your friend that you know how to get through a maze, without divulging any details about the path. You could simply traverse the maze within a time limit, while your friend was forbidden from watching. (The time limit is necessary because given enough time, anyone can eventually find their way out through trial and error.) Your friend would know you could do it, but they wouldn’t know how.
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.
The friend sees you enter the maze at the entrance. They don't watch you traverse the maze, instead they run around the outside of the maze to the exit. They see you leave by the exit 2 minutes later.
They don't know the path you took and they can be reasonably sure you didn't brute-force it in that time.
FWIW the linked paper on nuclear warheads is fairly accessible. You don’t need to understand nuclear physics to grok the algorithm.
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.
As demonstrated in central north america recently the real challenge isn't in proving election results .. it's in the greater social challenge of propagating belief and trust in the results in the face of concerted efforts to widely undermine such.
Well secure and rather indisputably valid elections are a solved problem, and many countries manage it. Identified electors cast ballots on paper counted under recorded and public observation. (I think a scantron would be fine, too).
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)
Can you name a country where an actually observably valid election takes place?
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.
Maybe I missed something in your question, but what we have in France seems pretty close.
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.
Same exact process in Italy, except we also use ballot tagging to fight organized crime. For all the problems we have, trusting the results of an election isn't one...
> 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.
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.
Mechanism - a good one - should solve various problems to have the issue resolved. They're saying they have "technical" mechanism, but if everybody would always follow the law it could be much simpler.
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.
The second paragraph is an assertion. And urban registration drives are heavily funded. Most people who do not vote do not vote because they do not want to vote.
I don’t think a scantron machine not connected to the Internet would sow distrust. We have seen them in our high schools. And Adversarial observers can validate the results on test samples quite easily.
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.
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?
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.)
US can probably run two parallel simultaneous systems of record - the technobabble one and regular one, with regular one being the authoritative. After some practice is accumulated working with the other one, they can decide what to do next.
IIRC, Hillary was among a group claiming "stolen elections" https://www.youtube.com/watch?v=hUqxX0YAafg and that her opponent was an illegitimate president... so, you know, it's not a unique claim. Also miss Abrams seems to make similar claims. These claims happen a bit in local elections.
There’s a much longer and “prouder” tradition of Americans claiming elections were rigged stretching all the way back to when it was true. Bush v Gore is another recent example but older folks will probably remember claims about Kennedy’s election and Nixon’s in ‘60. Andrew Jackson is somewhat credibility accused. And that’s just presidential elections off the top of my head.
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.
I understand the big difference between Trumps delusions, and Clinton’s opinions.
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.
I'm not giving Clinton any credit for anything (if anything, I'm denying her credit—for things she didn't do), and nobody is saying Clinton was innocent. You just distorted what had happened and are now twisting what I said.
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.
On the one hand we have the Mueller report which finds that there was Russian interference in the 2016 election in the form of coordinated social media and other 'attacks' on the Clinton campaign. This seems to form some reasonable basis for making claims that the election was ‘stolen’ (informally, and clearly not a legal basis to overturn a result).
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.
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 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.
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.
In the paper the authors describe using a blockchain to store the results. The blockchain is only mined in private, by an administrator, where voter id information is removed after the election. What is the benefit of a blockchain over a table (csv, JSON, database, excel etc) to store the data? Blockchains application is when you need to reach shared consensus without trust. We’re not in this situation that the paper describes.
Side topic, but why does something relatively respectable like Quanta Magazine need a reading progress bar? These odd decisions truly amaze me sometimes.
At least on macOS you can enable a setting to always show the scroll bar. And on Android Firefox it displays the scroll bar while actively scrolling so you know your relative position in the page.
Maybe because it can then also cater to audiences who do not generally visit such sites or reading long-er articles.
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.
Sure, but that only works if you both know the answer. Zero knowledge proofs are neat because you can prove you know the answer to somebody who doesn't know it.
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."
Hashing parts of the problem works for interactive proofs.
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.
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...)
It would be a random string for the verifier as he does not know the secret. It’s much like one can sign a document without revealing a secret key. In fact signatures are proofs of g^sk=pk where the document hash is a verifier challenge.
You just enlarged the number of people in the confidence. Most people in the universe will still be completely uninformed about it, even if you spent tremendous resources on making it readily publicly available. Just considering human beings, most people are already dead anyway.
> 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. Now with blockchain, my life is so easy - I just show them the blockchain transaction and they know that I know.
> 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, ...
I thought the joke would continue that now with blockchain, I don't have a girlfriend anymore.
Except that any of the various RFC3161 compliant crypto timestamp services available would have done, too. They are run i.e. by the Swiss Post (commercial), or the german DFN (a non-profit conglomerate of german research facilities and universities). So you could show your girlfriend the crypto timestamp with its included Hash, and also proof you had the secret at a specific point in time, without giving it away.
Not sure if you are trolling? If the secret is on the blockchain, it literally becomes public by definition. And if it's encrypted somehow, what is the point of the blockchain?
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.
He can tell, because he has a secret bot detection bot. That bot can detect 100% correctly with no false-positives, as long as he never reveals how it operates. The bot is named ZeroK.
He doesn't need to, he only needs to be confident that someone with more knowledge (or confidence) in the actual status of the commenter won't make a counter-bet
During the old forum mafia days message digests were one of the ways people made predictions that you'd reveal later. You would usually tack on something random at the end to make guessing hard.
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!