New trapdoor one-way function on elliptic curves and its application to asymmetric encryption and shorter signatures

The present invention relates to a trapdoor unidirectional encryption function and an encryption system that utilizes such a function.

The trapdoor one-way function (TOWF) is an openly computable function that can be inverted by only one entity. A special secret called a secret key is required to calculate the reciprocal of TOWF.

A classic example of TOWF is the RSA function based on the relationship MedM (modN). The public RSA function w is calculated as: W (x) = x^emodN. The numbers e and N are public values. The number N is chosen to be the product of two separate prime numbers p and q of the two secrets. Inverting an RSA function with private key operation w can be done as follows: W^-1(y) = y^dmodN. Here, d = (1 / e) mod (p-1) (q-1), which is the private key.

Inverting an RSA function without a private key is considered a difficult problem. Factoring N to obtain the prime numbers p and q is infeasible in terms of computation for large values of N, so the private keys w = (p-1) (q-) also maintain confidentiality. In fact, much of the security of online banking today is due to the difficulty of inverting RSA functions without a private key. In other words, the world generally thinks that the RSA function is TOWF.

As a TOWF, RSA functions can be used as the basis for cryptographic systems that perform both digital signatures and public key cryptography. To digitally sign message M with the trapdoor one-way function W, the private key operation W^-1And the public hash function H, S = W^-1Calculate (H (M)). The hash function has two purposes: M to W^-1It may be compressed to a digest size that can be handled by, and prevent any potential attacks, including converting the signature of one message into the signature of a related but unauthorized message. To confirm the signature S of message M with the trapdoor one-way function, confirm that H (M) = W (S).

Public key cryptography in TOWF is somewhat the opposite of signing. Instead of the hash method, the coding method E is used. Calculate the ciphertext C = W (E (M)) to encrypt message M. M = E to decrypt ciphertext C^-1(W^-1(C)) is calculated. The coding function helps to fit M to the size required for W to be applied, and also helps prevent some related message attacks.

One alternative cryptosystem is based on the difficulty of the discrete log problem. A particularly robust cryptosystem, whose security is based on the discrete value logarithm problem, utilizes an elliptic curve and has the advantage of reduced bandwidth compared to the RSA TWOF cryptosystem.

Elliptic curve cryptosystems reduce bandwidth compared to RSA TOWF, but there is still a need to minimize bandwidth while preserving the desired attributes of existing systems. Moreover, TOWF does not rely on random number generators, so it may be easier to execute in some cases even with large bandwidth requirements.

Therefore, an object of the present invention is to provide a TOWF cryptosystem that eliminates or alleviates the above drawbacks.

To facilitate the understanding of the principles underlying the present invention, an overview of the mathematical foundations of these principles is provided below.

The elliptic curve E is a set of points (x, y) that satisfy the definition equation of the elliptic curve. The definition equation is quadratic for y and cubic for x, and is non-singular. The coordinates x and y are elements of a field, which is a set of elements that can be added, subtracted, multiplied, and divided (except for zero for division). Examples of fields include rational and real numbers. There are also finite fields, which are the most frequently used bodies in cryptography. An example of a finite field is a set of integers modulo the prime number q.

Without loss of generality, the elliptic curve definition equation can be of Weierstrass form. The Weierstrass equation is y when the field F is obtained from an integer modulo the prime number q> 3.²= x³It takes the form + ax + b, where a and b are the elements of the body F.

The elliptic curve E contains a point (x, y), which is the solution of the definition equation, and another point, that is, the point at infinity O. The elliptic curve also has a group structure, which means that two points P and Q on the curve can be added together to form a third point P + Q. The point O is the identity element of the group, which means that P + O = O + P = P for all points P. For all points P, Q and R, the addition is associative, P + (Q + R) = (P + Q) + R, and commutative, P + Q = Q + R. Is. Each point P has a negative point -P and P + (-P) = O. The curve equation is y²= x³In the Weierstrass equation of the form + ax + b, the reciprocal of P = (x, y) is easily determined as -P = (x, -y). The formula for adding points P and Q with respect to their coordinates is only reasonably complex, including a small number of field operations in the field on which E is defined.

