Document Type : Research Article
Authors
Cryptography and Data Security Laboratory, School of Mathematics, Iran University of Science & Technology, Narmak, Tehran, Iran.
Abstract
Digital signature schemes are used to guarantee for non-repudiation and authenticity of any kind of data like documents, messages or software. The Winternitz one-time signature (WOTS) scheme, which can be described using a certain number of so-called “function chains”, plays an important role in the design of both stateless and stateful many-time signature schemes. The main idea of WOTS scheme is the use of a limited number of function chains, all of which begin at some random values. This work introduces WOTS-GES, a new WOTS type signature scheme in which the need for computing all of the intermediate values of the chains is eliminated. More precisely, to compute each algorithm of the proposed scheme, we only need to calculate one intermediate value. This significantly reduces the number of required operations needed to calculate the algorithms of WOTS-GES. To achieve this results, we have used the concept of “leveled” multilinear maps which is also
referred to as graded encoding schemes. We expect these results to increase the efficiency of Winternitz based digital signature schemes.
Keywords
[1] Dan Boneh and Alice Silverberg. Applications of multilinear forms to cryptography. Contemporary Mathematics, 324(1):71–90, 2003.
[2] Sanjam Garg, Craig Gentry, and Shai Halevi. Candidate multilinear maps from ideal lattices. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 1–17. Springer, 2013.
[3] Massoud Hadian Dehkordi and Hossein Oraei. How to construct a verifiable multi-secret sharing scheme based on graded encoding schemes. IET Information Security, 13(4):343–351, 2019.
[4] Sanjam Garg, Craig Gentry, Shai Halevi, and Daniel Wichs. On the implausibility of differinginputs obfuscation and extractable witness encryption with auxiliary input. Algorithmica, 79(4):1353–1373, 2017.
[5] Huijia Lin and Stefano Tessaro. Indistinguishability obfuscation from trilinear maps and blockwise local prgs. In Annual International Cryptology Conference, pages 630–660. Springer, 2017.
[6] Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM Journal on Computing, 45(3):882–929, 2016.
[7] Prabhanjan Ananth, Aayush Jain, and Amit Sahai. Robust transforming combiners from indistinguishability obfuscation to functional encryption. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 91–121. Springer, 2017.
[8] Susan Hohenberger, Amit Sahai, and Brent Waters. Full domain hash from (leveled) multilinear maps and identity-based aggregate signatures. In Annual Cryptology Conference, pages 494–512. Springer, 2013.
[9] Jia Yu, Hui Xia, Huawei Zhao, Rong Hao, Zhangjie Fu, and Xiangguo Cheng. Forwardsecure identity-based signature scheme in untrusted update environments. Wireless Personal Communications, 86(3):1467–1491, 2016.
[10] Ozg¨ur Dagdelen, David Galindo, Pascal V´eron, ¨Sidi Mohamed El Yousfi Alaoui, and Pierre-Louis Cayrel. Extended security arguments for signature schemes. Designs, Codes and Cryptography, 78(2):441–461, 2016.
[11] Daofeng Li, Haiqiang Chen, Cheng Zhong, Taoshen Li, and Feng Wang. A new self-certified signature scheme based on ntrus ing for smart mobile communications. Wireless Personal Communications, 96(3):4263–4278, 2017.
[12] Leslie Lamport. Constructing digital signatures from a one-way function. Technical report, Citeseer, 1979.
[13] Tal Malkin, Daniele Micciancio, and Sara Miner. Efficient generic forward-secure signatures with an unbounded number of time periods. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 400–417. Springer, 2002.
[14] Johannes Buchmann, Erik Dahmen, and Andreas H¨ulsing. Xmss-a practical forward secure signature scheme based on minimal security assumptions. In International Workshop on PostQuantum Cryptography, pages 117–129. Springer, 2011.
[15] Ralf Hauser, Tony Przygienda, and Gene Tsudik. Reducing the cost of security in link-state routing. In Proceedings of SNDSS’97: Internet Society 1997 Symposium on Network and Distributed System Security, pages 93–99. IEEE, 1997.
[16] Ralph C Merkle. A certified digital signature. In Conference on the Theory and Application of Cryptology, pages 218–238. Springer, 1989.
[17] Andreas H¨ulsing, Christoph Busold, and Johannes Buchmann. Forward secure signatures on smart cards. In International Conference on Selected Areas in Cryptography, pages 66–80. Springer, 2012.
[18] Andreas H¨ulsing, Lea Rausch, and Johannes Buchmann. Optimal parameters for xmss mt. In International Conference on Availability, Reliability, and Security, pages 194–208. Springer, 2013.
[19] Daniel J Bernstein, Daira Hopwood, Andreas H¨ulsing, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Michael Schneider, Peter Schwabe, and Zooko Wilcox-OHearn. Sphincs: practical stateless hash-based signatures. In Annual international conference on the theory and applications of cryptographic techniques, pages 368–397. Springer, 2015.
[20] Andreas H¨ulsing, Joost Rijneveld, and Fang Song. Mitigating multi-target attacks in hashbase PKC 2016, pages 387–416. Springer, 2016.
[21] Jean-Philippe Aumasson and Guillaume Endignoux. Improving stateless hash-based signatures. In Cryptographers Track at the RSA Conference, pages 219–242. Springer, 2018.
[22] Jean-Philippe Aumasson, Daniel J Bernstein, Christoph Dobraunig, Maria Eichlseder, Scott Fluhrer, Stefan-Lukas Gazdag, Andreas H¨ulsing, Panos Kampanakis, Stefan K¨olbl, Tanja Lange, et al. Sphincs+. 2019.
[23] Alejandro Hevia and Daniele Micciancio. The provable security of graph-based one-time signatures and extensions to algebraic signature schemes. In International Conference on the Theory and Application of Cryptology and Information Security, pages 379–396. Springer, 2002.
[24] Chris Dods, Nigel P Smart, and Martijn Stam. Hash based digital signature schemes. In IMA International Conference on Cryptography and Coding, pages 96–115. Springer, 2005.
[25] Johannes Buchmann, Erik Dahmen, Sarah Ereth, Andreas H¨ulsing, and Markus R¨uckert. On the security of the winternitz one-time signature scheme. In International conference on cryptology in Africa, pages 363–378. Springer, 2011.
[26] Andreas H¨ulsing. W-ots+–shorter signatures for hash-based signature schemes. In International Conference on Cryptology in Africa, pages 173–188. Springer, 2013.
[27] Sanjam Garg. Candidate Multilinear Maps. PhD thesis, University of California Los Angeles, 2013.
[28] Adeline Langlois, Damien Stehl´e, and Ron Steinfeld. Gghlite: More efficient multilinear maps from ideal lattices. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 239–256. Springer,2014.
[29] Martin R Albrecht, Catalin Cocis, Fabien Laguillaumie, and Adeline Langlois. Implementing candidate graded encoding schemes from ideal lattices. In International Conference on the Theory and Application of Cryptology and Information Security, pages 752–775. Springer, 2015.
[2] Sanjam Garg, Craig Gentry, and Shai Halevi. Candidate multilinear maps from ideal lattices. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 1–17. Springer, 2013.
[3] Massoud Hadian Dehkordi and Hossein Oraei. How to construct a verifiable multi-secret sharing scheme based on graded encoding schemes. IET Information Security, 13(4):343–351, 2019.
[4] Sanjam Garg, Craig Gentry, Shai Halevi, and Daniel Wichs. On the implausibility of differinginputs obfuscation and extractable witness encryption with auxiliary input. Algorithmica, 79(4):1353–1373, 2017.
[5] Huijia Lin and Stefano Tessaro. Indistinguishability obfuscation from trilinear maps and blockwise local prgs. In Annual International Cryptology Conference, pages 630–660. Springer, 2017.
[6] Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM Journal on Computing, 45(3):882–929, 2016.
[7] Prabhanjan Ananth, Aayush Jain, and Amit Sahai. Robust transforming combiners from indistinguishability obfuscation to functional encryption. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 91–121. Springer, 2017.
[8] Susan Hohenberger, Amit Sahai, and Brent Waters. Full domain hash from (leveled) multilinear maps and identity-based aggregate signatures. In Annual Cryptology Conference, pages 494–512. Springer, 2013.
[9] Jia Yu, Hui Xia, Huawei Zhao, Rong Hao, Zhangjie Fu, and Xiangguo Cheng. Forwardsecure identity-based signature scheme in untrusted update environments. Wireless Personal Communications, 86(3):1467–1491, 2016.
[10] Ozg¨ur Dagdelen, David Galindo, Pascal V´eron, ¨Sidi Mohamed El Yousfi Alaoui, and Pierre-Louis Cayrel. Extended security arguments for signature schemes. Designs, Codes and Cryptography, 78(2):441–461, 2016.
[11] Daofeng Li, Haiqiang Chen, Cheng Zhong, Taoshen Li, and Feng Wang. A new self-certified signature scheme based on ntrus ing for smart mobile communications. Wireless Personal Communications, 96(3):4263–4278, 2017.
[12] Leslie Lamport. Constructing digital signatures from a one-way function. Technical report, Citeseer, 1979.
[13] Tal Malkin, Daniele Micciancio, and Sara Miner. Efficient generic forward-secure signatures with an unbounded number of time periods. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 400–417. Springer, 2002.
[14] Johannes Buchmann, Erik Dahmen, and Andreas H¨ulsing. Xmss-a practical forward secure signature scheme based on minimal security assumptions. In International Workshop on PostQuantum Cryptography, pages 117–129. Springer, 2011.
[15] Ralf Hauser, Tony Przygienda, and Gene Tsudik. Reducing the cost of security in link-state routing. In Proceedings of SNDSS’97: Internet Society 1997 Symposium on Network and Distributed System Security, pages 93–99. IEEE, 1997.
[16] Ralph C Merkle. A certified digital signature. In Conference on the Theory and Application of Cryptology, pages 218–238. Springer, 1989.
[17] Andreas H¨ulsing, Christoph Busold, and Johannes Buchmann. Forward secure signatures on smart cards. In International Conference on Selected Areas in Cryptography, pages 66–80. Springer, 2012.
[18] Andreas H¨ulsing, Lea Rausch, and Johannes Buchmann. Optimal parameters for xmss mt. In International Conference on Availability, Reliability, and Security, pages 194–208. Springer, 2013.
[19] Daniel J Bernstein, Daira Hopwood, Andreas H¨ulsing, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Michael Schneider, Peter Schwabe, and Zooko Wilcox-OHearn. Sphincs: practical stateless hash-based signatures. In Annual international conference on the theory and applications of cryptographic techniques, pages 368–397. Springer, 2015.
[20] Andreas H¨ulsing, Joost Rijneveld, and Fang Song. Mitigating multi-target attacks in hashbase PKC 2016, pages 387–416. Springer, 2016.
[21] Jean-Philippe Aumasson and Guillaume Endignoux. Improving stateless hash-based signatures. In Cryptographers Track at the RSA Conference, pages 219–242. Springer, 2018.
[22] Jean-Philippe Aumasson, Daniel J Bernstein, Christoph Dobraunig, Maria Eichlseder, Scott Fluhrer, Stefan-Lukas Gazdag, Andreas H¨ulsing, Panos Kampanakis, Stefan K¨olbl, Tanja Lange, et al. Sphincs+. 2019.
[23] Alejandro Hevia and Daniele Micciancio. The provable security of graph-based one-time signatures and extensions to algebraic signature schemes. In International Conference on the Theory and Application of Cryptology and Information Security, pages 379–396. Springer, 2002.
[24] Chris Dods, Nigel P Smart, and Martijn Stam. Hash based digital signature schemes. In IMA International Conference on Cryptography and Coding, pages 96–115. Springer, 2005.
[25] Johannes Buchmann, Erik Dahmen, Sarah Ereth, Andreas H¨ulsing, and Markus R¨uckert. On the security of the winternitz one-time signature scheme. In International conference on cryptology in Africa, pages 363–378. Springer, 2011.
[26] Andreas H¨ulsing. W-ots+–shorter signatures for hash-based signature schemes. In International Conference on Cryptology in Africa, pages 173–188. Springer, 2013.
[27] Sanjam Garg. Candidate Multilinear Maps. PhD thesis, University of California Los Angeles, 2013.
[28] Adeline Langlois, Damien Stehl´e, and Ron Steinfeld. Gghlite: More efficient multilinear maps from ideal lattices. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 239–256. Springer,2014.
[29] Martin R Albrecht, Catalin Cocis, Fabien Laguillaumie, and Adeline Langlois. Implementing candidate graded encoding schemes from ideal lattices. In International Conference on the Theory and Application of Cryptology and Information Security, pages 752–775. Springer, 2015.
)