MULTI-MESSAGE MULTI-USER SIGNATURE AGGREGATION

Abstract

A PQ signature scheme MMSAT that is capable of aggregating and compressing unrelated messages signed individually by different parties. The scheme extends the notion of multi-signatures, which are signatures that support aggregation of signatures on a single message signed by multiple parties.

Claims

1. A method for signing and subsequently verifying a collection of digital messages comprising: in at least one processor-based subsystem, selecting parameters that include two rings Ring1 and Ring2 and a module Mod, a ring homomorphism RHom from Ring1 to Ring2, a linear transformation THom from Ring2 to Mod, one or more range-defining bounds, and one or more formatted hash functions; for each User_i selecting a private key PrivKey_i that includes an element f_i in the Ring1 satisfying a first set of predetermined conditions and selecting an associated public key PubKey_i that includes the value RHom(f_i); for each User_i selecting a digital document Doc_i and an element Rand_i in Ring1 satisfying a second set of predetermined conditions, and computing a signature Sig_i that includes elements C_i and Z_i in Ring1, wherein C_i is the output of a function whose input includes one or more quantities derived from THom(RHom(Rand_i)), Doc_i, and PubKey_i, and wherein the element Z_i is the output of a function whose input includes PrivKey_i, Rand_i, and C_i, and wherein Z_i satisfies a third set of predetermined conditions; aggregating a collection of signatures Sig_1, . . . , Sig_K on documents Doc_1, . . . , Doc_K to form an aggregate signature AggSig that includes quantities Z, Y, Y_1, . . . , Y_K, wherein the element Y is in Ring2 and is computed as the output of a function whose input includes RHom(Rand_1), . . . , RHom(Rand_K), wherein the elements Y_1, . . . , Y_K are in Mod and wherein each Y_i is computed as the output of a function whose input includes THom(RHom(Rand_i)), and wherein the element Z is in Ring1 and is computed as the output of a function whose input includes C_1, . . . , C_K and Z_1, . . . , Z_K; and verifying the validity of the aggregate signature AggSig on the documents Doc_1, . . . , Doc_K for the public keys PubKey_1, . . . , PubKey_K by a process that includes verifying that the quantities Z, Y, Y_1, . . . , Y_K satisfy a fourth set of predetermined conditions.

2. The method of claim 1 wherein Ring1 is equipped with one or more functions that measure a size of the elements of Ring1.

3. The method of claim 2 wherein the first set of predetermined conditions includes the condition that the size of the ring element f_i using the first size measure is less than the first range-defining bound.

4. The method of claim 2 wherein the second set of predetermined conditions includes the condition that the size of the ring element Rand_i using the second size measure is less than the second range-defining bound.

5. The method of claim 2 wherein the third set of predetermined conditions includes the condition that the size of the ring element Z_i using the third size measure is less than the third range-defining bound.

6. The method of claim 2 wherein the fourth set of predetermined conditions includes the condition that the size of the ring element Z using the fourth size measure is less than the fourth range-defining bound.

7. The method of claim 1 wherein the quantity C_i is computed as the output of the first formatted hash function evaluated at a list of inputs that includes THom(RHom(Rand_i)), Doc_i, and PubKey_i.

8. The method of claim 1 wherein the quantity Z_i is computed using the sum of Rand_i and the product of PrivKey_i and C_i in Ring1.

9. The method of claim 1 wherein linear functions L1, L2, L3 are determined using the output of the second formatted hash function evaluated at quantities that include C_1, . . . , C_K, wherein L1 is a linear function from Ring1 to Ring1, wherein L2 is a linear function from Ring2 to Ring2, wherein L3 is a linear function from Mod to Mod, wherein RHom composed with L1 equals L2 composed with RHom, and wherein THom composed with L2 equals L3 composed with THom.

10. The method of claim 9 wherein the functions L1, L2 and L3 are linear forms with small non-zero integer coefficients.

