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) as possessing a pre-specified property (e.g. being valid) or not possessing the property is performed by (1) assigning a distinct integer pto each element, and (2) accumulating the elements possessing the property or the elements not possessing the property using a P-th root u(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.