• Article
  • | |
  • Metrics
  • |
  • Reference [8]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    One Way functions play an important role in complexity theory of computation and public key cryptography. Inspired by the work of Grollmann and Selman, the work of Grollmann and Selman to the result of relativization and nonuniform complexity classes are generalized in this paper, the equivalence of the include relation of complexity class UP /poly, UP, P /poly and the existence of strongly relativization one way function, weakly relativization one way function are proved.

    Reference
    [1] Grollmann, J., Selman, A.L. Complexity measures for public -key cryptosystems. SIAM Journal on Computing, 1988,17(2):309~335.
    [2] Boppana, R.B., Lagarias, J.C. One-Way functions and circuit comple xity. In: Selman, A.L., ed. Lecture Notes in Computer Science 223. Berlin: Sprin ger-Verlag, 1986. 51~65.
    [3] Homer, S., Wang, J. Absolute results concerning one-way functions and their applications. Mathematical Systems Theory, 1989,22(1):21~35.
    [4] Lü, Yi-zhong, Gu, Lei. Existence of oneway function in boolean circuit. Computer Research and Development, 1992,29(7):1~5 (in Chinese).吕义忠,顾蕾.布尔分层one-way函数的存在性.计算机研究与发展,1992,29(7):1~5.
    [5] Karp, R.M., Lipton, R.J. Some connections between nonuniform and un iform complexity classes. In: Proceedings of the 12th ACM Symposium on Theory of Computing. New York: ACM Press, 1980. 302~309.
    [6] Kbler, J, Watanabe, O. New collapse consequences of NP havi ng small circuits. In: Flp, Zoltán, eds. Lecture Notes in Compu ter Science 944. Berlin: Springer-Verlag, 1995. 196~208.
    [7] Balcazar, J.L., Diaz, J., Gabarro, J. Structural Complexity I. Berl in: Springer-Verlag, 1988.
    [8] Watanabe, O. On one-way functions. In: Du, D,, Hu, G., eds. Combin atorics, Computing and Complexity. Boston: Kluwer Academic Publishers and Scienc e Press, 1989. 98~131.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

曹子宁,吕义忠,石纯一.相对化One-Way函数的存在性.软件学报,2001,12(6):884-888

Copy
Share
Article Metrics
  • Abstract:3487
  • PDF: 4404
  • HTML: 0
  • Cited by: 0
History
  • Received:October 13,1999
  • Revised:March 23,2000
You are the first2034256Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063