Use of modular roots to perform authentication including, but not limited to, authentication of validity of digital certificates

A computer-implemented authentication method for providing authentication for a plurality of elements as possessing a pre-specified property, each element being operable to acquire the property and/or to lose the property, each element being associated with a distinct integer greater than 1, the method comprising:

• a first computer system generating an integer pE1 associated with an element E1 which is one of said elements;
• the first computer system obtaining data representing a pE1-th root of a base number modulo a predefined composite integer;
• the first computer system providing said data to a second computer system to enable the second computer system to prove that the element E1 possesses the pre-specified property.

A computer-implemented authentication method for providing authentication for a plurality of elements as possessing a pre-specified property, each element being operable to acquire the property and/or to lose the property, each element being associated with a distinct integer greater than 1, the method comprising:

• obtaining first data A1(P1) evidencing that all the elements of the set P1 possess said property or all the elements of the set P1 do not possess said property, wherein the first data A1(P1) is a function of each element of the set P1, and the first data A1(P1) has a size independent of the number of elements in the set P1;
• dividing the set P1 into two or more non-empty subsets P1.1 . . . P1.k;
• for each subset P1.i (i=1, . . . , k), obtaining first data A1(P1.i).

A computer-implemented authentication method for providing authentication for a plurality of elements as possessing a pre-specified property, each element being operable to acquire the property and/or to lose the property, each element being associated with a distinct integer greater than 1, the method comprising:

• obtaining first data A1(P1) evidencing that all the elements of the set P1 possess said property or all the elements of the set P1 do not possess said property, wherein the first data A1(P1) represents a P-th root u1/P (mod n) of an integer u modulo a predefined composite integer n, where P is the product of the integers associated with the members of the set P1;
• dividing the set P1 into two or more non-empty subsets P1.1, . . . P1.k;
• for each subset P1.i (i=1, . . . , k), obtaining first data A1(P1.i) by raising the P-th root u1/P (mod n) to a power which is the product of the integers associated with the elements that belong to the set P1 but not to the subset P1.i.

A computer-implemented method for providing authentication as to whether or not elements possess a pre-specified property, each element being operable to acquire the property and/or to lose the property, wherein the authentication is to be provided in each of a plurality of consecutive periods of time, the method comprising:

• for each period j of said plurality of consecutive periods of time, determining if an element E1 is to be authenticated in the period j as possessing said property;
• if the element E1 is to be authenticated in the period j as possessing said property, then providing a decryption key DKj(E1) to each computer system which is to provide evidence data cj(E1) in the period j that the element E1 possess said property, wherein DKj(E1) is generated from a pE1-th root u(j)1/pE1 (mod n) of an integer u(j) modulo a predefined composite integer n, where u(j) depends on j, where pE1 is an integer assigned to the element E1, the decryption key DKj(E1) being for decrypting at least a portion of the evidence data cj(E1);
• if the element E1 is not to be authenticated in the period j as possessing said property, then not providing the decryption key DKj(E1) to at least one of said computer systems.