与えられた位数の楕円曲線を構成する複雑さについて
スポンサーリンク
概要
- 論文の詳細を見る
有限体上の楕円曲線の位数は多項式時間で計算できることがSchoofにより示されたが,逆に,与えられた位数を持つ有限体上の楕円曲線を多項式時間で計算できるかどうかは1986年以来の未解決問題である.本論文ではこの未解決問題に関して,与えられた位数を持つ楕円曲線を求める多価部分関数fの難しさの特徴付けを行う.その結果,もしブール式を充足させる割り当てを一つ出力する多価部分関数satがfに多項式時間Turing帰着するならば,多項式時間階層がNPまで潰れることを示す.また拡張Riemann予想の仮定のもとで,この未解決問題と等価な問題を示す.
- 1999-11-08
著者
-
満保 雅浩
筑波大学大学院システム情報工学研究科
-
山道 将人
東北大学大学院情報科学研究科情報基礎科学専攻
-
満保 雅浩
東北大学大学院情報科学研究科情報基礎科学専攻
-
静谷 啓樹
東北大学大学院情報科学研究科情報基礎科学専攻
-
静谷 啓樹
東北大学大学院情報科学研究科
-
満保 雅浩
東北大学大学院情報科学研究科:東北大学情報処理教育センター
関連論文
- 属性ベース暗号の一改良 (情報セキュリティ)
- 検証機能を有する楕円曲線上のスカラ倍算の委託計算
- 効率的な改良PayWord小額決済方式(応用,サイバーワールド論文)
- OTU2000暗号方式に対する格子理論に基づく攻撃実験(その2)
- 代数的トーラス上の離散対数問題に関する計算量理論的考察(情報通信基礎サブソサイエティ合同研究会)
- 行列型楕円離散対数問題の構成とその難しさについて
- 与えられた位数の楕円曲線を構成する複雑さについて
- 廉価なスイッチとSecure Shellを利用した安全な情報コンセントの構成方法
- 商用目的に適した鍵回復システムの開発
- 属性ベース暗号の一改良
- ペアリング演算ASICの開発
- 2ZB-8 改ざん検出機能を有する電子透かしの多層化方式(セキュリティ(2),学生セッション,セキュリティ)
- 改良PayWord方式の効率化検証(オフィスインフォメーションシステム、Webシステム及び一般)
- 公開検証型電子投票の安全性について(オフィスインフォメーションシステム、Webシステム及び一般)
- 追跡可能性を有する部分ブラインド署名の一構成(情報通信基礎サブソサイエティ合同研究会)
- 追跡可能性を有する部分ブラインド署名の一構成(情報通信基礎サブソサイエティ合同研究会)
- 追跡可能性を有する部分ブラインド署名の一構成(情報通信基礎サブソサイエティ合同研究会)
- 柔軟な改ざん検出機能を有する電子透かし方式(セッション1)
- 小額決済方式PayWordのコスト削減手法の提案(知的生産活動における情報アクセス制御技術及び一般)
- 小額決済方式PayWordのコスト削減手法の提案(知的生産活動における情報アクセス制御技術及び一般)
- 有向グラフに対する推移署名方式の構成法(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 有向グラフに対する推移署名方式の構成法(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 有向グラフに対する推移署名方式の構成法(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 大学における情報リテラシー教育の最近の動向(2.第1回情報シナジー研究会)
- 順序を考慮した暗号プロトコルのモデルと具体例
- 安全性証明可能暗号システムの強選択暗号文攻撃における安全性解析
- 一方向性落し戸環準同型に基づくメッセージ確認方式
- 非可換環上の多重署名についての考察
- 環準同型の性質をもつ暗号化関数の一構成
- 離散対数暗号系に付随する言語の複雑さについて
- 離散対数暗号に付随する言語の複雑さについて
- 抽象的DDoS攻撃問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- 代数的トーラス上の離散対数問題に関する計算量理論的考察(情報通信基礎サブソサイエティ合同研究会)
- 代数的トーラス上の離散対数問題に関する計算量理論的考察(情報通信基礎サブソサイエティ合同研究会)
- 音情報に対する電子透かし : 乱択法とうなり法(情報通信基礎サブソサイエティ合同研究会)
- 公開鍵基盤の頑健化について(情報通信基礎サブソサイエティ合同研究会)
- 音情報に対する電子透かし : 乱択法とうなり法(情報通信基礎サブソサイエティ合同研究会)
- 公開鍵基盤の頑健化について(情報通信基礎サブソサイエティ合同研究会)
- 音情報に対する電子透かし : 乱択法とうなり法(情報通信基礎サブソサイエティ合同研究会)
- 公開鍵基盤の頑健化について(情報通信基礎サブソサイエティ合同研究会)
- 抽象的DDoS攻撃問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- DH問題とその派生問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- 抽象的DDoS攻撃問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- DH問題とその派生問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- DH問題とその派生問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- グラフ同型を用いた離散対数型暗号の考察
- グラフ同型を用いた離散対数型暗号の考察
- グラフ同型を用いた離散対数型暗号の考察
- 正則な格子における最近傍格子点問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- 正則な格子における最近傍格子点問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- 正則な格子における最近傍格子点問題の複雑さについて(情報通信基礎サブソサイエティ合同研究会)
- フィードバックシフトレジスタとテーブル関数を用いた乱数生成に関する一考察
- CRYPTO'97国際会議報告
- 電子透かしの理論的枠組に関する一考察
- 平方根べき乗問題について
- 様々な署名構造に適用可能な RSA 型多重署名方式
- 検索クエリ中のワイルドカードを秘匿する隠れベクトル暗号システム
- 多価関数における自己帰着とmany-one型帰着について(情報通信基礎サブソサイエティ合同研究会)
- 多価関数における自己帰着とmany-one型帰着について(情報通信基礎サブソサイエティ合同研究会)
- 多価関数における自己帰着とmany-one型帰着について(情報通信基礎サブソサイエティ合同研究会)
- 与えられた位数の楕円曲線を構成する複雑さについて
- DNAを用いた投票方式の一検討
- 自己復号型秘密情報通信方式における鍵配送についての一提案
- 攻撃通信検知のための合成型機械学習手法の一検討
- 情報の漏れを許容する知識の対話証明(一般,情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般)
- SLPに基づく強RSA仮定とDDH仮定の分離(一般,情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般)
- 情報の漏れを許容する知識の対話証明(一般,情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般)
- SLPに基づく強RSA仮定とDDH仮定の分離(一般,情報セキュリティ,ライフログ活用技術,ライフインテリジェンス,オフィス情報システム,一般)
- 閾値(委任)署名の匿名性に関する考察
- 閾値(委任)署名の匿名性に関する考察
- 閾値(委任)署名の匿名性に関する考察
- 1ビットの鍵共有に必要十分なカード配布枚数について
- 検索クエリ中のワイルドカードを秘匿する隠れベクトル暗号システム (特集 人と共存するコンピュータセキュリティ技術)
- 情報の漏れを許容する知識の対話証明
- SLPに基づく強RSA仮定とDDH仮定の分離
- 最短なオイラー閉路状鍵共有
- 最小枚数のカードの配布によるオイラー閉路状鍵共有
- カードの配布によるオイラー閉路状鍵共有
- カードの配布を用いた受領確認可能な鍵共有プロトコル
- 情報理論的に安全で受領確認可能な鍵共有法
- SLPに基づく強RSA仮定とDDH仮定の分離
- 情報の漏れを許容する知識の対話証明