The Value of Errors in Proofs

Katie Steckles

Nevanlinna Prize and Abel Prize winner Avi Widgerson opened this year’s HLF with a fantastic mathematics lecture, laying out the history of proofs from the ancient Greeks through to a 2020 result on quantum proof systems. Widgerson talked us through a range of proof systems, including probabilistic provers, which prove things are true with a high probability.

This might seem paradoxical – Widgerson admits, “Proofs are holy in mathematics; errors are terrible, and we try to eradicate them”. But if you know something is true with, for example, probability ⅔, repeated trials can reduce this error to below whatever arbitrary degree of certainty you like. So the value of the ‘errors in proofs’ mentioned in the title is that even though they’re not 100% certain, probabilistic methods can be used to prove plenty of things – including some things that can’t be proven using traditional deterministic methods.

The idea of proof verification was illustrated using a simple example by Widgerson: if you have a large integer, and want to prove it’s not a prime number, you can do this by writing down two smaller numbers that can be multiplied together to give the big number as the result. The amount of work it takes to find these factors might be considerable, but mathematicians are less interested in this, and care more about the next step – verification. If I wanted to check that your ‘proof’ – consisting of two smaller numbers – does indeed prove your big number isn’t prime, all I need to do is multiply them together. If your proof works, then it’s easy to verify – and verifiers are the real stars of proof systems.

Zero Knowledge? Zero problem!

Another type of paradoxical proof system Avi mentioned was that of Zero-Knowledge proofs. Conceived in 1985 by Goldwasser, Micali and Rackoff, these are a form of interactive proof – one in which a verifier, aiming to check whether a proof is correct, can ask a theoretically unlimited number of questions of the prover, to interrogate the proof and check it’s correct. Rather than just being sent the proof and verifying it, the verifier is allowed an interactive conversation back and forth with the prover. This opens up more possibilities for proof methods.

Zero-knowledge proofs are a particular form of interactive proof that sound very confusing. In a zero knowledge proof, the verifier is not allowed to learn any information during the verification process, apart from the truth value of the statement in question. So, our example of proving a number is composite by stating two of its factors doesn’t fit in this category – because the verifier will also learn the values of the factors. So how is it possible to convince someone you’ve proved something without giving them any information?

One classic example of a zero knowledge proof was first published by Jean-Jacques Quisquater et al in the 1989 paper “How to Explain Zero-Knowledge Protocols to Your Children“. The idea is that there’s a secret cave, with a fork in the path going to the left and right. The paths join together in a loop at the back of the cave, but you can’t go around the whole loop without knowing a secret magical password, as there’s a magical door blocking the way.

The prover knows the magical password, and wants to prove they know it to a verifier. This can be easily achieved by the prover going into the magical cave with the verifier, leaving them at the entrance, and heading off to the left but coming back from on the right. This simple method could convince the verifier that they know the secret magical password, but without them actually hearing what it is.

More complex versions of this protocol exist – in which it’s possible for the prover to convince the verifier that they know the password, but without anyone else watching from the viewpoint of the verifier from being able to know for sure that the prover knows the password. It can very quickly become a knotty tangle of truth, proof and knowledge!

A Puzzling Protocol

Another more complicated protocol, involving another example Widgerson used in his talk, is that of sudoku puzzles. Widgerson explained that if you want to prove you have the solution to a sudoku, you can present someone with your solution, and they can check that the solution satisfies all the conditions required of a sudoku – that each row, column and 3-by-3 box contains all the numbers from 1-9 once each.

But what if you want to prove to someone that you can solve a sudoku, but without revealing to them what the solution is? They might want to solve it themselves later! This is possible with zero knowledge proofs – in the 2007 paper “Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles”, Gradwohl, Naor, Pinkas and Rothblum presented a variety of protocols for communicating sudoku solutions – including cryptographic methods, and physical protocols involving scratch-off cards.

My favourite, though, is one entitled “A physical protocol using scissors”. The idea is that the solver produces a version of the solved puzzle in which it’s clear which cells originally had number clues in – by using a different colour for those cells. This ensures the puzzle you’ve solved is the actual puzzle you’re talking about, and you haven’t brought the solution to an easier puzzle. (If you want to be sure, the number clues can be copied through on to the back and this side shown to the verifier).

The verifier then chooses one from ‘rows’, ‘columns’ or ‘subgrids’. The prover uses scissors to cut the puzzle into nine pieces, according to the set chosen, then proceeds to cut up each row, or column, or subgrid into nine individual squares, putting each set of nine tiny squares into a separate envelope (sealed, so any tampering is evident). These can then be passed to the verifier, who can check that each one contains the numbers 1-9, and that the correct number and combination of original clue numbers is present in the sets.

The fact that the verifier chooses which direction to initially slice the sudoku will prevent the prover from being able to cheat – without a valid solution to the original puzzle, at least one of the three choices will result in a set of envelopes with the incorrect set of clue numbers on the pieces. With repeated trials using different copies of the same solution, this uncertainty can be reduced to suit your requirements – as Avi Widgerson explained, even if there’s a chance your proof has an error, it can still have immense value.

The post The Value of Errors in Proofs originally appeared on the HLFF SciLogs blog.