Public key cryptography and error correcting codes as Ising models

David Saad, Yoshiyuki Kabashima, Tatsuto Murayama

Research output: Chapter in Book/Report/Conference proceedingConference 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

    Saad, D., Kabashima, Y., & Murayama, T. (2001). Public key cryptography and error correcting codes as Ising models. In L. P. H. P. Sollich, & R. F. Streater (Eds.), Disordered and complex systems (Vol. 553, pp. 89-94). American Institute of Physics. https://doi.org/10.1063/1.1358168