Math in your sanitary pass

QR codes are loaded with math. The health pass consists of 7,225 little white or black squares, arranged in 85 rows and 85 columns, that encode vaccination status, or test result, or certificate of recovery. This poses some very interesting mathematical and computer problems.

The first problem is geometric. The optical reader that scans the QR code sees the square in perspective, as any quadrilateral. So the perspective must be straightened: this is fairly easy. You also have to recognize the top and bottom, the right and left. This is also quite easy because three of the four corners are decorated with small 7 × 7 squares that are easily recognizable. Sometimes the QR code is presented on a sheet of paper that has been folded or crumpled and the rows and columns are not straight: you have to rectify them. Thirteen 5 × 5 squares, also recognizable, are spread out in the large square to help the software get it all straight.

Detectable although unreadable

The second problem comes from the fact that the reader can get confused because some of the little squares can be damaged. You have to use error-correcting codes that produce deliberately redundant messages, to make sure you get back what you need. Airplane pilots have known this for a long time by saying “Papa, Tango, Charlie” instead of “PTC”. QR codes use a more elaborate method, invented by Irving Reed and Gustave Solomon in 1960 and based on deep arithmetic theorems. The result is remarkable, since the reading can be done correctly even if 30% of the small squares are unreadable. Try making an ink stain (not too big) in the middle of your health pass and you will see that it is still valid.

Finally, the authenticity of the document must be guaranteed. Here again, very subtle mathematical and computer methods are used. Anyone can read the content of the certificate (provided they know a little about computers) but it is accompanied by an encrypted and unforgeable “digital signature” produced from the content of the message using an asymmetric secret code. The idea is that some operations are easy to do and almost impossible to undo.

Isn’t it said that it is easier to get toothpaste out of the tube than to get it in? The tube in question is still mathematical, based on 19th century arithmetic, greatly improved by 20th century computer scientists. Thanks to these methods, the TousAntiCovid Verif application can guarantee authenticity: we can verify a signature that a forger could not have produced.

Possible malpractice

However, not everything is perfect and malfeasance is possible. Access codes to Medicare servers can be stolen, or a dishonest caregiver could make a fake vaccination certificate. On the other hand, TousAntiCovid Verif only guarantees the validity of the pass, and does not provide any information other than name and date of birth. However, the QR code contains other data, such as the date of vaccination, type of vaccine, etc., which are intended for border crossings and which should not be accessible to everyone. Even if it is not legal, many websites allow to read and store the complete content of health passes.

Two centuries of mathematics have passed since the pioneering work of Carl Friedrich Gauss and Evariste Galois led to the emergence of modern cryptography. They would have been the first to be surprised to see that they are at the origin of these small black and white squares. Science takes its time and reserves surprises.