Paper Info
Title
Solving Hidden Number Problem with One Bit Oracle and Advice
Abstract
In the Hidden Number Problem (HNP), the goal is to find a hidden number s, when given p, g and access to an oracle that on query a returns the k most significant bits of $s\cdot g^a \bmod p$.We present an algorithm solving HNP, when given an advice depending only on p and g; the running time and advice length are polynomial in logp. This algorithm improves over prior HNP algorithms in achieving: (1) optimal number of bits k 驴 1 (compared with k 驴 驴(loglogp)); (2) robustness to random noise; and (3) handling a wide family of predicates on top of the most significant bit.As a central tool we present an algorithm that, given oracle access to a function f over ${\mathbb Z}_N$, outputs all the significant Fourier coefficients of f (i.e., those occupying, say, at least 1% of the energy). This algorithm improves over prior works in being: Local. Its running time is polynomial in logN and $L_1(\widehat f)$ (for $L_1(\widehat f)$ the sum of f's Fourier coefficients, in absolute value). Universal. For any N,t, the same oracle queries are asked for all functions f over ${\mathbb Z}_N$ s.t. $L_1(\widehat f)\le t$. Robust. The algorithm succeeds with high probability even if the oracle to f is corrupted by random noise.
Year
DOI
Venue
2009
10.1007/978-3-642-03356-8_20
CRYPTO
Keywords
Field
DocType
bit oracle,significant fourier coefficient,cdot g,oracle query,bmod p,random noise,bits k,oracle access,prior hnp algorithm,hidden number problem,mathbb z,significant bit
Discrete mathematics,Most significant bit,Hidden number problem,Polynomial,Absolute value,Random noise,Oracle,Theoretical computer science,Robustness (computer science),Fourier series,Mathematics
Conference
Volume
ISSN
Citations 
5677
0302-9743
14
PageRank 
References 
Authors
0.81
10
1
Name
Order
Citations
PageRank
Adi Akavia139515.47