Solving Hidden Number Problem

with One Bit Oracle and Advice

Adi Akavia

Institute for Advanced Study, Princeton NJ 08540

DIMACS, Rutgers University, Piscataway, NJ 08854

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 · g a mod p.
We present an algorithm solving HNP, when given an advice depend-
ing only on p and g; the running time and advice length are polynomial in
log p. This algorithm improves over prior HNP algorithms in achieving:
(1) optimal number of bits k ≥ 1 (compared with k ≥ Ω(log log p)); (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 ZN , 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 log N and L1 (f) (for L1 (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 ZN s.t. L1 (f) ≤ t.
– Robust. The algorithm succeeds with high probability even if the
oracle to f is corrupted by random noise.

1 Introduction
The Hidden Number Problem (HNP) was introduced by Boneh and Venkatesan
[4] in the context of proving bit security for the Diffie-Hellman function. In HNP,
for p a prime, and g a generator of Z∗p , the goal is to find a hidden number s ∈ Z∗p ,
when given p, g and oracle access to the function
def
Pp,s,k (a) = M SBp,k (s · g a mod p)
mapping each a ∈ 1, . . . , p to the k most significant bits in the binary represen-
tation of s · g a mod p. √
Boneh-Venkatesan [4] gave an algorithm solving HNP for any k ≥ log p +
log log p in running time polynomial in log p (aka, efficient). Subsequently, Boneh-
Venkatesan [5] gave an efficient algorithm solving HNP for k ≥ Ω(log log p) pro-
vided the algorithm is given a short advice depending only on p and g (and not
on s). Extensions to the case g is not a generator are given in [8,14,15].

This research was supported in part by NSF grant CCF-0514167, by NSF grant
CCF-0832797, and by Israel Science Foundation 700/08. akavia@[Link]

S. Halevi (Ed.): CRYPTO 2009, LNCS 5677, pp. 337–354, 2009.


c International Association for Cryptologic Research 2009
338 A. Akavia

1.1 New Result: Solving HNP with One Bit Oracle and 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
def
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

∃c, δ s.t. ∀Pp ∈ P, L1 (Pp ) ≤ (log p)c and maj(Pp ) ≤ 1 − δ

p ) def     def
for 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 ε = c τ (P) for any c < 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).1
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 = MSBk the k most significant bits); and
3. Handling the wide family of concentrated predicates (rather than only
MSBk ).

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
    2
  2 
f (α) ≥ τ f(β) .
β∈Zp

1
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.
 Solving Hidden Number Problem 339

Our SFT algorithm, given p, τ , t, and oracle access to a function f over Zp

s.t. L1 (f) ≤ t, outputs all the τ -significant Fourier coefficients of f . Our SFT
algorithm is:
– 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 (f) ≤ 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
handling all functions f over Zp (complexity scales with L1 (f)). (ii) The first
analysis proving robustness to noise in the context of universal SFT algorithms.
We remark that these improvements are of independent interest in the context
of sparse Fourier approximation, compressed sensing and sketching (cf. [3]).

Comparison to other SFT algorithms. For functions over the boolean hyper-cube
Zn2 , Kushilevitz-Mansour (KM) gave a local universal SFT algorithm almost two
decades ago [12]. Our algorithm matches the KM benchmark for the case of
functions over Zp for any positive integer p.
For functions over Zp , prior SFT algorithms [6,2,7] are not universal. In con-
current works [10,11] gave a universal SFT algorithm for a restricted class of
functions over Zp : compressible or Fourier sparse functions.2
Noise is out of scope in the analysis of the universal algorithms [12,10,11].
These SFT algorithms [12,6,2,7,10,11] are insufficient for our result solving
HNP. Both universality as well as handling functions that are neither compress-
ible nor Fourier sparse are crucial for our algorithm solving HNP. Robustness to
noise leads to robustness when solving HNP.

1.3 Techniques Overview

In HNP the goal is to find a hidden number s when given p, g and oracle access
to a function Pp,s . We reduce the HNP problem to the problem of the finding
significant Fourier coefficients of a function fs defined by
def
fs (y) = Pp,s (DLp,g (y))

for DLp,g (y), the discrete log of y, i.e., the a ∈ Zp−1 s.t. y = g a mod p. We then
find the significant Fourier coefficients of fs using our universal SFT algorithm.
Universality is crucial. Finding the Fourier coefficients of fs requires access
to fs . To read the values fs (y) on entries y it suffices to query Pp,s on the
discrete-logs DLp,g (y). With universal algorithms, access to all entries y read
2
For g a function over Zp and c, c > 0 absolute constants (indep. of p), g is compress-
ible if for all i, the i-th largest Fourier coefficient of g has magnitude at most O(1/ci );

and g is Fourier sparse if it has at most (log p)c non-zero Fourier coefficients.
340 A. Akavia

by the algorithm can be granted using an advice depending only on p. This is

because universal algorithms read a fixed set of entries y for all the considered
functions over Zp ; implying that the discrete-logs DLp,g (y) for all read entries
y can be provided via an advice depending only on p. In contrast, with non-
universal algorithms, providing access to fs is intractable (assuming computing
discrete logs is intractable).

Achieving universality. We say that a set of queries S ⊆ Zp is good if we can

find the significant Fourier coefficients of all considered function over Zp when
reading only entries in S. We present a combinatorial condition on sets S, and
prove that any set S satisfying this condition is good. Furthermore, we show
that sets S satisfying the condition exists, and can be efficiently construction
by a randomized algorithm. We remark that explicit constructions of such good
sets are given in subsequent works [3].
The combinatorial condition is that S = ∪log p
=0 (A − B ) for A a small biased

