A Robust Verifiably Encrypted Signature Scheme

Jianhong Zhang, Wei ZouLecture Notes in Computer Science 2006 · DOI · OpenAlex

Abstract

Verifiably Encrypted Signatures (VES) are essential primitives for achieving fair exchange in digital transactions, allowing a signer to provide an encrypted signature that a verifier can validate without accessing the underlying plaintext. This paper presents a critical cryptanalysis of a previously proposed identity-based VES scheme by Gu et al., demonstrating its vulnerability to universal forgery. To address these security gaps, we propose a novel identity-based VES scheme based on bilinear pairings. Our construction is provably secure against existential forgery and extraction under the Computational Diffie-Hellman Problem (CDHP) within the Random Oracle Model. Furthermore, the proposed scheme offers improved efficiency, resulting in shorter signature lengths and lower computational overhead compared to existing flawed constructions.

1. Introduction

In digital commerce, the "Fair Exchange" problem describes a scenario where two parties, Alice and Bob, wish to swap digital items (such as a signature for a payment) without either party being able to cheat. Verifiably Encrypted Signatures (VES) provide an "optimistic" solution to this problem. In a VES protocol, Alice creates a signature and encrypts it such that Bob can mathematically verify its validity without being able to read it. If Alice receives her payment but refuses to provide the decryption key, a trusted third-party Adjudicator can decrypt the signature for Bob.

Identity-Based (ID-based) cryptography further enhances this by using a user's public identifier (e.g., an email address) as their public key, eliminating the need for complex Public Key Infrastructure (PKI) and certificate management. This paper identifies fundamental flaws in a previous ID-based VES attempt and proposes a robust, efficient alternative.

2. Cryptanalysis of the Gu et al. Scheme

The authors demonstrate a "Universal Forgery Attack" against the identity-based VES scheme proposed by Gu et al. The vulnerability arises because the verification equation treats two components of the signature, $U_1$ and $U_2$, as independent variables.

In the flawed scheme, the verification equation does not sufficiently "bind" these variables to the message or the signer's identity. Consequently, an attacker can solve for values that satisfy the verification equation without ever possessing the signer's private key. The paper provides a four-step algorithm that allows any malicious actor to forge a valid-looking encrypted signature for any arbitrary message $m$, rendering the Gu et al. scheme insecure for practical use.

3. The Proposed Robust VES Scheme

To rectify these vulnerabilities, the authors propose a new ID-based VES scheme utilizing Bilinear Pairings on cyclic groups $G_1$ and $G_2$. The construction is designed to tightly couple the encrypted components, ensuring that they cannot be manipulated independently by an attacker.

3.1 Mathematical Foundation

The security of the scheme is rooted in the Computational Diffie-Hellman Problem (CDHP). The system utilizes a map $e: G_1 \times G_1 \to G_2$ with properties of bilinearity, non-degeneracy, and computability. By basing the signature on these properties, the authors ensure that the relationship between the encrypted signature and the signer's identity is mathematically inseparable without the proper keys.

4. Security Analysis

The authors provide formal security proofs using the Random Oracle Model. The security of the scheme is evaluated based on two primary criteria:

  • Unforgeability: The authors prove that if an attacker could successfully forge a signature in this VES scheme, they would effectively be able to break the well-established Hess signature scheme. This reduction demonstrates that the VES scheme is as secure as the underlying signature primitive.
  • Opacity (Security against Extraction): This property ensures that no one (except the Adjudicator) can extract the original signature from the encrypted version. The authors prove that extracting the signature is computationally equivalent to solving the CDHP, which is considered infeasible for modern cryptographic parameters.

5. Performance and Efficiency

Beyond security improvements, the proposed scheme offers significant performance advantages:

  • Signature Size: The resulting verifiably encrypted signature is shorter than those produced by the flawed Gu et al. scheme. This reduction in size translates to lower bandwidth requirements and reduced storage costs for high-volume transaction systems.
  • Computational Complexity: The paper provides a detailed complexity analysis, showing that the scheme scales efficiently with the number of hash and signature queries ($q_{H}$ and $q_{VS}$).

6. Limitations and Future Work

While the proposed scheme is a significant advancement, two primary limitations remain:

  1. Random Oracle Model: The security proofs rely on the idealized assumptions of the Random Oracle Model. Developing an ID-based VES that is secure in the "Standard Model" remains an open challenge in the field.
  2. Key Escrow: As with most identity-based systems, a Private Key Generator (PKG) is required. This central authority possesses the ability to forge signatures, which may be a concern for decentralized applications requiring absolute trustlessness.

7. Conclusion

By identifying and fixing the universal forgery vulnerability in previous identity-based VES constructions, this work provides a robust foundation for fair exchange protocols. The new scheme combines the practical benefits of identity-based cryptography with the rigorous security of bilinear pairings, offering a more efficient and secure solution for modern digital transactions.

Summary updated

BibTeX
@inproceedings{zhang2006robust,
  author = {Jianhong Zhang and Wei Zou},
  title = {{A Robust Verifiably Encrypted Signature Scheme}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2006},
  doi = {10.1007/11807964\_74},
}

Loading related content...

Figure