One-show blind signature systems

The invention relates to a public keyword digital signature method in which private keywords are generated and kept secret by a issuing party, public-key words are publicized by the issuing party, and digitally signed messages from the issuing party and tested by the reviewing party for validity with the public keyword of the reviewer being known.

Such digital signature methods are also known in the art as blind signature methods and are described in EP-A-0 139 313 and EP-A-0 218 305.

The invention further relates to a digital public key signature system having a issuing and a reviewing side; the issuing page has means for generating private keywords, means for publishing public keywords, output means for outputting digital signatures, and means for testing these digital signatures.

Blind signatures can be used relatively directly to build a payment system, as described, for example, in D. Chaum: "Security without identification: Transaction systems to make Big Brother obsolete", Communications of the ACM, October 1985, pp. 1030-1044. For example, in such systems, a bank may charge one dollar for a blind signature. Customers can buy such signatures from the bank, with blind printing preventing the bank from learning which signatures have been purchased and then using them, for example, in a store. In an online transaction with the bank, the business can, upon receipt of a specific signature, check whether this signature has not already been used up elsewhere. If trades fail to pass such a test, someone could use the same number in more than one store, and the blind signature would protect the person from being traced. However, the online exam is often costly or unfavorable.

Another use of blind signatures is in credit mechanisms. These were also introduced in the cited article and have since been detailed in "A secure and privacy-protecting protocol for transmitting personal information between organizations", published in Proceedings of Crypto 86, AM Odlyzko Ed., Springer-Verlag, 1987, by D Chaum and J.-H. Evertse. When creating "digital aliases" when claiming or receiving credit in such mechanisms, an online transaction may be required to ensure that the same alias has not been previously used.

US-A-4 393 269 discloses a method and apparatus for uniquely identifying the identity of a user and the content of a message in a system having a plurality of terminals interconnected via a common transmission channel, wherein a respective pair of at different terminals in Users who have exchanged a contract that includes multiple reference signatures, each of which forms the tail of a single-ended encrypted signature sequence, each of which is a one-way function of the secret encryption key of each user and a number known to both parties. Each terminal connected to the system has means for generating a multi-digit ranking vector, which is a cryptographic function of the entire message to be transmitted.

There are essentially three pages in all blind signature systems: (1) the signature output page, (2) several pages to which signatures are output by the first page, and (3) several pages to which the signatures are presented from the second page. One aspect that could be improved - without reducing the inability to allocate for "honest" second pages - is that the third party must inquire with each other or with a clearing center before accepting a signature; otherwise they would have no handle if it should turn out that the same signature has already been presented to more than one third page.

It is therefore an object of the present invention to provide a digital public key signature system which enables the issuing of signatures from a first page to a second page and the presentation of the signature by the second page at a third page, wherein a cooperation between the First and third page does not lead to finding second pages that submit a signature no more than once.

Another object of the present invention is to enable such unrecoverability unconditionally in the sense that (assuming that the second page presents a signature no more than once) even if the first and third pages have unlimited computing capacity available , a finding remains impossible.

In order to accomplish these objects, the invention provides a method of said type, characterized by the steps of: issuing digital signatures through an issuing party and ensuring by the issuing party that each of the issued signatures contains identification information in its structure; partly presenting the structure of some of the issued signatures before at least one checking page to allow the checking party, with the issuing party the digital signature property of the submitted signatures, while at least a part of the identification information contained in the at most once submitted signatures even before collaboration each examining side and the issuing side remains hidden, so that the identification information can not be derived from the at most once submitted signatures; and testing the submitted signatures by the issuing party to obtain the identification information contained in the signatures submitted more than once, the identification information being derivable from the signatures presented more than once.

The invention further provides a system of the said type, characterized in that a. in that the output devices are designed to output digital signatures which contain identification information in their structure; b. that means are provided on the side of the checking party to check with the issuing party the structure of the signatures when these are partially presented, and means are provided for concealing at least a part of the identification information in the unique signatures submitted; and c. in that the signature test devices are designed to output the identification information in the signatures presented more than once.

