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

Abstract

Authentication of elements (e.g. digital certificates 140 ) as possessing a pre-specified property (e.g. being valid) or not possessing the property is performed by (1) assigning a distinct integer p i to each element, and (2) accumulating the elements possessing the property or the elements not possessing the property using a P-th root u 1/P (mod n) of an integer u modulo a predefined composite integer n, where P is the product of the integers associated with the accumulated elements. Alternatively, authentication is performed without such accumulators but using witnesses associated with such accumulators. The witnesses are used to derive encryption and/or decryption keys for encrypting the data evidencing possession of the property for multiple periods of time. The encrypted data are distributed in advance. For each period of time, decryption keys are released which are associated with that period and with the elements to be authenticated in that period of time. Authentication can be performed by accumulating elements into data which are a function of each element but whose size does not depend on the number of elements, and transmitting the accumulator data over a network to a computer system which de-accumulates some elements as needed to re-transmit only data associated with elements needed by other computer systems. This technique is suitable to facilitate distribution of accumulator data in networks such as ad hoc networks.

1 . A network transmission method comprising transmitting, over a computer network, a computer program operable to perform 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 authentication method comprising, for at least one element El 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 E1;   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 E1 possesses the pre-specified property;   wherein for each said period j for which the element E1 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 P1 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.   
     
     
         2 . The network transmission method of  claim 1  wherein the elements are either (a) digital certificates each of which certifies that a cryptographic key is associated with an entity, or (b) entitlements to use one or more resources, and said property is validity of a digital certificate or an entitlement. 
     
     
         3 . The network transmission method of  claim 1  wherein in the authentication, the first value is made available to a verifier together with the witness value or a proof of knowledge of the witness value. 
     
     
         4 . The network transmission method of  claim 3  wherein the computer program is operable to perform the authentication operations for at least one said time period j. 
     
     
         5 . The network transmission method of  claim 1  wherein the accumulator value is a P j -th root u 1/P     j    (mod n) of an integer u modulo said predefined composite integer, where P j  is the product of the distinct integers associated with the members of the set P1 j , where u is a constant or is a predefined function of the period of time. 
     
     
         6 . The network transmission method of  claim 1  wherein said verifying, that the p E1 -th power of the witness value equals the first value, is performed by a verifier computer system, and the p E1 -th root of the base number is a secret not provided to the verifier computer system. 
     
     
         7 . The network transmission method of  claim 2  wherein in the authentication, the first value is made available to a verifier together with the witness value or a proof of knowledge of the witness value. 
     
     
         8 . The network transmission method of  claim 7  wherein the computer program is operable to perform the authentication operations for at least one said time period j. 
     
     
         9 . The network transmission method of  claim 2  wherein the accumulator value is a P j -th root u 1/P     j    (mod n) of an integer u modulo said predefined composite integer, where P j  is the product of the distinct integers associated with the members of the set P1 j , where u is a constant or is a predefined function of the period of time. 
     
     
         10 . The network transmission method of  claim 2  wherein said verifying, that the p E1 -th power of the witness value equals the first value, is performed by a verifier computer system, and the p E1  -th root of the base number is a secret not provided to the verifier computer system.