set and B ’s that are “small biased on [0..2 ]”; where we say that B has small
bias on I if Fourier coefficients of (the characteristic function of) B approximate
the Fourier coefficients of (the characteristic function) of I.
We prove that such sets S are good in two parts. First, for functions with
bounded L1 (f), we prove S is good using Fourier analysis. Second, for noise
corrupted functions f  = f + η, we prove S is good by showing the algorithm
behaves similarly on the noisy and non-noisy functions. The latter is needed, as
√
the Fourier approach fails for noisy f  due to their typically huge L1 (f ) ≈ p.

Comparison to prior works. Prior algorithms solving HNP follow a lattice based
approach dating back to [4], in which HNP is reduced to the problem of finding
closest lattice vectors (CVP), and the latter is solved using LLL algorithm [13].
In comparison, we take a Fourier approach inspired by [2].
We compare the set of queries used in the different SFT algorithms.
In the universal SFT algorithm for functions over the boolean hypercube Zn2
[12], the set of queries is constructed using small biased sets in Zn2 , and the proof
is Fourier analysis based.
In the (non-universal) SFT algorithms for functions over Zp [6,2,7], the set
of queries must be freshly chosen for each given input function f . Their anal-
ysis proves success with high probability over the sampled set of queries using
deviation from expectation bounds.
In the universal SFT algorithm for (restricted class of) functions over Zp
[10,11], the set of queries is constructed using “K-majority k-strongly selective
sets”.

1.4 Paper Organization

The rest of this paper is organized as follows. In section 2 we summarize pre-

liminary terminology, notations and facts. In section 3 we present our algorithm
solving HNP with advice. In section 4 we present our universal SFT algorithm.
In section 5 we discuss bit security implications.
 Solving Hidden Number Problem 341

2 Preliminaries

In this section we summarize preliminary terminology, notations and facts.

Let N, Z, R and C denote the natural, integer, real and complex numbers
respectively. Let P denote the set of all primes. Let ZN and Z∗N denote the
additive and the multiplicative groups of integers modulo N . We identify the
elements of ZN with integers in 0, . . . , N −1, and denote abs(α) = min {α, N − α}
def
for all α ∈ ZN . Let Br = { z ∈ C | |z| ≤ r} denote the complex ball of radius r.

2.1 Fourier Transform

We give definitions and properties for normed spaces and Fourier transform.

Inner product, norms, convolution. The inner product of complex val-

def 1

ued functions f, g over a domain G is f, g = |G| x∈G f (x)g(x). Denote
def  def
the normalized 2 norm of f by f 2 = f, f , its ∞ norm by f ∞ =
def 
max { |f (x)| | x ∈ G}, and its un-normalized L1 -norm by L1 (f ) = x∈G |f (x)|.
def
Theconvolution of f and g is the function f ∗ g: G → C defined by f ∗ g(x) =
y∈G f (y)g(x − y).
1
|G|

Characters and Fourier transform. The characters of ZN are the functions

def
χα : ZN → C, α ∈ ZN , defined by χα (x) = e2πiαx/N . The Fourier transform
of a complex valued function f over ZN is the function f: ZN → C defined
by f(α) = f, χα . For any α ∈ ZN and τ ∈ [0, 1], we say that α is a τ -
def
 2
 
significant Fourier coefficient iff f(α) ≥ τ f 2 . Denote by Heavy (f ) the set
2 τ
of all τ -significant Fourier coefficients of f .
A few useful properties of the Fourier transform follow.

Proposition 1. For any f, g: ZN → C,

 2    2
1. Parseval Identity: 1
N x∈ZN |f (x)| = α f (α) .

2. Convolution Theorem: (f  ∗ g)(α) = f(α) · g(α).

g (α) = f(α − α0 ) (where
3. Phase Shift: For any α0 ∈ ZN , if g = f · χ−α0 , then 
subtraction is modulo N ).
4. Scaling: For any s ∈ Z∗N , if g(x) = f (sx) ∀x, then  g(α) = f(α · s−1 ) ∀α
(where multiplication and inverse are modulo N ).

Proof. Proof is standard, see [16]. 



def 1 t−1
Proposition 2. Let St (α) = t y=0 χα (y) for some t ∈ [0..N − 1]. Then:
342 A. Akavia

2π
1 1−cos( N αt)
1. |St (α)|2 = t2 1−cos( 2π
N α)
2
2. Pass Band: ∀α ∈ ZN and γ ∈ [0, 1], if abs(α) ≤ γ N 2t , then |St (α)| > 1 − 6 γ
5 2
 2
3. Fast decreasing: ∀α ∈ ZN , |St (α)|2 < 23 abs(α)
N/t

2
4. Fourier bounded: ∀α ∈ ZN , |St (α)| ≤ 1

2π
Proof. Recall that χα (x) = ω αx for ω = ei N a primitive root of unity of or-
−αt
−1
der N . By the formula for geometric sum St (α) = 1t ωω−α −1 . Assigning wβ =
cos(2πβ/N )+i sin(2πβ/N ) for β = αt in the numerator and β = α in the denom-
2
inator and using standard trigonometric identities, we conclude that |St (α)| =
2π
1 1−cos( N αt)
t2 1−cos( 2π α) . The upper and lower bounds on St are obtained using the Taylor
N
θ2 θ2 θ4
approximation for the cosine function: 1 − 2! ≤ cos(θ) ≤ 1 − 2! + 4! . Details
appear in [2,1]. 


2.2 Chernoff/Hoeffding Tail Inequality

The Chernoff/Hoeffding bound on the deviation from expectation of sums of
independent random variables follows.

Proposition 3 (Chernoff/Hoeffding Bound [9]). Let X1 , . . . , Xt be inde-

pendent random variables
 of expectations μ1 , .. . , μy and bounded
 values |Xi | ≤
1 t 1 t  2tη2
M . Then, ∀η > 0, Pr[ t i=1 Xi − t i=1 μi  ≥ η] ≤ 2 · exp − M 2 .

2.3 Noise Models

