New Distinguishers for Negation-Limited Weak Pseudorandom Functions

doi:10.4086/toc.2024.v020a002

	New Distinguishers for Negation-Limited Weak Pseudorandom Functions
	Chen, Zhihuai 1; Guo, Siyao 2; Li, Qian 3; Lin, Chengyu 4; Sun, Xiaoming 1
	2024-07-29
发表期刊	THEORY OF COMPUTING
ISSN	1557-2862
卷号	20 页码:19
摘要	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.
关键词	pseudorandom functions negation-limited circuits Fourier analysis
DOI	10.4086/toc.2024.v020a002
收录类别	SCI
语种	英语
资助项目	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类目	Computer Science, Theory & Methods
WOS记录号	WOS:001279785200001
出版者	UNIV CHICAGO, DEPT COMPUTER SCIENCE
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/39690
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	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.