11. The method of claim 9 wherein the quantity Z is computed using the output of the function L1 evaluated at Z_1, . . . , Z_K.

12. The method of claim 9 wherein the quantity Y is computed using the output of the function L2 evaluated at RHom (Rand_1), . . . , RHom(Rand_K).

13. The method of claim 9 wherein the fourth set of predetermined conditions includes the condition that RHom(Z) is equal to Y plus L2 evaluated at RHom(f_1)*RHom(D_1), . . . , RHom(f_K)*Rhom(D_K), wherein the quantity D_i is computed as the output of the first formatted hash function evaluated at a list of inputs that includes Y_i, Doc_i, and PubKey_i.

14. The method of claim 9 wherein the fourth set of predetermined conditions includes the condition that THom(Y) is equal to L3 evaluated at Y_1, . . . , Y_K.

15. The method of claim 1 wherein the fourth set of predetermined conditions includes the condition that the quantities D_1, . . . , D_K are distinct, wherein the quantity D_i is computed as the output of the first formatted hash function evaluated at a list of inputs that includes Y_i, Doc_i, and PubKey_i.

16. The method of claim 1 wherein F_q is a finite field and Ring1 and Ring2 are finite F_q-algebras and M is a finite F_q-vector space and RHom is an F_q-algebra homomorphism and THom is an F_q-linear transformation.

17. The method of claim 16 wherein multiplication in Ring1 is convolution product and multiplication in Ring2 is coordinate-by-coordinate product, and RHom is a finite Fourier transform following by a projection onto one or more coordinates.

18. The method of claim 16 wherein the dimensions of Ring1 and Ring2 as vector spaces over F_q are prime.

19. The method of claim 16 wherein the size measures on Ring1 are computed using the values of specified F_q-coordinates centered into the range from −q/2 to q/2.

20. The method of claim 16 wherein the coefficients of the linear transformation THom satisfy the fifth range-defining bound.

21. The method of claim 1 wherein the digital document Doc_i is selected as the output of the third formatted hash function evaluated at an unencrypted and unhashed digital document UEDoc_i.

22. The method of claim 1 wherein the element Z in Ring1 is computed as the output of a function whose input additionally includes Doc_1, . . . , Doc_K.

23. The method of claim 9 wherein the input to the second formatted hash function additionally includes some or all of the quantities Y_1, . . . , Y_K, Doc_1, . . . , Doc_K, PubKey_1, . . . , PubKey_K.

24. The method of claim 1 wherein the module M is equal to the ring Ring2 and the linear transformation THom is the identity map.

25. The method of claim 5 wherein the third range-defining bound is chosen so that a list of signatures signed by one private key is indistinguishable from a list of signatures signed by a second private key.

26. The method of claim 1 wherein the parameters additionally include a ring Ring2′, a function whose input includes elements Z, C_1, . . . , C_K of Ring1 and an element Y of Mod and whose output is a homomorphism PHom from Ring2 to Ring2′, and a linear function L2′ from Ring2′ to Ring2′ such that PHom composed with L2′ is equal to L2 composed with PHom, and wherein the aggregate signature AggSig additionally includes elements Y_1′, . . . , Y_K′, F_1, . . . F_K, F_1′, . . . , F_K′, wherein Y_1′, . . . , Y_K′ are in Ring2′ and wherein each Y_i′ is computed as the output of a function whose input includes PHom (Z, C_1, . . . , C_K, Y; RHom(Rand_i)), and wherein the elements F_1, . . . , F_K are in Mod and wherein each F_i is computed as the output of a function whose input includes THom(RHom(f_i)), and wherein the elements F_1′, . . . , F_K′ are in Ring2′ and wherein each F_i′ is computed as the output of a function whose input includes PHom (Z, C_1, . . . , C_K, Y; RHom(f_i)), and wherein the process of verifying the validity of the aggregate signature AggSig on the documents Doc_1, . . . , Doc_K for the public keys PubKey_1, . . . , PubKey_K includes verifying that the quantities Z, Y, Y_1, . . . , Y_K, Y_1′, . . . , Y_K′, F_1, . . . F_K, F_1′, . . . , F_K′ verify a fifth set of predetermined conditions.

