Method to trace traceable parts of original private keys in a public-key cryptosystem

摘要

The aim of the present invention is to propose a very fast alternative mechanism to the traitor tracing algorithm introduced by Boneh and Franklin to trace private keys in a public-key cryptosystem. This invention concerns a method to trace traceable parts of original private keys in a public-key cryptosystem consisting of one public key and λ corresponding private keys, a private key being formed by 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 (π)}=(π₁, . . . , π_λ) and a scaling vector {right arrow over (c)}=(c₁, c₂, . . . , c_λ), comprising the steps of: obtaining the traceable part {right arrow over (d)}=(d₁, . . . , d_2k)^T of a rogue private key,applying a Berlekamp-Massey algorithm on the traceable part {right arrow over (d)}=(d₁, . . . , d_2k)^T of the rogue private key, to obtain the k coefficients of an 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.