Another object of the present invention is to enable the first and third pages to effectively detect a second page that has submitted a single signature more than once and to trace back to the respective output of the signature through the first page.

Another object of the present invention is to be able to perform recognition and tracing at any time after a signature has been submitted more than once.

Another object of the present invention is to enable the second page to code a number in the form of the submitted signature.

Another object of the present invention is to enable this number to represent a value and that the second page be able to receive a refund for the difference between the displayed value and the maximum value at a later time.

A further object of the present invention is to obtain a refund for at least portions of more than one submitted signature, such that the respective originally indicated value is not displayed during the refund.

Another object of the present invention is to provide efficient, economical and practical apparatus and methods which fulfill the other objects of the invention.

Other objects, features and advantages of the present invention will become apparent from the summary of the description and the appended claims with the figures of the drawings.

1 shows a flow chart of a preferred embodiment of a first exemplary protocol for obtaining a one-time dummy signature in accordance with the present invention.

FIG. 2 shows a flowchart of a preferred embodiment of a first exemplary protocol for presenting a once-present dummy signature in accordance with the present invention.

3 shows a flow chart of a first embodiment of a first exemplary multiple template recognition and traceback protocol according to the present invention.

4 is a flow chart of a preferred embodiment of a second exemplary system for obtaining a once-present blind signature in accordance with the present invention as compared to FIG.

5 shows a flowchart of a preferred embodiment of a second exemplary system for presenting a once-present blind signature according to the present invention, compared to FIG.

6 shows a flow chart of a preferred embodiment of a refund signature template system according to the invention for the embodiments of FIG. 4 and FIG. 5.

In accordance with these and other objects of the present invention, a brief description of a preferred embodiment follows. This summary contains simplifications and omissions, as the description is merely illustrative and illustrative of some aspects of the invention, but not limitation of scope. Detailed descriptions of preferred embodiments that enable one skilled in the art to achieve and apply the inventive concepts will be made later.

The basic protocol has three parts: the page P receives from page B a once presentable signature; the page P presents the one-time available signature of the page S; and B detects and tracks signatures that have been submitted more than once. (These letters are mnemonic means for the sake of clarity only and represent the customer, the bank and the business without any limitation of the applications).

B ensures that a particular structure is built into the signatures as they are issued. When presented, certain parts of this structure are disclosed, with the selection of parts at least slightly out of P's control. Even if only a further part of the signature were disclosed, a simple calculation was sufficient to determine an identification means built into the structure of the signature. If the signature were presented a second time, the disclosure of other parts of the structure may be expected to be traceable via the means of identification.

More specifically, a particular case of the preferred embodiment (referred to as t = 1 in the further description) includes a signature over a value in the form f (g (a, c), g (au, d)) where f and g Disposable functions are. When this signature is presented, the pre mappings must be submitted under one of the gs, but it is only necessary to show the mapping of the other g. This data can be tested by S by simply applying the public functions and checking whether the result is the message of the received digital signature.

Suppose the pre-mappings below the other g also become known upon a second submission of the signature. First, it should be noted that the two template events can be easily associated with each other since they have exactly the same image under f. The identification information u would then be easily derivable by simply forming u = a-1 (au), which is a group operation.

The choice of which g is revealed with its arguments can be coded as a single bit. Generally speaking, there are t terms in the signature each having the form shown. A T-bit string represents a query that determines which half of each term will be opened. If these queries differ even in one bit position, enough is uncovered to be able to easily determine u.

Of course, for non-traceability, it is important that a g can not be inverted to reveal its pre-mappings. If the arguments c and d are arbitrarily chosen from a group at least as large as the range of g, it is not possible to unambiguously invert g.

In one variant, an amount, for example a monetary amount, is encoded in a part of the query string. B also outputs other signatures that can be presented only if the corresponding bit of the query string is 0. This allows P to receive change for the unused value. Since these signatures can be separate signatures, change for more than one original signature can be immediately obtained, thus concealing the exact amounts of each payment.

