FOLLOW
0 Reviews   |   241 Views   |   1 Followers

Sign here, Online

Patent

US7461261

Owner

EPFL

Filing Date

February 13, 2004

Priority Date

February 13, 2004

Portfolio

Undeniable Signature - EPFL

Intro

The aim of the invention is to propose an undeniable signature which is a size smaller than the currently available undeniable signatures, i.e. less than 80 bits. The size could be an issue in several applications such as bank payments, in which the cardholder wishes to keep a trace of each transaction in the card.

Claims

1. A method for generating an undeniable signature on a set of data, the method comprising the following steps: transforming the set of data to a se...
  1. A method for generating an undeniable signature on a set of data, the method comprising the following steps: transforming the set of data to a sequence of a predetermined number of blocks, the blocks being members of an Abelian group, the transformation being a one way function; applying to each block a group homomorphism to obtain a resulting value, in which a number of elements of an initial group is larger than the number of elements of a destination group; and storing the resulting value in a memory.
  2. The method of claim 1, wherein the initial group is formed by invertible integers modulo n, denoted as Zn*.
  3. The method according to claim 2, wherein the group homomorphism computation is based on computation of a residue character (χ) on the set of invertible integers Zn*.
  4. The method according to claim 3, wherein the residue character (χ) computation in based on a parameter (π) serving as a key.
  5. The method according to the claim 4, wherein this key parameter (π) is determined by: π· π=n, π being the complex conjugate of π.
  6. The method according to claim 4, wherein the parameter is a secret key on an asymmetric key pair public/secret.
  7. The method according to claim 2, wherein the group homomorphism computation is determined by raising an element of Zn* to the power of r(q−1), in which n=p·q such that p=rd+1 and q are prime, gcd(r, d)=1, gcd(q−1, d)=1, then by computing a discrete logarithm.
  8. The method according to claim 7, wherein the group homomorphism is calculated using a factorization of n.
  9. The method according to claim 1, wherein the length of the signature is dependent of the number of elements of the destination group and the number of blocks.
  10. A method of confirming by a Verifier an undeniable signature (y1, . . . , yt) of a set of data (m) generated by a Signer taking into account a predefined security parameter of the confirmation protocol, this Signer having a public/secret key pair, this method comprising the following steps: obtaining a personal value (ρ) from the Signer, this personal value being part of the public key (G, H, d, ρ, (e1, . . . es)) of the Signer; extracting a first sequence of elements (e1, . . . es) from the public key, generating a second sequence of elements (g1, . . . gs) from the personal value (ρ), generating a third sequence of elements (x1, . . . , xt) from the set of data (m); randomly picking challenge parameters ri∈G and aij∈Zd for i=1, . . . , k and j=1, . . . , s+t and computing a challenge value ui=dri+ai1g1+ . . . aisgs+ais+1x1+ . . . +ais+txt; sending by the Verifier the challenge value uj to the Signer; receiving from the Signer a commitment value (i>), this commitment value (i>) being calculated by the Signer based on a response value vi=f(ui); sending by the Verifier the challenge parameters ri and aij to the Signer; verifying by the Signer whether ui=dri+ai1g1+ . . . aisgs+ais+1x1+ . . . +ais+txt, and in a positive event, opening by the Signer the commitment on the response value (vi); and verifying by the Verifier whether vi=ai1e1+ . . . aises+ais+1x1+ . . . +ais+txt.
  11. A method for denying to a Verifier by a Signer on an alleged non-signature (z1, . . . , zt) of a set of data (m), this signature being supposedly generated according to claim 1 by the Signer, this Signer having a public/secret key pair, this method taking into account a predefined security parameter (l) of the denial protocol and comprising the following steps: obtaining by the Verifier a personal value (ρ) of the Signer, this personal value being part of the public key (G, H, d, ρ, (e1, . . . es)) of the Signer; extracting by the Verifier a first sequence of elements (e1, . . . es) from the public key; generating by the Verifier and the Signer a second sequence of elements (g1, . . . gs) from the personal value (ρ); generating by the Verifier and the Signer a third sequence of elements (x1, . . . , xi) from the set of data (m); calculating by the Signer the true signature (y1, . . . , yt); and repeating the following steps l times, l being the predetermined security parameter; randomly picking by the Verifier challenge parameters rj∈G and aji∈Zd for i=1, . . . , s and j=1, . . . , t and λ∈Zp* where p is the smallest prime dividing d; computing uj: =drj+aj1g1+ . . . ajsgs+λxj, and wj: =aj1e1+ . . . ajses+λzj for j=1 . . . t; sending by the Verifier the challenge values uj and wj to the Signer; computing by the Signer a response test value TVj: =(zj-yj)·; for each j=1 to t, determining whether the test value TVj=0; in a negative event, calculating a test parameter λj according to the following formula: wj-vj,=λj(zj-yj); determining an intermediate value (IV), the intermediate value (IV) being equal to one valid test parameter (λ) and in case of no valid test parameter is found, selecting as the intermediate value (IV) a random value; sending a commitment value CT based on the intermediate value (IV), to the Verifier; sending by the Verifier the challenge parameters rj, aji and test parameter (λ)to the Signer; verifying by the Signer whether uj=drj+aj1g1+ . . . ajsgs+λxj and wj:=aj1e1+ . . . ajses+λzj for j=1 . . . t hold, in a positive event, the Signer opens the commitment on the intermediate value (IV) to the Verifier; and verifying by the Verifier that the test parameter (λ) is equal to the intermediate value (IV).
  12. The method of claim 11, in which the determination of the valid test parameter comprises a check whether (wj-vj,) and (zj-yj) are not equal to 0.
  13. The method of claim 11, in which j>1, the determination of the valid test parameter comprises the check whether (wj-vj,) and (zj-yj) are not equal to 0, and that all of the test parameters are the same.
read more

Abstract

The aim of the invention is to propose the generation, verification and denial of an undeniable signature which has a size smaller than the currently ...
The aim of the invention is to propose the generation, verification and denial of an undeniable signature which has a size smaller than the currently available undeniable signatures, i.e. less than 80 bits. This aim is achieved by the method to generate an undeniable signature (y1,...,y) on a set of data, this method comprising the following steps: (1) transforming the set of data (m) to a sequence of a predetermined number (t) of blocks (X, ..., X), these blocks being members of an Abelian group, this transformation being a one way function, and (2) applying to each block (x,) a group homomorphism (f) to obtain a resulting value(y), in which the number of elements of the initial group (G) is larger than the number of elements (d) of the destination group (H).
read more
Write Review

Here are the reviews from the crowd!

No ratings yet Wisenheimer. Be the first!

Rate the patent & write your own review!

Rating categories
WOW!
GOTCHA!
DEAL!
Where should our donation go to?
Your review
Write about potential applications
Write about potentially interested companies
Choose a name

Convinced about the patent? Contact us!

Your bid
Your e-mail
Your message