27. The method of claim 1 wherein the quantity C_i is computed as the output of the first formatted hash function evaluated at a list of inputs that includes THom(RHom(Rand_i)), Doc_i, and THom(RHom(f_i)).

28. The method of claim 26 wherein the fifth set of predetermined conditions includes the condition that PHom(RHom(Z)) is equal to PHomZ (Y) plus L2′ evaluated at F_1′*PHom(RHom(D_1)), . . . , F_K′*PHom(RHom(D_K)), wherein the quantity D_i is computed as the output of the first formatted hash function evaluated at a list of inputs that includes Y_i, Doc_i, and F_i.

29. The method of claim 26 wherein the fifth set of predetermined conditions includes the condition that PHom(Y) is equal to L2′ evaluated at Y_1′, . . . , Y_K′.

30. The method of claim 26 wherein the coefficients of the linear transformation PHom satisfy the sixth range-defining bound.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0011] These and other features, aspects, and advantages of the present invention will become better understood with reference to the following description, appended claims, and accompanying drawings where:

[0012] FIG. 1 is a block diagram of an exemplary system that can be used in practicing embodiments of the present invention.

DETAILED DESCRIPTION

[0013] The subject innovation is now described with reference to the drawings, wherein like reference numerals are used to refer to like elements throughout. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It may be evident, however, that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to facilitate describing the present invention.

[0014] Post-Quantum (PQ) signature schemes are known for large key and signature sizes, which may inhibit their deployment in real world applications. The present invention is a PQ signature scheme MMSAT that is a scheme capable of aggregating and compressing unrelated messages signed individually by different parties. The present invention extends the notion of multi-signatures, which are signatures that support aggregation of signatures on a single message signed by multiple parties. Multi-signatures are especially useful in Blockchain applications, where a transaction may be signed by multiple users. The present invention achieves significant gains in bandwidth and storage requirements by allowing aggregation and compression of multi-key and multi-message transactions. The present invention is derived by extending the PASS.sub.RS scheme, so the security of the scheme relies on the hardness of the Vandermonde-SIS problem. When aggregated and compressed, a signature includes two parts. The first part is a post-quantum size signature that grows very slowly, scaling by on the order of log K bits for K signatures. The second part scales linearly with K, but bears only a short fixed cost of 2λ bits per signature, where λ represents the security parameter. Even for a modest number of signatures, the overhead of MMSAT is in line with that of traditional signature schemes such as the Elliptic Curve Digital Signature Algorithm (ECDSA). The present invention additionally includes a variant MMSATK of MMSAT that is capable of aggregating and compressing the public keys used by different parties.

[0015] Referring now to FIG. 1, an exemplary system 10 that can be used in practicing embodiments of the invention includes two processor-based subsystems 105 and 155 that are in communication over a channel 50, which may be, for example, any wired or wireless communication channel such as a telephone or internet communication channel in, for example, a cloud-based system. In the example hereof, the channel can be considered a secure or an insecure channel. The subsystem 105 includes processor 110 and the subsystem 155 includes processor 160. The subsystems may typically include mobile devices, computers, or terminals. When programmed in the manner to be described, the processors 110 and 160 and their associated circuits may be used to implement an embodiment of the present invention and to practice an embodiment of the method of the invention. The processors 110 and 160 may each be any suitable processor, for example, an electronic digital processor or microprocessor. It should be understood that any general purpose or special purpose processor, or other machine or circuitry that can perform the functions described herein, electronically, optically, or by other means, can be utilized. The subsystem 105 typically includes memories 123, clock and timing circuitry 121, input/output functions 118 and display 125. Inputs can include a touchscreen/keyboard input as represented at 103. Communication is via transceiver 135, which may include any suitable device for communicating signals.

