正則な格子における最近傍格子点問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
スポンサーリンク
概要
- 論文の詳細を見る
格子暗号技術は整数論上の問題である素因数分解問題と離散対数問題のどちらにも依存しない暗号系として近年注目を集めている.格子暗号系は最短ベクトル問題や最近傍格子点問題という格子上の問題にその安全性を依存している.これらの問題はNP困難であることが知られており,またその近似問題についても多くの研究が行われている.しかし,実際の暗号系に用いられる格子は構造上の特徴があるため,その特徴を利用してそれらの問題を効率的に解く方法が存在する可能性もある.本論文では最近傍格子点問題の複雑さについて,格子構造の観点からアプローチするという新たな試みを行い,格子の基底行列を正則行列に制限してもその難しさがNP困難であることを示す.
- 社団法人電子情報通信学会の論文
- 2006-03-09
著者
-
静谷 啓樹
東北大学大学院情報科学研究科情報基礎科学専攻
-
磯辺 秀司
東北大学大学院情報科学研究科
-
布田 裕一
松下電器産業株式会社マルチメディア開発センター
-
磯辺 秀司
東北大大学院情報科学研究科
-
長谷川 真吾
東北大学大学院情報科学研究科
-
大森 基司
松下電器産業(株)マルチメディア開発センター
-
長谷川 真吾
東北大大学院情報科学研究科
-
静谷 啓樹
東北大大学院情報科学研究科
-
布田 裕一
松下電器産業
-
大森 基司
松下電器産業
-
大森 基司
松下電器産業(株)情報通信研究所
-
静谷 啓樹
東北大学大学院情報科学研究科
関連論文
- 代数的トーラス上の離散対数問題に関する計算量理論的考察(情報通信基礎サブソサイエティ合同研究会)
- 効率的なモンゴメリ型楕円曲線のスカラ倍演算(2)
- 行列型楕円離散対数問題の構成とその難しさについて
- 与えられた位数の楕円曲線を構成する複雑さについて
- 素数位数を有する楕円曲線の構成とその計算量評価 (代数曲線とその応用論文小特集)
- 効率的なOEF上楕円曲線の構成
- 楕円曲線の構成とその計算量評価について
- Schoofのアルゴリズムに関する基礎的考察
- 追跡可能性を有する部分ブラインド署名の一構成(情報通信基礎サブソサイエティ合同研究会)
- 追跡可能性を有する部分ブラインド署名の一構成(情報通信基礎サブソサイエティ合同研究会)
- 追跡可能性を有する部分ブラインド署名の一構成(情報通信基礎サブソサイエティ合同研究会)
- 有向グラフに対する推移署名方式の構成法(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 有向グラフに対する推移署名方式の構成法(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 有向グラフに対する推移署名方式の構成法(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 大学における情報リテラシー教育の最近の動向(2.第1回情報シナジー研究会)
- 一方向性落し戸環準同型に基づくメッセージ確認方式
- 非可換環上の多重署名についての考察
- 環準同型の性質をもつ暗号化関数の一構成
- 離散対数暗号系に付随する言語の複雑さについて
- 離散対数暗号に付随する言語の複雑さについて
- 抽象的DDoS攻撃問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- 代数的トーラス上の離散対数問題に関する計算量理論的考察(情報通信基礎サブソサイエティ合同研究会)
- 代数的トーラス上の離散対数問題に関する計算量理論的考察(情報通信基礎サブソサイエティ合同研究会)
- 平成20年度東北大学学士課程入学者の基礎的な情報対応能力について
- 平成20年度東北大学学士課程入学者の基礎的な情報対応能力について
- 平成19年度東北大学学士課程入学者の基礎的な情報対応能力について
- 音情報に対する電子透かし : 乱択法とうなり法(情報通信基礎サブソサイエティ合同研究会)
- 公開鍵基盤の頑健化について(情報通信基礎サブソサイエティ合同研究会)
- 音情報に対する電子透かし : 乱択法とうなり法(情報通信基礎サブソサイエティ合同研究会)
- 公開鍵基盤の頑健化について(情報通信基礎サブソサイエティ合同研究会)
- 音情報に対する電子透かし : 乱択法とうなり法(情報通信基礎サブソサイエティ合同研究会)
- 公開鍵基盤の頑健化について(情報通信基礎サブソサイエティ合同研究会)
- 抽象的DDoS攻撃問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- DH問題とその派生問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- 抽象的DDoS攻撃問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- DH問題とその派生問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- DH問題とその派生問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- 情報教育用計算機システムとその運用状況について(2.第1回情報シナジー研究会)
- グラフ同型を用いた離散対数型暗号の考察
- グラフ同型を用いた離散対数型暗号の考察
- 平成19年度東北大学学士課程入学者の基礎的な情報対応能力について
- 東北大学川内北キャンパスの無線ＬＡＮ接続サービス
- IT の教育利用に関する学士課程入学者に対するアンケート調査 ―IT 志向と教育利用ニーズを中心として―
- 平成18 年度東北大学学士課程入学者の基礎的情報対応能力について
- 言語認識の複雑さと関数計算の複雑さの関係(セキュリティ関係,一般)
- 言語認識の複雑さと関数計算の複雑さの関係(セキュリティ関係,一般)
- 言語認識の複雑さと関数計算の複雑さの関係(セキュリティ関係,一般)
- 正則な格子における最近傍格子点問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- 正則な格子における最近傍格子点問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- 正則な格子における最近傍格子点問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- ユーザのプライバシ保護を考慮した通信販売システム
- 電子透かしの理論的枠組に関する一考察
- 平方根べき乗問題について
- 効率的なモンゴメリ型楕円曲線のスカラ倍演算(2)
- ディジタル放送の限定受信方式に適した乱数加算型暗号の考察
- 多価関数における自己帰着とmany-one型帰着について(情報通信基礎サブソサイエティ合同研究会)
- 多価関数における自己帰着とmany-one型帰着について(情報通信基礎サブソサイエティ合同研究会)
- 多価関数における自己帰着とmany-one型帰着について(情報通信基礎サブソサイエティ合同研究会)
- The Computational Difficulty of Solving Cryptographic Primitive Problems Related to the Discrete Logarithm Problem(Public Key Cryptography)(Cryptography and Information Security)
- Complexity Analysis of the Cryptographic Primitive Problems through Square-Root Exponent(Discrete Mathematics and Its Applications)
- 退化的グラフの全彩色
- 部分k-木の全彩色を求める線形時間アルゴリズム
- 部分k-木の全彩色を求める多項式時間アルゴリズム
- 情報の漏れを許容する知識の対話証明 (情報セキュリティ)
- SLPに基づく強RSA仮定とDDH仮定の分離 (情報セキュリティ)
- 情報の漏れを許容する知識の対話証明 (ライフインテリジェンスとオフィス情報システム)
- SLPに基づく強RSA仮定とDDH仮定の分離 (ライフインテリジェンスとオフィス情報システム)
- 情報の漏れを許容する知識の対話証明(一般,情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般)
- SLPに基づく強RSA仮定とDDH仮定の分離(一般,情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般)
- 情報の漏れを許容する知識の対話証明(一般,情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般)
- SLPに基づく強RSA仮定とDDH仮定の分離(一般,情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般)
- 1ビットの鍵共有に必要十分なカード配布枚数について
- 情報の漏れを許容する知識の対話証明
- SLPに基づく強RSA仮定とDDH仮定の分離
- 学習支援や授業ふり返りのための板書レクチャーの簡易コンテンツ化(映像(2),五感メディアの品質,コミュニケーションデザイン,画像符号化,食メディア,一般)
- 学習支援や授業ふり返りのための板書レクチャーの簡易コンテンツ化(映像(2),五感メディアの品質,コミュニケーションデザイン,画像符号化,食メディア,一般)
- 最短なオイラー閉路状鍵共有
- 最小枚数のカードの配布によるオイラー閉路状鍵共有
- カードの配布によるオイラー閉路状鍵共有
- カードの配布を用いた受領確認可能な鍵共有プロトコル
- 情報理論的に安全で受領確認可能な鍵共有法
- SLPに基づく強RSA仮定とDDH仮定の分離
- 情報の漏れを許容する知識の対話証明