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

    Abstract

    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
    Pages89-94
    Number of pages6
    Volume553
    DOIs
    Publication statusPublished - 9 Feb 2001
    EventDisordered and Complex Systems -
    Duration: 9 Feb 20019 Feb 2001

    Other

    OtherDisordered and Complex Systems
    Period9/02/019/02/01

    Bibliographical note

    Copyright of American Institute of Physics(AIP).

    Keywords

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

    Fingerprint

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

    Cite this