The cryptographic methods and devices described herein may be divided into a basic first embodiment and a second, extended embodiment. In the first embodiment, a first transaction (FIG. 1) allows page P to obtain a signature from page B. A second transaction (Figure 2) allows this signature of P to be accepted by S in response to a number w that may be P a priori unknown. The third transaction allows B to reveal u (an identification information) which associates B with P if, and only if, P submits the signature with sufficiently different w (Figure 3). The second embodiment may use this third transaction as it is, but has a modified output transaction between P and B (Figure 4), a modified template transaction between P and S (Fig. 5) and a transaction between P and B for not recovering (FIG. 6).

While it is believed that the terms in Figs. 1-6 will be understood by those skilled in the art, for the sake of clarity they will first be presented herein.

The operations performed are grouped in flowchart boxes. The column in which a box is located indicates which page performs the operation defined in the box. The columns are indicated by the name of the page at the top. The operation of storing a value under a symbolic name is indicated by the symbolic name on the left side of an equals sign and an expression for the value on the right. Another type of surgery is the equality test. The symbol "? =?" The test serves to display these tests, and the page to be tested ends the protocol if the test is negative. (If the test is the last operation performed from a page during a protocol, the success or failure of the test determines the success or failure of the page in the protocol). The last type of operation is sending a message. This is represented by a message number on the left, followed by the name of the recipient's page and an arrow (appearing for readability either as the recipient's name followed by the left arrow when the recipient is on the left or as the right Arrow followed by the recipient's name if the recipient is on the right), followed by a colon and finally an expression, indicating the actual value of the message to be sent.

Several types of expressions are used. One is just the word "random". This means that a value is preferably chosen consistently from a suitable group defined in the text and independent of anything else in the protocol. Thus, a page should preferably use a physical random number generator for this purpose, possibly with appropriate post-processing. However, in practice, known cryptographic and pseudorandom methods may be used in conjunction with physical sources.

Another type of expression involves exponential calculation. The total exponential calculation preferably takes place via the residual amounts on the basis of a composite number M whose factorization is preferably only available on side B, these moduli being known per se and first being described in "A method for obtaining digital signatures and public-key cryptosystems". , by Rivest, Shamir and Adleman, Communications of the ACM, February 1978, pp. 120-126. If no operation is explicitly specified, a multiplication modulo M is assumed.

Different public exponents can be used with the module M. In Figs. 1, 2, and 3, only the public exponent p is used. This may be any suitable number: 2, a low odd prime, a prime large enough to ensure that it is a co prime to the order of the reduced residue system, or another integer. In the extension of Figs. 4, 5 and 6, p = GCD (p (1), p (2), ..., p (t)) and q = GCD (q (1), q (2)) ..., q (t)). p (i) and q (i) can each have a certain prime factor as well as other common factors; they can also have increasing amounts of one or more factors. For example, p (i) = 2i and q (i) = 2i are considered to be safe and economical to compute, especially when the convention assumes that smaller exponents represent smaller values.

Even public exponents require special attention, as would be understood by one skilled in the art, since square roots do not exist for many residuals. Thus, the selection of the things to be signed by B (which are determined by the group denoted v, as will be described later) necessarily excludes the non-signable. Another approach to this problem is to apply the known special composite form with exactly two factors that are respectively congruent to 3 modulo 4: the obscuring factors randomly show a standard public non-square number with the Jacobi symbol 1 together with a figure below f adapted to obtain the Jacobi symbol 1; in each term of a signature under a certain even exponent, after an option for B, the public non-square number would be included under the signature, and signatures of figures below f would be accepted with an arbitrary multiple of the public non-square number. It should also be noted that when the public non-square number is substituted by both sides, it can be taken from P by the signature if the square root is also public. Of course, care must be taken to ensure that s is large enough to keep acceptably low the chance that a square root in a selected message will be known to a cheater.

If "/" is used in the base, the multiplicative inverse is first calculated for the right side expression and then multiplied by the expression on the left side; if it is used by B in the exponent, the women designate the same situation as just described, but the arithmetic is a modulus of the order of the group of residual moduli M; if it is used from a page other than B in the exponent, it denotes an integer division. The results of all operations are coded as binary integers for the sake of simplicity and clarity (the least positive representative is assumed to be residual classes). The concatenation labeled "" is thus defined as juxtaposition of the value-representing bit vectors.

