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

Mariusz Jurkiewicz


In this paper we construct and consider a new group-based digital signature scheme with evolving secret key, which is built using a bilinear map. This map is an asymmetric pairing of Type 3, and although, for the reason of this paper, it is treated in a completely abstract fashion it ought to be viewed as being actually defined over $E(\FF_{q^{n}})[p]\times E(\FF_{q^{nk}})[p]\to \FF_{q^{nk}}[p]$. The crucial element of the scheme is the key updater algorithm. With the adoption of pairings and binary trees where a number of leaves is the same as a number of time periods, we are assured that an updated secret key can not be used to recover any of its predecessors. This, in consequence, means that the scheme is forward-secure. To formally justify this assertion, we conduct analysis in \fucma~security model by reducing the security of the scheme to the computational hardness of solving the Weak $\ell$-th Bilinear Diffie-Hellman Inversion problem type. We define this problem and explain why it can be treated as a source of security for cryptographic schemes. As for the reduction itself, in general case, it could be possible to make only in the random oracle model.

Full Text:



A. Anderson, Invited lecture, in Fourth Annual Conference on Computer and Communications Security, ACM, Am Psychiatric Assoc, 1997.

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-1_28.

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.

D. Boneh, X. Boyen and E.-J. Goh, ”Hierarchical Identity Based Encryption with Constant Size Ciphertext”, Cryptology ePrint Archive, Report 2005/015. [Online]. Available:

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.

J. Buchmann, E. Dahmen and A. Hülsing, ”XMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions”, in Post-Quantum Cryptography, B.-Y. Yang, Ed. 2011, pp. 117–129.

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.

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.

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.

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.

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.

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.

S. Hohenberger and B.Waters, ”New Methods and Abstractions for RSABased 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.

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.

M. Jurkiewicz, ”Improving Security of Existentially Unforgeable Signature Schemes”, International Journal of Electronics and Telecommunications, vol. 66, no. 3, pp. 473–480, 2020, doi: 0.24425/ijet.2020.131901.

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.

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.


  • There are currently no refbacks.

International Journal of Electronics and Telecommunications
is a periodical of Electronics and Telecommunications Committee
of Polish Academy of Sciences

eISSN: 2300-1933