On the Σ^b_1-Definability of Integer Factoring
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, we introduce an approach to cryptology using bounded arithmetic, and we investigate factorization. Factorization supports the security of many kinds of cryptosystems. If it could be efficiently computed, then those systems would not be secure any longer. Since functions that are Σ^b_1-definable in S^1_2 are computable in polynomial time, it is a worthwhile task to try to Σ^b_1-define the factoring function. At present, however, it turns out to be necessary to add some axiom to the theory S^1_2 with respect to primality.
- 一般社団法人情報処理学会の論文
- 1999-12-15
著者
-
多田 充
北陸先端科学技術大学院大学情報科学研究科
-
Tada Mitsuru
School Of Information Science Japan Advanced Institute Of Science And Teclmology
-
Shizuya Hiroki
Education Center For Information Processing And Graduate School Of Information Sciences Tohoku Unive
関連論文
- 高速な署名方式の安全性に関する研究
- 素因数分解に基づく効率的な署名方式の提案(21世紀のコンピュータセキュリティ技術)
- 高速な署名を実現する新しいパラダイムの提案
- 素因数分解に基づく効率的な署名方式
- 署名者の意思を反映する多重署名方式の提案
- 意思付多重署名方式についての研究
- 意思付多重署名方式についての研究
- A Note on AM Languages Outside NP ⋃ co-NP (Special Section on Cryptography and Information Security)
- A Note on the Complexity of Breaking Okamoto-Tanaka ID-Based Key Exchange Seheme (Special Section on Cryptography and Information Security)
- Demonstrating Possession without Revealing Factors (Special Section on Cryptography and Information Security)
- On the Complexity of the Discrete Logarithm for a General Finite Group (Special Section on Cryptography and Information Security)
- 順序付き多重署名の弱さに関する考察
- 関連づけ可能な匿名オフライン電子マネー
- 関連づけ可能な匿名オフライン電子マネー
- On the Σ^b_1-Definability of Integer Factoring
- 岡本-田中鍵共有方式のなりすましに関する安全性
- Proposal for New E-cash System Using Message Recovery Signature (特集 情報セキュリティの理論と応用)
- On the Security of the Okamoto-Tanaka ID-Based Key Exchange Scheme against Active Attacks