Paper 2021/1338
Embedded Multilayer Equations: a New Hard Problem for Constructing PostQuantum Signatures Smaller than RSA (without Hardness Assumption)
Dongxi Liu
Abstract
We propose a new hard problem, called the Embedded Multilayer Equations (eMLE) problem in this paper. An example of eMLE, with one secret variable x and three layers, is given below. 6268 = 57240 * x + (1248 * x + (9 * x mod 16) mod 2053) mod 65699 In this example, the eMLE problem is to find x from the above equation. eMLE in this paper has the same number of variables and equations. The hardness of eMLE problem lies in its layered structure. Without knowing the eMLE value of lower layer (i.e., the layer with modulus 2053), the top layer (i.e., the layer with modulus 65699) has many candidate solutions; the adversary has to search the solution space for a few valid ones. A lowerbound for the number of searches has been proven in the paper, together with the expected number of valid solutions. The hardness of eMLE can be increased by adding more layers, without changing the number of variables and equations; no existing NPcomplete problems have this feature. Over the hardness of eMLE, a postquantum signature scheme, eMLESig, is constructed. Compared with all existing signature schemes (conventional and postquantum), eMLESig might be the simplest to understand, analyze, instantiate, and implement. At the security level above 128 bits, five configurations are provided; all of them have keys and signatures smaller than RSA keys and signatures (above 380 bytes) at the 128bit security level. The smallest configuration is with two variables and three layers, having 84.1/52.2 bytes for private/public key and 168.4 bytes for signatures.
Note: New eMLESig is multivariate cubic equations, but can be extended to any high degree (e.g., 7th degree; Hilbert's 13th problem is 7th degree equation).
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. Minor revision.
 Keywords
 Postquantum SignatureRSAComplexity theory
 Contact author(s)
 dongxi liu @ csiro au
 History
 20211102: last of 10 revisions
 20211005: received
 See all versions
 Short URL
 https://ia.cr/2021/1338
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1338, author = {Dongxi Liu}, title = {Embedded Multilayer Equations: a New Hard Problem for Constructing PostQuantum Signatures Smaller than RSA (without Hardness Assumption)}, howpublished = {Cryptology ePrint Archive, Paper 2021/1338}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/1338}}, url = {https://eprint.iacr.org/2021/1338} }