Secure user identification based on constrained polynomials

Abstract

Methods and apparatus for providing secure user identification or digital signatures based on evaluation of constrained polynomials. In an exemplary user identification technique, a prover sends a verifier a commitment signal representative of a first polynomial satisfying a first set of constraints. The verifier sends the prover a challenge signal representative of a second polynomial satisfying a second set of constraints. The prover generates a response signal as a function of (i) information used to generate the commitment signal, (ii) a challenge signal, and (iii) a private key polynomial of the prover, such that the response signal is representative of a third polynomial satisfying a third set of constraints. The verifier receives the response signal from the prover, and authenticates the identity of the prover by evaluating a function of information contained in at least a subset of (i) the commitment signal, (ii) the challenge signal, (iii) the response signal and (iv) a public key of the prover. In a digital signature technique, the challenge signal may be generated by the prover applying a hash function to (i) a message and (ii) information used to generate the commitment signal, and the prover sends the message to the verifier. The verifier uses a result of applying the hash function to the message and the commitment signal to authenticate a digital signature of the prover. The constraints on the polynomials are selected such that an attacker will find it very difficult to recover the private key polynomial from the partial information sent between the prover and verifier.