Extractable Witness Encryption for the Homogeneous Linear Equations Problem

Witness encryption is a cryptographic primitive which encrypts a message under an instance of an NP language and decrypts the ciphertext using a witness associated with that instance. In the current state of the art, most of the witness encryption constructions are based on multilinear maps. Following the construction of Choi and Vaudenay based on RSA-related problems, we suggest a novel witness key encapsulation mechanism based on the hardness of solving homogeneous linear Diophantine equations (HLE problem). Our arithmetic-based construction aims to solve an issue raised by these authors where the security might be compromised if the adversary is able to find small solutions to a homogeneous linear Diophantine equation, while avoiding the inefficiency of multilinear maps. The security of our scheme is based on a hidden group order and a knowledge assumption.