Paper 2020/974

Compact-LWE-MQ^{H}: Public Key Encryption without Hardness Assumptions

Dongxi Liu and Surya Nepal

Abstract

Modern public key encryption relies on various hardness assumptions for its security. Hardness assumptions may cause security uncertainty, for instance, when a hardness problem is no longer hard or the best solution to a hard problem might not be publicly released. In this paper, we propose a public key encryption scheme Compact-LWE-MQ^{H} to demonstrate the feasibility of constructing public key encryption without relying on hardness assumptions. Instead, its security is based on problems that are called factually hard. The two factually hard problems we propose in this work are stratified system of linear and quadratic equations, and layered learning with relatively big errors. The factually hard problems are characterized by their layered structures, which ensure that the secrets at a lower layer can only be recovered after the secrets in a upper layer have been found {\it correctly} (i.e., leading to consistent lower layer secrets, not necessarily the original upper layer ones). On the other hand, without knowing the secrets in the lower layer, the upper layer subproblem can only be solved by exhaustive search. Based on the structure of factually hard problems, we prove that without brute-force search the adversary cannot recover plaintexts or correct private key, and then discuss CPA-security and CCA-security of Compact-LWE-MQ^{H}. We have implemented Compact-LWE-MQ^{H} with a number of lines of SageMath code. Simplicity of Compact-LWE-MQ^{H} makes it easy for understanding, cryptanalysis, and implementation. In our configuration for 128-bit security, the dimensional parameter is $n=4$ ($n$ has the same meaning as in LWE). For such a tiny parameter, the current analysis tools like LLL lattice reduction algorithm are already efficient enough to perform attacks if the security claim of Compact-LWE-MQ^{H} does not hold. That is, the security of Compact-LWE-MQ^{H} is not assumed with the capability of cryptanalysis tools. SageMath code of verifying Compact-LWE-MQ^{H} security is also included in Appendix.