The rational function (x, y) of two variables on the field is the ratio of two polynomials of two variables on the same field, respectively. Therefore, r (x, y) = p (x, y) / q (x, y), where q and q are polynomials of x and y. The x and y polynomials are ax^myⁿIs the sum of the terms of the form, where a is the element of the body (which in some cases depends on m and n), where m and n are non-negative integers. For example, x²y-3y⁴+1 is a polynomial of x and y. For any rational function r (x, y) and the elements u and v of the field, there is a value of the rational function r (x, y) at the point (u, v). Its value is the origin of the body or the point at infinity, written as r (u, v). The value r (u, v) is easy by substituting the element u of the field into each variable x and v into each y to find all the numbers of the field operations such as multiplication, addition and division. Obtained in. Occasionally a zero division occurs, which generally indicates that the value r (u, v) is actually infinite, which is considered an exception because its value does not exist in the body. Therefore, it is possible to find the value of r (x, y) for a point (x, y) on the curve. It is also possible to define the value of r (x, y) at point O, which makes it possible to find the value of r at each point on the curve.

A rational map on the elliptic curve E also has (t, w) = (r (u, v), s (u, v)) if (u, v) is a point on E. It is a pair of rational functions r (x, y) and s (x, y) such as points on E. More generally, this must hold even if (u, v) is replaced with O, and even if (t, w) is acceptable to be O, but this is true for both t and w. Corresponds to infinity.

A rational map on an elliptic curve can actually be added just like the points on that curve. Additive rules are similar, except that they operate with rational functions instead of operations under the field, i.e. with symbolic functions of x and y.

A rational map (r, s) on E is equivalent to another rational map (r', s') if r is equivalent to r'and s is equivalent to s'as a rational function on E. It is considered to be.

One special kind of rational map is an endomorphic map. The endomorphism map e is a rational map e = (r, s) with additive properties, i.e. for any two points P and Q at e (P + Q) = e (P) + e (Q). is there. One important theorem for elliptic curves states that if e is a rational map with the property e (O) = O, then e is also an endomorphic map. This theorem makes it much easier to determine if a given rational map is an endomorphic map.

An important example of an endomorphic map is e (P) = mP, that is, e = [m] defined by the sum of m copies of the point P. Since the addition law for the curve E is defined by a rational function, so is the iterative sum mP, which is m copies of P. Because these rational functions can be repeated. Therefore e (P) is a rational map. Since the additive operation on the curve E is associative, for e = [m] e (P + Q) = m (P + Q) = m (P) + m (Q) = e (P) + e (Q). Therefore, e is an endomorphic map because it has an additive property.

If there is an endomorphism map different from [m], then E is said to have complex multiplication. Elliptic curves defined on a finite field always have complex multiplication. In other words, they have an endomorphic map e that is different from [m] for every integer m.

