Paper 2015/111

The Multivariate Hidden Number Problem

Steven D. Galbraith and Barak Shani


This work extends the line of research on the hidden number problem. Motivated by studying bit security in finite fields, we define the multivariate hidden number problem. Here, the secret and the multiplier are vectors, and partial information about their dot product is given. Using tools from discrete Fourier analysis introduced by Akavia, Goldwasser and Safra, we show that if one can find the significant Fourier coefficients of some function, then one can solve the multivariate hidden number problem for that function. This allows us to generalise the work of Akavia on the hidden number problem with (non-adaptive) chosen multipliers to all finite fields. We give two further applications of our results, both of which generalise previous works to all (finite) extension fields. The first considers the general (random samples) hidden number problem in F_{p^m} and assumes an advice is given to the algorithm. The second considers a model that allows changing representations, where we show hardness of individual bits for elliptic curve and pairing based functions for elliptic curves over extension fields, as well as hardness of any bit of any component of the Diffie-Hellman secret in F_{p^m} (m>1).

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.This paper is to appear at ICITS 2015
hidden number problembit securityhardcore bits
Contact author(s)
barak shani @ auckland ac nz
2015-04-07: revised
2015-02-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Steven D.  Galbraith and Barak Shani},
      title = {The Multivariate Hidden Number Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2015/111},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.