Graph-Based Construction for Non-Malleable Codes

Shohei Satake; Yujie Gu; Kouichi Sakurai

Paper 2021/164

Graph-Based Construction for Non-Malleable Codes

Shohei Satake

Yujie Gu

Kouichi Sakurai

Abstract

Non-malleable codes are introduced to protect the communication against adversarial tampering of data, as a relaxation of the error-correcting codes and error-detecting codes. To explicitly construct non-malleable codes is a central and challenging problem which has drawn considerable attention and been extensively studied in the past few years. Recently, Rasmussen and Sahai built an interesting connection between non-malleable codes and (non-bipartite) expander graphs, which is the first explicit construction of non-malleable codes based on graph theory other than the typically exploited extractors. So far, there is no other graph-based construction for non-malleable codes yet. In this paper, we aim to explore more connections between non-malleable codes and graph theory. Specifically, we first extend the Rasmussen-Sahai construction to bipartite expander graphs. Accordingly, we establish several explicit constructions for non-malleable codes based on Lubotzky-Phillips-Sarnak Ramanujan graphs and generalized quadrangles, respectively. It is shown that the resulting codes can either work for a more flexible split-state model or have better code rate in comparison with the existing results.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Contact author(s): shohei_satake @ meiji ac jp
History: 2022-05-25: last of 6 revisions; 2021-02-17: received; See all versions
Short URL: https://ia.cr/2021/164
License: CC BY

BibTeX

@misc{cryptoeprint:2021/164,
      author = {Shohei Satake and Yujie Gu and Kouichi Sakurai},
      title = {Graph-Based Construction for Non-Malleable Codes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/164},
      year = {2021},
      url = {https://eprint.iacr.org/2021/164}
}