Oil and Vinegar Makes A Hard Problem Easy
Fixing The Hole In The Internet in a Post Quantum World
Okay. This isn’t going to be an easy read, but it reveals an amazing method, and that could help fix our security in a world of quantum computers. The method involves taking a hard problem to solve, and then applying a trap door. If we know a little secret, the hard problem becomes easy.
Overall, quantum computers will be able to break our existing public key methods, such as discrete logs, RSA and elliptic curves. And so NIST has created a Post Quantum Cryptography competition, and one of the methods is known as Rainbow. This is known as the Oil and Vinegar method and uses multivariate cryptography with an added trapdoor. Unfortunately, Rainbow was cracked before the NIST announcement of the methods that it wants to be standardized, and how now been dropped from the competition. But the Oil and Vinegar method is still a strong method, so let’s take a simple example, and work through how the trapdoor works.
With multivariate cryptography, we have n variables within polynomial equations. For example, if we have four variables (w,x,y,z) and an order of two, we could have [here]:
w²+4wx+3x²+2wy−4wz+2wx+6xz=387
