Constructing efficient and secure batch signature schemes
148 viewsDOI:
https://doi.org/10.54939/1859-1043.j.mst.CSCE5.2021.49-60Keywords:
Merkle Tree; Node; Hash Chain; EUF-CMA Security; Batch Signature Schemes.Abstract
In ordinary signature schemes, such as RSA, DSA, ECDSA, the signing process is performed only for a single message. Due to performance issues, in some contexts, the above solutions will become unsuitable if a party needs to sign multiple messages simultaneously. For example, in the authenticated key exchange protocols based on signatures between client and server, the server is expected to handle multiple key exchange requests from different clients simultaneously. Batch signing is a solution that generates signatures for multi-messages simultaneously with a single (ordinary) signature generation. In this article, we will consider some of the existing batch signing solutions and point out a few of their weakness. To deal with these problems, the paper also proposes two secure types of batch signature schemes, but still ensures the same efficiency as the existing batch signing solution.
References
[1]. R. C. Merkle. “Protocols for public-key cryptosystems”. In: Proceedings of the 1980 IEEE Symposium on Security and Privacy, pp. 122–134 (1980).
[2]. S. Goldwasser, S. Micali, and R. Rivest. “A Digital Signature Scheme Secure Against Adaptative Chosen-Message Attacks”. SIAM Sournal of Computing, 17(2):281-308, April 1988.
[3]. D. Pointcheval, and J. Stern. “Security proofs for signature schemes”. International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1996.
[4]. Christopher J. Pavlovski and Colin Boyd. “Efficient batch signature generation using tree structures”. In International Workshop on Cryptographic Techniques and E-Commerce: CrypTEC’99, pages 70–77. City University of Hong Kong Press, 1999.
[5]. D. Pointcheval, and J. Stern. “Security arguments for digital signatures and blind signatures”. Journal of cryptology 13.3 (2000): 361-396.
[6]. Ernest F. Brickell, David Pointcheval, Serge Vaudenay, and Moti Yung, “Design validations for discrete logarithm based signature schemes”, In Hideki Imai and Yuliang Zheng, editors, PKC 2000, volume 1751 of LNCS, pages 276-292. Springer-Verlag, 2000.
[7]. A. Kalja. “The first ten years of X-road”. In Estonian Information Society Yearbook 2011/2012, pages 78–80. Department of State Information System, Estonia, 2012.
[8]. A. Ansper, et al. “High-performance qualified digital signatures for X-road”. In Nordic Conference on Secure IT Systems. Springer, Berlin, Heidelberg, 2013.
[9]. International standard ISO/IEC DIS 14888-3. Information technology -- Security techniques -- Digital signatures with appendix -- Part 3: Discrete logarithm based mechanisms. ISO/IEC JTC 1/SC 27, 2016.
[10]. A. Buldas, R. Laanoja, and A. Truu. “A server-assisted hash-based signature scheme”. In Nordic Conference on Secure IT Systems. 2017. Springer.
[11]. D. J. Bernstein, et al. “The SPHINCS+ signature framework”. Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. 2019.
[12]. J. W. Bos, et al. “Rapidly verifiable XMSS signatures”. IACR Transactions on Cryptographic Hardware and Embedded Systems (2021): 137-168.
