Method for publishing certification information representative of selectable subsets of rights and apparatus and portable data storage media used to practice said method

A method for controlling, and distributing information among, a plurality of stations, one of said stations being a user station operated by a user U to generate a plurality of private encryption keys KeyU,i and others of said stations being certifying stations operated by a plurality of certifying authorities for publishing related information, said related information identifying particular rights certified to said user U, so that a corresponding public key KeyU,sum(i)*P of said user U can be determined by a party communicating with said user U from said published related information with assurance that at least rights asserted by said user U have been certified by corresponding ones of said certifying authorities CA, but said party cannot claim that other rights were asserted;

• said method comprising the steps of:
• a) defining a finite group [P] with a binary operation [+] and publishing a particular point P in said group;
• b) defining and publishing a binary operation K*p, where K is an integer and p is a point in said group, such that K*p is a point in said group computed by applying said operation [+] to K copies of said point p, and computation of K from knowledge of the definition of said group [P], said point p, and K*p is hard;
• c) controlling each of said certifying stations to publish a certificate CERTU,i for said user U, wherein;
• CERTU,i=(rU,i+rCAi)*P;
• and wherein
• rU,i is a random integer known only to said user U and rCAi is a random integer generated by an ith one of said certifying stations;
• d) controlling each of said certifying stations to publish a message Mi said message Mi identifying particular rights certified to said user U by an ith one of said certifying stations;
• e) controlling each of said certifying stations to generate an integer Ii, and send Ii to said user station, wherein;
• Ii=rCAi+H(Mi)KeyCAi;
• and wherein
• H(Mi) is an integer derived from said message Mi in accordance with a publicly known algorithm H, and rCAi is one of said random integers generated by, and KeyCAi is a private key of, an ith one of said certifying stations;
• f) publishing a public key KeyCAi*P for each of said certifying authorities CA;
• and
• g) controlling said user station to compute a plurality of private keys KeyU,i, wherein
• KeyU,i=rU,i+Ii=rU,i+rCAi+H(Mi)KeyCAi whereby
• h) said user can generate a private key KeyU,sum(i) to communicate while asserting only a selected subset of rights
• KeyU,sum(i)=sum(KeyU,i)=sum(rU,i+rCAi+H(Mi)KeyCAi) summed over asserted rights;
• and
• i) said communicating party can compute said user's public key KeyU,sum(i)*P, summed over asserted rights, as
• KeyU,sum(i)*P=sum[+](CERTU,i[+]H(Mi)KeyCAi*P)=sum[+]((rU,i+rCAi)*P[+]H(Mi)KeyCAi*P)=sum(rU,i+rCAi+H(Mi)KeyCAi)*P
• from knowledge of H, messages Mi, [P], said public keys KeyCAi*P, and certificates CERTU,i.