We say that η is an ε-random noise if its values η(a), a ∈ Zp , are chosen in-
dependently at random from distributions of expected absolute values at most
E[|η(a)|] ≤ ε.
We focus on additive noise η corrupting functions f to a function f  = f + η.
Without loss of generality, f and η accept values in the balls B1 , B2 respectively.

3 Solving Hidden Number Problem with Advice

In this section we present our algorithm solving with advice HNPP,ε .
Fix a family of functions P = Pp : Z∗p → B1 p∈P and a noise parameter ε.

Definition 1 (Hidden Number Problem). In the (extended) Hidden Num-

ber Problem HNPP,ε the goal is to find a hidden number s ∈ Z∗p , when given a
prime p, a generator g of Z∗p , and oracle access to the function

 def
Pp,s (a) = Pp (s · g a mod p) + η(a)

for η an ε-random noise.

 Solving Hidden Number Problem 343

Let , q, t be functions over P. We say that an algorithm ( , q, t)-solves HNPP,ε

if there is an advice Advp,g depending only on p, g of length |Advp,g | ≤ (p),

such that the following holds. Given p, g, Advp,g , and oracle access to Pp,s , the
algorithm outputs s with probability at least q(p); and its running time is at
most t(p). We say that the algorithms solves with advice HNPP,ε if 1/q(p), (p)
and t(p) are polynomial in log p.

3.1 Solving with Advice HNPP,ε : Concentrated P

We present an efficient algorithm solving with advice HNPP,ε for concentrated

P. We remark that concentration defined here differ than concentration in [2].
Let M , τ and α be functions mapping indices p ∈ P into non-negative reals
M (p), τ (p) and a non-zero element α(p) ∈ Zp .
Definition 2 (Concentration). P is (M, τ, α)-concentrated if for all Pp ∈ P,
 2
