Abstract
Digital signature schemes often face a tension between computational efficiency and the rigor of their security proofs. This paper introduces a modified version of the Nyberg-Rueppel (mNR) signature scheme that addresses this trade-off. By proving security in the Generic Group Model (GM) under the Discrete Logarithm (DL) assumption, the authors provide a scheme with a "tight" security reduction. Furthermore, the mNR scheme is shown to be highly efficient for Self-Certified Identity-Based (SCID) cryptography, offering substantial bandwidth savings and reduced computational overhead compared to traditional public-key infrastructures.
Introduction
In modern cryptography, widely used signature schemes like DSA or ECDSA are often conjectured to be secure but lack formal reductions to standard mathematical problems unless analyzed in the Random Oracle Model (ROM). While the ROM is a useful tool, it treats hash functions as ideal random functions, which may not always reflect real-world implementations. Additionally, the original Nyberg-Rueppel (NR) scheme, designed for message recovery, requires complex and error-prone redundancy functions to prevent forgery.
This work proposes the Modified Nyberg-Rueppel (mNR) scheme to bridge this "proof gap." The mNR scheme avoids the pitfalls of redundancy functions while maintaining high efficiency and providing a robust security proof in a model that more accurately reflects generic group operations.
The Modified Nyberg-Rueppel (mNR) Scheme
The core innovation of the mNR scheme lies in its modification of the verification equation. While the original NR scheme aimed for message recovery, mNR incorporates a discrete exponentiation of the message ($g_1^m$) directly into the verification process. This change effectively replaces the need for a delicate redundancy function with a standard, well-understood cryptographic operation.
The authors evaluate the scheme's performance by comparing the number of computational operations—specifically exponentiations—and the resulting bit-length of signatures against benchmarks such as DSA, ECDSA, and various pairing-based signatures.
Security Analysis
The security of the mNR scheme is established using the Generic Group Model (GM). In this model, an adversary is assumed to have no knowledge of the internal representation of group elements and can only interact with them through a "black box" that performs group operations.
The authors demonstrate that breaking the mNR scheme is computationally equivalent to solving the Discrete Logarithm (DL) problem. Crucially, this reduction is "tight," meaning that any successful attack on the signature can be directly and efficiently converted into a solution for the underlying hard mathematical problem.
As shown in the comparison table above, the proposed scheme ("THIS") achieves a tight security reduction under the DL assumption within the GM, placing it alongside other high-security variants while maintaining a focus on efficiency.
Applications in SCID Cryptography
A significant contribution of this work is the application of mNR to Self-Certified Identity-Based (SCID) cryptography. SCID schemes represent a middle ground between traditional Public Key Infrastructure (PKI) and fully identity-based systems. In SCID, a user's public key is implicitly verified by their identity, eliminating the need for large, explicit certificates.
The mNR scheme is particularly well-suited for SCID for several reasons:
- Bandwidth Optimization: Because mNR is an Elgamal-type signature, it allows for "public reconstruction data" that is significantly shorter than traditional certificates.
- Efficiency: Verification of an mNR signature requires only 3 exponentiations, compared to 4 for the equivalent "twin-NR" signature, which provides similar security levels but with higher overhead.
- Short Authenticity Proofs: In an SCID infrastructure using 160-bit elliptic curves, an mNR-based authenticity proof is only 482 bits. In multi-level hierarchies, mNR can achieve up to a 50% reduction in length compared to traditional PKI-style short signatures.
Conclusion
The Modified Nyberg-Rueppel signature scheme offers a compelling alternative for applications requiring both high security and efficiency. By providing a tight security proof in the Generic Group Model and demonstrating significant advantages in SCID environments, the authors present a practical solution for bandwidth-constrained and high-performance cryptographic systems. While the scheme sacrifices the message recovery property of the original NR, the gains in security and its utility in identity-based infrastructures make it a valuable addition to the cryptographic toolkit.
Summary updated