近似GCD問題に対する改良アルゴリズム(セキュリティ,一般)
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,整数の倍数の近似値が複数個与えられたときにその公約数を求める多変数のapproximate common divisor problem (ACDP)の解析を行った.これまでに格子を用いたCoppersmithの理論に基づいてACDPを解く多項式時間アルゴリズムが提案されてきた.2001年にHowgrave-Grahamは与えられる近似値が2つの場合に,誤差が小さいときのACDPを解く多項式時間アルゴリズムを提案した.ついで,2011年にCohn, Heningerはこの手法を一般に複数個の近似値が与えられた場合に拡張した.本論文では部分問題として誤差のない厳密な倍数が1つ与えられるpartially approximate common divisor problem (PACDP)のみについて解析をしている.我々は一般に複数個の近似値が与えられた場合のPACDPに対してCohn, Heningerのアルゴリズムを改良したアルゴリズムを提案する.PACDPでは,Cohn, Heningerは不等式(α_1+…+α_n)/n<β^<(n+1)/n>を満たすとき,多項式時間で解けることを示した.我々はCohn, Heningerのアルゴリズムから格子の構成を変更することによってこの条件を^n√<α_1…α_n><β^<(n+1)/n>に改善した.この不等式の左辺はCohn, Heningerがα_1,…,α_nの相加平均としたところを我々のアルゴリズムではα_1,…,α_nの相乗平均となっており,我々のアルゴリズムはより広いクラスの問題に適用可能である.さらにHowgrave-Grahamのアルゴリズムから多変数への拡張を考えたときに多項式時間で解けるべき条件を考えると,我々のアルゴリズムの条件のほうがCohn, Heningerのものより自然な条件となっている.
- 一般社団法人電子情報通信学会の論文
- 2012-07-12
著者
関連論文
- RSA暗号のSmall Secret Key Attackに対する簡単な証明とその拡張(セキュリティ関係,一般)
- 研究グループが脆弱性を発見した場合にとるべき行動についての法的考察(プロジェクトマネジメント関係,一般)
- Secret Handshakeの安全性について(情報通信基礎サブソサイエティ合同研究会)
- 5. 素因数分解は,RSA暗号解読より真に難しいか?(素数)
- 暗号における理論と実装のギャップ : 置き換えアプローチの二面性(暗号理論入門(4))
- Small secret key attack on Takagi's variant of RSA (part 1) (オフィスインフォメーションシステム)
- Small secret key attack on Takagi's variant of RSA (part 1) (情報セキュリティ)
- APOPが破られた(オピニオン)
- RSA暗号のSmall Secret Key Attackに対する簡単な証明とその拡張(セキュリティ関係,一般)
- RSA暗号のSmall Secret Key Attackに対する簡単な証明とその拡張(セキュリティ関係,一般)
- Bulk量子計算モデル上におけるGroverのアルゴリズムの繰返し回数について
- A-7-11 MD4を用いたチャレンジ&レスポンス認証に対する現実的な攻撃(A-7.情報セキュリティ,一般セッション)
- 素因数分解ハードウェアの研究・開発動向について(セキュリティ基盤技術,情報システムを支えるコンピュータセキュリティ技術の再考)
- Paillierの観点から見たディジタル署名の安全性の再考
- 双線形写像を用いた墨塗り署名方式の安全性について(セキュリティ基盤技術,ユビキタス社会を支えるコンピュータセキュリティ技術)
- Secret Handshakeの安全性について(情報通信基礎サブソサイエティ合同研究会)
- Secret Handshakeの安全性について(情報通信基礎サブソサイエティ合同研究会)
- AS-3-3 非線形ランプ型秘密分散(招待講演,AS-3.情報ハイディングの理論と技術,シンポジウム)
- 分散画像の回転を許す一般アクセス構造に対して複数の画像を隠す視覚復号型秘密分散法
- 安全性を証明可能なハッシュ関数の設計論
- RSA暗号に対する格子理論に基づく攻撃(その2)
- 暗号学における双対性 : ゴールとシナリオの間には(チュートリアル)
- RSA暗号に対する格子理論に基づく攻撃
- 墨塗り・削除署名の拡張
- 墨塗り・削除署名の拡張
- 使い捨てIDを用いた処理負荷の少ない相手認証方式の提案(情報通信基礎サブソサイエティ合同研究会)
- MD5に対するコリジョンアタックの改良
- MD5に対するコリジョンアタックの改良
- 使い捨てIDを用いた処理負荷の少ない相手認証方式の提案(情報通信基礎サブソサイエティ合同研究会)
- 使い捨てIDを用いた処理負荷の少ない相手認証方式の提案(情報通信基礎サブソサイエティ合同研究会)
- 境界要素法の変数変換型の自動数値積分法とその誤差解析
- ナップザック暗号における密度の再考(情報通信基礎サブソサイエティ合同研究会)
- ナップザック暗号における密度の再考(情報通信基礎サブソサイエティ合同研究会)
- ナップザック暗号における密度の再考(情報通信基礎サブソサイエティ合同研究会)
- 公開鍵暗号方式における強い攻撃モデルの証明(不)可能性(情報通信基礎サブソサイエティ合同研究会)
- 公開鍵暗号方式における強い攻撃モデルの証明(不)可能性(情報通信基礎サブソサイエティ合同研究会)
- 公開鍵暗号方式における強い攻撃モデルの証明(不)可能性(情報通信基礎サブソサイエティ合同研究会)
- 素因数分解ハードウェアの現状(ミニ素因数分解編) : 2006年秋(知的生産活動における情報アクセス制御技術及び一般)
- 素因数分解ハードウェアの現状(ミニ素因数分解編) : 2006年秋(知的生産活動における情報アクセス制御技術及び一般)
- CS-6-2 量子計算機による素因数分解の実現可能性(CS-6.量子ビットの現在、量子コンピューティングの将来,シンポジウム)
- 素因数分解ハードウェアの現状 : 関係式探索ステップ編 : 2006年夏
- 素因数分解ハードウェアの現状 : 関係式探索ステップ編 : 2006年夏
- 素因数分解ハードウェアの現状(関係式探索ステップ編) : 2006年夏
- 公開鍵暗号の数理, 森山大輔・西巻陵・岡本龍明著, 共立出版・日本応用数理学会監修, 2011年
- 科学通信 科学ニュース:暗号の米政府標準方式が危機に
- 国際会議CRYOT0 2011報告
- 暗号における理論と実装のギャップ : 置き換えアプローチの二面性
- 国際会議ASIACRYPT 2011報告
- 近似GCD問題に対する改良アルゴリズム(セキュリティ,一般)
- 近似GCD問題に対する改良アルゴリズム(セキュリティ,一般)
- 近似GCD問題に対する改良アルゴリズム(セキュリティ,一般)
- 近似GCD問題に対する改良アルゴリズム(セキュリティ,一般)
- AI-1-1 計算能力の向上と暗号解読(AI-1.暗号研究の現状とブレークスルーに向けて,ソサイエティ企画)
- 複数の復号指数を持つRSA暗号の安全性解析