Cryptology ePrint Archive: Report 2010/200

Generic Constructions for Verifiably Encrypted Signatures without Random Oracles or NIZKs

Markus Rückert and Michael Schneider and Dominique Schröder

Abstract: Verifiably encrypted signature schemes (VES) allow a signer to encrypt his or her signature under the public key of a trusted third party, while maintaining public signature verifiability.

With our work, we propose two generic constructions based on Merkle authentication trees that do not require non-interactive zero-knowledge proofs (NIZKs) for maintaining verifiability. Both are stateful and secure in the standard model. Furthermore, we extend the specification for VES, bringing it closer to real-world needs. We also argue that statefulness can be a feature in common business scenarios.

Our constructions rely on the assumption that CPA (even slightly weaker) secure encryption, ``maskable'' CMA secure signatures, and collision resistant hash functions exist. ``Maskable'' means that a signature can be hidden in a verifiable way using a secret masking value. Unmasking the signature is hard without knowing the secret masking value.

We show that our constructions can be instantiated with a broad range of efficient signature and encryption schemes, including two lattice-based primitives. Thus, VES schemes can be based on the hardness of worst-case lattice problems, making them secure against subexponential and quantum-computer attacks.

Among others, we provide the first efficient pairing-free instantiation in the standard model.

Category / Keywords: public-key cryptography / Generic construction, Merkle tree, post-quantum, standard model

Date: received 10 Apr 2010, last revised 17 Apr 2010

Contact author: markus rueckert at cased de

Available format(s): PDF | BibTeX Citation

Note: Preliminary draft.

Version: 20100417:083301 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]