Zulfikar Ramzan

A system retroactively detects malicious software on an end user system without performing expensive cross-referencing directly on the endpoint device. A client provides a server with information about files that are on it together with what it knows about these files. The server tracks this information and cross-references it against new intelligence it gathers on clean or malicious files. If a discrepancy in found (i.e., a file that had been called malicious, but that is actually benign or… Show more

A system retroactively detects malicious software on an end user system without performing expensive cross-referencing directly on the endpoint device. A client provides a server with information about files that are on it together with what it knows about these files. The server tracks this information and cross-references it against new intelligence it gathers on clean or malicious files. If a discrepancy in found (i.e., a file that had been called malicious, but that is actually benign or vice versa), the server informs the client, which in turn takes an appropriate action based on this information. Show less

A computer-implemented method for selectively authenticating a request based on an authentication policy is described. A request is received from a client. A determination is made as to which authentication threshold is applied to the request based on an authentication policy. The request is authenticated if the authentication threshold is satisfied. The authentication threshold is modified if the request is not successfully authenticated.

The present invention relates to the security of general purpose computing devices, such as laptop or desktop PCs, and more specifically to the detection of malicious software (malware) on a general purpose computing device. A challenge in detecting malicious software is that files are typically scanned for the presence of malicious intent only once (and subsequent rescanning is typically performed in a simplistic manner). Existing methods in the art do not address how to most effectively… Show more

The present invention relates to the security of general purpose computing devices, such as laptop or desktop PCs, and more specifically to the detection of malicious software (malware) on a general purpose computing device. A challenge in detecting malicious software is that files are typically scanned for the presence of malicious intent only once (and subsequent rescanning is typically performed in a simplistic manner). Existing methods in the art do not address how to most effectively rescan collections of files in a way that tries to optimize performance and efficacy. Accordingly we present novel methods, components, and systems for intelligently rescanning file collections and thereby enabling retroactive detection of malicious software and also retroactive identification of clean software. These methods may also be useful if additional information is now available regarding a file that might be useful to an end-user or an administrator, even though the file's core disposition might not have changed. More specifically, we describe methods, components, and systems that perform data analytics to intelligently rescan file collections for the purpose of retroactively identifying malware and retroactively identifying clean files. The disclosed invention provides a significant improvement with regard to efficacy and performance compared to previous approaches. Show less

A system for retroactively detecting malicious software on an end user system without performing expensive cross-referencing directly on the endpoint device. A client provides a server with information about files that are on it together with what it knows about these files. The server tracks this information and cross-references it against new intelligence it gathers on clean or malicious files. If a discrepancy is found (i.e., a file that had been called malicious, but that is actually benign… Show more

A system for retroactively detecting malicious software on an end user system without performing expensive cross-referencing directly on the endpoint device. A client provides a server with information about files that are on it together with what it knows about these files. The server tracks this information and cross-references it against new intelligence it gathers on clean or malicious files. If a discrepancy is found (i.e., a file that had been called malicious, but that is actually benign or vice versa), the server informs the client, which in turn takes an appropriate action based on this information. Show less

A candidate suspicious website is identified. A plurality of lightweight features associated with the candidate suspicious website is identified. A filter score is determined based on the plurality of lightweight features, wherein the filter score indicates a likelihood that the candidate suspicious website is a malicious website. Whether the filter score exceeds a threshold is determined. Responsive at least in part to the filter score exceeding the threshold it is determined that the… Show more

A candidate suspicious website is identified. A plurality of lightweight features associated with the candidate suspicious website is identified. A filter score is determined based on the plurality of lightweight features, wherein the filter score indicates a likelihood that the candidate suspicious website is a malicious website. Whether the filter score exceeds a threshold is determined. Responsive at least in part to the filter score exceeding the threshold it is determined that the candidate suspicious website is a suspicious website. Whether the suspicious website is a malicious website is determined by identifying software downloaded to the computing system responsive to accessing the suspicious website and determining whether the software downloaded to the computing system is malware based on characteristics associated with the downloaded software. Show less

An individualized time-to-live (TTL) is determined for a reputation score of a computer file. The TTL is determined based on the reputation score and the confidence in the reputation score. The confidence can be determined based on attributes such as the reputation score, an age of the file, and a prevalence of the file. The reputation score is used to determine whether the file is malicious during a validity period defined by the TTL, and discarded thereafter.

A method and apparatus for resolving a cousin domain name to detect web-based fraud is described. In one embodiment, the method for resolving cousin domain names of a legitimate domain name comprising applying at least one rule to a domain name to generate one or more candidate cousin domain names and comparing the at least one candidate cousin domain name with legitimate domain information to identify the legitimate domain name that is imitated by at least one portion of the domain name.

Systems, computer-readable media storing instructions, and methods can infer a state of behavior. Such a method can include constructing a graph including nodes representing hosts and domains based on an event dataset. The graph can be seeded with information external to the event dataset. A belief whether each of the nodes is in a particular state of behavior can be calculated based on marginal probability estimation.

The performance and hence the user experience of just-in-time application streaming is significantly enhanced by predicting which sections of an application are likely to execute next, and transmitting those sections from the server to the endpoint. A control flow graph of the application is created and analyzed against the execution state of the application such that it can be predicated which code pages the application is likely to utilize next. This analysis can be performed on the server… Show more

The performance and hence the user experience of just-in-time application streaming is significantly enhanced by predicting which sections of an application are likely to execute next, and transmitting those sections from the server to the endpoint. A control flow graph of the application is created and analyzed against the execution state of the application such that it can be predicated which code pages the application is likely to utilize next. This analysis can be performed on the server, endpoint or any combination of the two. The predicted code pages are proactively pushed and/or pulled such that the application can continue executing without delay. This significantly enhances the performance of application streaming and network file system technologies, and is especially beneficial for very performance sensitive applications.

Show less

Methods, components and systems for implementing secure and efficient broadcast encryption schemes with configurable and practical tradeoffs among a pre-broadcast transmission bandwidth t, a key storage cost k, and a key derivation cost c, in which the schemes use subtree difference and key decomposition to generate secondary keys, use the secondary keys to encrypt the broadcast and generate ciphertexts, and use the RSA encryption scheme to implement derivability between the primary keys and… Show more

Methods, components and systems for implementing secure and efficient broadcast encryption schemes with configurable and practical tradeoffs among a pre-broadcast transmission bandwidth t, a key storage cost k, and a key derivation cost c, in which the schemes use subtree difference and key decomposition to generate secondary keys, use the secondary keys to encrypt the broadcast and generate ciphertexts, and use the RSA encryption scheme to implement derivability between the primary keys and the secondary keys. To decrypt the broadcast, a privileged user uses one of its primary keys to derive a secondary key, which is used to decrypt the broadcast. The product of key derivation costc and the key storage cost k is at most (2a-log a-2)log.sub.a n, when n is the number of users, 1.ltoreq.b.ltoreq.log n, a=2.sup.b, and revoked users r<n/3.
Show less

A protocol for closing all active communication links between one device (110.1) and one or more other devices in a group provides that the first device sets up the group by generating an input to a predefined function (e.g. one-way function) according to some random distribution, computing the output of the one-way function, and sharing the output value with all other devices in the group. Then to close all communication links, the first device broadcasts the stored input to all other devices… Show more

A protocol for closing all active communication links between one device (110.1) and one or more other devices in a group provides that the first device sets up the group by generating an input to a predefined function (e.g. one-way function) according to some random distribution, computing the output of the one-way function, and sharing the output value with all other devices in the group. Then to close all communication links, the first device broadcasts the stored input to all other devices in the group. The other devices may check that the one-way function applied to this input results in the shared output value, and if so, close the communication link. Show less

A hash function is applied to a prefix of a VIL input. The output is added to a suffix of the input. A block cipher is applied to results of the addition. An encryption function is performed on the prefix. The final output is the output of the block cipher and the encryption function. In a second encryption technique, a hash function is applied to an input, and the output of the hash function has first and second portions. A block cipher is applied to the second portion. The output of the block… Show more

A hash function is applied to a prefix of a VIL input. The output is added to a suffix of the input. A block cipher is applied to results of the addition. An encryption function is performed on the prefix. The final output is the output of the block cipher and the encryption function. In a second encryption technique, a hash function is applied to an input, and the output of the hash function has first and second portions. A block cipher is applied to the second portion. The output of the block cipher is added to the first portion, and a second function is applied to the result of this first addition. The output of the second function is added to the second portion. An inverse hash function is then applied to the output of the first and second additions, creating an encrypted output.
Show less

A server (120) uses a password (.pi.) to construct a multiplicative group (Z.sub.N*) with a (hidden) smooth order subgroup (<x'>), where the group order (P.sub..pi.) depends on the password. The client (110) uses its knowledge of the password to generate a root extraction problem instance (z) in the group and to generate data (y) allowing the server to construct a discrete logarithm problem instance (y') in the subgroup. The server uses its knowledge of the group order to solve the root… Show more

A server (120) uses a password (.pi.) to construct a multiplicative group (Z.sub.N*) with a (hidden) smooth order subgroup (<x'>), where the group order (P.sub..pi.) depends on the password. The client (110) uses its knowledge of the password to generate a root extraction problem instance (z) in the group and to generate data (y) allowing the server to construct a discrete logarithm problem instance (y') in the subgroup. The server uses its knowledge of the group order to solve the root extraction problem, and solves the discrete logarithm problem efficiently by leveraging the smoothness of the subgroup. A shared key (sk) can be computed as a function of the solutions to the discrete logarithm and root extraction problem instances. In some embodiments, in an oblivious transfer protocol, the server queries the client (at 230) for data whose position in a database (210) is defined by the password. The client provides (240) such data without knowing the data position associated with the server's query. The client obtains the data position independently from the password. The data positions and/or the respective data are used for authentication and shared secret key generation. Other embodiments are also provided. Show less

Using a password (.pi.), a client (C) computes part (H.sub.1(<C,.pi..sub.C>) of the password verification information of a server (S), and together they use this information to authenticate each other and establish a cryptographic key (K'), possibly using a method resilient to offline dictionary attacks. Then over a secure channel based on that cryptographic key, the server sends an encryption (EE.sub.<C,.pi.>(sk)) of a signing key (sk) to a signature scheme for which the server… Show more

Using a password (.pi.), a client (C) computes part (H.sub.1(<C,.pi..sub.C>) of the password verification information of a server (S), and together they use this information to authenticate each other and establish a cryptographic key (K'), possibly using a method resilient to offline dictionary attacks. Then over a secure channel based on that cryptographic key, the server sends an encryption (EE.sub.<C,.pi.>(sk)) of a signing key (sk) to a signature scheme for which the server know a verification key (pk). The encryption is possibly non-malleable and/or includes a decryptable portion (E<.sub.C,.pi.>(sk)) and a verification portion (H.sub.8(sk)) used to verify the decrypted value obtained by decrypting the decryptable portion. The signing key is based on the password and unknown to the server. The client obtains the signing key using the password, signs a message, and returns the signature to the server. The server verifies this signature using the verification key, hence getting additional proof that the client has knowledge of the password. The client and the server generate a shared secret key (K''), more secure than the password, for subsequent communication.
Show less

Methods, systems, and products for detecting phishing attempts through fingerprinting are provided. In an embodiment, there is a computer program product that comprises a computer-readable medium and computer program instructions encoded on the medium for deterring fraud perpetrated through an incoming electronic message containing an address for responding to the incoming electronic message. The instructions are for extracting the address from the incoming electronic message and generating a… Show more

Methods, systems, and products for detecting phishing attempts through fingerprinting are provided. In an embodiment, there is a computer program product that comprises a computer-readable medium and computer program instructions encoded on the medium for deterring fraud perpetrated through an incoming electronic message containing an address for responding to the incoming electronic message. The instructions are for extracting the address from the incoming electronic message and generating a fingerprint based on the extracted address. It is then determined whether the generated fingerprint matches a plurality of stored legitimate fingerprints. When there is a lack of a match, an action is taken to prevent use of the address. Show less

Methods and systems are provided that allow multiple identity-based digital signatures to be merged into a single identity-based "aggregate" digital signature. This identity-based aggregate signature has a shorter bit-length than the concatenation of the original unaggregated identity-based signatures. The identity-based aggregate signature can be verified by anyone who obtains the public keys of one or more Private Key Generators (PKGs), along with a description of which signer signed which… Show more

Methods and systems are provided that allow multiple identity-based digital signatures to be merged into a single identity-based "aggregate" digital signature. This identity-based aggregate signature has a shorter bit-length than the concatenation of the original unaggregated identity-based signatures. The identity-based aggregate signature can be verified by anyone who obtains the public keys of one or more Private Key Generators (PKGs), along with a description of which signer signed which message. The verifier does not need to obtain a different public key for each signer, since the signature scheme is "identity-based"; the number of PKGs may be fewer than the number of signers. Consequently, the total information needed to verify the identity-based aggregate signature--namely, a description of who signed what, the PKGs' public keys, and the identity-based aggregate signature itself--may be less than the information needed to verify separate digital signatures--namely, a description of who signed what, the public verification keys for all of the signers, and the concatenation of the signers' signatures. In some embodiments, the identity-based aggregate signature scheme has essentially the minimum-possible Kolmogorov complexity.
Show less

An efficient hashing technique uses ##EQU00001## operations to hash a string "w" words long rather than the w.sup.2 operations of the prior art. This efficiency is achieved by squaring the sum of the key and the string to be hashed rather than forming a product of the key and the string to be hashed h(m)=((m+a).sup.2 mod p)mod 2.sup.1.

An (n,k,r,t)-exclusive set system over a set U includes elements S.sub.f each of corresponds to a polynomial f(u) in one or more coordinates of u.epsilon.U. The polynomial is zero on U\S.sub.f but is not zero on S.sub.f. In some embodiments, an asymptotically low key complexity k is provided.

In a broadcast encryption scheme, an optimal or near-optimal set covering CV(f,P) is computed for a set P of privileged users and at most a predefined number f of revoked users ("free riders"). The covering consists of elements of a predefined set cover CC(U) for the set of all users U. The covering is computed by finding optimal or near-optimal coverings for privileged users for CC(U) elements that are proper subsets of U. More particularly, possible assignments of free riders to the subsets… Show more

In a broadcast encryption scheme, an optimal or near-optimal set covering CV(f,P) is computed for a set P of privileged users and at most a predefined number f of revoked users ("free riders"). The covering consists of elements of a predefined set cover CC(U) for the set of all users U. The covering is computed by finding optimal or near-optimal coverings for privileged users for CC(U) elements that are proper subsets of U. More particularly, possible assignments of free riders to the subsets are examined, and an assignment is selected to fit an optimality criterion for the total set covering. In some embodiments, only "meeting point" elements of CC(U) are fully examined. A meeting point is an element containing at least two "immediate child" elements each of which contains a revoked user. An immediate child of a "parent" element is a proper subset of the parent with no intermediate elements (no elements containing the child as a proper subset and itself being a proper subset of the parent). An ordered list MP of meeting points is computed efficiently. The list is ordered by the number of elements in a chain from the meeting point to the root. The complete-subtree method is used in some embodiments. The methods have applications besides broadcast encryption, e.g. certificate revocation.
Show less

Revocation of digital certificates in a public-key infrastructure is disclosed, particularly in the case when a certificate might need to be revoked prior to its expirations. For example, if an employee was terminated or switched roles, his current certificate should no longer be valid. Accordingly, novel methods, components and systems are presented for addressing this problem. A solution set forth herein is based on the construction of grounded dense hash trees. In addition, the grounded… Show more

Revocation of digital certificates in a public-key infrastructure is disclosed, particularly in the case when a certificate might need to be revoked prior to its expirations. For example, if an employee was terminated or switched roles, his current certificate should no longer be valid. Accordingly, novel methods, components and systems are presented for addressing this problem. A solution set forth herein is based on the construction of grounded dense hash trees. In addition, the grounded dense hash tree approach also provides a time-communication tradeoff compared to the basic chain-based version of NOVOMODO, and this tradeoff yields a direct improvement in computation time in practical situations. Show less

A method, article of manufacture and apparatus for performing private retrieval of information from a database is disclosed. In one embodiment, the method comprising obtaining an index corresponding to information to be retrieved from the database and generating a query that does not reveal the index to the database. The query is an arithmetic function of the index and a secret value, wherein the arithmetic function includes a multiplication group specified by a modulus of a random value whose… Show more

A method, article of manufacture and apparatus for performing private retrieval of information from a database is disclosed. In one embodiment, the method comprising obtaining an index corresponding to information to be retrieved from the database and generating a query that does not reveal the index to the database. The query is an arithmetic function of the index and a secret value, wherein the arithmetic function includes a multiplication group specified by a modulus of a random value whose order is divisible by a prime power, such that the prime power is an order of the random value. The secret value is an arithmetic function of the index that comprises a factorization into prime numbers of the modulus. The method further comprises communicating the query to the database for execution of the arithmetic function against the entirety of the database. Show less

A method, article of manufacture and apparatus for performing private retrieval of information from a database is disclosed. In one embodiment, the method comprising obtaining an index corresponding to information to be retrieved from the database and generating a query that does not reveal the index to the database. The query is an arithmetic function of the index and a secret value, wherein the arithmetic function includes a multiplication group specified by a modulus of a random value whose… Show more

A method, article of manufacture and apparatus for performing private retrieval of information from a database is disclosed. In one embodiment, the method comprising obtaining an index corresponding to information to be retrieved from the database and generating a query that does not reveal the index to the database. The query is an arithmetic function of the index and a secret value, wherein the arithmetic function includes a multiplication group specified by a modulus of a random value whose order is divisible by a prime power, such that the prime power is an order of the random value. The secret value is an arithmetic function of the index that comprises a factorization into prime numbers of the modulus. The method further comprises communicating the query to the database for execution of the arithmetic function against the entirety of the database. Show less

A method, article of manufacture and apparatus for performing private retrieval of information from a database is disclosed. In one embodiment, the method comprising obtaining an index corresponding to information to be retrieved from the database and generating a query that does not reveal the index to the database. The query is an arithmetic function of the index and a secret value, wherein the arithmetic function includes a multiplication group specified by a modulus of a random value whose… Show more

A method, article of manufacture and apparatus for performing private retrieval of information from a database is disclosed. In one embodiment, the method comprising obtaining an index corresponding to information to be retrieved from the database and generating a query that does not reveal the index to the database. The query is an arithmetic function of the index and a secret value, wherein the arithmetic function includes a multiplication group specified by a modulus of a random value whose order is divisible by a prime power, such that the prime power is an order of the random value. The secret value is an arithmetic function of the index that comprises a factorization into prime numbers of the modulus. The method further comprises communicating the query to the database for execution of the arithmetic function against the entirety of the database.
Show less

A method, article of manufacture and apparatus for performing private retrieval of information from a database is disclosed. In one embodiment, the method comprising obtaining an index corresponding to information to be retrieved from the database and generating a query that does not reveal the index to the database. The query is an arithmetic function of the index and a secret value, wherein the arithmetic function includes a multiplication group specified by a modulus of a random value whose… Show more

A method, article of manufacture and apparatus for performing private retrieval of information from a database is disclosed. In one embodiment, the method comprising obtaining an index corresponding to information to be retrieved from the database and generating a query that does not reveal the index to the database. The query is an arithmetic function of the index and a secret value, wherein the arithmetic function includes a multiplication group specified by a modulus of a random value whose order is divisible by a prime power, such that the prime power is an order of the random value. The secret value is an arithmetic function of the index that comprises a factorization into prime numbers of the modulus. The method further comprises communicating the query to the database for execution of the arithmetic function against the entirety of the database. Show less

A method and apparatus for obtaining access to services of service providers. In one embodiment, the method comprises requesting a desired service through a foreign service provider, generating a hash tree and generating a digital signature on a root value of the hash tree, sending the digital signature and the root value to the foreign service provider, providing one or more tokens to the foreign service provider with the next packet if the foreign service provider accepts the signature and… Show more

A method and apparatus for obtaining access to services of service providers. In one embodiment, the method comprises requesting a desired service through a foreign service provider, generating a hash tree and generating a digital signature on a root value of the hash tree, sending the digital signature and the root value to the foreign service provider, providing one or more tokens to the foreign service provider with the next packet if the foreign service provider accepts the signature and continuing to use the service while the foreign service provider accepts tokens.
Show less

A method and apparatus for obtaining access to services of service providers. In one embodiment, the method comprises requesting a desired service through a foreign service provider. (101), generating a hash tree and generating a digital signature on a root value of the hash tree (102), sending the digital signature and the root value to the foreign service provider (103), providing one or more tokens to the foreign service provider with the next packet if the foreign service provider accepts… Show more

A method and apparatus for obtaining access to services of service providers. In one embodiment, the method comprises requesting a desired service through a foreign service provider. (101), generating a hash tree and generating a digital signature on a root value of the hash tree (102), sending the digital signature and the root value to the foreign service provider (103), providing one or more tokens to the foreign service provider with the next packet if the foreign service provider accepts the signature (105) and continuing to use the service while the foreign service provider accepts token (107).
Show less

Embodiments in accordance with the invention install a primary security browser extension first in the browser event notification order list and a secondary security browser extension last in the event notification order list. On receipt of a user data event including user confidential data at the primary security browser extension, the user confidential data is obfuscated by the primary security browser extension and the user data event including the obfuscated data is released to a next… Show more

Embodiments in accordance with the invention install a primary security browser extension first in the browser event notification order list and a secondary security browser extension last in the event notification order list. On receipt of a user data event including user confidential data at the primary security browser extension, the user confidential data is obfuscated by the primary security browser extension and the user data event including the obfuscated data is released to a next browser extension in the browser event notification order list. Upon receipt of the user data event at the secondary security browser extension, the obfuscated data is restored with the original user confidential data and the user data event is released for further processing. Show less

A certification authority (CA, 120) generates decryption key data (K'.sub.Fj) for each set (F) in the complement cover (804) for a plurality of digital certificates. The CA encrypts all or a portion of the validity proof data (c.sub.j(i)) for each digital certificate (140.i) for each time period j for which the validity proof is to be provided. For each certificate, the decryption can be performed with decryption keys (K.sub.ij) that can be obtained from the decryption key data (K'.sub.Fj) for… Show more

A certification authority (CA, 120) generates decryption key data (K'.sub.Fj) for each set (F) in the complement cover (804) for a plurality of digital certificates. The CA encrypts all or a portion of the validity proof data (c.sub.j(i)) for each digital certificate (140.i) for each time period j for which the validity proof is to be provided. For each certificate, the decryption can be performed with decryption keys (K.sub.ij) that can be obtained from the decryption key data (K'.sub.Fj) for any set containing the certificate. The CA distributes the encrypted portions of the validity proof data to prover systems that will provide validity proofs in the periods j. To perform certificate re-validation in a period j, the CA constructs the complement cover for the set of the revoked certificates, and distributes the decryption key data (K'.sub.Fj) for the sets in the complement cover. In some embodiments, for each period j, the decryption keys (K.sub.ij) are also a function of the decryption key data provided for the preceding periods of time. Therefore, to perform the re-validation, the CA constructs the complement cover not for the set of all the revoked certificates but only for the set of the certificates revoked in the previous period j-1. The complement cover size can therefore be reduced. Other features and embodiments are also provided.
Show less

A method and apparatus for implementing portions of a provisional signature scheme are disclosed. In one embodiment, the method comprises creating a provisional signature by performing an operation on a message and completing the provisional signature to create a final signature on the message. Such a scheme may be used for server assisted signature schemes, designated confirmer signature schemes and blind signature schemes.

Different targets (c.sub.0, N.sub.1) of a digital certificate are mapped into a "super-target" using methods allowing a certificate validity verifier (110) to compute the super-target. The certificate includes the super-target instead of the targets. Also, a certificate with multiple targets can be signed with a redactable signature by the certification authority (CA 120). When the certificate's owner provides the certificate to a verifier together with a validity proof, the owner redacts the… Show more

Different targets (c.sub.0, N.sub.1) of a digital certificate are mapped into a "super-target" using methods allowing a certificate validity verifier (110) to compute the super-target. The certificate includes the super-target instead of the targets. Also, a certificate with multiple targets can be signed with a redactable signature by the certification authority (CA 120). When the certificate's owner provides the certificate to a verifier together with a validity proof, the owner redacts the certificate to delete unnecessary targets. A single validity proof (c.sub.i(F)) may be provided to certificate owners for a set (F) of the certificates via a multicast transmission if a multicasting group (2010) is formed to correspond to the set. Show less

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.sub.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.sup.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… Show more

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.sub.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.sup.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.
Show less

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.sub.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.sup.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… Show more

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.sub.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.sup.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.
Show less