Paper 2021/164

Graph-Based Construction for Non-Malleable Codes

Shohei Satake
Yujie Gu
Kouichi Sakurai

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.

Available format(s)
Publication info
Contact author(s)
shohei_satake @ meiji ac jp
2022-05-25: last of 6 revisions
2021-02-17: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.