Threshold Circuit Lower Bounds on Cryptographic Functions

In this work, we are interested in non-trivial upper bounds on the spectral norm of binary matrices $M$ from {-1, 1} $^{N × N}$. It is known that the distributed Boolean function represented by $M$ is hard to compute in various restricted models of computation if the spectral norm is bounded from above by N1-ε, where $\varepsilon > 0 $ denotes a fixed constant. For instance, the size of a two-layer threshold circuit (with polynomially bounded weights for the gates in the hidden layer, but unbounded weights for the output gate) grows exponentially fast with $n := \log N$. We prove sufficient conditions on $M$ that imply small spectral norms (and thus high computational complexity in restricted models). Our general results cover specific cases, where the matrix $M$ represents a bit (the least significant bit or other fixed bits) of fundamental functions. Functions like the discrete multiplication and division, as well as cryptographic functions such as the Diffie-Hellman function (IEEE Trans. Inform. Theory 22(6) (1976) 644-654) and the decryption functions of the Pointcheval (Advances in Cryptology--Proceedings of EUROCRYPT '99, Lecture Notes in Computer Science, Springer, Berlin, 1999, pp. 239-254) and the El Gamal (Advances in Cryptology--CRYPTO '84, 1984, pp. 10-18) cryptosystems can be addressed by our technique. In order to obtain our results, we make a detour on exponential sums and on spectral norms of matrices with complex entries. This method might be considered interesting in its own right.