New Distinguishers for Negation-Limited Weak Pseudorandom Functions
文献类型：期刊论文
| 作者 | Chen, Zhihuai1; Guo, Siyao2; Li, Qian3; Lin, Chengyu4; Sun, Xiaoming1 |
| 刊名 | THEORY OF COMPUTING
 |
| 出版日期 | 2024-07-29 |
| 卷号 | 20页码:19 |
| 关键词 | pseudorandom functions negation-limited circuits Fourier analysis |
| ISSN号 | 1557-2862 |
| DOI | 10.4086/toc.2024.v020a002 |
| 英文摘要 | We show how to distinguish circuits with log k negations (a.k.a. kmonotone functions) from uniformly random functions in exp ( O(n1/3k2/3)) 1 / 3 k 2 / 3 )) time using random samples. The previous best distinguisher, due to the learning algorithm by Blais, Canonne, Oliveira, Servedio, and Tan (RANDOM'15), requires exp ( O(n1/2k)) (n 1 / 2 k)) time. Our distinguishers are based on Fourier analysis on slices of the Boolean cube. . We show that some "middle" slices of negation-limited circuits have strong low-degree Fourier concentration and then we apply a variation of the classic Linial, Mansour, and Nisan "Low-Degree algorithm" (JACM'93) on slices. Our techniques also lead to a slightly improved weak learner for negation-limited circuits under the uniform distribution. |
| 资助项目 | National Natural Science Foundation of China[62325210] ; National Natural Science Foundation of China[62002229] ; NYTP[20121201] ; NYU Shanghai Boost Fund ; Hetao Shenzhen-Hong Kong Science and Technology Innovation Cooperation Zone Project[HZQSWS-KCCYB-2024016] ; U.S. Department of Energy (DOE), Office of Science, Office of Advanced Scientific Computing Research[DE-SC-0001234] ; Columbia-IBM center for Blockchain and Data Transparency ; JPMorgan Chase Co. ; LexisNexis Risk Solutions |
| WOS研究方向 | Computer Science |
| 语种 | 英语 |
| WOS记录号 | WOS:001279785200001 |
| 出版者 | UNIV CHICAGO, DEPT COMPUTER SCIENCE |
| 源URL | [http://119.78.100.204/handle/2XEOYT63/39689]  |
| 专题 | 中国科学院计算技术研究所期刊论文_英文 |
| 通讯作者 | Chen, Zhihuai |
| 作者单位 | 1.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China 2.NYU Shanghai, Comp Sci, Shanghai, Peoples R China 3.Shenzhen Res Inst Big Data, Shenzhen Int Ctr Ind & Appl Math, Shenzhen, Guangdong, Peoples R China 4.Espresso Syst, Menlo Pk, CA USA |
| 推荐引用方式 GB/T 7714 | Chen, Zhihuai,Guo, Siyao,Li, Qian,et al. New Distinguishers for Negation-Limited Weak Pseudorandom Functions[J]. THEORY OF COMPUTING,2024,20:19. |
| APA | Chen, Zhihuai,Guo, Siyao,Li, Qian,Lin, Chengyu,&Sun, Xiaoming.(2024).New Distinguishers for Negation-Limited Weak Pseudorandom Functions.THEORY OF COMPUTING,20,19. |
| MLA | Chen, Zhihuai,et al."New Distinguishers for Negation-Limited Weak Pseudorandom Functions".THEORY OF COMPUTING 20(2024):19. |
入库方式： OAI收割
来源：计算技术研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。