Cryptology ePrint Archive: Report 2015/111

The Multivariate Hidden Number Problem

Steven D. Galbraith and Barak Shani

Abstract: 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).

Category / Keywords: public-key cryptography / hidden number problem, bit security, hardcore bits

Original Publication (with minor differences): This paper is to appear at ICITS 2015

Date: received 13 Feb 2015, last revised 6 Apr 2015

Contact author: barak shani at auckland ac nz

Available format(s): PDF | BibTeX Citation

Version: 20150407:042656 (All versions of this report)

Short URL: ia.cr/2015/111

Discussion forum: Show discussion | Start new discussion