Theoretical results suggest that learning good parameters for a small neural network can be as computationally hard as breaking RSA.

Judge as of 2014-05-15. The claim is hedged ('suggest'). True: peer-reviewed theoretical results exist by 2014 showing that learning or training small neural networks (or intersection-of-halfspaces or threshold-circuit classes that such networks represent) is computationally hard under cryptographic assumptions tied to RSA or factoring (for example, Kearns–Valiant 1994, or Klivans–Sherstov), or NP-hardness of training small networks together with crypto-based hardness. Mostly true: such results exist, but they rest on related cryptographic assumptions (for example, lattice problems or general one-way functions) rather than RSA specifically, or they apply to network classes somewhat different from 'smallish' networks. Mixed: the hardness results that exist are mainly NP-hardness of exact training, with only a loose link to cryptography. Mostly false: the cited results concern quite different settings and do not reasonably support the comparison. False: no theoretical results of this kind existed.

Set before the research began.

1. E1 Cryptography and machine learning - People | MIT CSAIL MIT CSAIL (Ronald L. Rivest)

   “Valiant 22, 21 turned to cryptographic assumptions (namely, the difficulty of inverting RSA, the difficulty of recognizing quadratic residues modulo a Blum integer, and the difficulty of factoring Blum integers).”

2. E2 Cryptography and machine learning - People | MIT CSAIL MIT CSAIL (Ronald L. Rivest)

   “Angluin and Kharitonov 5 have done so, showing that (modulo the usual cryptographic assumptions regarding RSA, quadratic residues, or factoring Blum integers), that there is no polynomial-time prediction algorithm, even if membership queries are allowed, for the following classes of functions:”

The evidence shows RSA-related cryptographic hardness results for learning or predicting certain function classes [E1][E2]. It does not show that those classes are neural networks or close to them, which the criteria require for a true or mostly true verdict.