Efficient verifiably encrypted signatures from lattices

Abstract

Verifiably encrypted signature schemes can convince a verifier that a given ciphertext is an encryption of an ordinary signature on a given message and the ordinary signature can be recovered by the third party, called adjudicator. In 2010, Ruckert et al. proposed a general construction for the verifiably encrypted signatures, and then, they also showed that there exist the lattice-based verifiably encrypted signature schemes. Their constructions are very insightful, but their schemes need an extra adjudication setup phase and Merkle trees, so they have large parameters and keys, that is, they are inefficient. Also, their schemes provide only the limited signature capacity because the signing keys should be reissued after generating th verifiably encrypted signatures. To overcome the weaknesses of Ruckert et al.'s scheme, we construct a verifiably encrypted signature scheme based on the hard lattice problems. Our scheme provides the full functionality, i.e., the signatures can be generated without any limitations and does not need any extra adjudication setup phases. Moreover, the size of the secret keys in our scheme is constant. Our scheme provides unforgeability, opacity, extractability, and abuse-freeness in the random oracle model.