TL;DR
This paper introduces two novel proxy re-signature schemes, Smb and Sid-mb, that are proven secure in the standard model without relying on the random oracle heuristic. These schemes offer enhanced security and efficiency, with Sid-mb being the first ID-based proxy re-signature scheme provably secure in the standard model.
What Problem Does This Paper Address?
Proxy re-signature schemes allow a trusted third party (a proxy) to transform a signature from one party (delegator) into a signature for another party (delegatee) on the same message. This is useful for various applications like simplifying key management and enabling interoperability in digital rights management. However, existing schemes suffer from two main drawbacks:
- Random Oracle Dependence: Their security proofs rely on the random oracle model, which is a theoretical construct. Schemes proven secure in this model can sometimes be insecure when instantiated with real-world hash functions. The authors aim to provide schemes secure in the "standard model," which is a stronger guarantee.
- Certificate Management Complexity: Existing schemes use public keys that are arbitrary strings, requiring certificates to bind them to identities. This adds complexity. The authors propose an ID-based approach where a user's identity (like an email address) serves as their public key, eliminating the need for certificates.
Methods
The paper proposes two schemes, building upon Waters' approach [20] and utilizing bilinear maps.
- Smb (Multi-Use Bidirectional Scheme): This is the first proxy re-signature scheme that is existentially unforgeable in the standard model. It supports bidirectional re-signing (A's signature to B's, and vice-versa), multi-use (transformed signatures can be re-transformed), and is a private proxy scheme. Its security is based on the Computational Diffie-Hellman (CDH) assumption.
- Sid-mb (ID-based Multi-Use Bidirectional Scheme): This scheme extends Smb to an ID-based setting. It's the first ID-based proxy re-signature scheme provably secure in the standard model, also offering bidirectional, multi-use, and private proxy properties. Its security also relies on the CDH assumption.
Both schemes are computationally efficient, with the core operations (Sign and ReSign) involving only two exponentiations in the underlying group.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Standard Model Security is Achievable: The paper demonstrates that it's possible to construct secure proxy re-signature schemes without relying on the random oracle heuristic, a significant step towards more robust cryptographic primitives.
- ID-Based Proxy Re-Signatures without Random Oracles: The introduction of Sid-mb is a breakthrough, offering the benefits of ID-based cryptography (simpler key management) combined with the security guarantees of standard model proofs for proxy re-signature.
- Efficiency Trade-offs: While the proposed schemes are efficient in terms of operations, they inherit a drawback from Waters' approach: relatively large public parameters. The authors suggest techniques to mitigate this.
Key Results
- Smb: The first bidirectional, multi-use proxy re-signature scheme proven existentially unforgeable in the standard model.
- Sid-mb: The first ID-based bidirectional, multi-use proxy re-signature scheme proven existentially unforgeable in the standard model.
- Efficiency: Both schemes are computationally efficient, with Sign and ReSign operations requiring only two exponentiations in the group G1.
- Security Basis: Security is proven under the Computational Diffie-Hellman (CDH) assumption.
Limitations and Future Work
- Public Parameter Size: A notable limitation is the relatively large size of public parameters, inherited from the underlying construction. The authors mention that techniques from Naccache [15] and Sarkar and Chatterjee [17] can be used to reduce this size, potentially at the cost of security reduction.
- Static Corruption: The security proofs are for static corruption, meaning the adversary must declare corrupted parties before the security game begins. The authors acknowledge that adaptive corruption (where the adversary can corrupt parties during the game) is a more challenging and desirable security notion, leaving it as future work.
Summary updated