Solving Hidden Number Problem

Solving Hidden Number Problem-PDF Download

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

Share Pdf : Solving Hidden Number Problem

Download and Preview : 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.
handling all functions f over Zp complexity scales with L1 fb 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. concurrent works 10 11 gave a universal SFT algorithm for a restricted class. of functions over Zp compressible or Fourier sparse functions 4. 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. 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. 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. For g a function over Zp and c c0 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. 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 fb we prove S is good using Fourier analysis Second for noise. corrupted functions f 0 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 0 due to their typically huge L1 fb0 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. 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,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. 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. ued functions f g over a domain G is hf gi G x G f x g x Denote. the normalized 2 norm of f by kf k2 hf f i its norm by kf k. max f x x G and its un normalized L1 norm by L1 f x G f x. ThePconvolution of f and g is the function f g G C defined by f g x. G y G f y g x y, Characters and Fourier transform The characters of ZN are the functions. ZN C ZN defined by x e2 i x N The Fourier transform. of a complex valued function f over ZN is the function fb ZN C defined. by fb hf i For any ZN and 0 1 we say that is a, significant Fourier coefficient iff fb kf k2 Denote by Heavy f the set. of all significant Fourier coefficients of f, A few useful properties of the Fourier transform follow. Proposition 1 For any f g ZN C,1 Parseval Identity N x ZN f x fb.
2 Convolution Theorem f g fb gb, 3 Phase Shift For any 0 ZN if g f 0 then gb fb 0 where. subtraction is modulo N, 4 Scaling For any s Z N if g x f sx x then gb fb s 1. where multiplication and inverse are modulo N,Proof Proof is standard see 16 t. def 1 Pt 1, Proposition 2 Let St t y 0 y for some t 0 N 1 Then. 2 1 1 cos N t,1 St t2 1 cos 2,2 Pass Band ZN and 0 1 if abs N then St 1 56 2.
3 Fast decreasing ZN St 23 abs,4 Fourier bounded ZN St 1. Proof Recall that x x for ei N a primitive root of unity of or. 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. inator and using standard trigonometric identities we conclude that St. 1 1 cos N t, t2 1 cos 2 The upper and lower bounds on St are obtained using the Taylor. approximation for the cosine function 1 2 cos 1 2 4 Details. appear in 2 1 t,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. 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. We focus on additive noise corrupting functions f to a function f 0 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 Zp 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. Pp s a Pp s g a mod p a,for an random noise, 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. L1 P and P, P is concentrated if c 0 s t p P M p and 1 p are at most log p c.
Let P denote a lower bound on the maximum weight P. trivial Fourier coefficients 6 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,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,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. 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, We show that Algorithm 1 outputs the hidden number s with probability.
q p p Fix p and denote p p Recall that P,since P is M concentrated and that P p s Pp s. d c by Propo, 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, Thus L 3 s 1 with probability at least 1 1 p 1 by Theorem 4 Implying. 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. Solving Hidden Number Problem with One Bit Oracle and Advice Adi Akavia 1 Institute for Advanced Study Princeton NJ 08540 2 DIMACS Rutgers University Piscataway NJ 08854 Abstract In the Hidden Number Problem HNP the goal is to nd a hidden number s when given p gand access to an oracle that on query areturns the kmost signi cant bits of sgamod p We present an algorithm solving HNP

Related Books