CHAPTER 3 Families of Post-quantum Schemes 35 This construction allows to use under-defined systems for signature schemes, i.e., systems with more variables than equations. The equation system composed of z and �� may have more than one solution. Any of these solutions is a valid signature. The confidence in multivariate signature schemes is quite high. For example, there is a consensus that the HFEv- signature scheme 50, 40 can be considered secure. The disadvantage of HFEv- is its relatively large public key 51. Research on parameters that are post-quantum secure is still ongoing. Under the assumption that systems of 200–256 variables over ��2 (or systems of similar entropy over larger fields) are required to withstand attacks by quantum computers, the size of the public key is between 500kB and 1MB. Other examples for promising multivariate signature schemes are Rainbow 25 and MQDSS 36. There are attempts to reduce the key sizes by using systems in fewer variables but of higher degree and over much larger fields. However, the security of such systems is not well understood. A second approach is to use sparse systems in order to compress the public key. However, the sparsity usually leads to a loss in security; construction of secure sparse systems is an open research question 26, Sec. 6.1. The situation looks different for public-key encryption schemes:Here the resulting equation system must have only one solution, otherwise the cipher text cannot be uniquely decrypted. In order to achieve this for arbitrary inputs, the system must be over-defined, i.e., the public key �� must have more polynomials than variables. Many constructions for public-key encryption that have been proposed were broken quickly because the trapdoor could not effectively be hidden from an attacker. Currently, there are not many multivariate public-key encryption schemes that are considered secure. An example is the PMI-plus public-key encryption system 24. PMI-plus is secure against known attack strategies but it is considered to be too premature for confidence in its security. Building a strong, efficient, and secure multivariate encryption scheme is an open challenge. Constructions based on random multivariate systems can also be used for pseudo random-number generators, cryptographic hash functions, and symmetric encryption. For example, the symmetric block cipher QUAD 6 is using �� + �� quadratic polynomials with n variables over ��2. These polynomials are not secret. QUAD uses a state that is initialized with a secret n-bit key. In each iteration, the equations are evaluated at the state vector. The result of the first m polynomials is appended to the key stream, the state is updated with the result of the
PQC_for_Dummies
To see the actual publication please follow the link above