Security of the most significant bits of the Shamir message passing scheme (Q2759102)

Let \(p\) be a prime number and \(g\in\mathbb{F}_p\) a primitive root. \textit{D. Boneh} and \textit{R. Venkatesan} [Lect. Notes Comput. Sci. 1109, 129-142 (1996)] have proposed a polynomial time algorithm for recovering a hidden element \(\alpha\in \mathbb{F}_p\) from rather short strings of the most significant bits of the remainder modulo \(p\) of \(\alpha g^x\) for several values of \(x\), selected uniformly at random in the interval \([0,p-2]\). They showed also how to apply this result to the computational security of the most significant bits of private keys of some cryptosystems. NEWLINENEWLINENEWLINEUnfortunately, these results concerning security are not quite correct. In the paper under review this mistake is corrected for the Shamir message passing scheme by presenting an accurate analysis of the bit security of this cryptosystem. A similar correction concerning the Diffie-Hellman key exchange scheme had been previously carried out by the current authors [Proc. Workshop on Cryptography and Computational Number Theory, Singapore 1999, Birkhäuser, Prog. Comput. Sci. Appl. Log. 20, 257-268 (2001; Zbl 0997.94548)]. To this end, the authors extend the results of Boneh-Venkatesan on the distribution of exponential functions modulo \(p\) and on rounding techniques in lattices to situations involving an element \(g\in\mathbb{F}_p\) which is not necessarily a primitive root. To state the main result: Let \(m\in [1,p-1]\) be a message that Alice sends to Bob with the Shamir scheme, and let \(A,B,C\in [1,p-1]\) be the three numbers to be transmitted (recall that \(A=m^a\), with \(a\) selected at random by Alice, \(B=A^b\) with \(b\) selected at random by Bob and \(C=B^u\) with \(u\) the inverse of \(a\) modulo \(p-1\)). Asume that we are given an oracle that for any given values of \(A,B,C\) it outputs the \(\lceil n^{1/2}\rceil+\lceil\log n\rceil\) most significant bits of \(m\); then, there exists a probabilistic polynomial time algorithm which computes the message \(m\) from the values \(A,B,C\), for all except \(O(p^{\frac 12+\varepsilon})\) messages, which uses \(O(n^{1/2}\log n)\) calls of the oracle.