The functions f and g are preferably publicly agreed one-way functions with (supposedly) two arguments, such functions being well known in the art. Any map under g can be assumed to be adaptive as an argument to f, and any map below f can be represented as residual modulo M, all in a standard fashion. These functions should preferably be "collision-free" in that it is difficult to find more than one valid argument pair that yields the same result, which is a property generally achieved in cryptography.

Another desirable property of g is that for every single allowable first argument, there are the same number of second arguments that produce each possible output; in other words, setting a first argument results in a k-to-one mapping from the second argument to the output. This novel and inventive feature offers the advantage of "unconditional" protection against traceability; that is, even infinite computational power is unable to determine the first argument of a g, if only the result exists. In any case, functions with such properties or properties close in absolute or purely computational sense may have similar benefits. Since a "random" one-way function of concatenating the arguments (appropriate size) closely approximates the desired properties, it can be assumed that almost any one-way function can be used.

An example of the manner of creating such a preferred function is the application of a one-way bijective function, known in public key cryptography as the group's "discrete-log" problems, to the second argument and using the associated one Group operation for combining the result with the mapping under a one-way function of the first argument. For example, the first argument may use, as the exponent of a primitive element modulo, a first large prime and the result (possibly after applying, for example, DES with a fixed key or the like) may, modulo a second large prime number, result in the elevation of a primitive element modulo the second prime number are added to the second argument power. A bijective post-encryption of the final result can be done by the final application of, for example, DES with a fixed key; A similar pre-encryption of each of the original two arguments can also be used.

The infix operator "" denotes the group operation of addition modulo a prime number that is as large as each u, as will be described. It will be apparent to those skilled in the art how to use a bitwise exclusive-or operation or other suitable group operation.

Indexes of both symbolic names and message numbers indicate indices that are above the natural numbers for clarity; the group notation (including the group difference) is used to indicate the ordered groups over which they extend. Symbolic names i, j and k are used as indices. As usual, the cardinal property of groups is indicated by surrounding "" symbols. A special operation represented as "@" is used for the sake of clarity as a prefix of the symbolic name of an index; it denotes the position of the index within the ordered index group. (For example, if i {3, 1, 4} and g 1, g 2, g 3, g 4 = 4, 8, 1, 7, then g i = 1, 4, 7 and g i + g @ i = 5, 12, 8). The usual notation Π is used for products modulo M, where the index in the expression following Π runs over the entire index group.

The two parameters s and t are considered known and accepted by all pages using them; they determine the size of the index groups used and increasing them increases security. Very high safety is expected from t = 100 and s = 200, but in practice much lower values ​​can be used. This is especially true when several cases of Fig. 1 are merged, as described below. The value of u is at least P and B known and may be a distinctive identifying means for the particular transaction or for said combined transactions.

Referring to Fig. 1, the first part of a flowchart for the preferred embodiment will be described below.

Box 101 shows that P ri, ai, ci, and di, as previously described, randomly select, where i extends over the first s natural numbers. The ri are used by raising in public exponents to form "masking factors", and are thus preferably chosen from [1, ...., M-1] as known in the art. The ai are preferably uniform to reduce the chance of two customers choosing the same. ci and di are used as a second argument for g, and are thus preferably chosen to maximize the desired properties already described for g, for example by uniformly choosing them from the range of the second argument of g. P then computes xi by applying g to the corresponding ai as the first argument and ci as the second argument. Subsequently, the yi are calculated similarly, but each ai is combined with u by the group operation to form the first argument for g, and the di are used as the second argument, with the result symbolically called the corresponding yi. Subsequently, s messages are formed and sent to B as indicated by the notation already described. The i-th message [11.1] i is a product modulo M raised from ri to the pth power of f, applied to the first argument xi and the second argument yi.

