A Multi-Trapdoor Commitment Scheme from the RSA Assumption

Ryo NISHIMAKI
Eiichiro FUJISAKI
Keisuke TANAKA

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E95-A    No.1    pp.176-184
Publication Date: 2012/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E95.A.176
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Secure Protocol
Keyword: 
non-interactive commitment,  multi-trapdoor commitment,  non-malleability,  RSA assumption,  weak signature,  

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


Summary: 
This paper presents a new non-interactive multi-trapdoor commitment scheme from the standard RSA assumption. Multi-trapdoor commitment is a stronger variant of trapdoor commitment. Its notion was introduced by Gennaro at CRYPTO 2004. Multi-trapdoor commitment schemes are very useful because we can convert a non-interactive multi-trapdoor commitment scheme into a non-interactive and reusable non-malleable commitment scheme by using one-time signature and transform any proof of knowledge into a concurrently non-malleable one (this can be used as concurrently secure identification). Gennaro gave concrete constructions of multi-trapdoor commitment, but its security relies on stronger assumptions, such as the strong RSA assumption and the q-strong Diffie-Hellman assumption as opposed to our construction based on the standard RSA assumption. As a corollary of our results, we constructed a non-interactive and reusable non-malleable commitment scheme from the standard RSA assumption. Our scheme is based on the Hohenberger-Waters (weak) signature scheme presented at CRYPTO 2009. Several non-interactive and reusable non-malleable commitment schemes (in the common reference string model) have been proposed, but they all rely on stronger assumptions (such as the strong RSA assumption). Thus, we give the first construction of a non-interactive and reusable non-malleable commitment scheme from the standard RSA assumption.