Abstract: Verifiably encrypted signatures (VES) can ensure the fairness of the Internet exchange process effectively. In a VES system, a signer can generate an ordinary signature on a given message using the secret key of the signer and then encrypt it under the public key of the adjudicator. A verifier should be able to verify that this encrypted signature is indeed an encryption of the ordinary signature of the signer, but the verifier cannot be able to extract the ordinary signature. The ordinary signature can only be recovered by the adjudicator from this encrypted signature. Using the technique of basis delegation in fixed dimension suggested by Agrawal et al in CPYPTO 2010, the lattice-based preimage sampling algorithm and a non-interactive zero-knowledge proof for the learning with errors (LWE) problem, this paper constructs a new verifiably encrypted signature scheme from lattices, and based on the hardness of the short integer solution (SIS) problem and the LWE problem, this proposed construction is provably strong unforgeable in the random oracle model. Compared with current verifiably encrypted signature schemes, this scheme needs that the public-private key pair of the signer should be generated according to the public key of the adjudicator, and this scheme can resist quantum attacks and enjoy simpler constructions, shorter public-private keys, smaller signature size and higher efficiency.

Key words: verifiably encrypted signature (VES), fixed dimension, lattice, random oracle model, the learning with errors