[0016] The subsystem 155 in this illustrative embodiment can have a similar configuration to that of subsystem 105. The processor 160 has associated input/output circuitry 164, memories 168, clock and timing circuitry 173, and a display 176. Inputs include a touchscreen/keyboard 155. Communication of subsystem 155 with the outside world is via transceiver 162.

[0017] The present invention is a PQ signature scheme, referred to herein as “MMSAT,” which supports aggregation across unrelated signatures signed by different users. An aggregated MMSAT signature has size roughly equal to a single PQ signature plus 2λ-bits per signature aggregated. From a practical perspective, even for a modest number of signatures (e.g., a few hundred), the aggregate signature size of MMSAT represents an improvement over traditional signature schemes such as elliptic curve-based signatures (ECDSA), e.g. it is 19-times smaller than Bimodal Lattice Signature Scheme (BLISS) and 1.9 times smaller than ECDSA for 1000 signatures at 128-bit security.

[0018] The present invention uses an ∞-norm analysis to give improved estimates for the forgery probability from lattice reduction, leading to optimized parameters.

[0019] The present invention is a method and system for multiple users to sign multiple documents, for those signatures to be aggregated and compressed based on ring homomorphisms and linear transformations, and for the users' public keys to be aggregated and compressed based on ring homomorphisms and linear transformations. The ring homomorphism may utilize two rings Ring1 and Ring2 and a module Mod, a ring homomorphism RHom: Ring1-->Ring2, and a linear transformation THom: Ring2-->Mod. The private keys can include elements f lying in a specified subset of Ring1, the public keys can include the value RHom(f) in Ring2, the individual signatures in accordance with the invention may include quantities computed from the individual documents and individual private and public keys via specified formatted hash functions and algebraic operations in the ring Ring1 and applications of the maps RHom and THom, and the aggregated and compressed signature on the collection of documents may include quantities computed from the individual signatures, the individual documents, and the individual public keys via specified formatted hash functions and algebraic operations in the rings Ring1 and Ring2 and applications of the maps RHom and THom.

[0020] Table 1, shown below, lists public parameters used variously by PASS.sub.RS and MMSAT and MMSATK.

TABLE-US-00001 TABLE 1 Public parameters for PASS.sub.RS, MMSAT, and MMSATK N a prime (dimension parameter) q a prime satisfying q ≡ 1 (mod N) (modulus parameter) g a primitive N.sup.th root of unity in Z.sub.q R.sub.q the ring Z.sub.q[x]/(x.sup.N − 1), often identified with Z.sub.q.sup.N with multiplication * * multiplication in R.sub.q, convolution product in Z.sub.q.sup.N ⊙ coordinate-by-coordinate multiplication in R.sub.q ≅ Z.sub.q.sup.N λ bit security parameter space of message digests μ ∈  Ω a subset of {g.sup.j:1 ≤ j ≤ N − 1} t =|Ω|, the number of elements in Ω B.sub.t ≈t/N, parameter used to select t dimension parameter for signature compression map T, satisfies   ≥  t′ [00001]$\begin{array}{c}\mathrm{dimension}\mathrm{parameter}\mathrm{for}\mathrm{key}\mathrm{compression},\\ \mathrm{satisfies}{q}^{t^{\prime }}\ge \text{?}\mathrm{and}\left(\begin{array}{c}t\\ t^{\prime }\end{array}\right)\ge \text{?}\end{array}$ k L.sup.∞-norm bound for commitment polynomial y b L.sup.∞-norm bound for rejection sampling is k − b K number of individual signatures contained in an aggregate signature B.sub.k, B.sub.q multipliers used for L.sup.1-norm bounds for aggregate signature, related by B{square root over (K)}(k − b) ≈ B.sub.qq. d.sub.e the number of 1's and −1's in a challenge polynomial, d.sub.e ≤ b/2 d.sub.f the number of 1's and −1's in a private key T a Z.sub.q-linear map T:Z.sub.q.sup.t .fwdarw. Z.sub.q   used for compression Hash.sub.C a hash/encoder function {0, 1}   .fwdarw.  (d.sub.e) Hash.sub.B a hash/encoder function {0, 1}   .fwdarw. {−1, 1}  Hash.sub.Ω a hash/encoder function {0, 1}   .fwdarw. {subsets of Ω containing t′ elements} indicates data missing or illegible when filed

