Analysis of the strong instance for the vector decomposition problem
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
A new hard problem called the vector decomposition problem (VDP) was recently proposed by Yoshida et al., and it was asserted that the VDP is at least as hard as the computational Diffie-Hellman problem (CDHP) under certain conditions. Kwon and Lee showed that the VDP can be solved in polynomial time in the length of the input for a certain basis even if it satisfies Yoshida's conditions. Extending our previous result, we provide the general condition of the weak instance for the VDP in this paper. However, when the VDP is practically used in cryptographic protocols, a basis of the vector space ν is randomly chosen and publicly known assuming that the VDP with respect to the given basis is hard for a random vector. Thus we suggest the type of strong bases on which the VDP can serve as an intractable problem in cryptographic protocols, and prove that the VDP with respect to such bases is difficult for any random vector in ν.
Abstract
A new hard problem called the vector decomposition problem (VDP) was recently proposed by Yoshida et al., and it was asserted that the VDP is at least as hard as the computational Diffie-Hellman problem (CDHP) under certain conditions. Kwon and Lee showed that the VDP can be solved in polynomial time in the length of the input for a certain basis even if it satisfies Yoshida's conditions. Extending our previous result, we provide the general condition of the weak instance for the VDP in this paper. However, when the VDP is practically used in cryptographic protocols, a basis of the vector space ν is randomly chosen and publicly known assuming that the VDP with respect to the given basis is hard for a random vector. Thus we suggest the type of strong bases on which the VDP can serve as an intractable problem in cryptographic protocols, and prove that the VDP with respect to such bases is difficult for any random vector in ν.
참고문헌 (8)
- I. Duursma, "On the vector decomposition problem for m-torsion points on an elliptic curve", Proc. IEEE International Symposium on Information Theory (ISIT), 통권 : 27, pp.545~545 (2004)
- I. Duursma, "The vector decomposition problem for elliptic and hyperelliptic curves", J. Ramanujan Math. Soc., 20(1), pp.59~76 (2005)
- ElGamal type signature schemes for n-dimensional vector spaces, "I. Duursma", Cryptology ePrint Archive, 312~ (2006)
- G. Frey, "A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves", Math. Comp., 62(206), pp.865~874 (1994)
- 권세란, "벡터 분해 문제의 어려움에 대한 분석", 정보보호학회논문지, 17(3), pp.27~34 (2007), 한국정보보호학회
- A. Menezes, "educing elliptic curve logarithms to logarithms in a finite field", IEEE Trans. Inform. Theory, 39(5), pp.1639~1646 (1993)
- M. Yoshida, "Inseparable multiplex transmission using the pairing on elliptic curves and its application to watermarking", Proc. Fifth Conference on Algebraic Geometry, Number Theory, Coding Theory and Cryptography (2003), University of Tokyo
- M. Yoshida, "Vector decomposition problem and the trapdoor inseparable multiplex transmission scheme based the problem", Proc. of the 2003 Symposium on Cryptography and Information Security (SCIS) (2003)