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