Box 102 indicates that after receiving the messages [11.1], v first randomly selects uniformly from the subgroups of [1 .... s] with the cardinality st and then sends this subgroup back to P as message [12].

Box 103 first describes how P checks whether the cardinality of subgroup st received as message [12] is st. As required by the notation already defined, P stops the process if this test does not turn out positive; otherwise, P continues by first assigning index j to this group. Then, messages [13.1] j, [13.2] j, [13.3] j and [13.4] j are formed from rj, aj, cj and dj and sent to B.

Box 104 defines the actions of C upon receipt of messages [13.1] j, [13.2] j, [13.3] j and [13.4] j. For all the indices j in the group v, the message [11.1] j is compared for equality with the product modulo M of the message [13.1] j in the pth power of a map under f of its two arguments, each of which is a map under g is. The first application of g has the message [13.2] j as its first argument and [13.3] j as its second; the second has a first argument consisting of the message [13.2] j combined with u using the operation and a second argument [13.4] j. If all j pass the test, B continues. Then let k pass over all elements in {1, ..., s}, not in v. The product of all [11.1] k is formed and modulo M raised to the 1 / p power, which, as described, denotes the pth root. This value is supplied to P as the message [14].

Box 105 indicates that P initially sets k to extend over all elements in {1, ..., s} not contained in [12]. Subsequently, the received message [14] is raised to the pth power modulo M and compared for equality with the product modulo M of all of k indexed [11.1]. After passing the test, P continues by setting n as the product modulo M of the message [14] multiplied by the multiplicative inverse of the product of all rk. Finally, ak, ck, dk, xk, and yk are assigned new subscripts: the first item in the ordered index group over which j is ranked, the ai receiving the new index 1 selects the second item in the index group of j which determines Element gets the index 2, and so on for all elements in the index group; the same applies to ck, dk, xk and yk.

In the following, the second flowchart for a part of the preferred embodiment will be described in detail with reference to FIG.

Box 201 begins by sending the message [21.1] from P to S, which includes the value of n calculated in box 105 as described. The index set for i is the first t natural number. Then, for each value of i, a message [21.2] i is sent after being formed as a map under f with the first argument x'i and the second argument y'i.

Box 202 shows that S first randomly selects the index group w from all subgroups of {1, ..., t}. Then, S tests the power p of the message [21.1] for equality with the product of all [21.2] i, all modulo M. If the test passes, S continues to send the message [22], where w is supplied to P.

The box 203 describes the fulfillment of the query defined by the message [22] received from P. For the elements j in [22], a'j, c'j and y'j are sent to S as message [23.1] j, [23.2] j and [23.3] j; for the elements k in [1, ..., t], but not in [22], x'k, a'k u and d'k are written as messages [23.4] k, [23.5] k and [23.6] k sent.

Box 204 shows receiving and checking [23.1] to [23.6] by S. For each of the j in w, message [21.2] j is tested for equality with the mapping under f of two arguments: first, the mapping under g of [23.1] j and [23.2] j, in that order; second [23.3] k. For any k not contained in w, but in {1, ..., t}, the message [21.2] k is tested for equality with the mapping under f of two arguments: first [23.4] k; second, the mapping under g of [23.5] k and [23.6] k, in that order.

Referring now to Fig. 3, the third flowchart for a part of the preferred embodiment will be described below.

Box 301 shows how B first receives and stores [21.2] of each S.

Box 302 then indicates that B is searching for duplicities among those received in box 301 [21.2]. In one embodiment, [21.2] is suitably stored upon receipt in [301], which is well-suited for detecting duplications. (It will be appreciated by those skilled in the art that so-called "hashing" may be a suitable data structure for this purpose, and since these are already mappings under a one-way function, some of their bits may be used directly as hash values.) Another example would be storing many [21.2] as a disordered group and then periodically sorting the received [21.2] and, if possible, incorporating it into other already received [21.2]. In computer science, various ways of detecting such duplicities based on sorting or search techniques are known.

