The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E93-A No.1 pp.188-193

- Publication Date
- 2010/01/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.E93.A.188

- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)

- Category
- Mathematics

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Maki YOSHIDA, Shigeo MITSUNARI, Toru FUJIWARA, "The Vector Decomposition Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E93-A, no. 1, pp. 188-193, January 2010, doi: 10.1587/transfun.E93.A.188.

Abstract: 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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E93.A.188/_p

Copy

@ARTICLE{e93-a_1_188,

author={Maki YOSHIDA, Shigeo MITSUNARI, Toru FUJIWARA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={The Vector Decomposition Problem},

year={2010},

volume={E93-A},

number={1},

pages={188-193},

abstract={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.},

keywords={},

doi={10.1587/transfun.E93.A.188},

ISSN={1745-1337},

month={January},}

Copy

TY - JOUR

TI - The Vector Decomposition Problem

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 188

EP - 193

AU - Maki YOSHIDA

AU - Shigeo MITSUNARI

AU - Toru FUJIWARA

PY - 2010

DO - 10.1587/transfun.E93.A.188

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E93-A

IS - 1

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - January 2010

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

ER -