TY - JOUR

T1 - Analysis of the strong instance for the vector decomposition problem

AU - Kwon, Saeran

AU - Lee, Hyang Sook

PY - 2009/3

Y1 - 2009/3

N2 - 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 ν.

AB - 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 ν.

KW - Computational Difffie-Hellman problem

KW - Strong instance

KW - Vector decomposition problem

UR - http://www.scopus.com/inward/record.url?scp=64549129909&partnerID=8YFLogxK

U2 - 10.4134/BKMS.2009.46.2.245

DO - 10.4134/BKMS.2009.46.2.245

M3 - Article

AN - SCOPUS:64549129909

SN - 1015-8634

VL - 46

SP - 245

EP - 253

JO - Bulletin of the Korean Mathematical Society

JF - Bulletin of the Korean Mathematical Society

IS - 2

ER -