The Vector Decomposition Problem

スポンサーリンク

概要

• 論文の詳細を見る

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

著者

• YOSHIDA Maki

  Graduate School of Information Science and Technology, Osaka University

• MITSUNARI Shigeo

  Cybozu Labs, Inc.

• FUJIWARA Toru

  Graduate School of Information Science and Technology, Osaka University

関連論文

• The Vector Decomposition Problem
• The Vector Decomposition Problem
• Flexible Timed-Release Encryption
• Sufficient Conditions for Ruling-Out Useless Iterative Steps in a Class of Iterative Decoding Algorithms (Special Section on Information Theory and Its Applications)
• Local Weight Distribution of the (256, 93) Third-Order Binary Reed-Muller Code(Coding Theory)
• Local Weight Distribution of the (256, 93) Third-Order Binary Reed-Muller Code(HISC2006)
• Performance Analysis for Binary Image of Linear Block Codes over an Extended Field of GF(2)
• Adaptive Recursive Maximum Likelihood Decoding Based on the Coarsest Parallel Concatenation Decomposition : Evaluation of the Decoding Complexity by Simulation
• Selecting the Search Centers of h-Chase Decoding Algorithms by Simulation

スポンサーリンク