Efficient Pairing-Based Threshold Proxy Signature Scheme with Known Signers

Haifeng Qian, Zhenfu Cao, Qingshui XueInformatica 2005

TL;DR

This paper introduces a novel threshold proxy signature scheme that leverages bilinear pairings for enhanced efficiency and security. By building upon existing cryptographic primitives like Schnorr and GDH signatures, the proposed scheme offers robust protection against various attacks while maintaining a high level of performance, making it suitable for applications requiring secure delegation of signing capabilities.

What Problem Does This Paper Address?

Traditional proxy signature schemes allow a designated proxy to sign messages on behalf of an original signer. However, as these schemes evolved to include threshold capabilities (requiring a minimum number of proxies to sign) and known signers (identifying the specific proxies involved), they became increasingly complex and computationally expensive. Many existing threshold proxy signature schemes relied on discrete logarithm problems in modular multiplicative groups, which are computationally intensive. This paper addresses the need for a more efficient and secure threshold proxy signature scheme, particularly one that can handle known signers, by exploring the use of bilinear pairings.

Methods

The authors propose a threshold proxy signature scheme with known signers that utilizes bilinear pairings. The scheme is built upon several cryptographic components:

  • Bilinear Pairings: These are mathematical functions that map two elements from a group to an element in another group, offering powerful cryptographic properties. The paper leverages these pairings (specifically mentioning Weil or Tate pairings on elliptic curves) to achieve efficiency.
  • Schnorr Signature Scheme: Used for signing the "warrant" which contains delegation information. This scheme is chosen for its provable security in the random oracle model.
  • GDH Signature Scheme: This forms the basis for generating the actual proxy signatures. GDH groups are characterized by the hardness of the Computational Diffie-Hellman (CDH) problem but the ease of solving the Decision Diffie-Hellman (DDH) problem.
  • Verifiable Secret Sharing (VSS): Employed in the "Proxy Share Generation Protocol" to securely distribute secret shares among proxy signers.

The proposed scheme involves three main protocols:

  1. Proxy Share Generation Protocol (TPK): The original signer delegates signing authority by distributing secret shares to proxy signers using VSS.
  2. Generation of the Proxy Signature (TPS): A threshold of proxy signers cooperatively generate a proxy signature for a message.
  3. Proxy Signature Verification Protocol (TPV): A verifier checks the validity of the proxy signature.

A key innovation is the use of a "warrant" (mw) that records delegation details and is signed using Schnorr signatures, ensuring its integrity. The scheme also incorporates "known signers" by explicitly identifying the actual signers involved in generating a particular proxy signature.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bilinear Pairings for Efficiency: The core insight is that bilinear pairings, which have gained prominence in cryptography, can be effectively used to construct more efficient threshold proxy signature schemes compared to those based solely on discrete logarithms in traditional groups.
  • Combining Primitives for Robustness: The scheme cleverly combines Schnorr signatures (for warrant integrity) and GDH signatures (for proxy signing) with VSS (for secure share distribution) to achieve a comprehensive and secure solution.
  • Known Signers and Identifiability: The scheme explicitly addresses the "known signers" requirement, ensuring that the identities of the actual proxies involved in a signature can be verified, enhancing accountability.
  • Proxy Protection: The scheme is designed to be "proxy protected," meaning that even if a proxy signer is compromised, they cannot forge signatures on behalf of the original signer without the cooperation of other proxies.
  • Resistance to Attacks: The paper demonstrates that the proposed scheme is resilient against various attacks, including forgery, conspiracy, and public key substitution attacks, by leveraging the security properties of its underlying cryptographic components.

Key Results

The paper presents a threshold proxy signature scheme with known signers that is claimed to be efficient and secure. The security analysis demonstrates its ability to resist common attacks. The performance evaluation, presented in Table 1, compares the proposed scheme with existing ones (Sun's and Hsu et al.'s) and indicates significant efficiency gains, particularly in terms of computation time for various operations like secret share generation, proxy share generation, partial proxy signature, whole proxy signature, and proxy signature verification. The scheme also benefits from potentially smaller key and signature sizes due to its reliance on elliptic curves.

Limitations and Future Work

  • Reliance on GDH Groups: The scheme's security is tied to the hardness assumptions of GDH groups. While these are well-studied, any advancements that weaken these assumptions could impact the scheme's security.
  • Computational Cost of Pairings: While pairings offer efficiency gains over traditional discrete logarithm problems, they still involve non-trivial computations. The paper acknowledges this by providing a detailed example of Tate pairing computation.
  • Future Work: The authors suggest that their scheme is a first step in using bilinear pairings for threshold proxy signatures with known signers. Future work could explore further optimizations, different types of pairings, or extensions to other cryptographic primitives. The paper also notes that the scheme does not require a secure channel for delivering the signed warrant, which is an advantage.

Summary updated

BibTeX
@article{qian2005efficient,
  author = {Haifeng Qian and Zhenfu Cao and Qingshui Xue},
  title = {{Efficient Pairing-Based Threshold Proxy Signature Scheme with Known Signers}},
  journal = {Informatica},
  year = {2005},
}
Figure