One-show blind signature systems

Description: TECHNICAL FIELD [Detailed description of the invention]

Background of the invention 1. Field of invention The present invention relates to cryptographic systems, in particular public key digital signature systems that provide non-linkability. 2. Description of prior art The blind signatures are the European Patent Publication No. 0,139,313 (February 5, 1985) and the US Patent Application No. 784,999 Unanticipated blind signature of the priority claim based on the US Patent Application No. 524,896 Blind signature system by the Applicant. It is technically known as described in European Patent Publication No. 0,218,305 (April 15, 1987), which claims priority based on "system". These signatures (for example, Security without identification: Transaction systems to make Big-Brother on pages 1030-1044 of ACM Communications) It can be used rather directly to configure a payment system (as described in obsolete "(October 1985). In such a system, banks spend, for example, $ 1 to blind signature. Billing. People can buy such signatures from banks (blinding makes it impossible for banks to know which signatures people bought), for example at a store using that signature. The store is specific. When you receive the signature, it will be checked by the bank and online processing to make sure it is no longer in use somewhere else. If the store does not do such a check, someone will have more than one place. You can use the same number in your store and blind signatures prevent you from tracking someone, but online checks can be costly and infeasible in many applications. Another use for blind signatures is in the confidence guarantee mechanism. These mechanisms are also introduced in the above literature, and also A secure and privacy-protectig protocol for trasnmitting personal information between. Introduced in detail in "organizations" (published by the Applicant and JHEvertse in the Proceedings of Crypto86, AMOdlyzko, Ed., Springer-Verlag 1987). Once the "pen name" is defined, it is necessary to perform an online process to ensure that the same pen name has not been used before. In all of these systems, (1) the equipment owned by the person at the time of the signature issuance, (2) the equipment owned by multiple parties to whom the signature is issued by the equipment owned by the first party, and (3) the second party. There are substantially three types of party-owned equipment of multiple party-owned equipment for which a signature is presented by the owner-owned equipment of. One aspect that can be improved without reducing the impossibility of linking to the "honest" second party's owning device is another or some bill center before the third party's owning device receives the signature. It is something that must be checked at. Otherwise, the third party will be unreliable if it turns out that the same signature has already been presented to the owned equipment of two or more third parties. Purpose of the invention Therefore, a first object of the present invention is to issue a signature to a device owned by a second party by a device owned by the first party, and the device owned by the second party becomes a device owned by the third party. Public key digital that allows the signature to be presented and cannot track the second party's owned device that has not presented the signature more than once even if the first and third party's owned devices cooperate. To provide a signature system. Another object of the present invention is to make unlimited computer resources available to the first and third parties, even if the second party's own device does not present a signature more than once. It is to make such untraceableness absolute, even in the sense that it remains untraceable. Yet another object of the present invention is to enable the owned devices of the first and third parties to efficiently discover and track the owned devices of the second party who present one signature more than once (first). Return to the specific issuance of the signature by the party's owning device). An additional object of the present invention is to allow the discovery and tracking at any time after the signature has been presented more than once. Yet another object of the present invention is to allow a second party's own device to encode a number within the form of the signature presented. Yet another object of the present invention is to allow the second party's own device to later receive a refund for the difference between the offered value and the maximum value, the number representing the value. Yet another object of the present invention is to receive a refund of value for at least one copy of two or more signatures presented in such a way that the particular value originally presented is not revealed during the refund. Is to be able to do. Yet another object of the present invention is to provide an effective, economical and practical device and method for achieving the other object of the present invention. Other objects, features and advantages of the present invention may be understood by reading this description and the appended claims along with the drawings. A brief description of the drawing FIG. 1 shows a flowchart of a preferred embodiment of a first exemplary one-present blind signature acquisition protocol according to the invention. FIG. 2 shows a flowchart of a preferred embodiment of the first exemplary single presentation blind signature presentation protocol according to the invention. FIG. 3 shows a flowchart of a preferred embodiment of the first exemplary multiple presentation detection and tracking protocol according to the invention. FIG. 4 shows a flowchart of a preferred embodiment of a second exemplary single presentation blind signature acquisition system extended from FIG. 1 according to the present invention. FIG. 5 shows a flowchart of a preferred embodiment of a second exemplary single presentation blind signature presentation system extended to FIG. 2 according to the present invention. FIG. 6 shows a flowchart of a preferred embodiment of the refund signature presentation system for the exemplary embodiments of FIGS. 4 and 5 according to the present invention. A brief summary of the invention A brief summary of exemplary examples is provided according to these and other purposes of the present invention. Some simplifications and omissions have been made in this brief summary, but only to emphasize and introduce some aspects of the invention and limit the technical scope of the invention. It is not intended to be done. A detailed description of preferred exemplary embodiments suitable for enabling those skilled in the art to produce and use the invention concept will be given later. The basic protocol consists of three parts: the device owned by the party P obtains a one-time presentation signature from the device owned by the person B, and the device owned by the person P presents the one-time presentation signature to the device owned by the person S. That consists of the device owned by Party B at the time detecting and tracking signatures presented more than once (these letters represent payers, banks and stores without any restrictions in application). It was chosen as a means of storage only for clarification). When the signature is issued, some structure guaranteed by Party B's owning device is incorporated into the signature. When the signature is presented, some parts of this structure are revealed, and the choice of which parts are revealed is at least outside the limits of Party P's owning equipment. Once two or more parts of the signature are revealed, a simple calculation can determine the identifier embedded in the structure of the signature. If the signature is presented twice, it can be predicted that different parts of the structure will be revealed and can be tracked by identifiers. More specifically, the signature in the value of the form f (g (a, c), g (au, d)) in certain cases of the preferred embodiment (indicated later as t = 100). including. Where f and g are one-way functions. When this signature is presented, the foreground image of one of the plurality of functions g must be presented to the party S's owning device, while the other function g need only present that image. This data can be inspected by the party S's owning device by simply applying a public function to this data and checking the outcome of the digitally signed message received. It is assumed that the foreground image in the other function g is also known by the second presentation of the signature. The first notable point is that the two presentations are easily related to each other because they contain the exact same image in the function f. The identification information u is simply u = a^-1It is easily obtained by forming (au). Is a group operation. The choice of which function g reveals its arguments can be encoded as a single bit. More generally, there is a t term in the signature, each in the same form as presented. The t-bit string is a challenge to determine which half of the t term is exposed. If this challenge is different even at the 1-bit position, it becomes clear that there is enough to make u easy to determine. Of course, due to untraceability, it is necessary that the function g cannot be reversed in order to reproduce its foreground image. It is not possible to uniquely reverse the function g if the arguments of c and d are randomly selected from a set that is at least as large as the range of the function g. The variable encodes, for example, the total amount of money in some part of the challenge string. Other signatures that can only be presented if the corresponding bit of the challenge string is presented as 0 are also issued by Party B's owning device. These allow the then-owner P's equipment to earn change for unused value. However, since these may be individual signatures, change from two or more original signatures can be obtained at one time, thereby hiding the exact total amount used in the individual payments. General description The cryptographic methods and means described herein are divided into a basic first embodiment and a second extended embodiment. In the first embodiment, the first process (FIG. 1) allows party P's own device to obtain a signature from party B's own device. The second process (Figure 2) allows this signature from party P's own device to be accepted by party S's own device in response to a number w previously unknown to party P's own device. .. The third process allows party B's own device to expose the u (identifier) associated with party P's own device only if party P's own device presents a signature with a completely different w (third). 3 figure). The second embodiment can use this unmodified third process, but with the modified issuance process between the party P's own device and the party B's own device (Figure 4) and the parties. A modified presentation process between P's owning device and Party S's own device (Fig. 5) and an unpresented return request process between Party P's own device and Party B's own device (Fig. 6). Have. Detailed description of preferred embodiments The notation of FIGS. 1 to 6 is obvious to those skilled in the art, but will be outlined here first for clarity. The operations or actions performed are grouped together in a flow chart box. The column in which the box is located indicates the party-owned device that performs the operation or operation specified within the box. The columns are labeled by the name of the party's owning equipment that traverses above. The operation of saving a value based on the symbol name is represented by the symbol name on the left side of the sign and the expression for the value on the right side of the equal sign. Another type of operation is equation checking. The ? =? Symbol is used to indicate this check, and if the test is not maintained, the inspecting party's own device terminates the protocol (this check should be performed by the party's own device during the protocol). If it is the final operation, the success or failure of the check determines the success or failure of the party's own device by the protocol). The final kind of action is to send a message. This is indicated by the message number on the left. This is followed by the name of the receiving party's owning device and an arrow (for readability, if the receiving party's owning device is located on the left, then the name of the receiving party's owning device, followed by an arrow pointing to the left, and If the recipient's own device is located on the right side, it is represented as the name of the recipient's own device next to the arrow pointing to the right). This is followed by a colon, followed by an expression that indicates the actual value of the message to be sent. Several types of expressions are used. One is the word "random". This indicates that it is preferable that the values be selected evenly from the appropriate set specified in the specification and independent of everything else in the protocol. Therefore, for these purposes, it is preferred that the party's own equipment probably use a physical random number generator with appropriate post-processing. However, in practice, well-known cryptography and pseudo-random techniques can be applied, perhaps in combination with physical sources. Other types of expressions include exponential methods. All such exponential methods are preferably for the remainder modulo composite number M. The prime factorization of M is preferably available only to the devices owned by Part B, and such a method is "A method for obtaining digital signatures and public-key cryaptosystems" (by Rivest, Shamir and Adleman, Communications of the). It is technically well known as first proposed in ACM, February 1978, pp.120-126). If the operation is not clearly shown, M-wise multiplication is assumed. Different public indices can be used with Law M. In Figures 1 to 3, only the public index p is used. This can be any suitable number, i.e. 2, a properly sized odd prime number, a prime number large enough to be coprime to the order of the irreducible remainder system, or any other integer. .. In the extended examples of FIGS. 4 to 6, p = GCD (p (1), p (2), ........., p (t)) and q = GCD (q (1)). ), Q (2), ........., q (t)). Each of p (i) and q (i) may contain other common factors with different prime factors, or may contain increasing multiplicity of factors. For example, p (i) = 2 especially if the rule is that smaller indices represent smaller monetary units.ⁱAnd q (i) = 2ⁱIs reliable in the calculations and is believed to provide efficient use. Even-numbered public indices require special attention, as will be apparent to those skilled in the art, for one reason that there is no square root for many remainders. Therefore, the choice of what to sign by a device owned by one of ordinary skill in the art B (determined by a set called v as described below) inevitably avoids unsignability. Another way to deal with this problem is by applying a well-known specific composite number form with exactly two prime factors congruent with three, each of which is the method of 4, with the blind coefficient having the Jacobi symbol 1. Randomly include a standard open non-square root with the Jacobi symbol 1 along with the image in the function f so tuned. Each term of the signature in a different even index has a public non-square number included under the signature, at the option of the owned device of Party B. The signature of the image in the function f with an arbitrary multiple of the open non-square number is accepted. More notably, if the devices owned by both parties enter a public non-square number, the square root can also be retrieved from the signature by the device owned by Party P when it is also published. Of course, care must also be taken to ensure that s is large enough so that the square root on the selected message is small enough to allow the chances of being known by fraudsters. When the "/" is used in the base, the multiplicative reciprocal is first calculated for the expression on the right and then multiplied by the expression on the left. When used in an exponent by Party B's owning device, it represents exactly the same operation as just described, but the calculation is modulo the order of the remainder modulo M. When used in an exponent by a device owned by a party other than the device owned by party B, it represents an integer division. The results of all operations are coded as binary integers for convenience and clarity (minimum positive representation is taken for cosets). Therefore, the concatenation represented by "||" is defined as the juxtaposition of bit vectors representing values. The functions f and g are preferably publicly agreed one-way functions (think of) with two arguments, and such functions are technically well known. Each image in function g is assumed to fit as an argument to function f, and in all some standard methods, each image in function f can then be represented as a remainder modulo M. These functions can be "collision-free" in the sense that it is difficult to find two or more valid argument pairs that give rise to the same result, that is, the properties normally achieved in cryptography. preferable. A more desirable property of the function g is that for each particular allowed first argument, there are the same number of second arguments, each producing a possible output, in other words, any first argument. If you fix the argument of, a k-to-1 map is provided to the output from the second argument. This new and original property will provide the benefit of "unconditional" protection for tracking. That is, it seems that even infinite computational power cannot determine the first argument of the function g given only the result. In any case, a function having such properties or appearing to be close to them in some absolute or simply computational sense can provide similar benefits. Most arbitrary one-way functions can be used, as it is expected that the "random" one-way function from the concatenation of the (properly sized) arguments will come very close to the desired property. It is thought that it can be done. One exemplary method for achieving such a preferred function is to take a bijective one-way function as the second argument, as is well known in public-key cryptography as the "discrete logarithm" problem for some group. Applying to it, it is to use the group operation involved in combining the image based on the one-way function of the first argument with the result. For example, the first argument may be used as an exponent of primitive elements modulo the first large prime number, and the result (perhaps after applying a DES with a fixed key or something similar) , The primitive element modulo the second prime number is added to the result of the second argument. A bijective post-scramble process of the final result is provided, for example by the final application of DES with a fixed key, and similar pre-scramble processes for each of the original two arguments may also be used. The insertion operator "" is an additive group operation modulo a prime number as large as any u, as explained. It will be apparent to those skilled in the art how to use bit-by-bit exclusive OR or any suitable group operation. Suffixes in both symbolic names and message numbers indicate subscripts taken for natural numbers for clarity, and set notation (including set differences) is used to indicate the ordered set in which they move. There is. The symbol names i, j, k are used as subscripts. The cardinality of the sets (original number) is indicated by enclosing them with a "|" symbol as is normally done. The special operation shown as @ is used as a prefix in the subscript symbol name for clarity, which indicates the position of the subscript in its ordinal index set (eg if i {3,,). If 1,4} and g1, g2, g3, g4 = 4,8,1,7, then gi = 1,4,7 and gi = g @ i = 5,12,8). The usual Π notation is used for products modulo M, where the subscripts in the formula following Π are taken to change for the entire index set. It is assumed that the two parameters s and t are known and agreed by all parties using them. These parameters determine the size of the index set used, and increasing them increases safety. Very high safety may result from adopting t = 100 and s = 200, but in practice much smaller values can be used. This is especially true when multiple instances of Figure 1 are done together, as described below. The value of u is known at least to the device owned by Party P and the device owned by Party B and is a unique identifier for a particular process or a combination of processes as described above. The first part of the flowchart of the preferred embodiment will be described in detail with reference to FIG. Box 101 indicates that the device owned by Party P selects ri, ai, ci and di by random selection as already mentioned, where i is the first s natural numbers. ri are used to form "blind coefficients" by exponentiation, so they are selected from {1, ......, M-1} as technically known. It is preferable to do so. The ai is preferably uniform so that the devices owned by two different payers reduce the chances of choosing the same one. ci and di are used as the second argument to the function g, so it is preferable to choose to maximize the desired properties already described for the function g, eg the domain of the second argument of the function g. Is uniformly selected from. The owned device of party P then computes xi by applying the function g to the corresponding ai as the first argument and to the ci as the second argument. Then yi is calculated in the same way. However, each ai is combined with u by a group operation to form the first argument to the function g, di is taken as the second argument, and the result is symbolically shown as the corresponding yi. Then s messages are formed and sent to Party B's own device as indicated by the notation already described. The i-th message [11.1] i is the product of the function f applied to the first argument xi and the second argument yi multiplied by p of ri, modulo M. Box 102 selects v uniformly and randomly from the subset of {1, ......, s} in which Party B's own device first has the concentration st after receiving message [11.1], and then this Indicates that the subset is returned as a message [12] to the party P's owning device. Box 103 first shows how the owned device of Party P checks that the concentration of this subset received as message [12] is st. As required by the notation already defined, if this test is not satisfied, the party P's own device ceases to operate, otherwise the party P's own device first subscripts the range of this set. Continues operation by assigning. Then the messages [13.1] j, [13.2] j, [13.3] j, [13.4] j are formed from rj, aj, cj, dj, respectively and sent to the party B's own device. Box 104 defines the operation of the owned device of Party B after receiving the message [13.1] j, [13.2] j, [13.3] j, [13.4] j. For all subscripts j in the set v, the message [11.1] j is the image in the function f of the two arguments, each of which is the image in the function g, multiplied by the pth power of the message [13.1] j. The product is compared for equality inspection. The first application of the function g has message [13.2] j as its first argument and message [13.3] j as its second argument. The second application of the function g has a first argument and a second argument [13.4] j consisting of the message [13.2] j combined using u and the operation. If this check passes for all j, the party B's own device continues to operate. Then k can move over all the elements in {1, ......, s} that are not in v. Using M as a method, the product of all messages [11.1] k is formed and raised to the power of 1 / p, which indicates the p-th root as described above. This value is then given to party P's owning device as message [14]. Box 105 indicates that the device owned by the then-P is initially set to move over all elements in {1, ......, s} that are not in message [12]. ing. The received message [14] is then raised to the p-th power with M as the law and compared with the product of all messages [11.1] subscripted by k with M as the law for equality checking. If this check is passed, the party P's owning device proceeds to set n to the product of the message [14] multiplied by the multiplicative reciprocal of the product of all rks, with M as the law. Finally, ak, ck, dk, xk, yk are assigned to the new subscripts. The first element in the ordered index set in which j moves selects ai that receives the new index 1, and the second element in the index set of j determines which element obtains the index 2, and all of the index sets. The same is true for elements, and the same is true for ck, xk, yk. A second flowchart for a preferred embodiment will be described in detail with reference to FIG. Box 201 is initiated by the device owned by party P sending a message [21.1] containing the value of n calculated in box 105 to the device owned by party S, as described above. The index set for i is taken to be the first t natural numbers. Then, for each value of i, the message [21.1] i is formed as an image in the function f with the first argument xi'and the second argument yi', which is then sent to the party S's owning device. Box 202 indicates that the owned device of party S first randomly selects the index set w from all subsets of {1, ......, t}. The owned device of the party S then performs an equation check of the product of the message [21.2] to the p-th power and all the messages [21.2] i, all with M as the law. If the inspection is satisfied, the party S's owning device continues by sending a message [22] giving w to the party P's owning device. Box 203 is a meeting of challenges defined by the message [22] received by the device owned by Party P. For element j in message [22], a'j, c'j and y'j are sent to the owned device of party S as messages [23.1] j, [23.2] j, [23.3] j, respectively. , For element k in {1, ......, t} not in message [22], x'k, a'Ku and d'k are in message [23.4] k, [respectively. Sent as 23.5] k and [23.6] k. Box 204 indicates the reception and checking of messages [23.1] to [23.6] by the owned device of Party S. For each j in w, the message [21.2] j is equalized with the image in the function f of the two arguments, and the first argument is in that order in the messages [23.1] j and [23.2] j. The image in the function g, the second argument is the message [23.3] j. For each k in {1, ......, t} that is not in w, the message [21.2] k is equalized with the image in the function f of the two arguments, and the first argument is checked. The one is the message [23.4] k, and the second one is the image in the function g of the messages [23.5] k and [23.6] k in this order. A third flowchart for a preferred embodiment will be described in detail with reference to FIG. Box 301 shows how Party B's own device first obtains and records message [21.2] from each Party S's own device. Box 302 indicates that Party B's own device searches for duplicates in the message [21.2] received in Box 301. In one example, the message [21.2] is accumulated in some suitable way when it is received in Box 301. This accumulated material can be easily used to detect duplicates (as will be apparent to those skilled in the art, it is expected that so-called "hashing" is a suitable data structure for this, which is already a one-way function. Since it is an image in, some of those bits can be used directly as a hash value). Another example is for many messages [21.2] that should be accumulated as unsorted batches, then periodically sorting the ones received and perhaps combining them with others that have already been received. Various methods of such duplicate detection based on sorting or searching techniques are widely known in computer science and technology. Box 303 corresponds to at least two instances of a particular value of message [21.2] detected when iterated in 302, both owned by party B with available messages [23.1] and [23.5]. Shows that the device gets. These are expected to be obtained from the owned equipment of each party S that supplies the duplicate message [21.2]. For example, they are provided by multiple parties S's owning equipment with message [21.2]. If the batch sort is done in box 302, Party B's owning device can archive messages [23.1] and [23.5] and search for duplicates when needed. Alternatively, for example, if messages [23.1] and [23.5] are not delivered with [21.2], if the party B's own device knows which party S's own device supplied which message [21.2]. Party B's owning equipment probably requests these individually from multiple Party S's owning equipment. Box 304 shows how party B's owning device can reconstruct u corresponding to a particular message [21.2] for which both messages [23.1] and [23.5] are known. .. This is done by simply combining the reciprocal in the group of messages [23.1] with the message [23.5] using group operations. A fourth flowchart for a preferred embodiment will be described in detail with reference to FIG. The box in this flowchart represents a modification of the corresponding box in FIG. 1, which is the second embodiment. Only the modified parts are shown for clarity and readability. That is, boxes 401, 402, 403, 404, 405 indicate changes to boxes 101, 102, 103, 104, 105, respectively. Box 401 represents a change to the behavior specified in Box 101 for the party P's owning equipment. The definition of the symbolic name a used in box 101 is replaced with that in box 401. In all other respects, the actions and messages shown in Box 401 define only the additional actions that should be included in Box 101 for the second embodiment. The values for the i-th element (1 i s) of the four symbol names are randomly selected. That is, r "i is selected from the set of remainders modulo M. a" i is a string of length that can just hold the group elements in. bi is chosen as the bit string of appropriate length for the first input to the function g after being added to a "i. Ei is chosen as much as ci and di in Figure 1 (u is party B). It can be understood that it is not necessary to include as much information as required for ai, as it is selected by the owning equipment of and does not need to protect u against the "birthday paradox" induced problem. Therefore, it can be expected that the group elements in will conveniently leave ample room for the first argument of the function g to include a appropriately sized b.). For each paradox i moving from 1 to s. The value of ai is calculated as the concatenation of a "i and bi, and the bi part determines the high digit bit position (without leaving the modular addition defined by). The encoded result of this as a bitstring is the first input to the function g used to form xi in Figure 1. The coding and group operations shown in the formation of yi in Figure 1 leave no information about b in the first argument to its function g. In addition, zi is taken as an image in the function g formed from bi as the first argument and ei as the second argument. A message [11.2] i containing the corresponding zi branded by the law of M multiplied by r "i to the qth power is sent to the party B's own device. Box 402 is the same as Box 102, implying receipt of message [11.2] i. Box 403 indicates three additional messages contained within those listed in Box 103. For each j defined in Box 103, the messages [13.5] j, [13.6] j, [13.7] j sent by Party B's owning device contain r "j, bj, ej, respectively. .. Box 404 is a variant of Box 104 and contains everything except that the previous message [14] was not sent. Each message [11.2] j is equalized against the product of the corresponding received message [13.5] j squared to the q and the image in the function g. The first argument to the function g is the received message [13.6] j and the second argument is the received message [13.7] j. If the equality check is maintained, the messages [14.1] and [14.2] k are formed and sent to the party P's own device. Each term in the M modulo product that forms the message [14.1] is one of the message [11.1] k, the M modulo p-th root. The message [11.1] whose subscript is the first element in the ordinal set v- {1, ......, s} gets the p (1) root. A message whose subscript is the second element of the set gets the p (2) root. The same applies to the last element of this set. For each value of k that moves across the same index set, message [14.2] k is formed as the q (@k) root of message [11.2] k modulo M. Therefore, a message with a q (i) root has, for example, a subscript i, and is formed from a message in which the i-th element in the ordinal subscript set v- {1, ......, s} is the subscript. Will be done. Box 405 represents a modification of Box 105 to the equipment owned by Party P. That is, the definition of the symbolic name n used in box 105 is replaced with that provided in box 405, and in all other respects the actions and messages shown in box 405 specify only additional actions. .. The first message [14.1] raised to the p-th power is equalized with the product of the powers of the message [11.1] k modulo M. The term corresponding to each subscript value taken by k in the set defined in box 105 is the message [11.1] k raised by the integer quotient of p divided by p (i), where i is the position of that k (indicated by @k) in the index set. It is formed as the product of the message [14.1], which is the product of rk multiplied by the reciprocal of the multiplicative. Each term of this product corresponds to one of the elements in the index set of k, where the radix is rk and its exponent is the integer quotient of p divided by p (@k). Then mk is formed as the product of the message [14.2] k, which is r "k multiplied by the reciprocal of the multiplicative. Each of these corresponds to one of the elements in the index set of k, where the radix is r". It is k, and its exponent is the integer quotient of q divided by q (@k). Finally, the elements bk and ek are re-subscripted and re-labeled for later use as b'and e', respectively. The subscripts of the retained elements are their position numbers in the subscript set where k changes. A fifth flowchart for a preferred embodiment will be described in detail with reference to FIG. Box 501 indicates that Box 201 does not need to be modified in this second embodiment. Box 502 shows the changes in Box 202. This includes replacement of equality tests and possible changes in w to include some or all non-random parts. The non-random part is the agreed element of w, each corresponding to a monetary unit. If such an element appears in w, it means that the total amount corresponding to the monetary unit will be sent. The new check is an equality check between the p-adic message [21.1] and the product of the t term (1 i t) modulo M, where each of the forms [21.2] i is an integer p. It is raised to the power of the integer p divided by (i). Box 503 indicates that box 203 does not need to be modified except to check the probably non-random part of w that can be predicted as already mentioned. Box 504 only confirms that Box 204 does not need to be modified in this second embodiment. A sixth flowchart for a preferred embodiment will be described in detail with reference to FIG. This figure shows the process between the device owned by Party P and the device owned by Party B, which was not described in the first embodiment as already described. Box 601 sends four messages [61.1], [61.2], [61.3], [61.4] containing i, mi, b'i, e'i to Party B's own device by Party P's own device. It is shown that. Box 602 shows how Party B's own device first receives these four messages and saves the message [61.1] with the symbol name h. Next, the equipment owned by Party B undergoes an equality inspection. The left side is the message [61.2] squared to q (h), and the right side is the function g applied to the first argument message [61.3] and the second argument message [61.4]. Finally, before having to consider it to be included, Party B's own device searches for all previously accepted messages [61.3] and confirms that it does not contain this new message [61.3]. To do. Similarly, Party B's owning device receives the subscript of the received message [61.3] (beyond the prefix of length a ") in the variant of Figure 2 described in Figure 5. Also check that it is not equal to the subscript of any message [23.1]. Some changes and replacements will be apparent to those skilled in the art. For example, in the protocol of Figure 2, perhaps the compressed one-way function of xi and yi is sufficient to delegate the order to the party P's owning device instead of message [21.2] j (Figures 4 and 5). As mentioned later with respect to, even such a compressed image is unnecessary if a rule is made that the order of the images in the function f must be lexicographic in its binary representation). Alternatively, as another example, the amount of data that needs to be saved between Figures 1 and 2 by the party P's owning device is, for example, for the function f in box 201, without holding x'and y'. It can be reduced more than shown by simply reconstructing them as such. Instead of the specific blinds shown, which are essentially those of the first mentioned blind signature publication, the techniques disclosed in the second mentioned blind signature publication can also be used. In addition, the signature scheme indicated by the publication index q may be against a different law, or in a reserved application entitled Unanticipated signature systems of US Application No. 123703 filed by the Applicant on November 23, 1987. It may be a completely different type of signature as described. Such signatures are also in the product of terms, as in p, and multiple instances of the protocol in Figure 4 are made by a particular party P's owning device before message [14.2] is returned. .. These instances are done in such a way that party B's owning device receives all messages [11] before supplying multiple challenge sets v, and the limitation is that they have no common elements and have a concentration t. Only. Furthermore, this method can also be incorporated when applying the technique of FIG. Also, the signature of the first embodiment can use different public indices for different terms as is done in the second embodiment. The second embodiment also requires only a single public index when using the lexicographic ordering technique already described (in the case of Figure 4, the ordering must be sent as a so-called message [11.3]). Instead, this is checked by Party B's owning device as part of the inspection done in box 404 for the jth entry). Yet another variant contains more functions g in one function f. Techniques commonly referred to by those skilled in the art as "key sharing," "shadow," or "partial key" allow u to be split between these functions g. One less than the so-called "threshold" of these methods is the number of functions g whose arguments should be revealed during presentation. The variable may encode, for example, the total amount of money into several parts of the challenge string. Other signatures that can only be presented if the corresponding bit of the challenge string is presented as O may also be issued by Party B's owning device. These allow Party P's own equipment to obtain change for unused value. However, since these may be individual signatures, change from two or more original signatures can be obtained at one time, thereby hiding the exact total amount used in the individual payments. The issued signature may be presented in the exchange of value. To determine the total payment amount, the device owned by the party issuing the signature provides a gross display, and to determine the total refund amount, the device owned by the party issuing the signature provides a refund display, and the total payment amount. And the total refund amount may exceed the predetermined maximum value to identify the refund display. You may effectively collect the total refunds for multiple total payments and keep the link between the payment display and the refund display provided if each of the total refunds corresponds to a particular total payment. The description of the present invention has been described as an example, and those skilled in the art will recognize that various modifications, modifications and equivalents can be used without departing from the technical scope of the present invention. Let's do it.