# 論文翻訳: Verifiable Random Functions

Takami Torao 1999年の論文 #VRF

## 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