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 ɛ>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≔logN. 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.