Patent ID: 7747857

Claim:
A computer-implemented authentication method for providing authentication for a plurality of elements as possessing a pre-specified property, wherein for each time period j of a plurality of successive time periods, the authentication is to be provided for each said element which possesses the pre-specified property, each element being operable to acquire the property and/or to lose the property in each of the successive time periods j, each element being associated with a distinct integer greater than 1, the method comprising, for at least one element E 1 which is one of said elements, performing a set-up operation for the authentication, the set-up operation comprising: a first computer system generating the distinct integer p E1 associated with the element E 1 ; the first computer system obtaining data representing a p E1 -th root of a base number modulo a predefined composite integer whose factorization is a secret of the first computer system; the first computer system providing said data to a second computer system to enable the second computer system to prove that the element E 1 possesses the pre-specified property; wherein for each said period j for which the element E 1 is to be authenticated as possessing said property, the authentication is to be performed by operations comprising: the second computer system obtaining data representing an accumulator value which accumulates all the entities in a set P 1 j which is either (i) a set of the entities certified as possessing the pre-specified property in the period j, or (ii) a set of the entities certified as not possessing the pre-specified property in the period j; the second computer system combining the accumulator value with a value dependent on said p E1 -th root of the base number to obtain a witness value which is a p E1 -th root, modulo said composite integer, of a first value dependent on the base number and the accumulator value, the authentication comprising verifying that the p E1 -th power of the witness value equals the first value.