A NOTE ON COMPUTATIONAL INDISTINGUISHABILITY

被引：41
|
作者：
GOLDREICH, O
机构：
[1] Computer Science Department, Technion, Haifa
来源：
INFORMATION PROCESSING LETTERS | 1990年 / 34卷 / 06期
关键词：
analysis of algorithms; Computational complexity; randomness;
D O I：
10.1016/0020-0190(90)90010-U
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We show that the following two conditions are equivalent: (1) the existence of pseudorandom generators; (2) the existence of a pair of efficiently constructible distributions that are computationally indistinguishable but statistically very different. © 1990.
引用
收藏
页码：277 / 281
页数：5
相关论文
共 50 条
  • [1] Computational Indistinguishability Logic
    Barthe, Gilles
    Daubignard, Marion
    Kapron, Bruce
    Lakhnech, Yassine
    PROCEEDINGS OF THE 17TH ACM CONFERENCE ON COMPUTER AND COMMUNICATIONS SECURITY (CCS'10), 2010, : 375 - 386
  • [2] Computational indistinguishability: A sample hierarchy
    Goldreich, O
    Sudan, M
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1999, 59 (02) : 253 - 269
  • [3] On Computational Indistinguishability and Logical Relations
    Dal Lago, Ugo
    Galal, Zeinab
    Giusti, Giulia
    PROGRAMMING LANGUAGES AND SYSTEMS, APLAS 2024, 2025, 15194 : 241 - 263
  • [4] Computational indistinguishability and boson sampling*
    Nikolopoulos, Georgios M.
    PHYSICA SCRIPTA, 2023, 98 (01)
  • [5] Automated Proofs for Computational Indistinguishability
    Long Ngo
    Boyd, Colin
    Nieto, Juan Gonzalez
    COMPUTER JOURNAL, 2014, 57 (10): : 1513 - 1536
  • [6] Computational indistinguishability: A sample hierarchy
    Goldreich, O
    Sudan, M
    THIRTEENTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY - PROCEEDINGS, 1998, : 24 - 33
  • [7] The computational SLR: a logic for reasoning about computational indistinguishability
    Zhang, Yu
    MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE, 2010, 20 (05) : 951 - 975
  • [8] The Computational SLR: A Logic for Reasoning about Computational Indistinguishability
    Zhang, Yu
    TYPED LAMBDA CALCULI AND APPLICATIONS, PROCEEDINGS, 2009, 5608 : 401 - 415
  • [9] Termination-Insensitive Computational Indistinguishability (and applications to computational soundness)
    Unruh, Dominique
    2011 IEEE 24TH COMPUTER SECURITY FOUNDATIONS SYMPOSIUM (CSF), 2011, : 251 - 265
  • [10] A Tight Computational Indistinguishability Bound for Product Distributions
    Geier, Nathan
    THEORY OF CRYPTOGRAPHY, TCC 2022, PT II, 2022, 13748 : 333 - 347
12345