Improved identification schemes based on error-correcting codes |
| |
Authors: | Pascal Véron |
| |
Affiliation: | 1. G.E.C.T., Université de Toulon et du Var, B.P. 132, F-83957, La Garde Cedex, France
|
| |
Abstract: | As it is often the case in public-key cryptography, the first practical identification schemes were based on hard problems from number theory (factoring, discrete logarithms). The security of the proposed scheme depends on an NP-complete problem from the theory of error correcting codes: the syndrome decoding problem which relies on the hardness of decoding a binary word of given weight and given syndrome. Starting from Stern’s scheme 18], we define a dual version which, unlike the other schemes based on the SD problem, uses a generator matrix of a random linear binary code. This allows, among other things, an improvement of the transmission rate with regards to the other schemes. Finally, by using techniques of computation in a finite field, we show how it is possible to considerably reduce: - the complexity of the computations done by the prover (which is usually a portable device with a limited computing power). - the size of the data stored by the latter. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|