2018/06/25 by Gábor Ivanyos, Ivanyos, Gábor, Anupam Prakash +3 · 1 citation
Computer Science · #Cryptography and Data Security #Coding theory and cryptography #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.1806.09660
Let \mathbbFq be the finite field of size q and let ℓ: \mathbbFqn → \mathbbFq be a linear function. We introduce the \em Learning From Subset problem LFS(q,n,d) of learning ℓ, given samples u ∈ \mathbbFqn from a special distribution depending on ℓ: the probability of sampling u is a function of ℓ(u) and is non zero for at most d values of ℓ(u). We provide a randomized algorithm for LFS(q,n,d) with sample complexity (n+d)O(d) and running time polynomial in log q and (n+d)O(d). Our algorithm generalizes and improves upon previous results \citeFriedl, Ivanyos that had provided algorithms for LFS(q,n,q-1) with running time (n+q)O(q). We further present applications of our result to the \em Hidden Multiple Shift problem HMS(q,n,r) in quantum computation where the goal is to determine the hidden shift s given oracle access to r shifted copies of an injective function f: ℤqn → \0, 1\l, that is we can make queries of the form fs(x,h) = f(x-hs) where h can assume r possible values. We reduce HMS(q,n,r) to LFS(q,n, q-r+1) to obtain a polynomial time algorithm for HMS(q,n,r) when q=nO(1) is prime and q-r=O(1). The best known algorithms \citeCD07, Friedl for HMS(q,n,r) with these parameters require exponential time.