Concurrent Non-Malleable Witness Indistinguishable Argument from Any One-Way Function

摘要

Non-malleable witness indistinguishability (NMWI) is a security notion against man-in-the-middle attacks which requires that the witness encoded in the right interaction is computationally independent of that used by honest prover in the left. In STOC 2009, Lin et al. defined strongly non-malleable witness indistinguishability (SNMWI) which is similar in spirit to NMWI, and proposed a SNMWI scheme based on one-way function. In this paper, we firstly show that the two notions NMWI and SNMWI are incomparable: there exists a SNMWI argument which is not NMWI, and vice versa. Furthermore, it is pointed out that the SNMWI construction given in STOC 2009 is not NMWI. Then, we present a variant of LPV08 scheme [17] and show that this variant is a concurrent NMWI argument. Compared with the concurrent NMWI argument of [22] which was shown to be non-malleable by using non-black-box techniques and whose difficulty assumption was claw-free permutation, our new scheme is based on the existence of one-way functions and its proof of security relies on black-box techniques.