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 designing 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 proposed in this work are stratified system of linear and quadratic equations, and learning with relatively big errors. Such factually hard problems have the structures to ensure that they can only be solved by exhaustively searching their solution spaces, even when the problem size is very small. Based on the structure of factually hard problems, we prove that without brute-force search the adversary cannot recover plaintexts or private key components, and then discuss CPA-security and CCA-security of Compact-LWE-MQ^{H}. We have implemented Compact-LWE-MQ^{H} in SageMath. In a configuration for 128-bit security level, the public key has 3708 bytes and a ciphertext is around 574 bytes.