Certificateless signature and auditing schemes secure against super type adversaries without random oracle
Abstract
Cryptographic algorithms are essential for securing data in modern internet applications. As the volume of data increases and security challenges evolve, the significance of these algorithms intensifies. Certificateless public key cryptography addresses the challenges of certificate management inherent in traditional public key cryptography and resolves the key escrow issue associated with identity-based public key cryptography. Notably, previous certificateless signature schemes secure in the random oracle model exhibit vulnerabilities when instantiated in the standard model. There are two types of adversaries in certificateless signature scheme. Type Ⅰ and Type Ⅱ adversaries are further categorized into three levels: Normal, Strong, and Super, with Super denoting the most powerful known adversaries. In this work, we present a new certificateless signature scheme designed against Super Type Ⅰ and Type Ⅱ adversaries in the standard model based on the computational Diffie–Hellman problem; additionally, the certificateless signature approach can be extended to develop secure cloud auditing schemes, which is for addressing data integrity and security in cloud environments.
Keywords
INTRODUCTION
Cryptographic algorithms are fundamental to modern Internet technology, which ensures data security during transmission, storage, and processing. As data volume surges and security challenges intensify, their importance grows. In 1976, Diffie and Hellman [1] introduced public key cryptography (PKC), effectively addressing the inherent issues of key management and non-repudiation in traditional symmetric systems, thereby expanding the application of cryptography in network security. Public key encryption and key agreement techniques provide effective key management, while digital signature meets non-repudiation needs. In 1984, Shamir[2] proposed identity-based cryptography (IBC), using public identity information as public keys to avoid the complexity of traditional public key infrastructure (PKI), though it raises key escrow problem; i.e., the user’s private key is entirely generated by the key generation center (KGC) in IBC, which can impersonate any user without being detected. In 2003, Al-Riyami and Paterson [3] introduced certificateless PKC (CL-PKC), discarding the use of public key certificates, blending the benefits of traditional PKC and IBC, and enhancing usability and security. Subsequently, Huang et al.[4] established the first formal security model for certificateless signature and proposed a provably secure scheme under this model. In 2012, Huang et al.[5] further classified Type Ⅰ and Type Ⅱ adversaries in certificateless signature systems into three levels: Normal, Strong, and Super, with Super representing the strongest known adversaries. In the security model, the adversary’s attack capabilities are characterized by three types of Sign oracles (which take a message as input and return the signature), each with different operating conditions, as shown in Table 1.
Three types of Sign oracles
Normal sign | Public key has not been replaced |
Strong sign | If the public key is replaced, additional information must be provided |
Super sign | No additional information is required, even if the public key is replaced |
There are many provably secure certificateless signature schemes in the random oracle model (ROM), such as constructions [6–12]; in particular, the schemes[7,11,12] are secure against Super adversaries. The ROM is widely utilized in the security proofs of cryptographic schemes; however, in 1998, Canetti et al.[13] presented a scheme that is secure in the ROM but cannot be securely instantiated in the Standard Model (STM). This implies that proving a scheme secure in the ROM does not guarantee it is free from security flaws in practice, whereas proving security in the STM offers a more reliable assurance of the scheme’s security. In 2007, the provably secure certificateless signature scheme in the STM was first introduced by Liu et al.[14]. Thereafter, the scheme was improved by Xiong et al.[15]. Xia et al.[16] further analyzed the scheme by Xiong et al., demonstrating it is vulnerable to public key replacement attacks. Similarly, subsequent schemes[17–19] have been proven insecure against public key replacement attacks. Table 2 below summarizes recent certificateless signature schemes that claim security in the STM, with classifications in the model column—Normal, Strong, and Super—reflecting the adversary types as categorized in the work by Huang et al[5]. "NaS" indicates that it is not as specified, meaning that no proof exists or the current scheme cannot resist security analysis as defined in the security model. As shown in Table 2, existing certificateless signature schemes that are secure in the STM can only withstand attacks from Strong adversaries. To overcome these limitations, we propose a new certificateless signature scheme against Super Type Ⅰ and Super Type Ⅱ adversaries in the STM, which is reduced to the hardness of computational Diffie–Hellman (CDH) problem. In addition, we extend our technique to enable its application in the certificateless cloud auditing (CLCA) scheme.
Comparison of some certificateless signature schemes in the STM
Technical Overview
In 2015, Hung et al.[20] shed light on achieving a certificateless signature scheme that is secure against Super adversaries in the STM. However, Yang et al.[21] pointed out a flaw in the proof provided by Huang et al. regarding the Type Ⅱ adversary; i.e., the simulated signature provided by the simulator fails to pass verification of validity, preventing it from always correctly responding to adversary’s signature queries.
The base idea of our construction is that to achieve security against Super adversaries, the challenger should be able to simulate signatures using only existing secret information and the user’s public key during the simulation. This ensures that regardless of the adversary’s attempts to replace the user’s public key, the challenger can respond to signature queries. Since the secret information is known only to the challenger, the adversary cannot forge signatures merely by knowing the user’s public key. We observed that in the security proof of the Waters signature scheme [29], the challenger can compute a valid signature using a series of secret information embedded in the public parameters, the public parameters, and the message. The hard problem embedded in the public parameters and the public parameters computed from the secret information exhibit a certain degree of independence. This insight inspired us to construct a certificateless signature scheme based on the structure of the Waters scheme.
On another note, Hu et al.[30] proposed in 2007 that a certificateless signature scheme could be constructed by a signature scheme and an identity-based signature (IBS) scheme. However, this generic construction has certain limitations and cannot be directly considered secure against Super adversaries without modification. Paterson’s IBS scheme [31] is an extension of the Waters signature scheme; both are based on bilinear maps. In this scheme, the user’s private key corresponds to the Waters signature of the user’s identity. Similarly, this can be utilized as the partial private key for each user in the certificateless signature scheme. In the Waters signature scheme, a secret
Certificateless Cloud Auditing
Additionally, the certificateless signature construction technique employed in this paper can also be applied to the development of CLCA schemes. By using a similar approach, we can achieve a CLCA scheme that is against Super adversaries in the STM. As presented in Figure 1, cloud auditing is widely utilized in cloud storage services to address data security concerns. For instance, user data may be deleted or partially lost due to internal changes or cost considerations of cloud service providers. Moreover, the presence of attackers and malicious users exacerbates these risks. After uploading data to cloud servers, users often delete local copies, necessitating the mitigation of risks associated with traditional verification methods. In 2007, Ateniese et al.[32] proposed the provable data possession (POP), while Juels and Kaliski [33] independently introduced the proofs of retrievability (POR), both proven secure in the ROM. On the other hand, there are some cloud auditing schemes in the STM proposed. In 2016, Ma et al.[34] proposed a cloud auditing scheme based on the strong RSA assumption, and Zhang et al.[35] introduced an identity-based cloud auditing scheme that is also proven secure in the STM. However, existing secure CLCA schemes in the STM, such as those by Deng et al.[36] and Yang et al.[37], are only proved secure against Strong adversaries.
Organization
The rest of this paper is organized as follows. In Section 2, we first review some mathematical preliminaries including bilinear maps and hardness assumption. Then, we give the definition of certificateless signature and corresponding security model in Section 3. Next, our concrete construction is presented in Section 4, together with the security and efficiency analysis. In addition, we show an extension of our techniques for CLCA in Section 5. Finally, the conclusion part comes in Section 6.
PRELIMINARIES
In this section, we describe the definition of mathematical tools and mathematical assumptions.
Definition 1(Bilinear Maps):
1) Bilinearity:
2) Nondegeneracy:
3) Computability: e is efficiently computable.
Definition 2(CDH Problem): On inputs
We say that the
DEFINITION AND SECURITY MODEL
Definition of Certificateless Signature Schemes
According to [3], a certificateless signature scheme consists of the following seven algorithms: Setup, PartialKeyExt, SetSecretValue, SetPrivateKey, SetPublicKey, Sign, and Verify. The specific descriptions of the algorithms are as follows.
- Setup
- PartialKeyExt
- SetSecretValue
- SetPrivateKey
- SetPublicKey
- Sign
- Verify
Correctness Signatures generated by the algorithm Sign can pass through the verification in Verify. That is,
Security Models of Certificateless Signature
There are two types of adversaries in certificateless signature scheme. Type Ⅰ adversary, denoted by
Due to space limitations, we define Game 1 and Game 2, which simulate the interactions between the challenger and the Super adversary (The security models against Normal and Strong adversaries can be seen as special cases where the adversary is restricted more).
Game 1(against Super
● Setup: The Challenger
● Query: The adversary
– Create-User: Upon receiving a Create-User query with the user’s identity
– Partial-Private-Key-Extract: Upon receiving a Partial-Private-Key-Extract query with the user’s identity
– Secret-Value-Extract: Upon receiving a Secret-Value-Extract query with the user’s identity
– Public-Key-Replace: Upon receiving a Public-Key-Replace query with the user’s identity
– Super-Sign: Upon receiving a Super-Sign query with the user’s identity
● Forgery: The adversary
1) The adversary
2) The adversary
3) Signature
Game 2(against Super
● Setup: The Challenger
● Query: The adversary
– Create-User: Upon receiving a Create-User query with the user’s identity
– Secret-Value-Extract: Upon receiving a Secret-Value-Extract query with the user’s identity
– Public-Key-Replace: Upon receiving a Public-Key-Replace query with the user’s identity
– Super-Sign: Upon receiving a Super-Sign query with the user’s identity
● Forgery: The adversary
1) The adversary
2) The adversary
3) Signature
CONSTRUCTION AND SECURITY PROOF
Construction
- Setup
Let
- PartialKeyExt
and output
- SetSecretValue
- SetPrivateKey
- SetPublicKey
- Sign
and output
- Verify
holds or not. Output 1 if the equality holds; otherwise output 0.
Correctness Analysis
Security Proof
Theorem 1 Assume the
Proof We construct a simulator
● Setup: Let
Define the following functions for binary string
Then, we have:
● Query: The adversary
– Create-User: Upon receiving a Create-User query with the user’s identity
– Partial-Private-Key-Extract: Upon receiving a Partial-Private-Key-Extract query with the user’s identity
1)
2)
– Secret-Value-Extract: Upon receiving a Secret-Value-Extract query with the user’s identity
– Public-Key-Replace: Upon receiving a Public-Key-Replace query with the user’s identity
– Super-Sign: Upon receiving a Super-Sign query with the user’s identity
1)
2)
Otherwise,
If
● Forgery: The adversary
1)
2)
3) Signature
If any of the above conditions are not met,
Then
Probability analysis To make analysis simple, we need following conclusions. Form
Let
According to the simulation, the probability of
In the simulation, since all variates are chosen randomly, with above conclusions, we have
Also, we have
We can get the probability
Using a similar analysis technique, we can have
If
Theorem 2 Assume the
Proof We construct a simulator
● Setup: Let
Define the following functions for binary string
Then, we have:
● Query: The adversary
– Create-User: Upon receiving a Create-User query with the user’s identity
– Secret-Value-Extract: Upon receiving a Secret-Value-Extract query with the user’s identity
1)
2)
– Public-Key-Replace: Upon receiving a Public-Key-Replace query with the user’s identity
1)
2)
– Super-Sign: Upon receiving a Super-Sign query with the user’s identity
1)
2)
If
● Forgery: The adversary
1)
2)
3) Signature
If any of the above conditions are not met,
Then
Probability analysis Its probability analysis is similar to analysis for Theorem 1. Let
According to the simulation, the probability of
If
Efficiency Analysis
In this section, the proposed scheme is compared with some existing certificateless signature schemes in terms of efficiency. For efficiency comparison, we use the PBC library and select the Type A curve, conducting experiments on an Ubuntu22 virtual machine with the 12th Gen Intel(R) Core(TM) i7-12700H 2.70GHz processor and 16GB RAM. Then, the experiment results show that, every pairing operation (P) needs 1.58022ms, every multiplication (
The comparison of efficiency and signature length
Scheme | Signing cost | Verification cost | Signature length |
Wu et al.[25] | |||
Tseng et al.[26] | |||
Rastegari et al.[27] | |||
Ours |
EXPANSION: CERTIFICATELESS CLOUD AUDITING SCHEME
We can easily take advantage of the structure of the certificateless signature scheme to construct a CLCA scheme against Super adversaries in STM. In general, the CLCA scheme can be specified by nine algorithms: Setup, PartialKeyExt, SetSecretValue, SetPrivateKey, SetPublicKey, TagGen, Challenge, Respond and Verify. The first five algorithms are similar to those in the certificateless signature; TagGen, Challenge, Respond and Verify are as follows:
- TagGen
- Challenge
- Respond
- Verify
Now we can outline our CLCA scheme: Setup, PartialKeyExt, SetSecretValue, SetPrivateKey and SetPublicKey: Identical to our certificateless signature scheme.
- TagGen
and output
- Challenge
- Respond
and output
- Verify
holds or not. Output 1 if the equality holds; otherwise output 0.
DISCUSSION
This study introduces a novel certificateless signature scheme and demonstrates its security against Super adversaries in the STM. While previous research has proposed certificateless signature schemes in the STM, no scheme has been proven secure against Super adversaries in the STM. Additionally, we extend the structure of the proposed certificateless signature scheme to develop a CLCA scheme, which is also provably secure against Super adversaries in the STM. As far as we are aware, no existing schemes offer a similar level of security.
Based on our experimental results, although the efficiency of our scheme has not yet reached that of the most advanced schemes, the overhead is still within an acceptable range. Future work will focus on improving efficiency while maintaining the same level of security, such as by incorporating blockchain technology [38] to reduce computational and storage overhead. Furthermore, the scheme can be deployed as a component in systems such as Verifiable Query Layer (VQL) [39], enhancing system functionality and security, which presents a promising direction for further research.
CONCLUSION
To the best of our knowledge, no certificateless signature scheme has been proposed in the literature that is secure against Super adversaries without random oracles. In this paper, we introduce a certificateless signature scheme against Super adversaries based on the CDH problem. We then employ a similar technique to present a CLCA scheme with the same level of security. Our primary approach combines Water’s signature scheme [29] with Paterson’s IBS scheme [31], which is akin to the methodology used by Huang et al[20].
DECLARATIONS
Acknowledgments
We would like to express our sincere gratitude to the editor and anonymous reviewers for their helpful and professional comments and guidance in improving our manuscript.
Authors’ contributions
Made substantial contributions to the design and proof of the proposed scheme: S. Yao; Provided administrative support and supervision: G. Wu; Performed a substantial review of the proposed scheme, along with editorial work and proofreading: X. Liu.
Availability of data and materials
The rata data supporting the findings of this study are available within this Article and its Supplementary Material. Further data are available from the corresponding authors upon request.
Financial support and sponsorship
This paper is supported by the National Natural Science Foundation of China (No.62372103, No.62002058) and the Natural Science Foundation of Jiangsu Province (No.BK20200391).
Conflicts of interest
All authors declared that there are no conflicts of interest.
Ethical approval and consent to participate
Not applicable.
Consent for publication
Not applicable.
Copyright
© The Author(s) 2025.
REFERENCES
2. Shamir A. identity-based cryptosystems and signature schemes. In: Blakley GR, Chaum D, editors. Proceedings of the Annual International Cryptology Conference-CRYPTO; 1984 Aug 19-22; Santa Barbara, USA. Springer; 1984. pp. 47–53.
3. Al-Riyami SS, Paterson KG. Certificateless public key cryptography. In: Laih C, editor. Proceedings of the 9th International Conference on the Theory and Application of Cryptology and Information Security-ASIACRYPT; 2003 Nov 30 - Dec 4; Taipei, Taiwan. Springer; 2003. pp. 452–73.
4. Huang X, Susilo W, Mu Y, Zhang F. on the security of certificateless signature schemes from asiacrypt 2003. In: Desmedt Y, Wang H, Mu Y, Li Y, editors. Proceedings of the 4th International Conference on Cryptology and Network Security-CANS; 2005 Dec 14-16; Xiamen, China. Springer; 2005. pp. 13–25.
5. Huang X, Mu Y, Susilo W, Wong DS, Wu W. Certificateless signatures: new schemes and security models. Comput J. 2012;55:457-74.
6. Zhang Z, Wong DS, Xu J, Feng D. certificateless public-key signature: security model and efficient construction. In: Zhou J, Yung M, Bao F, editors. Proceedings of the 4th International Conference on Applied Cryptography and Network Security-ACNS; 2006 Jun 6-9; Singapore, Singapore. Springer; 2006. pp. 293–308.
7. Huang X, Mu Y, Susilo W, Wong DS, Wu W. Certificateless signature revisited. In: Pieprzyk J, Ghodosi H, Dawson E, editors. Proceedings of the 12th Australasian Conference on Information Security and Privacy-ACISP; 2007 Jul 2-4; Townsville, Australia. Springer; 2007. pp. 308–22.
8. Choi KY, Park JH, Hwang JY, Lee DH. Efficient certificateless signature schemes. In: Katz J, Yung M, editors. Proceedings of the 5th International Conference on Applied Cryptography and Network Security-ACNS; 2007 Jun 5-8; Zhuhai, China. Springer; 2007. pp. 443–58.
9. Tso R, Yi X, Huang X. Efficient and short certificateless signature. In: Franklin MK, Hui LCK, Wong DS, editors. Proceedings of the 7th International Conference on Cryptology and Network Security-CANS; 2008 Dec 2-4; Hong-Kong, China. Springer; 2008. pp. 64–79.
10. Zhang L, Zhang F, Zhang F. New efficient certificateless signature scheme. In: Denko MK, Shih C, Li K, et al., editors. Proceedings of the Emerging Directions in Embedded and Ubiquitous Computing-EUC; 2007 Dec 17-20; Taipei, Taiwan. Springer; 2007. pp. 692–703.
11. Hu BC, Wong DS, Zhang Z, Deng X. Key replacement attack against a generic construction of certificateless signature. In: Batten LM, Safavi-Naini R, editors. Proceedings of the 11th Australasian Conference on Information Security and Privacy-ACISP; 2006 Jul 3-5; Melbourne, Australia. Springer; 2006. pp. 235–46.
12. Chen Y, Tso R, Horng G, Fan C, Hsu R. Strongly secure certificateless cignature: cryptanalysis and improvement of two schemes. J Inf Sci Eng 2015;31: 297–314. Available from: http://www.iis.sinica.edu.tw/page/jise/2014/2015/201501_16.html.[Last accessed 29 Oct 2024].
13. Canetti R, Goldreich O, Halevi S. The random oracle methodology, revisited (preliminary version). In: Vitter JS, editor. Proceedings of the 30th Annual ACM Symposium on Theory of Computing-STOC; 1998 May 23-26; Dallas, USA. ACM; 1998. pp. 209–18.
14. Liu JK, Au MH, Susilo W. Self-generated-certificate public key cryptography and certificateless signature / encryption scheme in the standard model. In: Deng R, Samarati P, Baoand F, Miller S, editors. Proceedings of the 2nd ACM Symposium on Information, Computer and Communications Security-ASIACCS; 2007 Mar 20-22; Singapore, Singapore. ACM; 2007. pp. 273–83.
15. Xiong H, Qin Z, Li F. An improved certificateless signature scheme secure in the standard model. Fundam Informaticae 2008;88: 193–206. Available from: http://content.iospress.com/articles/fundamenta-informaticae/fi88-1-2-09.[Last accessed 29 Oct 2024].
16. Xia Q, Xu C, Yu Y. Key replacement attack on two certificateless signature schemes without random oracles. Key Eng Mat. 2010;439-440:1606-11.
17. Yuan H, Zhang F, Huang X, et al. Certificateless threshold signature scheme from bilinear maps. Inf Sci. 2010;180:4714-28.
18. Yu Y, Mu Y, Wang G, Xia Q, Yang B. Improved certificateless signature scheme provably secure in the standard model. IET Inf Secur. 2012;6:102-10.
19. Cheng L, Wen Q. Provably secure and efficient certificateless signature in the standard model. Int J Inf Commun Technol. 2015;7:287-301.
20. Hung Y, Huang S, Tseng Y, Tsai T. Certificateless signature with strong unforgeability in the standard model. Informatica 2015;26: 663–84. Available from: http://content.iospress.com/articles/informatica/inf1073.[Last accessed 29 Oct 2024].
21. Yang W, Weng J, Luo W, Yang A. Strongly unforgeable certificateless signature resisting attacks from malicious-but-passive KGC. Secur Commun Networks. 2017;2017:1-8.
22. Pang L, Hu Y, Liu Y, Xu K, Li H. Efficient and secure certificateless signature scheme in the standard model. Int J Commun Syst. 2017;30.
23. Wang F, Xu L. Strongly secure certificateless signature scheme in the standard model with resisting malicious-but-passive KGC attack ability. J Inf Sci Eng 2017;33: 873–89. Available from: https://jise.iis.sinica.edu.tw/JISESearch/pages/View/PaperView.jsf?keyId=157_2046.[Last accessed 29 Oct 2024].
24. Shim K. A new certificateless signature scheme provably secure in the standard model. IEEE Syst J. 2019;13:1421-30.
25. Wu C, Huang H, Zhou K, Xu C. Cryptanalysis and improvement of a new certificateless signature scheme in the standard model. China Commun. 2021;18:151-60.
26. Tseng Y, Fan C, Chen C. Top-level secure certificateless signature scheme in the standard model. IEEE Syst J. 2019;13:2763-74.
27. Rastegari P, Susilo W. On random-oracle-Free Top-Level Secure Certificateless Signature Schemes. Comput J. 2022;65:3049-61.
28. Yang X, Wen H, Liu L, Ren N, Wang C. Blockchain-enhanced certificateless signature scheme in the standard model. Math Biosci Eng. 2023;20:1271-73.
29. Waters B. Efficient identity-based encryption without random oracles. In: Cramer R, editor. Proceedings of the 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques-EUROCRYPT; 2005 May 22-26; Aarhus, Denmark. Springer; 2005. pp. 114–27.
30. Hu BC, Wong DS, Zhang Z, Deng X. Certificateless signature: a new security model and an improved generic construction. Des Codes Cryptogr. 2007;42:109-26.
31. Paterson KG, Schuldt JCN. Efficient identity-based signatures secure in the standard model. In: Batten LM, Safavi-Naini R, editors. Proceedings of the 11th Australasian Conference on Information Security and Privacy-ACISP; 2006 Jul 3-5; Melbourne, Australia. Springer; 2006. pp. 207–22.
32. Ateniese G, Burns RC, Curtmola R, et al. Provable data possession at untrusted stores. In: Ning P, di Vimercati SDC, Syverson PF, editors. Proceedings of the 2007 ACM Conference on Computer and Communications Security-CCS; 2007 Oct 28-31; Alexandria, USA. ACM; 2007. pp. 598–609.
33. Juels A, Jr BSK. Pors: proofs of retrievability for large files. In: Ning P, di Vimercati SDC, Syverson PF, editors. Proceedings of the 2007 ACM Conference on Computer and Communications Security-CCS; 2007 Oct 28-31; Alexandria, USA. ACM; 2007. pp. 584–97.
34. Ma M, Weber J, van den Berg J. Secure public-auditing cloud storage enabling data dynamics in the standard model. In: Proceedings of the Third International Conference on Digital Information, Data Mining, and Wireless Communications-DIPDMWC; 2016 July 6-8; Moscow, Russia. IEEE; 2016. pp. 170–75.
35. Zhang J, Li P, Mao J. IPad: ID-based public auditing for the outsourced data in the standard model. Clust Comput. 2016;19:127-38.
36. Deng L, Wang B, Wang T, Feng S, Li S. Certificateless provable data possession scheme with provable security in the standard model suitable for cloud storage. IEEE Trans Serv Comput. 2023;16:3986-98.
37. Yang G, Han L, Bi J, Wang F. A collusion-resistant certificateless provable data possession scheme for shared data with user revocation. Clust Comput. 2024;27:2165-79.
38. Xu Y, Ren J, Zhang Y, Zhang C, Shen B, et al. Blockchain empowered arbitrable data auditing scheme for network storage as a service. IEEE Trans Serv Comput. 2020;13:289-300.
Cite This Article

How to Cite
Download Citation
Export Citation File:
Type of Import
Tips on Downloading Citation
Citation Manager File Format
Type of Import
Direct Import: When the Direct Import option is selected (the default state), a dialogue box will give you the option to Save or Open the downloaded citation data. Choosing Open will either launch your citation manager or give you a choice of applications with which to use the metadata. The Save option saves the file locally for later use.
Indirect Import: When the Indirect Import option is selected, the metadata is displayed and may be copied and pasted as needed.
About This Article
Special Issue
Copyright
Data & Comments
Data

Comments
Comments must be written in English. Spam, offensive content, impersonation, and private information will not be permitted. If any comment is reported and identified as inappropriate content by OAE staff, the comment will be removed without notice. If you have any queries or need any help, please contact us at [email protected].