Cryptography – Miscellaneous
Reexamination Certificate
1998-06-16
2001-11-20
Hayes, Gail (Department: 2131)
Cryptography
Miscellaneous
C380S255000, C713S150000, C713S168000
Reexamination Certificate
active
06320966
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to secure cryptographic methods for demonstrating characteristics of privately held data, and more specifically to methods for demonstrating formulas from propositional logic without revealing additional information.
2. Description of the Prior Art
U.S. Pat. No. 5,521,980, filed Feb. 28, 1994, by the present applicant, describes and claims apparatus for demonstrating characteristics of privately held data without revealing additional information. In particular it describes how a prover party, holding one or more secrets, can securely demonstrate a relation that is linear in the secrets. A special case of demonstrating a linear relation pertains to demonstrating that a secret has a certain value.
In one application the privately held data represents a set of credentials that have been issued by some authorized party, and the prover party demonstrates that its credentials have a particular value or that a linear relation applies to the credentials, without revealing additional information. By denoting the absence of a credential by a specially appointed value, typically zero, and its presence by another, typically one, the prover party can demonstrate in this manner that it has or does not have that credential, by demonstrating that the secret representing the credential is one or zero, respectively. Similarly, it can demonstrate possession of exactly one of two such credentials, by demonstrating that the sum of the respective secrets equals 1. In general, in this manner possession of exactly l≧0 out of k≧l credentials can be demonstrated.
While the credential issuing and updating methods described in U.S. Pat. No. 5,521,980 are quite powerful, the method for demonstrating linear relations is seriously limited in functionality.
To demonstrate a system consisting of more than just a single linear relation, it would seem that the method described in U.S. Pat. No. 5,521,980 must be applied repeatedly, once for each relation. It would be desirable to have a method that allows any system of linear relations to be demonstrated by the prover party, without revealing additional information, and without significantly degrading efficiency.
The methods of U.S. Pat. No. 5,521,980 also cannot be applied to demonstrate that a credential that can take on many values does not have a certain value, without revealing information about its actual value.
The method for demonstrating possession of exactly l out of k credentials only applies to yes
o credentials, and does not allow one to demonstrate that one has at least l out of k credentials.
More generally, the methods in U.S. Pat. No. 5,521,980 do not allow to demonstrate arbitrary satisfiable formulas from so-called propositional logic for linear relations; these are formulas that connect atomic propositions by the logical connectives “AND,” “OR,” and “NOT,” the atomic propositions being linear relations over a finite field. “Satisfiable” in this context means that there exists an assignment to the variables in the atomic propositions, such that the formula becomes true. An example of such a formula is “(S
1
AND S
2
) OR (S
3
AND (NOT S
4
)),” where each of S
1
, . . . , S
4
denotes one linear relation involving numbers x
1
, . . . , x
k
; the formula is satisfiable if there is an assignment to (x
1
, . . . , x
k
) such that the formula becomes true. In this interpretation, the methods in U.S. Pat. No. 5,521,980 only allow to demonstrate formulas that connect linear relations by zero logical connectives; it does not allow demonstration of formulas that have one or more logical connectives.
A method is known in the art (see, Cramer, R., Damgard, I., and Schoenmakers, B., “Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols,” Advances in Cryptology—CRYPTO '94, Lecture Notes in Computer Science, Springer-Verlag, 1995) that allows the prover party to demonstrate, for example, that it knows secret keys corresponding to a second and a third public key, or to a fifth public key, without revealing more than that. This method, however, only allows to demonstrate monotone formulas, which are formulas with only “AND” and “OR” connectives: the “NOT” connective cannot be dealt with. More importantly, the atomic propositions for this method are of the form “The prover party knows a secret key corresponding to the i-th public key,” instead of linear relations between secrets.
U.S. Pat. No. 5,521,980 also describes a method for enabling the set of credentials, or part thereof, to be computed by the verifier party in case the prover party demonstrates the exact same linear relation more than once (or, more generally, more times than a predetermined limit). This method requires the prover party to know beforehand which particular linear relation it will have to demonstrate, which is often not desirable. Furthermore it would be desirable to have a method whereby the verifier party is able to compute the set of credentials, or a part thereof, in case the prover party demonstrates any two formulas from propositional logic (i.e., not necessarily the same) for the set of credentials, or any two formulas out of a special category of all such formulas.
Furthermore, the methods in U.S. Pat. No. 5,521,980 do not make any other distinction than between zero-knowledge proofs and signed proofs of formulas. They do not distinguish between how much of the verifier party's conviction can be passed on in case a signed proof was provided, in other words between different flavors of signed proof. In particular, in some cases it may be desirable that the verifier party can pass on its conviction that the prover party knows a set of secrets, but not any information about the formula that has been demonstrated by the prover party; in other cases the verifier party may need to be able to pass on its conviction that the prover party knows a set of secrets, and that the prover party has demonstrated one formula out of a subclass of formulas, without convincing of which one; and in still other cases the verifier party may need to be able to pass on its conviction that the prover party knows a set of secrets, as well as its conviction of the particular formula that the prover party has demonstrated.
The method described in U.S. Pat. No. 5,521,980 for demonstrating linear relations moreover requires the prover party to demonstrate knowledge of a representation with respect to a set of numbers. This set of numbers depends on the particular relation that has to be demonstrated. It would be desirable to have a method for which the set of numbers is always the same, regardless of the formula that has to be demonstrated. This would allow efficient use of the well-known simultaneous repeated squaring technique (see, for example, exercise 27 on page 465 of Knuth, D., “The Art of Computer Programming,” Volume 2/Seminumerical Algorithms, second edition, Addison-Wesley Publishing Company) because only a single table would be needed, containing for each non-empty subset of the set of numbers the product of the numbers in the subset, which could easily be pre-computed once and then stored.
OBJECTS OF THE INVENTION
Accordingly, it is an object of the present invention to:
allow a prover party to demonstrate any system of linear relations pertaining to a set of privately held secrets, without revealing additional information about the secrets;
allow a prover party to demonstrate that a linear relation does not pertain to a set of privately held secrets, without revealing additional information about the secrets;
allow a prover party to demonstrate that a set of privately held secrets satisfies at least some of a specified set of linear relations, without revealing additional information about the secrets;
allow a prover party to demonstrate arbitrary satisfiable formulas from propositional logic, atomic propositions being linear relations pertaining to a set of privately held secrets of the prover party, without revealing additional information about the secrets;
enable a verifier
Fasken Martineau DuMoulin LLP
Hayes Gail
Leaning Jeffrey S
Pillay Kevin
LandOfFree
Cryptographic methods for demonstrating satisfiable formulas... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Cryptographic methods for demonstrating satisfiable formulas..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cryptographic methods for demonstrating satisfiable formulas... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2568966