A Straight-Line Extractable Non-malleable Commitment Scheme

Seiko ARITA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E90-A    No.7    pp.1384-1394
Publication Date: 2007/07/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e90-a.7.1384
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Information Security
commitment scheme,  non-malleability,  the KEA1 assumption,  extractability,  

Full Text: PDF(197KB)>>
Buy this Article

Non-malleability is an important security property of commitment schemes. The property means security against the man-in-the-middle attack, and it is defined and proved in the simulation paradigm using the corresponding simulator. Many known non-malleable commitment schemes have the common drawback that their corresponding simulators do not work in a straight-line manner, requires rewinding of the adversary. Due to this fact, such schemes are proved non-malleable only in the stand-alone cases. In the multiple-instances setting, i.e., when the scheme is performed concurrently with many instances of itself, such schemes cannot be proved non-malleable. The paper shows an efficient commitment scheme proven to be non-malleable even in the multiple-instances setting, based on the KEA1 and DDH assumptions. Our scheme has a simulator that works in a straight-line manner by using the KEA1-extractor instead of the rewinding strategy.