Ring-based public key cryptosystem method

Abstract

A method of communicating information between users of a communications system includes the following steps: generating a ring R, ideals P and Q in R, a set of coset representatives C,for the ring R modulo the ideal Q, and a set of coset representatives C,for the ring R modulo the ideal P; generating at least one public key element h,, . . . , h,in the ring R as a function of at least two private key elements ƒ,, . . . ƒ,in R and the ideal Q of the first user; and transmitting from a first user to a second user a description of the ring R, the ideal Q, the ideal P, and the elements h,, . . . , h,in R; generating an element e in R as a function of the ideals P and Q, the public key elements h,, . . . , h,, a private message element m in R, and at least one private random element ø,, . . . , ø,of the second user; and transmitting the element e from the second user to the first user, such that the first user can determine the message element m by computing a result A in R of evaluating a function F of e, ƒ,, . . . , ƒ,, computing a coset representative a of A in the set of coset representatives C,, computing a result B of evaluating a function G of a, ƒ,, . . . , ƒ,, computing a coset representative b of B in the set of coset representatives C,, and computing a result c in the set of coset representatives C,of evaluating a function H of b, ƒ,, . . . , ƒ,.