Patent ID: 6889322

Claim:
A method for verifying, by a verifier, that a prover has access to a private key associated with a public key Kp, the method comprising: the prover sending an identification message to the verifier, the identification message comprising an indication of an identity of the prover, the indication of the identity including an indication of Kp; performing an identification round, the identification round comprising: the verifier choosing a challenge Q and a padding string X; the verifier sending an initialization message to the prover, the initialization message comprising a disguised form Y produced by applying a public disguising function Fp to Q and X, Y being equal to Fp(Q,X); the prover computing a random number R by applying a private disguising function Fv to Y, R being equal to Fv(Y); the prover sending a commit message to the verifier, the commit message comprising a disguised form of R produced by applying a function f to R, the disguised form of R being equal to f(R); the verifier sending a challenge message to the prover, the challenge message comprising the challenge Q and the padding string X; the prover verifying that Y=Fp(Q,X); the prover sending a response message to the verifier, the response message comprising a response A, the response A satisfying a predicate relationship Pred(A,Q,f(R),Kp), wherein satisfying the predicate relationship provides an indication that the prover has access to the private key; and the verifier verifying that A satisfies the predicate relationship Pred(A,Q,f(R),Kp); and the verifier determining that the prover has access to the private key based on a result of the performing step.