Box 303 shows that B receives messages [23.1] and [23.5], whichever are available, which correspond to at least two instances of a particular value of [21.1] recognized as repeated in 302. It is expected that these will be supplied by each S who have delivered the double [21.2]. For example, they may be supplied by the S together with [21.2]; when sorting the group in 302, B can archive [23.1] and [23.5] and find those that match duplicates as needed. On the other hand, if, for example, [23.1] and [23.5] are not supplied together with [21.2], then B may request them individually from the S, if B is known, which S [23.2] has delivered.

Box 304 shows how B can reconstruct the u corresponding to a particular [21.2] for which both [23.1] and [23.5] are known. This is achieved simply by combining the inverse in the group of [23.1] with the [23.1] using the group operation.

Referring to Fig. 4, the fourth flowchart of a part of the preferred embodiment will be described below.

The boxes in this flow chart indicate the modifications of the corresponding boxes in Fig. 1 which serve to form the second embodiment; for the sake of clarity and readability, only the changes are shown. Specifically, the boxes 401, 302, 403, 404 and 405 represent changes of the boxes 101, 102, 103, 104 and 105.

Box 401 shows the changes in actions defined in box 101 for P. The definition of a symbolic name a used in box 101 is replaced by that in box 401; otherwise, the operations and messages in the box 401 define only additional actions that should be included in the box 101 for the second embodiment. Values ​​of the i-th component (1≤i≤s) of four symbolic names are chosen at random: r "i is chosen from the group of modulo M residues; a" i is a string of just enough length, a group element to take up; bi is chosen as a bit string whose length after attachment to a "i has the appropriate size for the first input in g, and ei is chosen to be similar to ci and di in FIG. (It should be noted that u can be chosen by B and need not contain the amount of information required for ai, since it need not be protected against problems induced by the "Birthday Paradox"; thus, it can be expected that group elements under suitably leave sufficient space in the first argument of g that a suitably large b can be accommodated.) For each index i that continues to range from 1 to s, the value of ai is considered to be the Concatenation of a "i and bi, where the part bi occupies higher bit positions (which do not survive the defined modular addition).

Coding the result as a bit string is the first input to g used to form xi in FIG. The coding and the group operation in forming yi in Fig. 1 leave no information about b in the first argument for this g. Further, zi is used as the map under g formed of bi as the first argument and ei as the second argument. The message [11.2] i, which contains the corresponding zi concealed by multiplying modulo M by r'i raised to the power q, is sent to B.

The box 402 is equal to the box 102, where the receipt of the message [11.2] i is implicit.

Box 403 indicates three additional messages included in those described in box 103. For each j, as defined in 103, the messages sent by B [13.5] j, [13.6] j, and [13.7] j contain the values ​​r "j, bj and ej.

Box 404 shows the changes in box 104, all of which are trapped except for the fact that the message [14] is not sent. Each message [11.2] j is tested for equality with the product of the corresponding received message [13.5] j, which is raised to the power q, and a map under g. The first argument for g is the received message [13.6] j, and the second is the received [13.7] j. If equality is detected, messages [14.1] and [14.2] k are formed and sent to P. Every term in the product modulo M which forms [14.1] is the pth root modulo M of [11.1] k; the [11.1] k, whose index is the first element in the ordered group v- {1, ..., s}, gets the p (1) th root, the message whose index is the second element in the group , gets the p (2) th root and so on down to the last element in the group. For each value of k passing through the same index group, the message [14.2] k is formed as the q (@ k) -th root modulo M of the message [11.2] k; thus, for example, the message having the q (i) th root has the index 1 and is formed of a message whose index is the ith element in the ordered index group v- [1, ..., s}.

The box 405 represents the changes of box 105 to P: the definition of the symbolic name n used in box 105 is replaced by that of box 405; otherwise, the operations and messages of box 405 only define additional actions. First, the message [14.1] raised to the power p is checked for equality with a product of powers of [11.1] k modulo M. The term corresponding to each index value of k in the index group defined in 105 is [11.1] k, raised to a power that is the integer quotient of p divided by p (i), where i is the position of this (as @ k) in the index group. Then, n is formed as the product of the message [14.1] multiplied by the multiplicative inverse of a product rk. Each term in this product corresponds to one of the elements in the index group of k, where the base is rk and the exponent is the integer quotient p divided by p (@k). Then, mk is formed as the product of the message [14.2] k multiplied by the multiplicative inverse of a product rk. Each of these corresponds to one of the elements in the index group of k, where the base r "k and the exponent is the integer quotient q divided by q (@ k). Finally, the elements of bk and ek are re-indexed and renamed as b 'and e' for later use. The index of retained items is their item number in the index group over which k is ranked.

