Lehrstuhl Mathematik & InformatikComplexity Theoretic Aspects of some Cryptographic Functions
Abstract. In this work, we are interested in non-trivial upper bounds on the spectral norm of binary matrices M from {-1,1}^(N x 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 N^(1-epsilon), where epsilon > 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 a cryptographic decoding function. For instance, the decoding functions of the Pointcheval, the El Gamal, and the RSA-Paillier 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.