One prevailing theorem of elliptic curve theory states that any self-quasi-isomorphic map e is equivalent to the only rational map of the form (r (x), cyr'(x)), where r (x) is a rational function of a single variable, c is an element of a constant field, and r'(x) is a derivative of r (x). This result is not at all obvious, but if e is of the form (f (x, y), g (x, y)), then determining r (x) as outlined below is not possible. It's not too difficult.

For illustration, each y in f (x, y)²Replace with a polynomial that is linear or constant with respect to y. For example, the curve definition equation is y²= x³If + ax + b, then each y²X³Can be replaced with + ax + b, which is a constant with respect to y. Apply this as many times as necessary so that the numerator and denominator do not have a power of y higher than 1, in other words they are primary with respect to y. The modified f (x, y) has the form (a (x) + b (x) y) / (c (x) + d (x) y), where a, b, c and d are It is a polynomial function and should not be confused with the previous usage of these variables. y can be eliminated by multiplying the top and bottom by (c (x) -d (x) y), which is the bottom c (x)²-d (x)²y²= c (x)²-d (x)²Give (x3 + ax + b). Y in the numerator²Can also be erased. This gives the form g (x) + h (x) y, where g (x) and h (x) are rational functions of x. It can be proved that h (x) = 0. Because e is an endomorphic map, so e (-P) = -e (P), and therefore e (x, -y) = -e (x, y), and therefore everything on the curve. This is because g (x) + h (x) y = g (x) -h (x) y for (x, y). Therefore, it was found that r (x) is g (x). It is clear that r (x) found in this way is unique.

Similarly, the rational function g (x, y) can be displayed as a linear function h (x) + yk (x), where h (x) and k (x) are rational functions of x, for similar reasons. Can indicate that h (x) = 0. This means that k (x) can be determined, which provides a means to find the constant c in the form (r (x), cyr'(x)). Alternatively, c can be found by differentiating r (x) and then finding the value of e at some point P to solve for c.

All endomorphic maps have one action on elliptic curves corresponding to quadratic algebraic integers. The quadratic algebraic integer z is z for some integers u and v²It is a complex number such that + uz + v = 0. If e²If + [u] z + [v] = [0], the endomorphism map e corresponds to this algebraic integer, and the addition here is the addition of a rational map, as explained above. In this case, you can write e = [z], where [] indicates a rational map corresponding to a rational integer.

All real integers are quadratic algebraic integers, and the endomorphic map [m] corresponds to the integer m. A quadratic algebraic integer that is not a real integer is a complex number i that is the square root of -1, which is a quadratic equation i²Satisfy +1 = 0. For each quadratic algebraic integer that is not a real integer, there is only a finite set of elliptic curves with [z] as an endomorphic map. Known results provide a theoretical procedure for determining such curves and a method for determining [z] as a rational map.

In general, the order of the endomorphic map e is the number of points P such that e (P) = 0. More precisely, this is called the separation order of e. The actual order is the product of the separated order and another called the non-separated order. When e is displayed as (r (x), cyr'(x)) in its canonical form, the numerator order of r (x) is the order of e and the order of the denominator of r (x) is one less. .. (Here we assume that the numerator and denominator of r (x) are relatively prime.) Furthermore, for e = [z], the order of e is generally | z |²Have as. So, for example, the order of the endomorphic map [m] is | m |²= m²Is.

In conventional elliptic curve cryptography, the value of the endomorphism map [m] is frequently obtained. A few meters represent the private key, and [m] P = mP represents the public key. The function [m] appears in the fully expanded polynomial form of the numerator and denominator of r (x) for [m], even for large values of m.²It can be calculated much faster and more efficiently than adding terms. A very important finding here is the ability to efficiently calculate endomorphic maps of high order.

The following example enumerates all possible endomorphic maps of degree 2 on any elliptic curve. This list is complete down to rational maps and elliptic curve equivalence. These are taken from Silverman's "Advance Topics in the Arithmetic Elliptic Curves" (Silverman).

The first is e = [z] = [1 + i] defined on the curve E: y²= x³+ x, e (x, y) = ((x)²+1) / (z²x), (y (x)²-1))) / (z³x²)) As. Note that z appears as a rational function that defines the action of e, so e is defined only when E is defined on the field F that contains the value corresponding to z. (This comment also applies to the following two endomorphic maps e)

The second is e = [z] = [ (-2)] defined on E: y²= x³+ 4x²+ 2x, e (x, y) = ((x)²+ 4x + 2) / (z²x), (y (x)²-2)) / (z³x²)) As.

The third is e = [z] = [(1 + (-7)) / 2] defined on E: y²= x³-35x + 98, e (x, y) = ((x)²+ x (z²-2) -7 (1-z)⁴) / (Z²(x + z²-2)), (y ((x + z)²-2)²+7 (1-z)⁴)) / (z³(x + z²-2)²)) As.

<p> The inventors have recognized that the attributes of an elliptic curve cryptosystem can be used to obtain a TOWF that provides a robust cryptosystem with reduced bandwidth.</p><p> In one aspect, the invention<u style="single">Order</u>Provides a cryptosystem that operates on the elliptic curve E of n. This cryptosystem is z²+ uz + v = 0<u style="single">Meet</u>Cryptographic data of the self-quasi-isomorphic mapping [z] corresponding to the second-order algebraic integer z (where u and v are secret integers and v is relatively prime to n) and the self-quasi-isomorphic mapping [z]. Public key operations to apply to x to get modified data x'and [-w] to modified data x'to get data x<u style="single">(</u>[u] + [z]<u style="single">)</u>Has a private key operation that applies (w is an integer, wv = 1 mod n).</p><p> The present invention is, in other respects,<u style="single">Order</u>Provides a method for performing cryptographic operations in a cryptographic system operating on the elliptic curve E of n. This method is z²+ uz + v = 0<u style="single">Meet</u>A step of deriving a self-quasi-isomorphic map [z] corresponding to a quadratic algebraic integer z, in which u and v are secret integers and v is relatively prime to n, and a self-quasi-isomorphic map [ Steps to apply public key operation using z] to encrypted data x to obtain modified data x', and to obtain data x [-w]<u style="single">(</u>[u] + [z]<u style="single">)</u>A step of applying a private key operation using the to modified data x', including a step where w is an integer and wv = 1 mod n.</p><p> Next, an embodiment of the present invention will be described simply as an example with reference to the accompanying drawings.</p>

