The fundamental problems of Coding Theory are provably hard.
Berlekamp, E.R., R.J. McEliece, and H.C.A. Van Tilborg, 1978, "On The Inherent Intractability Of Certain Coding Problems", IEEE Trans. Inform. Theory, IT 24:384-386.
That paper very soon led McEliece to design a cryptographic scheme which is provably hard to break.
McEliece, R.J., "A Public-Key Cryptosystem Based on Algebraic Coding Theory", JPL DSN Progress Report 42-44, pp. 114-116, Jan-Feb 1978.