The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Cet article introduit un nouveau problème de calcul sur un espace vectoriel bidimensionnel, appelé problème de décomposition vectorielle (VDP), qui est principalement défini pour la conception de cryptosystèmes utilisant des appariements sur des courbes elliptiques. Nous montrons d'abord une relation entre le VDP et le problème informatique de Diffie-Hellman (CDH). Plus précisément, nous présentons une condition suffisante pour que le VDP sur un espace vectoriel bidimensionnel soit au moins aussi difficile que le CDH sur un sous-espace unidimensionnel. Nous présentons également une condition suffisante pour que le VDP à base fixe ait une trappe. Nous donnons ensuite un exemple d'espaces vectoriels qui satisfont à la fois des conditions suffisantes et sur lesquels le CDH est supposé dur dans les travaux précédents. En ce sens, le caractère intraitable du VDP est une hypothèse raisonnable, tout comme celle du CDH.
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.
Copier
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
Copier
@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},}
Copier
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 -