The Vector Decomposition Problem
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.
- 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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
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 -
English