Therefore, referring to FIG. 1, the cryptosystem 10 has a first entity 12 and a second entity 14 that communicate via the communication channel 16. The first entity 12 and the second entity 14 each have a cryptographic module 15 that applies a public key function or a private key function 18 that can be used by both entities 12, 14. Each entity 12, 14 utilizes the key function 18 with the TOWF to obtain encryption / decryption or signature / verification as described above.

In order to realize such a system, it is necessary to determine an appropriate TOWF with the corresponding public key function and private key function. The inventors have recognized that the use of the second-order algebraic integer z provides a suitable TOWF. Next, we find the curve E and the rational map that defines [z] on E. Its rational map [z] is TOWF. A wise choice of z ensures that it has the required cryptographic attributes, ie: (a) [z] can be calculated efficiently, (b) It is difficult to invert [z], (c) Difficult to determine z from the rational function that defines [z], (d) Knowing z guarantees that [z] can be inverted on a certain set of elliptic curve points.

More generally, a rational map r between two different curves E and E'can be used. The rational map can be used as a TOWF. However, it is convenient to use E = E'for ease of implementation. A rational map from E to E is the preferred embodiment.

The safest part of a rational map is that all rational maps (ie E to E) are a combination of translation and endomorphic mapping, and translation is easy to determine and invert. It is an endomorphic map. Therefore, endomorphism is a preferred embodiment of rational maps.

The inventors have found that one promising way to calculate the reciprocal of the trapdoor to invert z is the quadratic equation z for z.²Recognized to use + uz + v = 0. Where u and v are integers. Dividing this equation by vz gives (z + u) / v + (1 / z) = 0. Therefore, (1 / z) =-(z + u) / v. (1 / z) is generally not a quadratic algebraic integer. More precisely, if z has a degree greater than 1, (1 / z) is not a quadratic algebraic integer. Therefore, there is no endomorphic map that inverts [z]. Instead, there is a binary endomorphic map [z'] = [-(z + u)], which satisfies [z] [z'] = [v]. For a particular body F, the elliptic curve E<u style="single">Order</u>n can sometimes be relatively prime to v, which means that there exists an integer w such that wv = 1 mod n. This means that [w] acts as an inverse function of [v] for the point E defined on F.