[0021] In Table 2, an exemplary sign algorithm for individual signatures is shown.

TABLE-US-00002 TABLE 2 Sign Algorithm for PASS.sub.RS and MMSAT and MMSATK. The input to Hash.sub.C depends on the particular scheme Algorithm 1 Sign   Input: (μ, f, Scheme) 1: repeat 2:  [00002]$y\stackrel{\text{?}}{\leftarrow }{ℬ}^{\infty }\left(k\right)$ 3:  c ← Hash.sub.C(Scheme, μ) 4:  z ← f * c + y 5: [00003]$\mathrm{until}z\in {ℬ}^{\infty }\left(k-b\right)$ Output: (ŷ|.sub.Ω, z, μ) [00004]$\text{?}\text{indicates text missing or illegible when filed}$

[0022] In Table 3, an exemplary verification algorithm for individual signatures is shown.

TABLE-US-00003 TABLE 3 Verify Algorithm for PASS.sub.RS and MMSATK. The input to Hash.sub.C depends on the particular scheme Algorithm 2 Verify Input: (ŷ|.sub.Ω, z, μ, {circumflex over (f)}|.sub.Ω, Scheme)  1: c ← Hash.sub.C(Scheme, μ)  2: Z ← {circumflex over (f)}|.sub.Ω ⊙ ĉ|.sub.Ω + ŷ|.sub.Ω  3: if z ϵ B.sup.∞ (k − b) and Z = {circumflex over (z)}|.sub.Ω then  4:  result ← valid  5: else  6:  result ← invalid  7: end if Output: result

[0023] In Table 4, an exemplary MMSAT aggregate signature algorithm is shown.

TABLE-US-00004 TABLE 4 MMSAT: Aggregate Signature Algorithm with Signature Compression Algorithm 3 Aggregate Input: ( |.sub.Ω, z.sub.i, μ.sub.i, |.sub.Ω).sub.iϵ[K]  1: for i := 1 to K step 1 do  2:  c.sub.i ← Hash.sub.C(T(ŷ|.sub.Ω), μ.sub.i, |.sub.Ω)  3: end for  4: β ← Hash.sub.B(c.sub.1,..., c.sub.K)  5: z ← β.sub.1z.sub.1 + ... + β.sub.Kz.sub.K  6: Y ← β.sub.1 |.sub.Ω + ... + β.sub.K |.sub.Ω  7: if ||z||.sub.∞ ≤ B.sub.k{square root over (K)}(k − b) then  8:  result ← success  9: else 10:  result ← failture 11: end if Output: (z, Y, μ.sub.i, T( |.sub.Ω)).sub.iϵ[K], result

[0024] In Table 5, an exemplary MMSAT verify aggregate signature algorithm is shown.

TABLE-US-00005 TABLE 5 MMSAT: Aggregate Signature Verification Algorithm Algorithm 4 VerifyAggregate   Input: (z, Y, μ.sub.i, T(ŷ.sub.i|.sub.Ω), {circumflex over (f)}.sub.i|.sub.Ω).sub.i∈[K]  1: for i := 1 to K step 1 do  2:  c.sub.i ← Hash.sub.C(T(ŷ.sub.i|.sub.Ω), μ.sub.i, {circumflex over (f)}.sub.i|.sub.Ω)  3: end for  4: β ← Hash.sub.B(c.sub.1 , . . . , c.sub.K)  5: [00005]$Z\leftarrow \left(\underset{i=1}{\overset{K}{.Math.}}{\beta }_i\left({\widehat{f_i│}}_{\Omega }\odot \widehat{c_i}{│}_{\Omega }\right)\right)+Y$  6: [00006]$W\leftarrow \left(\underset{i=1}{\overset{K}{.Math.}}{\beta }_{i}T\left(\widehat{y_i}{│}_{\Omega }\right)\right)$  7: if ∥z∥.sub.∞ ≤ B.sub.k{square root over (K)}(k − b) and c.sub.1 , . . . , c.sub.K are distinct and T(Y) = W and Z = {circumflex over (z)}|.sub.Ω then  8:  result ← valid  9: else 10:  result ← invalid 11: end if Output: result

