Related to Standard Assumptions

CROSS-REFERENCE TO RELATED APPLICATIONS [1] This application claims the benefit of the filing date of the following U.S.

Provisional Application, which is hereby incorporated by reference in its entirety: Serial No. 61/994,208, filed on May 16, 2014, and titled "Shorter Signatures Almost Tightly Related to Standard Assumptions."

TECHNICAL FIELD [2] This invention relates to a method and an apparatus for cryptography, and more specifically, to a method and an apparatus for generating efficient digital signatures with security proofs in the standard model.

BACKGROUND

[3] A cryptosystem is said tightly secure when, in the security proof, a successful adversary is turned into an algorithm - with comparable running time - breaking the underlying number theoretic assumption with nearly the same probability as the adversary's advantage. Namely, if the adversary has advantage ε, the reduction should succeed with probability at least ε/c, where c is a small constant. So far, relatively few digital signature schemes have a tight security proof in the standard model (i. e. , without using the random oracle model) and existing ones tend to rely on relatively strong and non-standard assumptions.

[4] In 2013, J. Chen and H. Wee, in an article entitled "Fully, (Almost) Tightly Secure IBE and Dual System Groups," in Crypto'13, LNCS 8043, pp. 435-460, 2013 (hereinafter "Chen"), described signature schemes whose security can be almost tightly related to standard assumptions. Here, "almost tightly" means that, if the adversary has advantage ε, the reduction's probability of success is at least s/(c · X), where λ is the security parameter and c is a constant. As a result, the security bound is only affected by the security parameter, and not by the number of signatures observed by the adversary.

[5] The security of public -key cryptographic primitives is usually established by demonstrating that any successful probabilistic polynomial time (PPT) adversary Λ implies a PPT algorithm Έ solving a hard problem. In order to be convincing, such "reductionist" arguments should be as tight as possible. Ideally, algorithm S's probability of success should be about as large as the adversary's advantage. The results of M. Bellare and P. Rogaway, as described in an article entitled "The Exact Security of Digital Signatures - How to Sign with RSA and Rabin," in Eurocrypt'96, LNCS 1070, pp. 399-416, 1996, initiated an important body of work devoted to the design of primitives validated by tight security reductions in the random oracle model and in the standard model. So far, all signature schemes with tight security proofs in the standard model rely on strong and non-standard assumptions like the Strong RSA assumption or the Strong Diffie-Hellman assumption. No signature scheme is known to have a tight reduction in the standard model under the standard Diffie-Hellman assumption or the RSA assumption, for example. While there exist efficient signature schemes based on the Diffie-Hellman and RSA assumptions, their reductions all lose a factor of q with respect to the adversary's advantage, where q is the number of signature queries made by the adversary.

[6] Tight security proofs may be hard to achieve and are even known not to exist at all in some situations. On the positive side, long-standing open problems have been resolved in the recent years. D. Hofheinz and T. Jager, in an article entitled "Tightly Secure Signatures and Public-Key Encryption," in Crypto '12, LNCS 7417, pp. 590-607, 2012, showed the first public-key encryption scheme whose chosen-ciphertext security in the multi-user setting tightly relates to a standard hardness assumption. The Chen reference answered an important open question raised in an article, by B. Waters, entitled "Efficient Identity-Based Encryption Without Random Oracles," in Eurocrypt'05, LNCS 3494, 2005, by avoiding the concrete security loss, proportional to the number of adversarial queries, that affected the security reductions of all previous identity-based encryption (IBE) schemes based on simple assumptions, including those based on the dual system paradigm. The results of the Chen reference also implied the shortest signatures almost tightly related to standard assumptions in the standard model. In the terminology of the Chen reference, "almost tight security" refers to reductions where the degradation factor only depends on the security parameter λ, and not on the number q of adversarial queries which is potentially much larger. Indeed, it is common to assume λ = 128 and q « 2 ³⁰ .

[7] While the results of the Chen reference achieved a significant improvement by avoiding any dependency on the number q of adversarial queries in their security bound, their schemes feature longer signatures than existing signature schemes with loose reductions under standard assumptions. Here, "loose reduction" means that the reduction is affected by a multiplicative factor Ω (q) , where q is the number of signatures obtained by the adversary before outputting a signature forgery.

[8] Definitions for Linearly Homomorphic Structure-Preserving Signatures

[9] Let (G, G _T ) be groups of prime order p such that a bilinear map e: G x G→ G _T can be efficiently computed.

[10] A signature scheme is structure-preserving if messages, signatures and public keys all live in the group G. In linearly homomorphic structure-preserving signatures, the message space M consists of pairs M : = T x G ⁿ , for some n E N, where T is a tag space.

Depending on the application, one may or may not want the tags to be group elements. In the present application, they can be arbitrary strings.

[11] A linearly homomorphic structure-preserving signature (SPS) scheme over (G, G _T ) is a tuple of efficient algorithms ∑ = (Keygen, Sign, Sign Derive, Verify) for which the message space consists of M : = T x G ⁿ , for some integer n G po ly(T) and some set T, and with the following specifications.

[12] Keygen (A, n): is a randomized algorithm that takes in a security parameter l e N and an integer n G poly (X) denoting the dimension of vectors to be signed, where po ly (A) means that t and n are polynomial in λ. It outputs a key pair (pk, sk), where pk includes the description of a tag space T, where each tag serves as a file identifier.