In this case, the action of [z] on E (F) can be inverted by the endomorphism map [w] [z'] = [-w (z + u)]. If [z] can be found efficiently, so is [-w (z + u)]. An alternative expression for this is [-w] ([u] + [z]).

Therefore, the endomorphism map [z] is used as a public key operation, and [-w]<u style="single">(</u>[<u style="single">u</u>] + [z]<u style="single">)</u>It is possible to use this relationship as a private key operation.

The integers u, v are kept secret and are only available to the entity performing the private key function.

It will be understood that this is specific to body F and does not apply to E defined on other body F'. The point E defined on F is sometimes referred to as E (F) to emphasize that points with coordinates outside F are not considered.

In order for [z] to be a trapdoor one-way function, it should be computationally impossible to determine u and v from the public definition of [z], otherwise it in E (F). The reciprocal can be calculated efficiently as [-w] ([u] + [z]). Therefore, [z] must be given in a way that does not allow easy determination of u and v.

It is considered that u and v cannot be easily determined by giving [z] as a pair of rational functions. Usually, the first coordinate is a function of x only, so [z] is to some extent a basis form (r (x), g (x, y)), even if r (x) is two polynomials. Even if it is not feasible to fully expand as a ratio of, due to the large number of terms, the description for estimating r (x) may reveal the order of the numerator of r (x). unknown. Since the order of [z] is v, the description of [z] may expose v. Therefore, to ensure that [z] is a unidirectional trapdoor, it is important to ensure that u is also unexposed, otherwise [z] can be reversed as described above. ..

According to Silberman, determining the endomorphic mapping ring of a general elliptic curve is not a trivial matter. Since v and u essentially determine the endomorphic mapping ring down to the integer factor, it is generally not possible to determine v and u from the description of the elliptic curve alone. Therefore, from the description of a single complex endomorphism mapping, determining the endomorphism mapping ring does not appear to be a trivial matter yet. In particular, this means that determining u as a pair of rational functions from the description of [z] is still unlikely to be a trivial problem.

Therefore, the degree of z is reasonably large.<u style="single">Order</u>Should be selected to have. This is u²It helps to ensure that we cannot exhaust all possible values of u using the relationship &lt;4v. This can be said from the above. This is because z must be an imaginary complex number.

One possible assembly for [z] is based on the following findings. As mentioned above, if e = [z] = (r (x), cyr'(x)) has the degree m, then r (x) = p (x) / q (x), where And p and q are polynomials of degree m and m-1, respectively. The kernel of e e (Z) for j from 1 to m_j) = O m points elliptic O = Z₁, Z₂, ..., Z_mIs a set of. If j from 2 to m Z_j= (z_j, y_j), Q (x) = (xz₂) (Xz₃) ... (xz_m) Can be assumed. In addition, mZ_j= O. Because [z'] [z] = [m], where z'is mZ_j= [m] Z_j= [z'] [z] Z_jThis is because the conjugate of z determined above as = [z'] O = O. Furthermore, the kernel of e is on the elliptic curve E, though not necessarily as part of E (F).<u style="single">Order</u>It is a subgroup of m. Elliptic curves as a whole generally have at least m + 1 such subgroups.

Next, consider an elliptic curve containing the point B = (0, b). Suppose there is a point W such that [z] W = B. About j from 1 to m W_j= W + Z_jAnd. (W₁= W + Z₁Note that = W + O = W) Suppose that Wj = (wj, uj) for j from 1 to m. Then, for some constant d, p (x) = d (xw)₁) (Xw₂) ... (xw_m).

p (x) = d (xw)₁Note that) u (x). Here the root of u (x) is essentially a rational function of the root of q (x). When the roots of two polynomials have such a simple relationship, there is a transformation of the coefficients of the polynomial. For example, if the root of u (x) is the square of the root of q (x), u (x) = q (x) q (-x) (-1)^{deg q (x)}Is. Thus, it can be seen that the ability to numerically express q (x) provides a means of numerically expressing u (x).

Using the above findings, on some elliptic curve E whose finite x coordinate is the zero of the low Hamming Weight polynomial q (x).<u style="single">Order</u>You can search for subgroups of m. It is desirable to have a low humming weight polynomial q (x). This is because those numerical values can be obtained efficiently. Then we find the point W as above, which makes it possible to efficiently calculate the numerator p (x) as outlined above. If the values of p (x) and q (x) can be obtained, the value of r (x) can be obtained.

One explanation for how to find such polynomials p (x), q (x) is as follows. If Z_j-Z if is a kernel of [z]_jSo is so, so z_jCan appear as the double root of q (x). Suppose q (x) has a degree m that is a prime number. We further assume that m is an Elkies prime, but its exact meaning is not an issue in the discussion below. This is for a polynomial of degree (m-1) / 2 s (x) q (x) = s (x)²Means that it is the mth division polynomial (the m)^th It is one factor of division polynomial). The Schoof-Elkies-Atkin (SEA) algorithm for counting points on the elliptic curve E (F) involves the step of finding a polynomial of the form s (x). The coefficients of the polynomial v (x) are found by a recursion equation. Therefore, there are known methods for constructing such polynomials. In the SEA algorithm, such s (x) is found for values that are small in proportion to m, but it is advantageous to increase m for this purpose.

Another possible approach is to choose a low humming weight irreducible polynomial s (x). Let z be one of its roots, where z is the x-coordinate of a point on the elliptic curve E. That point is finite<u style="single">Order</u>Can have m. This finite<u style="single">Order</u>Is true for any root z of s (x) by applying the Galois automorphism map. If it is also true that these points originating from the roots of s (x) are closed down, that is, they form a subgroup of E, then s (x) has the desired shape. To do so, we basically need a Galois automorphic map g such that g (P) = 2P and a point P on E. By looking for g, P, and E to make this possible, we may find the polynomial s (x) of the desired form. As a practical matter, the y coordinate can only take one of two values and can be ignored.