The fifth flowchart for a part of the preferred embodiment will be described below with reference to FIG. 5.

The box 501 shows that the box 201 needs no change for this second embodiment.

Box 502 expresses the changes in box 202 which include the replacement of the equality test and a possible change in w to include some or all non-random parts, which may mean that agreed items of w correspond to one value unit, respectively, and that when such an element occurs in w, this indicates a transfer of an amount corresponding to this value unit. The new test concerns the equality of [21.1], raised to the power p, and a product modulo M of t terms (1≤i≤t), each in the form [21.1] i, raised to the integer power p divided by the integer power p (i).

The box 503 indicates that the box 203 does not need to be changed except that any possibly non-random parts of w that can be expected are checked, as already described.

The box 504 merely confirms that the box 204 for the second embodiment need not be changed.

In the following, the sixth flowchart for a part of the preferred embodiment will be described in detail with reference to FIG.

This figure represents a transaction between P and B which, as already mentioned, was not described for the first embodiment.

Box 601 shows that P sends four messages to B: [61.1], [61.2], [61.3], and [61.4], which include i, mi, b'i, and e'i.

Box 602 shows how B first receives these four messages and stores [61.1] under the symbolic name h. Then B tests equality: the left side is the message [61.2], raised to the power p (h), and on the right is g, applied to the first argument message [61.3] and the second argument message [61]. 61.4]. Finally, B searches all previously accepted [61.3] to make sure that the new [61.3] is not below them before it must be assumed to be included; Similarly, B also checks whether the suffix of the received message [61.3] (beyond the prefix whose length corresponds to that of a ") is not the suffix of any message [23.1] that is used in the modification of FIG. 2 was received.

Certain modifications and substitutions will be apparent to those skilled in the art.

In the protocol of Fig. 2, a one-way possibly-compressing function of xi and yi would be sufficient to indicate their order in place of the messages [21.2] j P. (Even such a compressed mapping is unnecessary if there is agreement that the order of the images should be lexicographically on their binary representations, as also mentioned below in connection with FIG. 4 and FIG. 5). As a further illustrative example, the amount of data that P must store between FIGS. 1 and 2 may be reduced below what is represented, for example, by not retaining x 'and y' and simply reconstructing them, such as this was done for f in the box 201.

Instead of the stated specific occlusion, which is essentially that of the first mentioned blind signature publication, the method according to the second named blind signature publication could be used. Further, the signature scheme denoted by the public exponent q could have a different modulus or even be a completely different type of signature, such as in the co-pending application entitled "Unanticipated signature systems", US application number 123703 filed by the Applicant on the 23rd November, 1987. Such signatures could also relate to the products of terms, for example those under p, where several parts of the protocol of FIG. 4 would be executed by a certain P before the [14.2] are returned. These parts may be executed such that B receives all the messages [11] before issuing multiple interrogation sets v, the only limitation being that they are discontinuous and have the cardinality t. Furthermore, this approach could also be used in the application of the method of FIG. 1. The signatures of the first embodiment could also use different public exponents for different terms, as in the second embodiment of the case; or the second embodiment requires only a single public exponent when using the aforementioned lexicographical ordering method. (In the case of Fig. 4 For example, if the order were to be sent as [11.3], it would be checked by B as part of the tests in box 404 for the jth entries.)

Another variant would be the provision of more g in one f. The u could be divided among these g by known methods, which are referred to inter alia as "key-sharing", "shadow" or "partial key". A number below the so-called "threshold" of these procedures would be the number of g whose arguments are to be revealed during submission.