Name
Abstract | ||
|---|---|---|
In 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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-68164-9_10 | AFRICACRYPT |
Keywords | Field | DocType |
signature-forgery attack,trms signature scheme,basic idea,tractable rationale maps signature,algebraic system,bner base,hybrid approach,experimental evidence,signature scheme,initial system,bner basis,grobner basis | Discrete mathematics,Linear methods,Algebraic number,Algebra,Cryptanalysis,Gröbner basis,Mathematics,Permutation polynomial,Bounded function | Conference |
Volume | ISSN | ISBN |
5023 | 0302-9743 | 3-540-68159-0 |
Citations | PageRank | References |
5 | 0.53 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luk Bettale | 1 | 111 | 7.18 |
| Jean-Charles Faugère | 2 | 1037 | 74.00 |
| Ludovic Perret | 3 | 546 | 39.06 |