首页    期刊浏览 2024年11月27日 星期三
登录注册

文章基本信息

  • 标题:Monotone Circuits: One-Way Functions versus Pseudorandom Generators
  • 本地全文:下载
  • 作者:Oded Goldreich ; Rani Izsak
  • 期刊名称:Theory of Computing
  • 印刷版ISSN:1557-2862
  • 电子版ISSN:1557-2862
  • 出版年度:2012
  • 卷号:8
  • 页码:231-238
  • 出版社:University of Chicago
  • 摘要:

    We study the computability of one-way functions and pseudorandom generators by monotone circuits, showing a substantial gap between the two: On one hand, there exist one-way functions that are computable by (uniform) polynomial-size monotone functions, provided (of course) that one-way functions exist at all. On the other hand, no monotone function can be a pseudorandom generator.

  • 关键词:monotone circuits; one-way functions; pseudorandom generators; cryptography
国家哲学社会科学文献中心版权所有