Public key cryptography and error correcting codes as Ising models

David Saad; Yoshiyuki Kabashima; Tatsuto Murayama

doi:10.1063/1.1358168

Public key cryptography and error correcting codes as Ising models

David Saad, Yoshiyuki Kabashima, Tatsuto Murayama

Research output: Chapter in Book/Published conference output › Conference 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 language	English
Title of host publication	Disordered and complex systems
Editors	L.P. Hughston P. Sollich, R.F. Streater
Place of Publication	New york
Publisher	American Institute of Physics
Pages	89-94
Number of pages	6
Volume	553
DOIs	https://doi.org/10.1063/1.1358168
Publication status	Published - 9 Feb 2001
Event	Disordered and Complex Systems - Duration: 9 Feb 2001 → 9 Feb 2001

Other

Other	Disordered and Complex Systems
Period	9/02/01 → 9/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

Access to Document

10.1063/1.1358168

NCRG_2001_008.pdf
Copyright of American Institute of Physics(AIP).
Accepted author manuscript, 163 KB

Cite this

@inproceedings{3a45793804c4423a989ebdaac70b602d,

title = "Public key cryptography and error correcting codes as Ising models",

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.",

keywords = "statistical physics, error correcting codes, sparse matrices, Shannon's bound, decoding dynamics, public-key cryptosystem, cyptographical",

author = "David Saad and Yoshiyuki Kabashima and Tatsuto Murayama",

note = "Copyright of American Institute of Physics(AIP).; Disordered and Complex Systems ; Conference date: 09-02-2001 Through 09-02-2001",

year = "2001",

month = feb,

day = "9",

doi = "10.1063/1.1358168",

language = "English",

volume = "553",

pages = "89--94",

editor = "{P. Sollich}, {L.P. Hughston} and R.F. Streater",

booktitle = "Disordered and complex systems",

publisher = "American Institute of Physics",

address = "United States",

}

TY - GEN

T1 - Public key cryptography and error correcting codes as Ising models

AU - Saad, David

AU - Kabashima, Yoshiyuki

AU - Murayama, Tatsuto

N1 - Copyright of American Institute of Physics(AIP).

PY - 2001/2/9

Y1 - 2001/2/9

N2 - 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.

AB - 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.

KW - statistical physics

KW - error correcting codes

KW - sparse matrices

KW - Shannon's bound

KW - decoding dynamics

KW - public-key cryptosystem

KW - cyptographical

UR - http://link.aip.org/link/?APCPCS/553/89/1

U2 - 10.1063/1.1358168

DO - 10.1063/1.1358168

M3 - Conference publication

VL - 553

SP - 89

EP - 94

BT - Disordered and complex systems

A2 - P. Sollich, L.P. Hughston

A2 - Streater, R.F.

PB - American Institute of Physics

CY - New york

T2 - Disordered and Complex Systems

Y2 - 9 February 2001 through 9 February 2001

ER -

Public key cryptography and error correcting codes as Ising models

Abstract

Other

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this