Secure user identification based on ring homomorphisms

A method for authenticating, by a second user, the identity of a first user, that includes a challenge communication from the second user to the first user, a response communication from the first user to the second user, and a verification by the second user, comprising the steps of:

• selection by the first user of a private key f in a ring R and a public key that includes φ(f) in a ring B that is mapped from f using the ring homomorphism φ:
• R→B, and publication by the first user of the public key;
• generation of the challenge communication by the second user that includes selection of a challenge c in the ring R;
• generation of the response communication by the first user that includes computation of a response comprising h in the ring R, where h is a function of c and f, and
• performing of a verification by the second user that includes determination of φ(c) from c, φ(h) from h, and an evaluation that depends on φ(h), φ(c) and φ(f).

An authentication method that includes authenticating, by a second user, of a signed digital message of a first user communicated from said first user to said second user, comprising the steps of:

• selecting by the first user, of a private key f in a ring R and a public key that includes φ(f) in a ring B that is mapped from f using the ring homomorphism φ:
• R→B, and publication by the first user of the public key;
• selecting, by the first user, of an element g1 in the ring R, determining φ(g1), and applying a hash function to at least a message m to produce an element c;
• generating, by the first user, an element h which is a function of c and f;
• communicating, from the first user to the second user, the message m and a digital signature comprising φ(g1) and h;
• determining, by the second user, of the element c, by applying a hash function to at least the message m, and determining, by the second user of φ(c) from c and φ(h) from h;
• and
• authenticating, by the second user, of the digital signature, said authenticating including an evaluation that depends on φ(h), φ(f) and φ(c).

A method for use by a first user to prove its identity to a second user who sends a challenge to the first user and wishes to authenticate the identity of the first user, comprising the steps of:

• selecting a private key f in a ring R and a public key that includes φ(f) in a ring B that is mapped from f using the ring homomorphism φ:
• R→B, and publication by the first user of the public key;
• receiving the challenge communication from the second user that includes selection of a challenge element c in the ring R;
• and
• generation of the response communication that includes computation of a response comprising h in the ring R, where h is a function of c and f;
• whereby the second user can perform a verification that includes determination of φ(c) from c, φ(h) from h, and an evaluation that depends on φ(h), φ(c) and φ(f).

A method for producing and sending a signed digital message comprising the steps of:

• selecting a private key f in a ring R and a public key that includes φ(f) in a ring B that is mapped from f using the ring homomorphism φ:
• R→B, and publication by the first user of the public key;
• selecting an element g1 in the ring R, determining φ(g1), and applying a hash function to at least a message m to produce an element c;
• generating an element h which is a function of c and f;
• and
• communicating the message m and a digital signature comprising φ(g1) and h.