Towards Witness Encryption Without Multilinear Maps

Current proposals of extractable witness encryption are based on multilinear maps. In this paper, we propose a new construction without. We propose the notion of hidden group with hashing and make an extractable witness encryption from it. We show that the construction is secure in a generic model. We propose a concrete construction based on RSA-related problems. Namely, we use an extension of the knowledgeof-exponent assumption and the order problem. Our construction allows to encrypt for an instance of the subset sum problem (actually, a multidimensional variant of it) for which short solutions to the homogeneous equation are hard to find. Alas, we do not propose any reduction from a known NP-complete problem.