セキュリティ
\(\newcommand{\eqdef}{\overset{\mathrm{def}}{=}}\)

論文翻訳: Verifiable Random Functions

Takami Torao 1999年の論文 #VRF
  • このエントリーをはてなブックマークに追加

Abstract

我々は、秘密シード \(s\) から擬似乱数関数 \(f_s\) の Goldreich-Goldwasser-Micali 構成を拡張する事によって、予測不可能性と検証可能性を効果的に組み合わせる。そのため \(s\) の知識は、任意の点 \(x\) で \(f_s\) を評価することを可能にするだけでなく、そのような証明が提供されなかった他の点で \(f_s\) の予測不可能性を損なうことなく、値 \(f_s(x)\) が確かに正しいという NP 証明を提供する。

Table of Contents

  1. Abstract
  2. 1 Introduction [under construction]
  3. 2 Preliminaries
  4. 3 The Notion of a VRF
    1. 3.1 An Informal Exposition
    2. 3.2 A Formal Definition
  5. 4 Forma statement of results
  6. 5 From Unpredictability to Pseudorandomness
  7. 6 Increasing the input length
  8. 7 A Verifiable Unpredictable Functions
    1. 7.1 Correctness of the VUF construction
  9. Acknowledgments
  10. References
  11. 翻訳抄

1 Introduction

擬似ランダムオラクル. Goldreich, Goldwasser および Micali [GGM86] はあるシード、つまり秘密の短いランダムなデータ列を使用して \(a\)-bit データ列から \(b\)-bit データ列へのランダムオラクルをシミュレートする方法を示した。彼らは、擬似乱数生成器が存在する場合 [BM84, Yao82]、\(s\) をシードとすると、関数 \(f_s \eqdef F(s,\cdot) : \{0,1\}^a \rightarrow \{0,1\}^b\) がオラクルに対する効率的な統計テストを通過するような多項式時間アルゴリズム \(F(\cdot,\cdot)\) が存在することを示した。つまり計算リソースが十分に制限されている観測者にとっては、アルゴリズム \(F\) が公に知られているとしても \(\{0,1\}^a\) から \(\{0,1\}^b\) へのランダムオラクルへのアクセスは (オラクルとして) \(f_s\) のアクセスと区別ができない (\(s\) が秘密のままであれば)。

検証可能疑似乱数関数を構築する問題. まさにこの定義により、擬似ランダムオラクル à la [GGM86] は検証可能ではない: シード (もしくは他の追加情報) の知識なしに、点 \(x\) での擬似ランダムオラクル \(f_s\) の値 \(z\) を受け取ったとしても、独立して選択された適切な長さのランダムデータ列と区別することができない。従って、もしそれが彼に都合が良いのなら、シード \(s\) を知っている当事者は、ある点 \(x\) における彼の疑似乱数オラクルの値が、検出されることを恐れずに \(f_x(x)\) 以外であると宣言できる可能性がある。このため我々はこれらの対象を標準的な用語 "疑似乱数関数" ではなく "擬似ランダムオラクル" と呼んでいる ─ 値 \(f_s(x)\) はオラクルから "湧いて出た" ように、受信者は単にシード \(s\) から正しく計算されたものとして信頼しなければならない。

2 Preliminaries

3 The Notion of a VRF

3.1 An Informal Exposition

3.2 A Formal Definition

4 Forma statement of results

5 From Unpredictability to Pseudorandomness

6 Increasing the input length

7 A Verifiable Unpredictable Functions

7.1 Correctness of the VUF construction

Acknowledgments

We thank Oded Goldreich, Shafi Goldwasser, Shai Halevi, Joe Kilian, and David Mazieres, Mori Naor, and Omer Reingold for their insightful comments and suggestions.

