IEICE Trans - The Vector Decomposition Problem

The Vector Decomposition Problem

Maki YOSHIDA
Shigeo MITSUNARI
Toru FUJIWARA

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Vol.E93-A No.1 pp.188-193
Publication Date: 2010/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E93.A.188
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Mathematics
Keyword:
computational problem, vector decomposition problem, computational Diffie-Hellman problem, elliptic curve, pairing,

Full Text: PDF(190.9KB)>>

Summary:
This paper introduces a new computational problem on a two-dimensional vector space, called the vector decomposition problem (VDP), which is mainly defined for designing cryptosystems using pairings on elliptic curves. We first show a relation between the VDP and the computational Diffie-Hellman problem (CDH). Specifically, we present a sufficient condition for the VDP on a two-dimensional vector space to be at least as hard as the CDH on a one-dimensional subspace. We also present a sufficient condition for the VDP with a fixed basis to have a trapdoor. We then give an example of vector spaces which satisfy both sufficient conditions and on which the CDH is assumed to be hard in previous work. In this sense, the intractability of the VDP is a reasonable assumption as that of the CDH.

open access publishing via