Patent ID: 7936882

Claim:
Method to trace traceable parts {right arrow over (d)}=(d 1 , . . . , d 2k ) T of original private keys in a public-key cryptosystem consisting of one public key and λ corresponding private keys, a private key being formed by at least a traceable array of 2k elements forming a syndrome of a generalized Reed-Solomon code with parameters (λ,λ-2k) defined by the base points {right arrow over (π)}=(π 1 , . . . , π λ ) and a scaling vector {right arrow over (c)}=(c 1 , c 2 , . . ., c λ ), comprising the steps of: obtaining the traceable part {right arrow over (d)}=(d 1 , . . . , d 2k ) T of a rogue private key where the array of 2k elements is a linear combination of arrays of 2k elements belonging to at least two original private keys such that the sum of the coefficients of the linear combination is equal to 1 mod q, applying a Berlekamp-Massey algorithm on the traceable part {right arrow over (d)}=(d 1 , . . . , d 2k ) T of the rogue private key, to obtain the k coefficients of the error-locator polynomial, applying the Chien's search algorithm to the error-locator polynomial, to obtain roots of the error-locator polynomial, determining the base points of the traceable part of the original private keys by computing the arithmetic inverse of each root, these base points allowing to uniquely determine the private key identity.