34 Post Quantum Crypto for Dummies ��0��3 + ��2��3 + ��0 + 1 = 0 ��0��1 + ��2��3 + ��2 + 1 = 0 ��0��1 + ��0��3 + ��0 + ��1 + 1 = 0 ��1��2 + ��2��3 + ��3 = 0 Figure 3.4: Example for a multivariate polynomial system of four equations in four variables x0,…, x3 (i.e., multivariate) of maximum degree two (i.e., quadratic) over ��2. This particular quadratic system is small and therefore easy to solve. A solution of this system is ��0 = 1, ��1 = 0, ��2 = 1, ��3 = 0. Classically, multivariate polynomial systems can be solved using different algorithms. In a brute-force search, all possible values for the variables are tested until the correct solution is found. This requires an exponential amount of time depending on the number of variables 11. An asymptotically more efficient approach is to solve the system numerically; there are several algorithms with different properties, e.g., the F4/F5 family 29, 30 and algorithms based on extended linearization (XL) 19.When taking quantum computers into account, Grover’s algorithm gives only the usual square-root speedup on exhaustive search 53. For constructing an asymmetric public-key system, the public key itself is a set of multivariate quadratic polynomials and the private key often is the knowledge of a trapdoor that allows to efficiently solve the multivariate system. Usually the trapdoor is constructed by computing the public key �� of m polynomials in n variables as the composition of two affine maps �� and �� and one quadratic map �� which is chosen such that it can be easily inverted 26, so �� = �� ∘��∘ ��. For signing a message z, Alice computes signature w by computing �� ′ = hash(��), �� = �� −1(�� ′), �� = �� −1(��), and �� = �� −1(��). Bob can simply verify the signature using the public key P of Alice by checking that hash(��) = �� (��). The public key �� must be constructed in such a way that an attacker is not able to invert the system. However, the composition of matrices �� , ��, and �� is not necessarily a hard instance of the M��-problem. Therefore, several compositions that were proposed have been broken. Nevertheless, there are constructions that are believed to be strong.
PQC_for_Dummies
To see the actual publication please follow the link above