[0025] In Table 6, an exemplary MMSAT sign algorithm with public key compression is illustrated.

TABLE-US-00006 TABLE 6 MMSATK: Aggregate Signature Algorithm with Public Key Compression Algorithms 5 Aggregate Input: ( |.sub.Ω, z.sub.i, μ.sub.i, |.sub.Ω).sub.iϵ[K]  1: for i := 1 to K step 1 do  2:  Y.sub.i ← T( |.sub.Ω)  3:  F.sub.i ← T( |.sub.Ω)  4:  c.sub.i ← Hash.sub.C(Y.sub.i, μ.sub.i, F.sub.i)  5: end for  6: β ← Hash.sub.B(ci,...,c.sub.K)  7: z ← β.sub.1z.sub.1 + ... + β.sub.Kz.sub.K  8: Y ← β.sub.1 |.sub.Ω + ... + β.sub.K |.sub.Ω  9: Ω′ ← Hash.sub.Ω(z, y, c.sub.1,..., c.sub.K) 10: for i := 1 to K step 1 do 11:  F.sub.i′ ← |.sub.Ω′ 12:  Y.sub.i′ ← |.sub.Ω′ 13: end for 14: if ||z||.sub.∞ ≤ B.sub.k{square root over (K)}(k − b) then 15:  result ← success 16: else 17:  result ← failture 18: end if Output: (z, Y, μ.sub.i, Y.sub.i, Y.sub.i′, F.sub.i, F.sub.i′).sub.iϵ[K], result

[0026] In Table 7, an exemplary MMSAT verify individual signature with compressed public key algorithm is shown.

TABLE-US-00007 TABLE 7 MMSATK: Aggregate Verification Algorithm with Compressed Public Key Algorithm 6 VerifyAggregate   Input: (z, Y, μ.sub.i, Y.sub.i, Y.sub.i′, F.sub.i, F.sub.i′,).sub.i∈[K]  1: for i := 1 to K step 1 do  2:  c.sub.i ← Hash.sub.C(Y.sub.i, μ.sub.i, F.sub.i)  3: end for  4: β ← Hash.sub.B(c.sub.1 , . . . , c.sub.K)  5: Ω′ ← Hash.sub.Ω(z, Y, c.sub.1 , . . . , c.sub.K)  6: [00007]$Z^{\prime }\leftarrow \left(\underset{i=1}{\overset{K}{.Math.}}{\beta }_i\left(F_i^{\prime }\odot \widehat{c_i}{│}_{{\Omega }^{\prime }}\right)\right)+{Y│}_{{\Omega }^{\prime }}$  7: [00008]$W^{\prime }\leftarrow \underset{i=1}{\overset{K}{.Math.}}{\beta }_i{Y}_i^{\prime }$  8: if ∥z∥.sub.∞ ≤ B.sub.k{square root over (K)}(k − b) and c.sub.1 , . . . , c.sub.K are distinct and Z′ = {circumflex over (z)}|.sub.Ω′ and W′ = Y|.sub.Ω′ then  9:  result ← valid 10: else 11:  result ← invalid 12: end if Output: result

[0027] It would be appreciated by those skilled in the art that various changes and modifications can be made to the illustrated embodiments without departing from the spirit of the present invention. All such modifications and changes are intended to be within the scope of the present invention except as limited by the scope of the appended claims.