Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleCryptanalysis of the TRMS signature scheme of PKC
Author(s) Faug`ere Jean-Charles, Bettale Luk, Ludovic Perret
TypeBook, Chapter in Book, Conference Proceeding
AbstractIn this paper, we investigate the security of the Tractable Rationale Maps Signature (TRMS) signature scheme [9] proposed at PKC’05. To do so, we present a hybrid approach for solving the algebraic systems naturally arising when mounting a signature-forgery attack. The basic idea is to compute Gröbner bases of several modified systems rather than a Gröbner basis of the initial system. We have been able to provide a precise bound on the (worst-case) complexity of this approach. For that, we have however assumed a technical condition on the systems arising in our attack; namely the systems are semi-regular [3,5]. This claim is supported by experimental evidences. Finally, it turns out that our approach is efficient. We have obtained a complexity bounded from above by 257 to forge a signature on the parameters proposed by the designers of TRMS [9]. This bound can be improved; assuming an access to 216 processors (which is very reasonable), one can actually forge a signature in approximately 51 hours.
URL http://link.springer.com/chapter/10.1007%2F978-3-540-68164-9_10
PublisherBerlin: Springer
Translation No
Refereed No