Public key cryptography and error correcting codes as Ising models

David Saad, Yoshiyuki Kabashima, Tatsuto Murayama

Research output: Chapter in Book/Published conference outputConference publication


We employ the methods of statistical physics to study the performance of Gallager type error-correcting codes. In this approach, the transmitted codeword comprises Boolean sums of the original message bits selected by two randomly-constructed sparse matrices. We show that a broad range of these codes potentially saturate Shannon's bound but are limited due to the decoding dynamics used. Other codes show sub-optimal performance but are not restricted by the decoding dynamics. We show how these codes may also be employed as a practical public-key cryptosystem and are of competitive performance to modern cyptographical methods.
Original languageEnglish
Title of host publicationDisordered and complex systems
EditorsL.P. Hughston P. Sollich, R.F. Streater
Place of PublicationNew york
PublisherAmerican Institute of Physics
Number of pages6
Publication statusPublished - 9 Feb 2001
EventDisordered and Complex Systems -
Duration: 9 Feb 20019 Feb 2001


OtherDisordered and Complex Systems

Bibliographical note

Copyright of American Institute of Physics(AIP).


  • statistical physics
  • error correcting codes
  • sparse matrices
  • Shannon's bound
  • decoding dynamics
  • public-key cryptosystem
  • cyptographical


Dive into the research topics of 'Public key cryptography and error correcting codes as Ising models'. Together they form a unique fingerprint.

Cite this