References

  1. [BG89] Mihir Bellare and Shafi Goldwasser. New paradigms for digital signatures and message authentication based on non-interactive zero knowledge proofs. In G. Brassard, editor, Advances in Cryptology—CRYPTO ’89, volume 435 of Lecture Notes in Computer Science, pages 194–211. Springer-Verlag, 1990, 20–24 August 1989.
  2. [BDMP91] Manuel Blum, Alfredo De Santis, Silvio Micali, and Giuseppe Persiano. Noninteractive zero-knowledge. SIAM Journal on Computing, 20(6):1084–1118, December 1991.
  3. [BFM88] Manuel Blum, Paul Feldman, and Silvio Micali. Noninteractive zero-knowledge and its applications (extended abstract). In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 103–112, Chicago, Illinois, 2–4 May 1988.
  4. [BM84] Manuel Blum and Silvio Micali. How to generate cryptographically strong sequences of pseudorandom bits. SIAM Journal on Computing, 13(4):850–864, November 1984.
  5. [CMS99] Christian Cachin, Silvio Micali, and Markus Stadler. Computationally private information retrieval with polylogarithmic communication. In J. Stern, editor,Advances in Cryptology—EUROCRYPT ’99, volume 1592 of Lecture Notes in Computer Science, pages 402–414. Springer-Verlag, 1999, 2–6 May 1999.
  6. [CD96] Ronald Cramer and Ivan Damgard. New generation of secure and practical RSA-based signatures. In Neal Koblitz, editor, Advances in Cryptology—CRYPTO ’96, volume 1109 of Lecture Notes in Computer Science, pages 173–185. Springer-Verlag, 18–22 August 1996.
  7. [CS99] Ronald Cramer and Victor Shoup. Signature schemes based on the strong RSA assumption. Technical Report 99-01, Theory of Cryptography Library, January 1999. See also revision, July 1999.
  8. [DN94] Cynthia Dwork and Moni Naor. An efficient existentially unforgeable signature scheme and its applications. In Yvo G. Desmedt, editor, Advances in Cryptology—CRYPTO ’94, volume 839 of Lecture Notes in Computer Science, pages 234–246. Springer-Verlag, 21–25 August 1994.
  9. [GHR99] Rosario Gennaro, Shai Halevi, and Tal Rabin. Secure hash-and-sign signatures without the random oracle. In J. Stern, editor, Advances in Cryptology—EUROCRYPT ’99, volume 1592 of Lecture Notes in Computer Science, pages 123–139. Springer-Verlag, 1999, 2–6 May 1999.
  10. [GGM86] Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. Journal of the ACM, 33(4):792–807, October 1986.
  11. [GL89] Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 25–32, Seattle, Washington, 15–17 May 1989.
  12. [GMW91] Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, 38(3):691–729, July 1991.
  13. [GMR89] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186–208, February 1989.
  14. [GMR88] Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing, 17(2):281–308, April 1988.
  15. [GMY83] Shafi Goldwasser, Silvio Micali, and Andy Yao. Strong signature schemes. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pages 431–439, Boston, Massachusetts, 25–27 April 1983.
  16. [NR97] Moni Naor and Omer Reingold. Number-theoretic constructions of efficient pseudo-random functions (extended abstract). In 38th Annual Symposium on Foundations of Computer Science, pages 458–467, Miami Beach, Florida, 20–22 October 1997. IEEE.
  17. [NR98] Moni Naor and Omer Reingold. From unpredictability to indistinguishability: A simple construction of pseudorandom functions from macs (extended abstract). In Hugo Krawczyk, editor, Advances in Cryptology—CRYPTO ’98, volume 1462 of Lecture Notes in Computer Science, pages 267–282. Springer-Verlag, 23–27 August 1998.
  18. [Pom90] Carl Pomerance. Factoring. In Carl Pomerance, editor, Cryptology and Computational Number Theory, volume 42 of Proceedings of Symposia in Applied Mathematics, pages 27–47. American Mathematical Society, 1990.
  19. [Rab80] Michael O. Rabin. Probabilistic algorithms for testing primality. Journal of Number Theory, 12:128–138, 1980.
  20. [Sha83] Adi Shamir. On the generation of cryptographically strong pseudorandom sequences. ACM Transactions on Computer Systems, 1(1):38–44, February 1983.
  21. [SS77] R. Solovay and V. Strassen. A fast Monte-Carlo test for primality. SIAM Journal on Computing, 6(1):84–85, March 1977.
  22. [Yao82] Andrew C. Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, pages 80–91, Chicago, Illinois, 3–5 November 1982. IEEE.

翻訳抄

  1. Silvio Micali, Michael Rabiny, Salil Vadhan (1999) Verifiable Random Functions