Statistical physics of error-correcting codes and public key cryptography
David Saad
U.M.I.S.T.
The relation between Ising spin systems and public-key cryptography
is investigated using methods of statistical physics. The insight
gained from the analysis is used for devising a matrix-based
cryptosystem whereby the ciphertext comprises products of the
original message bits; these are selected by employing two
predetermined randomly-constructed sparse matrices. The ciphertext
is decrypted using methods of belief-propagation. The analyzed
properties of the suggested cryptosystem show robustness against
various attacks and competitive performance to modern cyptographical
methods.
This work has been done in collaboration with Yoshiyuki Kabashima
(TITECH) and Tatsuto Murayama (TITECH).
Most of our publications in this area are accessible from our
website: http://www.ncrg.aston.ac.uk, in
particular the manuscripts NCRG/2001/008 and NCRG/2000/002.