Homomorphic Witness Encryption and Its Applications

In witness encryption (WE), an instance x$$ x $$ of an NP problem is allowed to be used to encrypt a message, and who holding a witness of the problem can efficiently decrypt the ciphertext. In this work, we put forth the concept of homomorphic witness encryption (HWE), where one can evaluate functions over ciphertexts of the same instance without decrypting them, that is, one can manipulate a set of ciphertexts with messages (M1,⋯,Mn)$$ \left({M}_1,\cdots, {M}_n\right) $$ to obtain the evaluation of f(M1,⋯,Mn)$$ f\left({M}_1,\cdots, {M}_n\right) $$, for any function f$$ f $$. We declare that such homomorphic witness encryption schemes can be generically constructed from indistinguishable obfuscation (iO$$ i\mathcal{O} $$) for any classes of functions. Then we propose the instantiate of multiplicatively homomorphic witness encryption (MHWE) and linearly homomorphic witness encryption (LHWE) using an iO$$ i\mathcal{O} $$, homomorphic encryption for NP problems such as Subset‐Sum and a batch‐processed GS‐proof system, which enables us to evaluate multiplication operations and linear operations over ciphertext. Furthermore, we show the practicality of homomorphic witness encryption by proposing new protocols for applications of interest, such as homomorphic time‐lock encryption, multi‐party contract signing, and e‐voting.