Paper 2022/907

A New Approach to Post-Quantum Non-Malleability

Xiao Liang, NTT Research
Omkant Pandey, Stony Brook University
Takashi Yamakawa, NTT Social Informatics Laboratories

We provide the first constant-round construction of post-quantum non-malleable commitments under the minimal assumption that post-quantum one-way functions exist. We achieve the standard notion of non-malleability with respect to commitments. Prior constructions required $\Omega(\log^*\lambda)$ rounds under the same assumption. We achieve our results through a new technique for constant-round non-malleable commitments which is easier to use in the post-quantum setting. The technique also yields an almost elementary proof of security for constant-round non-malleable commitments in the classical setting, which may be of independent interest. When combined with existing work, our results yield the first constant-round quantum-secure multiparty computation for both classical and quantum functionalities in the plain model, under the polynomial hardness of quantum fully-homomorphic encryption and quantum learning with errors.

Note: 1. Include additional intuitive explanations in the technical overview to enhance understanding; 2. Append a new corollary regarding constant-round multi-party computation (MPC) for quantum functionalities.

Available format(s)
Publication info
Published elsewhere. Major revision. FOCS
Contact author(s)
xiao crypto @ gmail com
omkant @ cs stonybrook edu
takashi yamakawa ga @ hco ntt co jp
2023-11-04: last of 2 revisions
2022-07-12: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-NoDerivs


      author = {Xiao Liang and Omkant Pandey and Takashi Yamakawa},
      title = {A New Approach to Post-Quantum Non-Malleability},
      howpublished = {Cryptology ePrint Archive, Paper 2022/907},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.