 • Date:31 Jul 2020
• Views:1
• Pages:17
• Size:272.06 KB

Share Pdf : Solving Hidden Number Problem

Report CopyRight/DMCA Form For : Solving Hidden Number Problem

Transcription:

1 1 New Result Solving HNP with One Bit Oracle Advice. We present an efficient algorithm solving HNP for any k 1 provided the. algorithm is given a short advice depending only on p and g and not on s. Furthermore our algorithm handles, Random noise With high probability our algorithm finds s even if the oracle. answers are flipped independently at random with sufficiently small proba. bility 0 Success probability is taken over the noise. Concentrated predicates Our algorithm finds s even when oracle access is to. the function,Pp s a Pp s g a mod p, where P Pp is any family of concentrated predicates We say that P. is concentrated if,cp log p c and maj Pp 1,c s t Pp P L1 P. Pp the sum of Fourier coefficients and maj Pp, maxb 0 1 Pra Zp Pp a b the frequency of the most common value. Noise is tolerated up to c0 P for any c0 1 and for any P a lower bound. on the maximum squared magnitude of the non trivial Fourier coefficients of. predicates Pp P In particular for P the most significant bit O 1 3. As a corollary of our algorithm for HNP we obtain bit security results for. Diffie Hellman related functions, Our result improves on prior HNP algorithms and the corresponding bit.
security results in achieving, 1 Optimal number of bits k 1 rather than k log log p. 2 Robustness to random noise for substantial e g is O 1 rather than. O 1 log p for P MSB k the k most significant bits and. 3 Handling the wide family of concentrated predicates rather than only MSB k. 1 2 New Tool Universally Finding Significant Fourier Coefficients. As a central tool we present an algorithm that finds the significant Fourier. coefficients of a complex valued functions f over Zp when given oracle access to. f aka SFT algorithm, Indexing Fourier coefficients by elements in Zp we say that is significant. if its Fourier coefficient occupies at least fraction of the energy. Our SFT algorithm given p t and oracle access to a function f over Zp. s t L1 fb t outputs all the significant Fourier coefficients of f Our SFT. algorithm is, For P the k log log p most significant bits prior works 5 tolerate adversarial. noise corrupting up to O 1 log p fraction of the oracle values. Local Its running time is polynomial in log p 1 and t. Universal For any p and t the same oracle queries are asked for all. functions f over Zp s t L1 fb t, Robust With high probability the algorithm succeeds even if the oracle to f. is corrupted by random noise probability is taken over the noise Tolerated. noise parameters are up to c for any constant c 1, This improves over prior works in giving i The first universal algorithm.