Document Type : Research Article
Authors
Electrical Engineering Department, Shahid Beheshti University, Tehran, Iran
Abstract
The security of public key cryptography relies on the complexity of certain mathematical hard problems. It is vital to comprehend the intricacy of these problems to develop secure cryptographic schemes and security protocols. This paper provides an overview of some widely recognized hard problems associated with the discrete logarithm problem, including the reductions among them. Furthermore, we introduce a novel hard problem that is equivalent to the discrete logarithm problem, which also has a decisional version. Additionally, a set of new problems is presented, which can be instrumental in the design of secure encryption schemes. This paper is intended to provide crucial insights into the realm of hard problems in cryptography, facilitating a better understanding of security measures.
Keywords
[2] Feng Bao, Robert H Deng, and Huafei Zhu. Variations of diffie-hellman problem. In Information and Communications Security: 5th International Conference, ICICS 2003, Huhehaote, China, October 10-13, 2003. Proceedings 5, pages 301–312.
Springer, 2003.
[3] Taiga Mizuide, Atsushi Takayasu, and Tsuyoshi Takagi. Tight reductions for diffie-hellman variants in the algebraic group model. In Topics in Cryptology–CT-RSA 2019: The Cryptographers’ Track at the RSA Conference 2019, San Francisco, CA, USA, March 4–8, 2019, Proceedings, pages 169–188. Springer, 2019.
[4] Naomi Benger, David Bernhard, Dario Catalano, Manuel Charlemagne, David Conti, Biljana Cubaleska, Hernando Fernando, Dario Fiore, Steven Galbraith, David Galindo, et al. Final report on main computational assumptions in cryptography ii. Technical report, ICT-2007-216676 D. MAYA. 6. European Network of Excellence in Cryptology, 2013.
[5] Jung Hee Cheon. Security analysis of the strong diffie-hellman problem. In Advances in Cryptology-EUROCRYPT 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28-June 1, 2006. Proceedings 25, pages 1–11. Springer, 2006.
[6] P Nigel Smart. Cryptography made simple. Springer, 2016.
[7] Christof Paar and Jan Pelzl. Understanding cryptography: a textbook for students and practitioners. Springer Science & Business Media, 2009.
[8] Robert Granger and Antoine Joux. Computing discrete logarithms. Cryptology ePrint Archive, Paper 2021/1140, 2021. https://eprint.iacr.org/2021/1140.
[9] Steven D Galbraith. Mathematics of public key cryptography, Version 2.0. Cambridge University Press, 2018.
[10] Kannan Balasubramanian. Variants of the diffiehellman problem. In Algorithmic Strategies for Solving Complex Problems in Cryptography, pages 40–54. IGI Global, 2018.
[11] Yael Tauman Kalai, Alex Lombardi, and Vinod Vaikuntanathan. Snargs and ppad hardness from the decisional diffiehellman assumption. In Advances in Cryptology- EUROCRYPT 2023: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 470–498. Springer, 2023.
[12] Abhishek Jain and Zhengzhong Jin. Noninteractive zero knowledge from sub-exponential ddh. In Advances in Cryptology–EUROCRYPT 2021: 40th Annual International Conference on the Theory and Applications of Cryptographic
Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part I, pages 3–32. Springer, 2021.
[14] Mahdi MahdaviOliaee and Zahra Ahmadian. Fine-grained flexible access control: ciphertext policy attribute based encryption for arithmetic circuits. Journal of Computer Virology and Hacking Techniques, pages 1–14, 2022.
[15] Steven Galbraith, Florian Hess, and Frederik Vercauteren. Aspects of pairing inversion. IEEE Transactions on Information Theory, 54(12):5719–5728, 2008.
[16] Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the weil pairing. Journal of cryptology, 17:297–319, 2004.
[17] Mohammad Ali. Attribute-based remote data auditing and user authentication for cloud storage systems. ISeCure, 14(3), 2022.
[18] Sina Abdollahi, Javad Mohajeri, and Mahmoud Salmasizadeh. Highly efficient and revocable cpabe with outsourcing decryption for iot. In 2021 18th International ISC Conference on Information Security and Cryptology (ISCISC), pages
81–88. IEEE, 2021.
[19] Ming Luo and Yuwei Wan. An enhanced certificateless signcryption in the standard model. Wireless Personal Communications, 98:2693–2709, 2018.
[20] Han-Yu Lin and Yao-Min Hung. An improved proxy re-encryption scheme for iot-based data outsourcing services in clouds. Sensors, 21(1):67, 2020.
)