If the kernel of the endomorphism map intersects group E (F) only at point O, the effect of endomorphism map e on group E (F) is reversible. In this case, the automorphism map e is the automorphism map of group E (F). In general, the group E (F) is cyclic, and in the following discussion, it is assumed that E (F) is cyclic. If e<u style="single">Order</u>For automorphic maps of the cyclic group of n, the algorithm implemented by the inventors determines the integer d so that e (G) = dG, and here we use the additive notation for that group. The cost of this algorithm is due to the factorization of n-1. Random values of n are generally about n^1/3It is known to have a factor f that is. Given a factor of this size, the algorithm can determine d in steps that are a constant multiple of f. This is considerably faster than the general algorithm that finds d given dG. These common algorithms are n^1/2Need a step.

Therefore, n-1 is n^1/3Like not having a factor f close to<u style="single">Order</u>It is desirable that group E (F) has n. An alternative to choosing n this way is n for the adversary being considered^1/3Simply choose n slightly larger so that the cost of the attack is too high. For example, at an 80-bit security level, such a large n is about 2 n.²⁴⁰Can be chosen to be, and at a 128-bit security level n is about 2³⁸⁴You can choose n as in. However, for efficiency reasons it is convenient to use a smaller n, so n-1 is n^1/3It is expected that special work will be done to ensure that it has a size similar to.

The method by which the endomorphism map e is used is generally shown in FIG. The first entity 12 takes one value of x. It can arbitrarily choose one of the two corresponding y values. It then applies the public key function [z] as the advantage map e = (r (x), g (x, y)) and e (x, y') to reach some value (x', y'). ) Is calculated. This would be a basic public key operation. The second entity 14 receives the message (x', y') and e to get the value (x, y).^-1To apply. This is a basic private key operation [-w]<u style="single">(</u>[u] + [z]<u style="single">)</u>Will. If y is changed to -y, y'changes to -y', but x'and x are unaffected. Therefore, y can be largely ignored for all practical purposes.

To apply this to the encryption shown in Figure 3, the first entity 12 sets x to plaintext and x'to the ciphertext by using the public key function [z]. Known elaborate approaches to public key cryptography generally apply some random padding to plaintext x, especially so that repeated encryption of the same plaintext gives different ciphertexts. The second entity 14 decrypts the ciphertext x'using a private key function to obtain the plaintext x.

To apply this to the signature as shown in Figure 4, the second entity 14 sets x'to be the message to be signed and signs x by applying the private key function. calculate. Some kind of hashing is commonly used to generate an x'from a long message, which is the standard technique for digital signatures. The first entity 12 uses the public key operation e to make sure that e (x, y) = (x', y'). Since the hash function is unidirectional, the first entity cannot forge a signature by starting at (x, y) and applying e to get (x', y'). This is because the next step is to find the message M such that x'= Hash (M), which is considered infeasible for unidirectional hash functions.

If the problem of inverting [z] is as difficult as the discrete-valued logarithm problem in E, the size of the crypto group can be smaller than the group used for RSA TOWF. For example, the 3072-bit RSA coefficient is considered to be approximately as safe as an elliptic curve defined on a 256-bit field. Both of these security levels are considered to be 128-bit, which is a commercial-grade security level that is very widely used today on the Internet, such as for online banking. The size of the elliptic curve trapdoor one-way function [z], signature x or basic ciphertext x'is 256 bits, whereas for RSA it is 3072 bits.

Compared to traditional Elliptic Curve Cryptography (ECC), the signature length for a 256-bit elliptic curve is about 512 bits, which is twice the size of the signature for an elliptic curve TOWF. Similar savings are possible for encryption.

In another embodiment and application of the present invention, TOWF is applied to a set of signatures or ciphertexts. Although the following describes the signature, it will be understood that the details about the ciphertext are exactly the same.

A collection of signatures is a single signature consisting of a large number of messages signed by a single signer, a single message signed by a large number of signers, or a large number of messages signed by a large number of signers. Means to represent.

Then, referring to Figure 5, t messages m₁, m₂, ..., m_tTo sign the, the signer (eg, 1st entity 12) hashes each message, transforms each hash into elliptic curve points, and t points P.₁, ... P_t, And these are added together at the point P = P₁+ ... + P_tTo cause. The signer then the inverse function e^-1Apply and sign S = e^-1Obtained (P), which is a single message for many messages. Next, validation by another entity (eg, second entity 14) hashes the message, transforms each hash into a single point, sums it to a total P, and then e (S) = P. It consists of applying the public key 18 operation e to S by checking whether it is. The advantage of repeating this and simply concatenating the messages is that the signing operation is additive, thus achieving great flexibility for signers who wish to change parts of the message.

The above procedure does not impose the order in which individual message components are signed, that is, signature verification involves a (out-of-order) set of signatures signed by the same entity. However, if individual scalar multiples ('weights') can be retrieved or derived by the validating entity, then this procedure is the individual signature component S.₁, ..., S_tIt should be noted that it can be easily generalized towards the weighted sum of individual signatures rather than the sum of. This allows the execution of ordering in the signing process for these t messages by making the weights dependent on the applicable ordering.

Then, referring to Figure 6, if t different signers (eg, first entity 12 as a whole) use the same elliptic curve group and separate TOWFe₁, ..., e_tIf they have, they can form a set signature of a single message as follows. To sign the message m, the first signer of the first entity 12 calculates the hash of the message and converts the hash to the elliptic curve point P. Then they together (ie, all signers of First Entity 12) by applying their respective private key operations._t^-1(e_t-1^-1(... (e₁^-1(P))))) is calculated, where the signatures are made in order by the entities 1, 2, ..., t. Verification (eg by second entity 14) involves applying each of the corresponding public key 18 operations in reverse order to see if the resulting point P corresponds to the hash value of the signed message m. Become.

