Complexity Theoretic Aspects of Some 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 N~(1-ε), 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: = 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 [9], the El Gamal [6], and the RSA-Paillir [2] 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.