Binary Tree Based Forward Secure Signature Scheme in the Random Oracle Model

Journal title

International Journal of Electronics and Telecommunications




vol. 67


No 4


Jurkiewicz, Mariusz : Faculty of Cybernetics, Military University of Technology, Warsaw, Poland



forward secure digital signature scheme ; bilinear pairing of Type 3 ; random-oracle model ; bilinear Diffie-Hellman inversion problem

Divisions of PAS

Nauki Techniczne




Polish Academy of Sciences Committee of Electronics and Telecommunications


[1] A. Anderson, Invited lecture, in Fourth Annual Conference on Computer and Communications Security, ACM, Am Psychiatric Assoc, 1997.
[2] M. Bellare and S. K. Miner, ”A Forward-Secure Digital Signature Scheme”, in Advances in Cryptology - CRYPTO ’99, 19th Annual International Cryptology Conference, 1999, pp. 431–449, doi: 10.1007/3-540-48405-128.
[3] D. Boneh and X. Boyen, ”Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles”, in Advances in Cryptology - EUROCRYPT 2004, C. Cachin and J.L. Camenisch, Eds. 2004, pp. 223- 238.
[4] D. Boneh, X. Boyen and E.-J. Goh, ”Hierarchical Identity Based Encryption with Constant Size Ciphertext”, Cryptology ePrint Archive, Report 2005/015. [Online]. Available:
[5] X. Boyen, H. Shacham, E. Shen and B. Waters, ”Forward Secure Signatures with Untrusted Update”, in Proceedings of CCS 2006, W. Rebecca Ed. 2006, pp. 191–200.
[6] J. Buchmann, E. Dahmen and A. H¨ulsing, ”XMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions”, in Post-Quantum Cryptography, B.-Y. Yang, Ed. 2011, pp. 117–129.
[7] J. Camenisch and M. Koprowski, ”Fine-grained Forward-secure Signature Schemes without Random Oracles”, Discrete Applied Mathematics, vol. 154, no. 2, pp. 175–188, Feb. 2006, doi: 10.1016/j.dam.2005.03.028.
[8] R. Canetti, S. Halevi, J. Katz, ”A Forward-Secure Public-Key Encryption Scheme”, in Advances in Cryptology - EUROCRYPT 2003, E. Biham, Ed. 2003, pp. 255–271.
[9] Y. Cui, E. Fujisaki, G. Hanaoka, H. Imai and R. Zhang, ”Formal Security Treatments for Signatures from Identity-Based Encryption”, in Provable Security, W. Susilo, J. K. Liu, Y. Mu, Eds. 2007, pp. 218–227.
[10] A. Fiat and A. Shamir, ”How to Prove Yourself: Practical Solutions to Identification and Signature Problems”, in Conference on the theory and application of cryptographic techniques, 1986, pp. 186–194.
[11] S. D. Galbraith, K. G. Paterson and N. P. Smart, ”Pairings for Cryptographers”, Discrete Applied Mathematics, vol. 156, no. 16, pp. 3113 - 3121, Sep. 2008, doi: 10.1016/j.dam.2007.12.010.
[12] S. Goldwasser S. Micali and R. L. Rivest, ”A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks”, SIAM Journal on Computing, vol. 17, no. 2, pp. 281–308, 1988, doi: 10.1137/0217017.
[13] S. Hohenberger and B.Waters, ”New Methods and Abstractions for RSA-Based Forward Secure Signatures”, in International Conference on Applied Cryptography and Network Security, M. Conti, J. Zhou, E. Casalicchio and Angelo Spognardi, Eds. 2020, pp. 292–312.
[14] G. Itkis, and L. Reyzin, ”Forward-secure Signatures with Optimal Signing and Verifying”, in Advances in Cryptology - CRYPTO ’01, 21st Annual International Cryptology Conference, J. Kilian, Ed. 2001, pp. 332–354.
[15] M. Jurkiewicz, ”Improving Security of Existentially Unforgeable Signature Schemes”, International Journal of Electronics and Telecommunications, vol. 66, no. 3, pp. 473–480, 2020, doi: 10.24425/ijet.2020.131901.
[16] H. Krawczyk, ”Simple Forward-secure Signatures from any Signature Scheme”, in Proceedings of the 7th ACM conference on Computer and Communications Security, P. Samarati, Ed. 2000, pp. 108–115, doi: 10.1145/352600.352617.
[17] S. Mitsunari, R. Sakai and M. Kasahara, ”A new traitor tracing”, IEICE transactions on fundamentals of electronics, communications and computer sciences, vol. 85, no. 2, pp. 481–484, Feb. 2002.






DOI: 10.24425/ijet.2021.137868