[13] Sign (sk, τ, ) : is a possibly randomized algorithm that takes as input a private key sk, a file identifier τ G T and a vector M = (M _ll ... , M _n ) G G ⁿ . It outputs a signature σ G G ^Us , for some n _s G poly(X). [14] SignDerive(pk, τ, {(tOj, σ^)}[ _{= 1} ) : is a derivation algorithm, possibly randomized. It inputs a public key pk, a file identifier τ as well as £ pairs (ω _ί( σ^) , each of which consists of a coefficient ω _; G Έ and a signature G G ^ns . It outputs a signature σ G G ^n>! on the vector M = where is a signature on j. [15] Verify(pk, τ, M, σ : is a deterministic verification algorithm that takes as input a public key pk, a file identifier τ £ T, a signature σ and a vector M = ( ₁₍ ... , M _n ). It outputs 0 or 1 depending on whether σ is deemed valid or not.

[16] In a one-time linearly homomorphic SPS, the tag τ can be omitted in the specification as a given key pair (pk, sk) only allows signing one linear subspace.

[17] As in all linearly homomorphic signatures, the securiry requirement is that the adversary be unable to create a valid triple (τ ^* , M ^* , σ ^* ) for a new file identifier τ ^* or for a vector M ^* outside the linear span of the vectors that have been legitimately signed for the tag T*. [18] Hardness Assumptions

[19] We use bilinear maps e: G x G→ G _T over groups (G, G, G _T ) of prime order p. In some cases, we will assume that G≠ G and that no efficiently computable isomorphism ¥:G→G or ¥:G→G is available.

[20] Definition 1 The Decision Linear Problem (DLIN) in G, is to distinguish the distributions (g ^a ,g ^b ,g ^ac ,g ^bd ,g ^c+d ) and (g ^a , g ^b , g ^ac , g ^bd , g ^z ), with a,b,c,d^1 _p ,

R R

z <- zZ _p , wherein "<-" indicates a probabilistic process. The Decision Linear Assumption is the intractability of DLIN for any PPT distinguisher D.

[21] The DLIN problem can be seen as the problem of deciding whether three vectors (g ^a , l«,,g), -€,,g ^b ,g), (g ^ab ,g ^cd ,g ^z ) form a subspace of dimension two (which is the case when z = c + d) or three.

[22] The DLIN problem can be generalized to higher dimensions than three.

[23] Definition 2 The tf-Linear Problem (tf-LIN) in G, is to distinguish the distributions

Di = {(flfi. - .9K.9.91 ¹ , - .9κ ^Κ · ¾} and

D ₂ = - , g _K > g, 9 ₁ ¹ , - .9 _Κ ^Κ · 9 ^{Z E} % _p ] [24] For each K≥ 2 , the A'-linear problem is known to remain generically hard even in the presence of an oracle that solves the (K— l)-linear problem.

[25] For K = 2, the A ^' -linear assumption is exactly the DLIN assumption. For K = 1, the assumption is equivalent to the Decision Diffie-Hellman assumption which says that the distributions {(g, g ^a , g ^b , g ^ab ) \a, b <- Έ _ρ ] and {(g, g ^a , g ^b , g ^c ) \a, b, c <- Έ _ρ ], are computationally indistinguishable. It is possible to rely on this assumption in asymmetric bilinear groups (G, G, G _T ) (i.e. , where G≠ G). When no isomorphism is efficiently computable between G and G in either direction, the DDH assumption can hold in both G and G. The hardness of DDH in both G and G is called Symmetric external

Diffie-Hellman assumption (SXDH). Importantly, the use of SXDH requires asymmetric pairings since DDH is easy when G = G.

[26] When K > 1, the A ^' -linear assumption is believed to hold even in pairing-friendly groups where G = G.

[27] Linearly Homomorphic Structure-Preserving Signatures

[28] Linearly homomorphic SPS (LHSPS) schemes are homomorphic signatures where messages and signatures live in the domain group G of a bilinear map. A recent article, by B. Libert, T. Peters, M. Joye, and M. Yung, entitled "Linearly Homomorphic

Structure-Preserving Signatures and their Applications," in Crypto 2013, LNCS 8043, pp. 289-307, 2013 (hereinafter "Libert"), described the following one-time construction and proved its security under the SDP assumption. [29] Keygen (A, n): given a security parameter λ and the dimension n E N of the subspace to be signed, choose bilinear group (G, G, G _T ) of prime order p > 2 ^λ . Then,

R _Λ R

choose g _z , g _r , h _z , h _u < _^ G. For i = 1 to n, choose Xi, i, 8 _i <- Έ _ρ and compute

9i ⁼ 9z ^Xi 9r ^Yi _> = h _z ^Xl h _u ^Sl . The private key is sk = {( i, 7;, <5;)} ₌₁ while the public key consists of pk = Q^, g _r ^~ , h _z ^~ , \T _Ul {(g _u }?^ E G ²ⁿ⁺⁴ . [30] Sign (sk, (M ... , M _n )) : to sign a vector ( ₁₍ ... , M _n ) E G ⁿ using

sk = {(Xi. Yi. ΜΓ and u = \\ΐ ₌₁ Μ7 ^δί .

[31] Sign Derive(pk, { <Wi, given the public key pk as well as { tuples (ω _ί( ffW), parse as = (z^r^U _j ) .G ³ for i = 1 to Compute and return σ = (z.r.u), where z =

[32] Verify(pk, σ, ( ₁₍ ..., _n )): given a signature σ = (z, r, ii)efi ³ and a vector ( ₁₍ ..., _n ), return 1 if and only if ( ₁₍ ..., _n )≠ 1 _G ) and (z, r, u) satisfy

n

l _Gr = e(z, c¾ · e(r, g ^{■ ~} [ e (M _t , g _t ),

i ⁼¹ (1) n

1 _t = e(z,h _z ^~ ) ^■ e(u, ¾ · ] ^~ [ e M _u h _t ).

i = l

[33] The security of the above scheme was proved under an assumption which is implied by DLIN.

[34] Under the k -linear assumption, the one-time linearly homomorphic

structure-preserving signature of the Libert reference can be extended as follows.

[35] Keygen(A, n): given a security parameter λ and the dimension n G M of vectors to be signed, choose bilinear group (G, G,€s _T ) of prime order p > 2 ^λ . For j = 1 to K,

R

choose generators g _j:Z> 9 _, r * ^~ Then, for each i = 1 to n, j = 1 to K, choose

R R _χ . γ _Η

Xi <- zZ _p , i <- Έ _ρ and compute g _jti = gj _z ^l g _jr ■ The private key is

sk = {{Xu

[36] Sign(sk, (M _{1 n} )): to sign (M _{1 n} ) G <Q ⁿ using sk = (fa,

compute and output σ = (z, r ₁₍ ... , G G^ ^"1"1 , where

[37] SignDerive(pk,{(<w _i ,CTW)}f ₌₁ ): given a public key pk and { tuples (ω^σ^), where ω; G Έ _ρ for each i, parse as = (z^r^,—,r _iK ) G (G ^fe+1 for i = 1 to £. Then, compute and return σ = (z, r ₁₍ ...,r _fe ), where z = Y\ ₌₁ z^ ¹ , r _j = Y\ ₌₁ r^ _j ^l for = 1 to K. [38] Verify(pk, σ, ( _{x n} )) : given σ = (z, ^ r _K ) G and ( i _n ), return 1 if and only if ( ₁₍ ... , _n )≠ ... , 1 _G ) and, for each G {1, ... , K], the following equality holds: π

IG _T = ^e ( ^z > 9 _j ,z) ^■ e(r _j , g _J>r · ] ^~ [ e M _u g _Jti . (2)

i=i

[39] Quasi- Adaptive NIZK Proofs

[40] Let R be a relation that takes as input a statement w and a witness x such that R(x, w) = 1 if and only if w belongs to a language £. We consider languages £ where it may be hard to distinguish random elements of £ from elements outside £. For example, consider an abelian group G of prime order p where the discrete logarithm problem is hard. If A G Z _p ⁿ is a matrix or rank t < n, deciding the membership in a linear subspace g ^A G Q ^txn is believed to be hard for carefully chosen groups: in other words, the language £ = {v G Q ⁿ \3x G Έρ s. t. v = g ^{x A} ] is hard to recognize. For such languages, proving the membership of a candidate w G £ is non-trivial. Whenever w G £, any element x such that R(x, w) = 1 is called a witness for the membership of w in £.

[41] A non-interactive zero-knowledge (NIZK) proof for a relation R usually consists of three algorithms (K, P, V), where K is a randomized algorithm that takes as input a security parameter l E N and outputs a common reference string (CRS) P is a randomized algorithm used by the prover on input of a statement w and a witness x such that

R(x, w) = 1 to generate a proof π for the statement w G £; algorithm V is a deterministic algorithm run by the verifier to output a binary value (which is 1 if and only if the verifier is convinced that w G £) on input of the CRS a statement w and a proof π. The CRS ψ should be seen as a set of common public parameters generated by some trusted party. The zero-knowledge property usually refers to the existence of a simulator S that takes as input a true statement w G £ but no witness. Instead of a witness, the simulator S uses a trapdoor T _sim associated with the CRS to generate simulated proofs π whose distribution is statistically indistinguishable from real proofs π generated using the actual algorithm P. The intuition is that a proof π leaks nothing beyond the validity of the statement w G £.

[42] Quasi- Adaptive NIZK (QA-NIZK) proofs are NIZK proofs where the CRS is allowed to depend on the specific language for which proofs have to be generated. The CRS is divided into a fixed part Γ, produced by an algorithm K ₀ , and a language-dependent part However, there should be a single simulator for the entire class of languages.

[43] Let I G N be a security parameter. For public parameters Γ produced by K ₀ , let D _r be a probability distribution over a collection of relations R " = {R _p } parameterized by a string p with an associated language £ _p = {x\3w: R _p (x, w) = 1).

[44] We consider proof systems where the prover and the verifier both take a label Ibl as additional input. For example, this label can be the message-carrying part of an

Elgamal-like encryption. Formally, a tuple of algorithms (K ₀ , K ₁₍ P, V) is a QA-NIZK proof system for R " if there exists a PPT simulator (S ₁₍ S ₂ ) such that, for any PPT adversaries ·Λ ₁ , Λ ₂ and ·Λ ₃ , we have the properties hereunder.

[45] Informally, quasi-adaptive completenes means that honestly generated proofs are alway accepted by the verifier. Quasi-adaptive soundness captures that it should be computationally infeasible for the prover to trick the verifier into accepting a proof for a false statement. As for the quasi-adaptive zero-knowledge property, it requires the existence of a simulator (S ₁₍ S ₂ ) that can emulate the behavior of the real prover P (which always generates proofs using the witnesses) without knowing the witnesses x: instead, (S ₁₍ S ₂ ) uses a simulation trapdoor r _sirn hidden in the CRS ψ to create simulated proofs. [46] Quasi- Adaptive Completeness:

Pr [Γ <- K ₀ (A); p <- D _r ; ψ <- Κ^Γ,ρ);

(x,w, Ibl) - ^Υ,-φ,ρ ; π - P(i/>, x, w, Ibl): V(^,x, π, Ibl) = l {R _p (x,w) = 1]

= 1.

[47] Quasi- Adaptive Soundness:

Pr [Γ <- K ₀ (A); p <- D _T ; ψ <- Κ^Γ,ρ); (χ,π, Ibl) <- Λ ₂ (Γ,ψ, p) = 1 A -,(3w:ff _p (x,w) = 1)] G negl(A).

[48] Quasi-Adaptive Zero-Knowledge:

Pr [Γ <- K ₀ (A); p <- D _r ; ψ <- Κ^μ,ρ) : Jl^ (Γ,ψ, p = 1]

« Pr [Γ <- K ₀ (A); p <- D _r ; (ψ,τ _5ίηι ) <- S^r. ) : «Λ^^'^'^Γ, , ) = 1], where

- P(i^, .,.,.) emulates the actual prover and outputs a proof π on input of (x, w) G ff _p and Ibl.

- S ₂ (ψ, T _sim , .,.) is an oracle that takes as input x G £ _p (i.e. , for which there exists w such that (x, w) G ff _p ) as well as a label Ibl, and outputs a simulated proof π <- S ₂ (ip,T _sim ,x,\b\ . [49] We assume that the CRS ψ contains an encoding of p, which is thus available to V. The definition of Quasi-Adaptive Zero- Knowledge requires a single simulator for the entire family of relations R " .

[50] An article by B. Libert, T. Peters, M. Joye, and M. Yung, entitled "Non-Malleability from Malleability: Simulation-Sound Quasi-Adaptive NIZK Proofs and CCA2-Secure

Encryption from Homomorphic Signatures," in Eurocrypt 2014, LNCS 8441, pp. 514-532, 2014, Cryptology ePrint Archive: Report 2013/691, (hereinafter "Libert2") showed that linearly homomorphic structure-preserving signatures can be used to construct constant-size QA-NIZK proofs showing that a vector of group elements belongs to a linear subspace. The idea is to have the language-dependent CRS ψ contain the verification key of a one-time

LHSPS and signature of each basis vector of the considered subspace. In order to prove that a vector of group elements v G Q ⁿ belongs to a subspace g ^A G Q ^txn of dimension n and rank t < n, the prover can use the witness x G TL _v ^l satisfying the equality v = g ^{x A} to derive a linearly homomorphic signature on the vector v using the signatures included in the CRS. In order to break the soundness of the proof system and prove the membership of a vector v outside the row space of g ^A G Q ^txn , the adversary would have to create a non-trivial homomorphic signature on v, as shown in the Libert2 reference. The resulting proof system also provides constant-size proofs, regardless of the dimensions of the subspace.

SUMMARY [51] According to an embodiment of the present principles, a method for signing a message is presented, comprising: accessing a first private key and a first set of public key elements, the first set of public key elements including a first set of vectors based on elements of a bilinear group and a second set of vectors based on one-time linearly homomorphic signatures, wherein at least one of the first set of vectors and the second set of vectors is generated using a probabilistic process; determining a first portion of a signature responsive to the message, the first private key and the first set of vectors; determining a second portion of the signature responsive to the first private key and the one-time linearly homomorphic signatures; forming the signature responsive to the first portion and the second portion; and transmitting the signature through a communication channel as described below. According to another embodiment of the present principles, an apparatus for performing these steps is also presented. [52] According to an embodiment of the present principles, a method for verifying a signature of a message is presented, comprising: accessing the message, the signature, and a first set of public key elements, the first set of public key elements including a first set of vectors based on elements of a bilinear group and a second set of vectors based on one-time linearly homomorphic signatures, wherein at least one of the first set of vectors and the second set of vectors is generated using a probabilistic process, wherein a first portion of the signature is determined responsive to the message, the first private key and the first set of vectors, and wherein a second portion of the signature is determined responsive to the first private key and the one-time linearly homomorphic signatures; and verifying whether the signature is valid responsive to the first set of public key elements and the message as described below. According to another embodiment of the present principles, an apparatus for performing these steps is also presented.

[53] According to an embodiment of the present principles, a computer readable storage medium having stored thereon instructions for signing a message or verifying a signature of a message according to the methods described above is presented.

BRIEF DESCRIPTION OF THE DRAWINGS

[1] FIG. 1 is a flow diagram depicting an exemplary cryptographic method, in accordance with an embodiment of the present principles.

[2] FIG. 2 is a block diagram depicting an exemplary cryptosystem, in accordance with an embodiment of the present principles.

[3] FIG. 3 illustrates a block diagram of an exemplary system in which various aspects of the exemplary embodiments of the present principles may be implemented.

DETAILED DESCRIPTION

[4] The present embodiments devise signature schemes that provide shorter signatures than the Chen- Wee schemes as described in the Chen reference while retaining almost tight security under the same assumptions. Under the DLIN assumption, we would like to reduce the signature length from 8 to 6 groups elements. Under the A ^' -linear assumption (which is believed weaker than DLIN when K > 2), we want to reduce the signature length of the Chen- Wee scheme from K to 2K + 2. Under the SXDH assumption, we aim for signatures made of 3 group elements (vs. 4 in the Chen reference). TABLE 1 summarizes some abbreviations used in the present application.

TABLE 1

[6] Our schemes build on ideas used in a signature scheme described in an article by C. Jutla and A. Roy, entitled "Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces," in Asiacrypt'13, LNCS 8269, pp. 1-20, 2013, Cryptology ePrint Archive: Report 2013/109,

2013 (hereinafter "Jutla2"), where each signature is an IND-CCA2-secure encryption - using the message to be signed as a label - of the private key augmented with a QA-NIZK proof that the encrypted value is a persistent hidden secret. The security proof uses a sequence of hybrid games, gradually moves to a game where all signatures contain an encryption of a random value while the QA-NIZK proofs are simulated proofs for false statements. At each step of the transition, increasingly many signatures are generated without using the private key and the CCA2-security of the encryption scheme ensures that this should not affect the adversary's probability to output a signature that does encrypt the private key. In the security proof of the Jutla2 reference, the latter approach implies that: (i) The number of transitions is proportional to the number of signing queries; (ii) A CCA2-secure encryption scheme is needed since, at each transition, the reduction needs to decrypt the ciphertext contained in the forgery.

[7] Here, our key observation is that, by using a QA-NIZK proof system where the proof length is independent of the dimensions of the considered linear subspace, the approach of the Jutla2 reference can be combined with the proof technique of the Chen reference so as to reduce the number of game transitions while retaining short signatures. In addition, the techniques of the Chen reference allow us to dispense with the need for a CCA2-secure encryption scheme and settle for a semantically secure one. In short, by guessing exactly one bit of the target message, the reduction can decrypt a Boneh-Boyen-Shacham ciphertext, described in an article by D. Boneh, X. Boyen, and H. Shacham, entitled "Short group signatures," in Crypto'Q , LNCS 3152, pp. 41-55, 2004, contained in the forgery while embedding a DLIN instance in outputs of signing queries. For L-bit messages, by applying the proof technique of the Chen reference and another article by M. Naor and O. Reingold, entitled "Number-theoretic Constructions of Efficient Pseudo-random Functions," in FOCS'97, pp. 458-467, 1997, we need L game transitions to reach a game where each signature encrypts a random function of the message and is independent of the private key. As a result, we obtain DLIN-based signatures comprised of only 6 group elements. [8] First embodiment

[9] FIG. 1 illustrates an exemplary cryptographic method 100 according to an embodiment of the present principles. In particular, this embodiment relies on the Decision Linear assumption in asymmetric bilinear group.

[10] Keygen(/ ): At step 110, method 100 chooses bilinear groups (G, G, G _T ) of prime i ^R

order p > 2 together with generators f, g, h, u <- G.

R

1. At step 120, for £ = 1 to L, it chooses V _{IQ , V _{I1 , W _{IQ , W _{{ 1} <- G to assemble row vectors.

V = (V ₀ , V ₁ V _L>0 , V _L>1 ) E G ^2L

W = (W ₀ , W ₁ W _Li0 , W _Lil €G ^2L .

2. At step 130, it defines the matrix

V ^T -^2LX2L

^Id f,2L 1

W ^T -^2LX2L

'^ft,2L 1

u ^1 2L -^1X2L

9 with Id _fi2L = f' ^2L G G ^2LX2L , ld _2L = h ¹ ^ £ G ^2LX2L , where I _2L G Z* ^{Lx 2L} is the identity matrix.

3. At step 140, it generates a key pair (sk _hsps , pk _hsps ) for the one-time linearly homomorphic structure-preserving signature in order to sign vectors of dimension n = 4L + 2. Let sk _hsps = Yi, Si)} i ² be the private key, of which the corresponding public key is pk _hsps = { _ζ , g _r ^~ , h _z ^~ , h _u ^~ , {(^Λ)}· ¹ ^ ² ). 4. At step 150, using sk _hsps = {χι, y _it it generates one-time linearly

homomorphic signatures {(Zj,Rj, t/,-)}^† ¹ on the rows = ( _l , ..., _/ - _4L+2 ) G Q4L+2 _G f M These are obtained as

4L+2 4L+2 4L+2

(Zj, Rj, Uj) = ( \ Mf , \ M , \ Af-*') V; G {1 4L + 1).

i=l i=l i=l

R

5. At step 160, it chooses ω <- Έ _Ρ , where TL _P is the set of integers between 0 and p— 1, where p is a prime, and computes Ω = ^ω G Q.

At step 170, the private key is defined to be SK = (ω, {χι, y _it and the public key is

PK =

(/, g, h, u,a = g", V, W,pk _hsps = ψ _γ , h _z , h _u , {{gM}^ ² ), {(Zj.Rj.Uj)}^ ¹ ).

[11] SignCSA ^' , M): Given a message M = M[l] ... M[L] G {0,1} ^L and the private key SK = (a>,{ _ilYi ,5 _i }tLt ² ,

R

1. At step 180, it chooses r,s <- Z _p and compute

σ ₁ = π ^{ω ■} H(V, M) ^{r ■} H(W, M) ^s , σ ₂ = f ^r σ ₃ = h ^s , (4) where H(V,M) = \[ ^L _i=1 V _MW and H(W,M) = X[ ^L _i=1 W _{M[ ]} .

2. At step 190, using {(Zj,Rj, t/,)}^† ¹ , it derives a one-time homomorphic signature (Z, R, U) which will serve as a non-interactive argument showing that the vector

, l-Mill Mill 1-MiLl MiLl l-Mill Mill 1-MiLl „ , _r .

(σ _1ι σ ₂ σ ₂ ...,σ ₂ ^{Ι ί} ,σ ₂ ^{1 ί} ,σ ₃ σ ₃ ', ...,σ ₃ , Ω) (5) is in the row space of M, which ensures that (σ ₁₍ σ ₂ , σ ₃ ) is of the form (4). Namely, compute

^Z = ^Z 4L+1 ·

L

R = «4L + 1 · ( ^ff 2i-M[i] ^{" R} 2L + 2i-M ⁽⁶⁾

At step 199, it returns the signature σ = (σ ₁₍ σ ₂ , σ ₃ , Ζ, R, U) G Q ⁶ . [12] Verily (ΡΚ, Μ, σ : Parse σ as (σ ₁ , σ ₂ , (τ ₃ , Ζ , R, U £ (G ⁶ and return 1 if and only if

^■ ( ^σ 2> [ dl i + MV]) ^{' 1 ■ β} (σ ₃ , ] ^_ [ ^2L + 2i+M [i] ) ^{" 1} · e(H, ^ _4L+2 )- ¹ i = l i = l

e(Z, /i _z ) · e(U, h _u ) = e^ h^ ^{' 1}

[13] Each signature consists of 6 elements of (G, which is as short as Lewko' s

DLIN-based signatures (see an article by A. Lewko, entitled "Tools for Simulating Features of Composite Order Bilinear Groups in the Prime Order Setting," in Eurocrypt 2012, 2012, Section 4.3) where the security proof incurs a security loss proportional to the number of signing queries. Under the same assumption, the Chen- Wee signatures of the Chen reference require 8 group elements. We thus shorten signatures by 25%. Under the A ^' -Linear assumption, our improvement is more dramatic. We also note that, using randomized batch verification techniques, the two verification equations can be

simultaneously verified by computing a product of 7 pairings where the Chen reference computes a product of 8 pairings.

[14] Note that we can obtain another embodiment by having the signature components live in Q while the public key components are in Q. The scheme also works in symmetric bilinear groups, where Q = Q. However, the above configuration yields shorter signatures in asymmetric bilinear groups (Q, Q, Q _T ) .

[15] From a security point of view, we can prove the following result.

[16] Theorem 1. The scheme provides existential unforgeability under chosen-message attacks if the DLIN assumption holds in (G and s. For L-bit messages, for any adversary <A, there exist DLIN distinguishers Έ and Έ' in G and G such that Adv^ A) <

Adv ^LIN ( l) + (2L + 1) · Adv°, ^LIN (/l), and with running times ί _Έ , < t _M + q ^■ poly (A, L).

[17] Second embodiment

[18] Our signature scheme of the first embodiment can be modified so as to rely on the A ^' -linear assumption with K > 2. The construction goes as follows. Keygen (A): Choose bilinear groups (Q, Q, Q _T ) of prime order p > 2 ^λ together

R

;enerators f, ... , f _K , u ₁ , ... , u _K <- G.

R

For j = 1 to K and £ = 1 to L, choose ¾ _ί, ο _> ¾ _ί, ι <- <G to assemble row vectors V _j = (V _{j 0} , V _{j l} V _hLi0l V _hLil ) G CJ ^2L V; G {1 K]

Define M G ^ ^{(2L+1) (if(2L+1)+1)} as the matrix

with Idf _2L = f _j ' ^2L G Q ^2LX2L for each j G {1, ...,K], where I _2L G Z ^2Lx2L is the identity matrix.

3. Generate a key pair (sk _hsps , pk _hsps ) for the one-time homomorphic

structure-preserving signature in order to sign vectors of dimension n = K(2L + 1) + 1. Let sk _hsps = {Xi,

corresponding public key is

P ^K hsps—

4. Using sk _hsps , generate one-t

on the rows M _t = ( , ...,M _iAL+2 ) G C^(2L+I)+I _{OF M}

R _ω .

5. Choose ω ₁₍ ...,ω _κ <- Έ _ρ and compute Ω; = u _{ ¹ G G for ί = 1 to K.

The private key consists of SK = {(ω ₁₍ ... , ω _κ ), sk _hsps ] and the public key is

PK = pk _hsps , {( ί,Λί, _! [20] Sign(Stf, ): In order to sign a message = M[l] ... M[L] G {0,1} ^L using the private key SK = {(ω ₁₍ ... , ), sk _hsps ],

R

1. Choose r ₁₍ ... r _K < _^ TL _p and compute

σ _ο V; G{1 tf} where H(V _j , M) = ¾ _Μ [ί] for each ; G {1, ... , K}.

K (2.L--

2. Using {(Z^ Ri^, ... , R _{i K} )} _i ^ ₁ , derive a one-time linearly homomorphic signature (Z, ... , R _K ) which will argue that the vector

f 1-Mill M ill 1-M\L] M\L] 1-Mill Mill 1-MiLl MiLl „ „

(σ ₀ , σ ₁ ', σ ₁ ', ... , σ ₁ ', σ ₁ ', ... , σ _κ ', σ _κ ', ... , σ _κ ¹ ', σ _κ ^ι ', Ω^ ... , Ω. _Κ ) is in the row space of M, which argues that (σ ₀ , σ _χ , ... , σ _κ ) was generated as per step 1.

Return the signature σ = (σ ₀ , σ ₁₍ ... , σ _κ , Ζ, R _lt ... , R _K ) G G 2if+2

[21] Ver ^' li ΡΚ, Μ, σ) : Parse σ as (σ ₀ , σ _ί , ... , σ _κ , Ζ, R ₁ , ... , R _K ) G G ^2K+2 and return 1 if and only if the following equations hold for each j G {1, ... , K}. e Z, 9j,z) ^■

L K

· · · ^e ( ^a K> 9j,2(K-l)L+2i+M[i]) ¹ " J ^"~ J ^e βί> 9j,2KL+ l + i) ¹

i = l i = l

[22] The security proof is completely similar to that of our first embodiment. The only difference is that, in order to achieve a tight reduction in the last step, the above scheme relies on a computational analogue of the A ^' -linear assumption instead of the Diffie-Hellman assumption. The reason is that, while the latter is not stronger than the A ^' -linear assumption, we do not know how to solve a A ^' -linear instance with only one call to a CDH oracle.

[23] In each signature, we only need 2K + 2 group elements instead of K in the Chen reference, which thus saves 2K— 2 elements when K > 1. As K increases, our signatures thus become almost 50% shorter than in the one described in the Chen reference.

[24] Under the SXDH assumption, a direct instantiation of the above scheme entails 4 elements of G per signature, which is as long as the Chen reference. However, the

QA-NIZK proof system as described in an article by C. Jutla and A. Roy, entitled "Switching Lemma for Bilinear Tests and Constant-size NIZK Proofs for Linear Subspaces," in

Cryptology ePrint Archive: Report 2013/670, 2013 (hereinafter "Jutla"), can supersede the one of the Libert2 reference since, under the SXDH assumption, it only requires one group element per proof, instead of two in the Libert2 reference. The signature thus becomes a triple (σ _χ , σ ₂ , Ζ ^~ ) = (μ ^ω■ H(V , M) ^r , f ^r , Z), where Z is a QA-NIZK proof of well-formedness for (σ ₁₍ σ ₂ ), so that we only need 3 group elements per signature (instead of 4 in the Chen reference).

[25] The reason why the proof system of the Jutla reference should be preferred under the SXDH assumption (i.e. , when K = 1) is the following. Under the A ^' -linear assumption, the proof sizes of the Libert2 and Jutla references are K + 1 and K ² , respectively. While the former is more efficient for K≥ 2 , the construction of the Jutla reference is optimal when K = 1. In the SXDH-based variant with shorter signatures, each signature consists of a pair (σ ₁₍ σ ₂ ) = (μ ^{ω ■} H(V, M ^r , f ^r G (G ² and a QA-NIZK proof Z G G that (σ ₁₍ σ ₂ ) has the correct form. [26] Advantageously, the present embodiments provide new signature schemes with almost tight security and shorter signatures.

[27] FIG. 2 depicts a block diagram of an exemplary cryptosystem, which includes key generator 210, sender 220 and receiver 230. Key generator 210 takes security parameter λ as input, and outputs a matching pair of public key (pk) and private key (sk) for some user. Sender 220 generates signature σ based on the private key, the public key, and message M. For signature σ, receiver 230 verifies whether the signature is valid or not.

[28] Sender 220 in the cryptosystem may correspond to a device (for example, a computer, a tablet, a mobile phone), a software application, or a combination of both a hardware module and a software application, and receiver 230 may correspond to a different device or software application. Sender 220 may receive a message through input devices, for example, a keyboard, touchscreen or voice/video input. Sender 220 and receiver 230 may be connected through a network, for example, through Internet or mobile network. Key generator 210 can be located in the same device as or in a different device from sender 220.

[29] FIG. 3 illustrates a block diagram of an exemplary system in which various aspects of the exemplary embodiments of the present principles may be implemented. System 300 may be embodied as a device including the various components described below and is configured to perform the processes described above. Examples of such devices, include, but are not limited to, personal computers, laptop computers, smartphones, tablet computers, digital multimedia set top boxes, digital television receivers, personal video recording systems, connected home appliances, and servers. System 300 may be communicatively coupled to other similar systems, and to trusted third parties via a communication channel and as known by those skilled in the art to implement the exemplary cryptosystems described above.

[30] The system 300 may include at least one processor 310 configured to execute instructions loaded therein for implementing the various processes as discussed above.

Processor 310 may include embedded memory, input output interface and various other circuitries as known in the art. The system 300 may also include at least one memory 320 (e.g., a volatile memory device, a non-volatile memory device). System 300 may additionally include a storage device 340, which may include non-volatile memory, including, but not limited to, EEPROM, ROM, PROM, RAM, DRAM, SRAM, flash, magnetic disk drive, and/or optical disk drive. The storage device 340 may comprise an internal storage device, an attached storage device and/or a network accessible storage device, as non-limiting examples. System 300 may also include a signing/verifying module 330 configured to process data to provide a signed message or to verify a signed message.

[31] Signing/verifying module 330 represents the module(s) that may be included in a device to perform the signing and/or verifying functions. As is known, a device may include one or both of the signing or verifying modules, for example, verifying the signature on a message may be done on a regular PC since signature verification does not involve secret key so that the PC need not include secure memory for storing the encryption key. Signing messages however, requires secret keys (i.e., the private signing key) and is done in a secure device, for example a smart card. As memory is expensive on smart card, the signature verification functionality may not always be provided on a smart card. The signing and/or verification may be performed using shared resources as known to those skilled in the art. Additionally, signing/verifying module 330 may be implemented as a separate element of system 300 or may be incorporated within processors 310 as a

combination of hardware and software as known to those skilled in the art.

[32] Program code to be loaded onto processors 310 to perform the various processes described hereinabove may be stored in storage device 340 and subsequently loaded onto memory 320 for execution by processors 310. In accordance with the exemplary

embodiments of the present principles, one or more of the processor(s) 310, memory 320, storage device 340 and signing/verifying module 330 may store one or more of the various items during the performance of the processes discussed herein above, including, but not limited to a public key, a private key, signed messages, equations, formula, matrices, variables, operations, and operational logic.

[33] The system 300 may also include communications interface 350 that enables communication with other devices via communication channel 360. The communication interface 350 may include, but is not limited to a transceiver configured to transmit and receive data from communication channel 360. The communication interface may include, but is not limited to, a modem or network card and the communication channel may be implemented within a wired and/or wireless medium. The various components of system 300 may be connected or communicatively coupled together using various suitable connections, including, but not limited to internal buses, wires, and printed circuit boards. [34] The implementations described herein may be implemented in, for example, a method or a process, an apparatus, a software program, a data stream, or a signal. Even if only discussed in the context of a single form of implementation (for example, discussed only as a method), the implementation of features discussed may also be implemented in other forms (for example, an apparatus or program). An apparatus may be implemented in, for example, appropriate hardware, software, and firmware. The methods may be implemented in, for example, an apparatus such as, for example, a processor, which refers to processing devices in general, including, for example, a computer, a microprocessor, an integrated circuit, or a programmable logic device. Processors also include communication devices, such as, for example, computers, cell phones, portable/personal digital assistants ("PDAs"), and other devices that facilitate communication of information between end-users.

[35] Reference to "one embodiment" or "an embodiment" or "one implementation" or "an implementation" of the present principles, as well as other variations thereof, mean that a particular feature, structure, characteristic, and so forth described in connection with the embodiment is included in at least one embodiment of the present principles. Thus, the appearances of the phrase "in one embodiment" or "in an embodiment" or "in one implementation" or "in an implementation", as well any other variations, appearing in various places throughout the specification are not necessarily all referring to the same embodiment.

[36] Additionally, this application or its claims may refer to "determining" various pieces of information. Determining the information may include one or more of, for example, estimating the information, calculating the information, predicting the information, or retrieving the information from memory. [37] Further, this application or its claims may refer to "accessing" various pieces of information. Accessing the information may include one or more of, for example, receiving the information, retrieving the information (for example, from memory), storing the information, processing the information, transmitting the information, moving the information, copying the information, erasing the information, calculating the information, determining the information, predicting the information, or estimating the information.

[38] Additionally, this application or its claims may refer to "receiving" various pieces of information. Receiving is, as with "accessing", intended to be a broad term. Receiving the information may include one or more of, for example, accessing the information, or retrieving the information (for example, from memory). Further, "receiving" is typically involved, in one way or another, during operations such as, for example, storing the information, processing the information, transmitting the information, moving the information, copying the information, erasing the information, calculating the information, determining the information, predicting the information, or estimating the information. [39] As will be evident to one of skill in the art, implementations may produce a variety of signals formatted to carry information that may be, for example, stored or transmitted. The information may include, for example, instructions for performing a method, or data produced by one of the described implementations. For example, a signal may be formatted to carry the bitstream of a described embodiment. Such a signal may be formatted, for example, as an electromagnetic wave (for example, using a radio frequency portion of spectrum) or as a baseband signal. The formatting may include, for example, encoding a data stream and modulating a carrier with the encoded data stream. The information that the signal carries may be, for example, analog or digital information. The signal may be transmitted over a variety of different wired or wireless links, as is known. The signal may be stored on a processor-readable medium.