In general, elliptic curve endomorphism maps are interchangeable, so the signing order of a single message by many entities does not seem to matter. However, it should be noted that this procedure can be easily generalized, for example to perform ordering in the signing process. This can be achieved, for example, by having each signing entity use an offset for the calculated signature, as described below.

Individual signatures by entity i at point P are e_i^-1(P + A_i), Where the elliptic curve point A_iIs unique for entity i. Then the ordered set book name on the message m by the entities 1,2, ..., t hashes m and converts it to elliptic curve point P (as before), followed by the signature. It is obtained by having each of the resulting entities apply its own signing operation to the obtained value. This is S₁= e₁^-1(P + A₁), S₂= e₂^-1(S₁+ A₂), ..., S_t= e_t^-1(S_t-1+ A_t), Bring, here S_tIs the obtained collective signature. Signature verification is at individual offset A₁, ..., A_tIf can be retrieved or derived by the verifying entity, it is now a minor modification of the above procedure, sequence S._t-1= e_t(S_t)-A_t, S_t-2= e_t(S_t-1)-A_t-1, ..., S₁= e₂(S₂)-A₂, P = e₁(S₁)-A₁Depends on calculating and checking whether the elliptic curve point P corresponds to the hash value of the signed message m.

Above, the modification of the original method is a unique offset A for each of the signing entities._iIt is described to carry out the ordering of the signing process using. S_i= e_i^-1(P + A_i) Not S_i= e_i^-1It turns out that modifications that define (f (P, i)) are possible, where f efficiently translates P from the public information associated with the entity i signing f (P, i). It is a mapping in E that has the property of being able to be recalculated. An ordered signature of a single message by a large number of entities requires a large number of titles, and the project is signed by the authorized parties in a particular hierarchical order (eg, bottom-up). It can be useful, for example, to sign and abandon a project in a large organization if it needs to be abandoned in.

Although the present invention has been described in connection with certain embodiments, its various modifications will be apparent to those skilled in the art without departing from the scope of the invention outlined in the claims attached herein. Will. The entire disclosure of all references listed above is incorporated herein by reference.

<figref num="1">It is a schematic diagram of a cryptographic exchange scenario.</figref><figref num="2">It is a schematic diagram which shows the use of the trap door one-way function.</figref><figref num="3">It is a schematic diagram showing the use of the trapdoor one-way function of FIG. 2 for encryption.</figref><figref num="4">It is a schematic showing the use of the trapdoor one-way function of FIG. 2 for digital signatures.</figref><figref num="5">It is a schematic showing the use of the trapdoor one-way function of FIG. 2 for aggregated signatures.</figref><figref num="6">It is a schematic diagram showing the use of the trapdoor one-way function of FIG. 2 for collective signatures with a single message and multiple trapdoor one-way functions for multiple signers.</figref>

10 Cryptographic system 12 1st entity 14 Second entity 15 Cryptographic module 16 communication channels 18 keys