Identification protocols

A system for verifying access to a private key associated with a public key Kp, the system comprising:

• a verifier;
• and
• a prover comprising a disguising unit;
• wherein the prover is operative to send 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;
• and
• the prover and the verifier together are operative to perform 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 in the disguising unit, 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 is operative to determine that the prover has access to the private key based on a result of the identification round.

A prover for use with a verifier for verifying access to a private key associated with a public key Kp, the prover comprising:

• a disguising unit;
• wherein the prover is operative to send 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;
• and
• the prover and the verifier together are operative to perform 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 in the disguising unit, 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 is operative to determine that the prover has access to the private key based on a result of the identification round.