p ) ≤ M (p)  
L1 (P and Pp (α(p)) ≥ τ (p).

P is concentrated if ∃c > 0 s.t. ∀p ∈ P, M (p) and 1/τ (p) are at most (log p)c .
 
  2
Let τ (P) denote a lower bound on the maximum weight P p (α) of non-trivial
Fourier coefficients α = 0, for all Pp ∈ P.

Theorem 1 (HNPP,ε ). For any concentrated P and ε ≤ c · τ (P) for c < 1,

there exists an algorithm that solves with advice HNPP,ε .

Proof. Let m, τ, α be s.t. P is (M, τ, α)-concentrated. We present an algorithm

that ( , q, t)-solves HNPP,ε for q(p) ≥ Ω(τ (p)) and for (p), t(p) polynomial in
log p, M (p) and 1/τ (p). The advice we use is:
def
Advp,g = {(x, DLp,g (x))}x∈S

for S ⊆ Zp a set of good queries for our universal SFT algorithm on input
parameters p, τ (p) and M (p) (cf. Definition 4). The function fs = fp,g,s over Zp
is defined by
def

fs (x) = Pp,s (DLp,g (x))
for all x ∈ Z∗p and fs (0) = 0. Note that we can access fs (x) for all x ∈ S by

querying Pp,s on a = DLp,g (x) provided in the advice. Our algorithm for HNPP,ε
follows.
Algorithm 1 Solving HNPP,ε .

1. Run the SFT Algorithm 2 on input p,τ (p),M (p), and oracle
access to the restriction of fs to S; denote its output by L.
2. Output ((α(p))−1 · β)−1 for a uniformly random β ∈ L.
344 A. Akavia

We show that Algorithm 1 outputs the hidden number s with probability

 
  2
q(p) ≥ Ω(τ (p)). Fix p and denote α = α(p), τ = τ (p). Recall that P p (α) ≥ τ
p (βs−1 ) ∀β (by Propo-
(since P is (M, τ, α)-concentrated), and that Pp,s (β) = P
sition 1 Item 4 and the definition of Pp,s (x) = Pp (s · x)). Therefore, the αs−1 -
Fourier coefficient of Pp,s is τ -significant, i.e.,
 2
 
Pp,s (α · s−1 ) ≥ τ.

Thus L  αs−1 with probability at least 1 − 1/pΩ(1) (by Theorem 4). Implying
that
β = αs−1
with probability at least (1 − 1/pΩ(1) )/ |L| ≥ Ω(τ ) (since β is a random element
in L, and employing the bound |L| ≤ O(1/τ ) from Theorem 4). When β = αs−1 ,
the output is
(α−1 β)−1 = (α−1 (αs−1 ))−1 = s.
We conclude that the output is s with probability q(p) ≥ Ω(τ ).
Finally, the advice length (p) and the running time t(p) are dominated by the
query complexity and running time of the SFT Algorithm which is polynomial
in log p, 1/τ (p) and M (p) (cf. Theorem 4). 


Remark 1. Tighter bounds on the success probability q(p) are possible at times.
E.g., for the most significant bits P = MSBk for any k ≥ 1, q(p) ≥ 1/2.

3.2 Solving with Advice HNPP,ε : Segment Predicates P

We solve with advice HNPP,ε for segment predicates P.
Let P = Pp : Z∗p → {±1} p∈P . Let σ, a be functions mapping primes p to
positive integers σ(p) and to elements a(p) ∈ Z∗p . Denote by σ(P) an upper
bound on σ(p) for all p.

Definition 3 (Segment Predicates [2]). P is a (σ, a)-segment predicate if

∀p, ∃Pp : Z∗p → {±1} s.t.
– Pp (x) = Pp (x · a(p)) for all x, and
– Pp (x + 1) = Pp (x) for at most σ(p) x’s in Zp .
P is a segment predicate if ∃c > 0 s.t. σ(p) < (log p)c for all p.

We say that P is far from constant if ∃δ > 0 s.t. ∀p, maj(Pp ) ≤ 1 − δ for maj(Pp )
the frequency of Pp ’s most common value.

Theorem 2. Let P be a far from constant segment predicate and ε ≤ c/σ(P)

for c < 1. Then there exists an algorithm that solves with advice HNPP,ε .
 Solving Hidden Number Problem 345

Proof. By Lemma 1, if P is a segment predicate, then P is concentrated; and

furthermore, τ (P) ≥ 1/σ(P). By Theorem 1 this implies that there exists an
algorithm that solves with advice HNPP,ε . 


Lemma 1. If P is a (σ, a)-segment predicate, then P is (M, τ, α)-concentrated

for M (p) = O(σ(p) ln p), τ (p) = Ω(1/σ(p)), and α(p) = a(p).

Proof. For each Pp ∈ P, extend Pp to a function over Zp by setting Pp (0) =

Pp (1). Fix p and drop its indices.
Consider first the case a(p) = 1. To show that L1 (P) ≤ M (p) and P (1) ≥ τ (p),
σ+1
we first show that P(α) = j=1 ( j /p)Sj (α) for all α ∈ Zp . A segment predicate
with a = 1 defines a partition of Zp into σ + 1 segments Ij , so that P is a
constant bj ∈ {±1} on each segment Ij . Thus, we can express P as a sum,

P = σ+1 j=1 Pj , of functions Pj : Zp → {−1, 0, 1} such that Pj (x) is the constant
P (x) for x ∈ Ij and 0 otherwise. By the linearity of the Fourier transform, for all

α ∈ Zp , P (α) = σ+1 
j=1 Pj (α). By definition of the Fourier transform, Pj (α) =

1 
b χ (x). Thus for cj the starting point of Ij and j = |Ij | its length,
p x∈I j j α    j −1
   j 
Pj (α) = |χα (cj )|  p1 x=0 χα (x) = ( j /p)Sj (α) for Sj (α) = 1j x=0 χα (x)
 
   σ+1
as defined in Proposition 2. We conclude that P (α) = j=1 ( j /p)Sj (α).
  
We show that L1 (P ) ≤ O(σ ln p). By Proposition 2, Sj (α) ≤ O abs(α)
p/j
   
 
for all j , implying that P (α) ≤ σ+1
(j /p)(p/j )
j=1 O abs(α) = O (σ/abs(α)) . Thus,
    
 
L1 (P ) = α P (α) ≤ O σ · α abs(α) 1
= O(σ ln p).
 
 
We show that P (1) ≥ Ω(1/σ). Let j ∗ be the length of the second longest
segment in I1 , . . . , Iσ+1 . Clearly j ∗ ≤ p/2. Moreover, j ∗ ≥ Ω(p/σ) because for
far from constant P, the longest segment is of length at most (1 − c)p for c > 0,
implying that the second longest is of length at least the average length cp/σ
2
over the remaining σ segments. By Proposition 2, |S (1)| ≥ Ω(1) for all ≤ p/2.
 2
 
Thus, Pj ∗ (α) ≥ ( j ∗ /p) · Ω(1) = Ω(1/σ). We conclude that for α(p) = 1 there
 2
 
is a function τ (p) ≥ Ω(1/σ(p)) such that P(α(p)) ≥ τ (p) for all p ∈ P.
Consider next the case of a(p) = 1. By definition of segment predicates, there
exists P  s.t. P (x) = P  (xa) for all x ∈ Z∗p . Extend P  to Zp . By Proposition 1,
for all α ∈ Zp P (α) = P  (α · a−1 ). Implying that L1 (P ) = L1 (P  ) ≤ O(σ ln p)
(because αa −1
= Zp for any a co-prime to p), and P (a) = P   (a · a−1 ) =
α∈Zp
 (1) ≥ Ω(1/σ).
P
We conclude that any family P of (σ, a)-segment predicates is (M, τ, α)-
concentrated for M (p) ≤ O(σ(p) ln p), τ (p) ≥ Ω(1/σ(p)) and α(p) = a(p). 


3.3 Solving with Advice HNPP,ε : The Single Most Significant Bit
We solve with advice HNPP,ε for P = MSB the single most significant bit.
346 A. Akavia

Let MSB = M SBp : Z∗p → {±1} p∈P the family of predicates giving the
single most significant bit M SBp (x) of x (in a ±1 binary representation).

Theorem 3. For any ε = O(1) sufficiently small, there exists an algorithm that
solves with advice HNPMSB,ε .

Proof. For the most significant bit M SBp , M SBp (x + 1) = M SBp (x) only for
one x ∈ Z∗p . Namely, MSB is a family of (σ, a)-segment predicates with σ(p) = 1,
a(p) = 1 for all p. By Theorem 2, this implies that for any ε = O(1) sufficiently
small, there exists an algorithm that solves with advice HNPP,ε . 


4 Universally Finding Significant Fourier Coefficients

In this section we present our universal SFT algorithm.

In the following We present the combinatorial condition on good queries sets
S; show such sets exists; and prove that our SFT algorithm succeeds even when
given oracle access only to the restriction of the input function f to the entries
in S.
We define good queries. Recall that A ⊆ ZN is γ-biased if |Ex∈A [χ(x)]| < γ for
all non-trivial characters χ of ZN . For B, I ⊆ ZN , we say that B is (γ, I)-biased
if |Ex∈B [χ(x)] − Ex∈I [χ(x)]| ≤ γ for all characters χ is ZN . Denote by A − B
the set of differences {a − b}a∈A,b∈B .

Definition 4 (Good Queries). Let S = {SN,τ,t }N,τ,t be a family of sets

SN,τ,t ⊆ ZN . We say that S is good if for all N , τ , t and for γ = O(τ /(t2 log N ))
(log N )
sufficiently small, SN,τ,t = =1 (A − B ) s.t.

– A is γ-biased in ZN , of size |A| = Θ( γ12 log N ).

– ∀ , B is (γ, [0..2 ])-biased in ZN , of size polynomial in log N and 1/γ,

We remark that the meaning of “sufficiently small γ” depends on the considered

noise parameter ε, specifically, on the ratio ε : τ . To simplify parameters, we fix
this ratio to be, say, ε < 0.9τ .
We show that good queries S exist. Moreover, there is a randomized algorithm
that constructs good sets SN,τ,t with high probability.
Proposition 4 (Good Queries Exist). There is a randomized algorithm that
given N, τ and t, outputs S = SN,τ,t such that S is good with probability at least
1 − 1/N Ω(1) ; and its running time is O(|S|).
(log N )
Proof. The algorithm outputs S = ∪=1 (A − B ) for independent uniformly
random sets A ⊆ ZN and B ⊆ [0..2 ], of sizes |A| = O( γ12 log N ) and |B | =
O( γ12 · log N · log log N ), = 1, . . . , (log N ).
Using Chernoff and Union bounds it is straightforward to show that S is good
with probability at least 1 − 1/N Ω(1) ; details omitted. 

 Solving Hidden Number Problem 347

We show that our SFT algorithm succeeds when given oracle access to the re-
striction of the input function f (or its corruption by noise f  = f + η) to good
 def
queries S = SN,τ,t . Denote this restriction by f|S = {(x, f  (x))}x∈S .
Let S = {SN,τ,t } be any family of good queries. For any integer N > 0, reals
τ, t > 0, a function f : ZN → B1 s.t. L1 (f) ≤ t, and an ε-random noise η for
ε < 0.9τ the following holds.

Theorem 4 (SFT). Our SFT algorithm, when given N , τ , t and f|S N,τ,t
for

f = f + η, outputs a list L ⊇ Heavyτ (f ) of size |L| ≤ O(1/τ ), with probability
at least 1 − 1/N Ω(1) ; and its running time is polynomial in log N , 1/τ and t.

The probability is taken over the random noise η. In particular, when there is
no noise, the success probability is 1.

Remark 2. Our SFT algorithm also handles: (i) Small amount of adversarial
noise, that is, noise corrupting ε-fraction of the values of f|SN,τ,t for sufficiently
small ε = O(τ / log N ). (ii) Input functions f accepting arbitrary complex values
(and their corruption by noise f  ).
To prove Theorem 4, we first present the details of our SFT algorithm
(Sect. 4.1), and then present its analysis (Sect. 4.2).

4.1 The SFT Algorithm

We give the details of our SFT algorithm. At a high level, the SFT algorithm is
a binary search algorithm that repeatedly:

1. Partitions the set of potentially significant Fourier coefficients into two

halves.
2. Tests each half to decide if it (potentially) contains a significant Fourier
coefficient. This is done by estimating whether the sum of squared Fourier
coefficients in each half exceeds the significance threshold τ .
3. Continues recursively on any half found to (potentially) contain signifi-
cant Fourier coefficients.

At each step of this search, the set of potentially significant Fourier coef-
ficients is maintained as a collection J of intervals: At the first step of the
search, all Fourier coefficients are potentially significant, so J contains the sin-
gle interval J = [1..N ]. At each following search step, every interval J ∈ J
is partitioned into two sub-intervals J1 and J2 containing the lower and upper
halves of J respectively, and the set J is updated to hold only the sub-intervals
that pass the test, i.e., those that (potentially) contain a significant Fourier co-
efficient. After log N steps this search terminates with a collection J of length
one intervals revealing the frequencies of the significant Fourier coefficients. For
all frequencies α of the significant Fourier coefficients,
 we then compute as an
O(τ )-approximation for f(α) the value valα = |A| 1
x∈A−y f (x)χα (x) for some
(log N )
arbitrary y ∈ ∪=1 B .
348 A. Akavia

The heart of the algorithm is the test deciding which intervals potentially
contain a significant Fourier coefficient (aka, distinguishing procedure). The dis-
tinguishing procedure we present,
  given an interval J, answers YES if its Fourier
   2
weight weight(J) = α∈Jf (α) exceed the significance threshold τ , and an-
swers NO if the Fourier weight of a slightly larger interval J  ⊇ J is less than
τ /2. This is achieved by estimating the 2 norm (i.e., sum of squared Fourier
coefficients) of a filtered version of the input function f , when using a filter h
that passes Fourier coefficients in J and decays fast outside of J.
The filters h that we use for depth of the search are the (normalized) periodic
square function of support size 2 or Fourier domain translations of this function:
⎧N
⎨ 2 · χ−c (y) y ∈ [0..2 ]
def
h,c (y) = (1)
⎩
0 otherwise

The filter h = h,c passes all frequencies that lie within the length N/2 interval
J centered around c, and decays fast outside of J. The filtered version of f is
f ∗ h, and we estimate its 2 norm f ∗ h 22 by the estimator:
⎛ ⎞2
1  1 
def
est,c (f ) = ⎝ χ−c (y)f (x − y)⎠ (2)
|A| |B |
x∈A y∈B

for A, B1 , . . . , B ⊆ ZN as specified in the definition of good queries 4.

A pseudo-code of the algorithm follows. We denote intervals by the pair {a, b}
of their endpoints. To simplify notations, we assume: (a + b )/2 is an integer
(otherwise, appropriate flooring/ceiling is taken); f 2 = 1 (otherwise  we nor-
1 2
malize f it by dividing each read value by an energy estimator |A| x∈A f (x) );

0 ∈  B (otherwise we change variable in x∈A χα (x)f (x) to z = x − y for a
random y ∈  B ).

Algorithm 2 SFT.
Input: N ∈ N, τ ∈ (0, 1], {(x, y, f (x − y))}x∈A,y∈B ∀ = 1, . . . , (log N )
1. Initialize: J ← {{0, N }}
2. While ∃{a, b} ∈ J s.t. b − a > 0 do:
(a) Delete {a, b} from J
(b) For each pair {a , b } in Low = a, a+b , High = a+b
2 + 1, b do:
  
2
2
i. Compute est,c ← |A| x∈A |B | y∈B χ−c (y)f (x − y)
1 1
for =
log(N/(b − a )), c = ((a + b )/2)
ii. If est,c ≥ τ /2, insert {a , b } to J
3. Sieving: For each {α, α} ∈ J ,
  2
 1 
(a) Compute val(α) ←  |A| x∈A χα (x)f (x)
(b) If val(α) < τ /2, delete {α, α} from J
4. Output L = { α | {α, α} ∈ J }
 Solving Hidden Number Problem 349

4.2 Proof of Theorem 4

In this section we bring the proof of Theorem 4.

Proof of Theorem 4. Let h,c and est,c (f ) be as defined in (1)-(2). Fix a suffi-
ciently small absolute constant c > 0. Consider condition (*) on f  = f + η:
 
(∗) est,c (f  ) − f ∗ h,c 22  < cτ for all = 1, . . . , (log N ), c ∈ ZN
By Lemma 2, when (*) holds, the SFT algorithm outputs L ⊇ Heavyτ (f ) in
running time polynomial in log N , 1/τ and t. By Lemma 3, when S is a good,
(*) holds with probability at least 1 − 1/N Ω(1) over the noise η. Thus, the SFT
algorithm outputs L ⊇ Heavyτ (f ) in time polynomial in log N , 1/τ and t.
 Proving |L| ≤ O(1/τ ) is similar.
 Consider condition (∗ ) saying that ∀α ∈ ZN ,
 1  
 |A| x∈A f  (x)χα (x) − f(α) < cτ . We show that first, if (*’) holds, then the
 2
 
sieving step leaves in J only {α, α} s.t. f(α) ≥ Ω(τ ); implying |L| ≤ O(1/τ )
by Parseval Identity. Second, when S is good, (*’) holds with high probability
over the noise η. We conclude that |L| ≤ O(1/τ ) with high probability over the
noise η. Details omitted from this extended abstract. 

We show that the SFT algorithm succeed on functions f  satisfying (*).
Lemma 2. Let f  = f + η and all other parameters be as in Theorem 4. If
conditions (*) holds for f  , then the SFT algorithm returns a list L ⊇ Heavyτ (f )
in running time polynomial in log N , 1/τ and t.
Proof. Denote J = [a , b ], = log(N/(b − a )) and c = (a + b )/2.
Correctness. Consider a significant Fourier coefficient α ∈ ZN . To show that
α ∈ L, it suffices to show that est,c (f  ) > τ /2 whenever J  α. The latter is true
because when J contains a τ -significant Fourier coefficient, then by Proposition
  
  2
21 Item (1), f ∗ h,c 2 ≥ Ω(
2 α∈Jf (α) ) ≥ Ω(τ ), which by (*) implies that
est,c (f  ) ≥ Ω(τ ) ≥ τ /2 (the latter holds by setting appropriate constants).
Efficiency. Fix , to bound the running time it suffices to show that
“est,c (f  ) ≥ τ /2” does not happen for too many disjoint intervals J of length
N/2 . If est,c (f  ) ≥ τ /2, then by condition (*), h,c ∗ f 22 ≥ Ω(τ ). By Claim 21
Item 2, the latter implies that for a slightly larger interval J  ⊇ J, |J  | / |J| ≤
O(1/γ), its Fourier weight (that is, sum of squared Fourier coefficients with fre-
quencies in J  ) is greater than Ω(τ ). This implies that est,c cannot be greater
than τ /2 too often, because there are at most O(1/τ ) disjoint intervals whose
|J  |
Fourier weight exceeds Ω(τ ) (by Parseval Identity), and thus at most O( τ1 · |J| )
(possibly, overlapping) intervals J  whose Fourier weight exceeds Ω(τ ). 

Claim 21. For integers , c > 0 and real γ > 0, let J,c = α | abs(α − c) ≤ 2N
  

an interval, and J,c,γ = α | abs(α − c) ≤ 3γ 2
· 2N its extension. Then: (1)
  2   2
   
h,c ∗ f 22 ≥ 16 α∈J,c f(α) , and (2) h,c ∗ f 22 ≤ α∈J  f(α) + γ.
,c,γ
350 A. Akavia

Proof. Denote h = h,c . By Parseval Identity and the convolution theorem,

  2 
 
2

h ∗ f 22 = α  h(α) f(α) . By definition of h, 
h(α) = S2 (α − c) for St (α) =
1
 t−1
t y=0 χα (y) as defined in Proposition 2. The proof follows from the properties
guaranteed in Proposition 2; details omitted from this extended abstract. 


We show that when using a good set of queries S condition (*) holds (with high
probability over the random noise η).
Lemma 3. Let f  = f + η and all other parameters be as in Theorem 4. Con-
dition (*) holds for f  with probability at least 1 − 1/N Ω(1) over the noise η.

Proof. Let S = log N

=1 (A − B ) for S = SN,t,τ from the good queries S of
Theorem 4. Recall that A is a γ-biased set and the B ’s are (γ, [0..2 ])-biased.
 Fix  ∈ [(log N 2)]  and c ∈ ZN . Denote B = B , h = h,c . Observe that
est,c (f ) − h ∗ f 2  ≤ (i) + (ii) + (iii) for:
 
– (i) := est,c (f ) − h ∗ f 22   
 1    
– (ii) := 2 |A| x∈A |B|
1
χ
y∈B −c (y)f (x − y) 1
|B| χ
y∈B −c (y)η(x − y) 
– (iii) := |est,c (η)|

We bound each of these terms. By Claim 22, (i) ≤ O(γL1 (f)2 log N ). By
Claims 23-24, with probability at least 1 − 3 exp (−Ω(|A| τ 2 )), (ii) + (iii) ≤
(2 + O(γL1 (f)2 log N ))(2ε2 + ε + O(τ )). Thus, for γ = O(τ /(t2 log N )) and
ε = O(τ ), with probability at least 1 − 3 exp (−Ω(|A| τ 2 )),
 
est,c (f  ) − h ∗ f 2
2 ≤ O(τ ) for all f s.t. L1 (f) ≤ t.

By union bound, this holds for all = 1, . . . , (log N ) with probability at least
1−3 exp (−Ω(|A| τ 2 )) log N = 1−1/N Ω(1) since |A| ≥ Ω((ln N )/τ 2 ) by definition
of good sets. 


Claim 22. (i) ≤ O(γL1 (f)2 log N ).

Proof. Denote I = [0..2 ]. Define gx (y) = χ−c (y)f (x − y) for y ∈ I and gx (y) = 0
otherwise. Then by the definition of est,c (f ) and h ∗ f 22 ,
  2  2 

   
(i) =  E E gx (y) − E E gx (y)  ≤ (i ) + (ii ) for:
x∈A y∈B x∈ZN y∈I 

 
 2
– (i ) := Ex∈A (Ey∈B gx (y)) − Ex∈A (Ey∈I gx (y)) 
2
 
 
– (ii ) := Ex∈A (Ey∈I gx (y))2 − Ex∈ZN (Ey∈I gx (y))2 

We show below that (i ) ≤ γ · L1 (f)2 · O(log N ) and (ii ) ≤ γ · L1 (f)2 . Combining
these bounds we get that (i) ≤ O(γL1 (f)2 log N ).
 Solving Hidden Number Problem 351

Bounding term (i’). We first get rid of the expectation over x ∈ A by up-
per bounding it with its value on a maximizing x0 ∈ A. We then switch to
the Fourier representation of gx0 and rely on B being (γ, I)-biased to bound the
difference between the expectations over y ∈ B and y ∈ I. Finally, we bound the
emerging quantity L1 (gx0 ) (using Proposition 2 and algebraic manipulations).
Details omitted from this extended abstract.

Bounding term (ii’). We first observe that the inner expectations are over the
same range I and variable. That is, (ii ) = |Ex∈A ḡ(x) − Ex∈ZN ḡ(x)| for ḡ(x) =
2
(Ey∈I gx (y)) . We then switch to the Fourier representation of ḡ and rely on A
being γ-biased to bound the difference between the expectations over x ∈ A and
x ∈ ZN .
 
   

(ii ) ≤ ḡ (α)  E χα (x) − E χα (x) ≤ γL1 (
  ḡ )
x∈A x∈ZN
α∈ZN

Finally we bound the emerging quantity L1 ( ḡ ). Observe that ḡ = (h ∗ f )2 (since

h ∗ f = Ey∈ZN |I| χ−c (y)f (x − y) = Ey∈I χ−c (y)f (x − y)). Therefore, L1 (
N
ḡ ) ≤

L1 (h ∗ f ) where we use the fact that for any function
2 
s, L1 (s ) ≤ L1 (
2 s)2 .

     
Observe further that L1 (h ∗ f )2 ≤ L1 (f)2 because h ∗ f (α) = h(α) · f(α) ≤
   
   
f (α), where the last inequality follows since  h(α) ≤ 1 for all α. Combining
the above bounds we conclude that (ii ) ≤ γL1 (f)2 . 


Claim 23. (ii) ≤ (1 + O(γL1 (f)2 log N ))(2ε2 + ε + O(τ )) with probability at
least 1 − exp (−Ω(|A| τ 2 )).

Proof. By Cauchy-Schwartz inequality, (ii)2 ≤ 4 · (a) · (b) for

   2
– (a) := 1
|A| x∈A
1
|B | y∈B χ−c (y)f (x − y)
   2
– (b) := 1
|A| x∈A
1
|B | y∈B χ−c η(x − y) .

To bound (b), observe that (b) = est,c (η) ≤ (iii). Therefore, by Claim 24,
(b) ≤ 2ε2 + ε + O(τ ) with probability at least 1 − 2 exp(−Ω(|A| τ 2 )).
To bound (a), observe that (a) = est,c (f ), implying by Claim 22 that
 
(a) − h ∗ f 2  ≤ O(γL1 (f)2 log N ). Next observe that h ∗ f 2 ≤ 1 (since
  2    
2 2
      
h ∗ f 2 = α h(α)f (α) where h(α) , f (α) ≤ 1 for all α). We conclude
2 3

therefore that |(a)| ≤ 1 + O(γL1 (f)2 log N ).

 
 
3
Here, f(α) ≤ 1 because f accepts values in B1 . The bound holds also for unbounded
  2

f , provided f is normalized to have α f(α) ≤ 1.
352 A. Akavia

Combining both bounds we conclude that with probability at least

1 − exp (−Ω(|A| τ 2 )), (ii) ≤ (1 + O(γL1 (f)2 log N ))(2ε2 + ε + O(τ )). 


Claim 24. (iii) ≤ 2ε2 + ε + O(τ ) with probability at least 1 − 2 exp(−Ω(|A| τ 2 )).

Proof. To bound (iii) = |est,c (η)| we rely on the randomness of

η. By definition of est,c (η) and the triangle inequality, |est,c (η)| ≤
   2
y∈B |η(x − y)| . Opening the parenthesis, |est,c (η)| ≤ (a)+(b)
1 1
|A| x∈A |B|
for:
1  1 
– (a) := |A| x∈A |B|2 y =y ∈B |η(x − y1 )| |η(x − y2 )|
  1 2 2
– (b) := |A| x∈A |B|2 y∈B |η(x − y)|
1 1

Expressions (a) and (b) are averages over the indep. random variables: vx,y1 ,y2 =
|B|
|η(x − y1 )| |η(x − y2 )|· |B|−1 and vx,y = |η(x − y)|2 · |B|
1
respectively (the factors
involving |B| are for proper normalization). We use Chernoff/Hoeffding bound
to upper bound expressions (a) and (b) separately, and then apply union bound
to upper bound their sum. Details omitted from this extended abstract. 


5 Bit Security Implications

We obtain bit security results as a corollary of our algorithm solving HNPP,ε .
We set some terminology. Let G = {gp } be a family of generators gp of Z∗p .
Let F = {fp } be a family of functions fp outputting secrets s when given public
data P Dp,g,s depending on the modulus p, a generator g and the secret s. Think
of F as the underlying hard to compute function. Let P = {Pp } be a family of
predicates over Z∗p . Denote by M B a “magic box” that, given p, g and P Dp,g,s ,
def
outputs M B(p, g, P Dp,g,s ) = Pp (s). We say that:
– P is as hard as F if there is an algorithm A that, given P Dp,gp ,s , oracle
access to M B, and an advice depending only on p and gp , outputs the secret
s with probability at least 1/poly(log p), while the running time and advice
length are polynomial in log p.
– F is G-accessible if there is an access algorithm that, given public data P Dp,g,s
for a secret s, and an element a ∈ Zp−1 , outputs public data P Dp,g,s·ga for
the secret s · g a mod p.

Theorem 5. For any G-accessible F and concentrated P, P is as hard as F .

Proof. Fix p and denote g = gp . Let Advp,g be an advice depending only on p

def
and g as used in Theorem 1 for solving HNPP,ε in Algorithm 1. Let Pp,s (a) =
Pp (s · g a ). Observe that given P Dp,g,s and oracle access to M B we can simulate
oracle access to Pp,s : For each query a, we compute P Dp,g,s·ga using the access
algorithm of F , and output val = M B(p, P Dp,g,s·ga ). By definition of M B,
val = Pp (s · g a ).
 Solving Hidden Number Problem 353

The algorithm A runs Algorithm 1 while simulating oracle access to Pp,s . By

Theorem 1, the output is s with probability at least 1/poly(log p). We conclude
that P is as hard as F . 


Let OK and EL denote the underlying hard families of functions in the Okamoto
conference key sharing scheme and in the (modified) ElGamal public key en-
cryption scheme as defined in [5]. The analysis of [5] shows that OK (EL ) is
G-accessible. We conclude therefore that for any concentrated predicate P, P is
as hard as computing OK (EL ). In particular, this holds for P = M SB1 .

Acknowledgments

The author is grateful to Shafi Goldwasser, Igor Shparlinski, Vinod Vaikun-

tanathan, and Avi Wigderson for helpful discussions.

References
1. Akavia, A.: Learning Noisy Characters, Multiplication Codes and Cryptographic
Hardcore Predicates. Ph.D dissertation, defended August 2007, MIT, EECS
(February 2008)
2. Akavia, A., Goldwasser, S., Safra, S.: Proving Hard-Core Predicates using List
Decoding. In: Proc. of 44th IEEE Annual Symposium on Foundations of Computer
Science (FOCS 2003), pp. 146–157. IEEE Computer Society, Los Alamitos (2003)
3. Akavia, A.: Finding significant fourier coefficients deterministically and locally.
ECCC Report TR08-102 (2008)
4. Boneh, D., Venkatesan, R.: Hardness of computing the most significant bits of
secret keys in diffie-hellman and related schemes. In: Koblitz, N. (ed.) CRYPTO
1996. LNCS, vol. 1109, pp. 129–142. Springer, Heidelberg (1996)
5. Boneh, D., Venkatesan, R.: Rounding in lattices and its cryptographic applica-
tions. In: SODA: ACM-SIAM Symposium on Discrete Algorithms (A Conference
on Theoretical and Experimental Analysis of Discrete Algorithms) (1997)
6. Gilbert, A.C., Guha, S., Indyk, P., Muthukrishnan, S., Strauss, M.: Near-optimal
sparse fourier representations via sampling. In: Proc. of 34 ACM Annual Sympo-
sium on Theory of Computing (STOC 2002), pp. 152–161. ACM Press, New York
(2002)
7. Gilbert, A.C., Muthukrishnan, S., Strauss, M.: Improved time bounds for near-
optimal sparse fourier representation via sampling. In: Proc. SPIE Wavelets XI
(2005)
8. González-Vasco, M.I., Shparlinski, I.: On the security of diffie-hellman bits. In:
Proc. Workshop on Cryptography and Computational Number Theory, Singapore,
pp. 257–268. Birkhäuser, Basel (2001)
9. Hoeffding, W.: Probability inequalities for sums of bounded random variables. J.
Amer. Stat. Assoc. 58, 13–30 (1963)
10. Iwen, M.A.: A deterministic sub-linear time sparse fourier algorithm via non-
adaptive compressed sensing methods. CoRR, abs/0708.1211 (2007)
11. Iwen, M.A.: A deterministic sub-linear time sparse fourier algorithm via non-
adaptive compressed sensing methods. In: SODA, pp. 20–29 (2008)
354 A. Akavia

12. Kushilevitz, E., Mansour, Y.: Learning decision trees using the Fourier spectrum.
SICOMP 22(6), 1331–1348 (1993)
13. Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational co-
efficients. Mathematische Annalen 261(4), 515–534 (1982)
14. Shparlinski, I., Winterhof, A.: A nonuniform algorithm for the hidden number
problem in subgroups. In: Bao, F., Deng, R.H., Zhou, J. (eds.) PKC 2004. LNCS,
vol. 2947, pp. 416–424. Springer, Heidelberg (2004)
15. Shparlinski, I., Winterhof, A.: A hidden number problem in small subgroups. Math.
Comp. 74, 2073–2080 (2005)
16. Terras, A.: Fourier Analysis on Finite Groups and Applications. Cambridge U.
Press, Cambridge (1999)