Patent US5263085A successfully refreshed from Google Patents.
US5263085A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Fast signature scheme based on sequentially linearized equations
Assignee: Yeda Research and Development Co Ltd
•
Filing: 1992-11-13
•
Granted: 1993-11-16
•
Expires: 2012-11-13
Abstract
Abstract A new type of digital signature scheme whose security is based on the difficulty of solving systems of k polynomial equations in m unknowns modulo a composite n is proposed. The scheme uses a simple technique (called sequential linearization) for embedding trapdoors into such systems of equations.
Inventors
- 👤 Adi Shamir
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 15:28
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/30; H04L9/3006; H04L9/302; H04L9/3093; H04L9/32; H04L9/3247
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
241 words
A method of generating and verifying digital signatures comprising the steps of: a) selecting a modulus n, b) selecting k=m-1 secret polynomials Fi of degree d (k>1, d>1, i=2 . . . ,m) where Fi contains variables y1. . . yi-1 in arbitrary form and yi in linear form, c) selecting a secret m×m matrix A with entries in [0,n), d) defining a linear transformation Y=AX (mod n), e) replacing each yi in each Fi by the linear combination of xt variables defined by A and simplifying the resulting polynomials Ei, f) selecting the coefficients of all the Ei polynomials and using them as a public key, g) generating a message M, h) computing the hashed form Hi(M) for i=2 . . . ,m, i) selecting a value for y1 in [0,n), j) sequentially solving the linear equations in yi derived from Fi (y1 . . . yi)=Hi(M)(mod n) for i=2 . . . ,m, k) computing X=A -1 Y (mod n) to derive a signature X of message M, l) transmitting to a verifier the modulus n of step a, the public key of step f, the message M of step q and the signature X of step k, m) verifying the signature X of the message M by computing the hashed form Hi(M) for i=2, . . . ,m, and verifying that equations Ei(x1, . . . ,xm)=Hi (M) (mod n) are satisfied for i=2, . . . ,m.
Claim 2
Independent Claim
241 words
A method of generating and verifying digital signatures comprising the steps of: a) selecting a modulus n, b) selecting k=m-1 secret polynomials Fi of degree d (k>1, d>1, i=2 . . . ,m) where Fi contains variables y1. . . yi-1 in arbitrary form and yi in linear form, c) selecting a secret m×m matrix A with entries in [0,n), d) defining a linear transformation Y=AX (mod n), e) replacing each yi in each Fi by the linear combination of xt variables defined by A and simplifying the resulting polynomials Ei, f) selecting the coefficients of all the Ei polynomials and using them as a public key, g) generating a message M, h) computing the hashed form Hi(M) for i=2 . . . ,m, i) selecting a value for y1 in [0,n), j) sequentially solving the linear equations in yi derived from Fi (y1 . . . yi)=Hi(M)(mod n) for i=2 . . . ,m, k) computing X=A -1 Y (mod n) to derive a signature X of message M, l) transmitting to a verifier the modulus n of step a, the public key of step f, the message M of step q and the signature X of step k, m) verifying the signature X of the message M by computing the hashed form Hi(M) for i=2, . . . ,m, and verifying that equations Ei(x1, . . . ,xm)=Hi (M) (mod n) are satisfied for i=2, . . . ,m.
Claim 3
Dependent Claim
17 words
The method of claim 1, including the further step of assigning arbitrary values to several yi variables.
Claim 4
Dependent Claim
24 words
The method of claim 1, including the further step of determining the values of several yj variables by solving subsystems of simultaneous linearized equations.
Claim 5
Dependent Claim
18 words
The method of claim 1, wherein the modulus n of step a is selected by a trusted center.
Claim 6
Dependent Claim
22 words
The method of claim 1, including the further step of applying an invertible k×k matrix B to the coefficients of step f.
Claim 7
Dependent Claim
23 words
The method of claim 1, including the further step of combining the coefficients of step f, during verification, by a secret linear combination.
Claim 8
Dependent Claim
21 words
The method of claim 1, wherein the modulus n is selected as a small number in the range (2,2 32 ].
Claim 9
Dependent Claim
266 words
Apparatus for generating and verifying digital signatures comprising: a) means for selecting a modulus n, b) means for selecting k=m-1 secret polynomials Fi of degree d(k>1; d>1, i=2, . . . ,m) where Fi contains variables y1, . . . ,yi-1 in arbitrary form and yi in linear form, c) means f or selecting a secret m×m matrix A with entries in [0,n), d) means for defining a linear transformation Y=AX (mod n) e) means f or replacing each yj in each Fi by linear combination of xt variables defined by A and simplifying the resulting polynomials Ei, f) means for selecting coefficients of all the Ei polynomials and using them as a public key, g) means for generating a message M, h) means for computing the hashed form Hi(M) for i=2, . . . ,m, i) means for selecting a value for y1 in [0,n), j) means for sequentially solving the linear equations in yi derived from Fi(y1, . . . ,yi)=Hi (M) (mod n) for i=2, . . . ,m, k) means for computing X=A -1 Y (mod n) to derive a signature X of the entity to prove its identity, l) means for transmitting to a verifier the modulus n of step a, the public key of step f, the message M of step q and the signature X of step k, m) means for verifying the signature X of the message M by computing the hashed form Hi (M) for i=2, . . . ,m, and verifying that equations Ei(x1, . . . ,xm)=Hi(M)(mod/n) are satisfied for i=2, . . . ,m.
Claim 10
Dependent Claim
266 words
Apparatus for generating and verifying digital signatures comprising: a) means for selecting a modulus n, b) means for selecting k=m-1 secret polynomials Fi of degree d(k>1; d>1, i=2, . . . ,m) where Fi contains variables y1, . . . ,yi-1 in arbitrary form and yi in linear form, c) means f or selecting a secret m×m matrix A with entries in [0,n), d) means for defining a linear transformation Y=AX (mod n) e) means f or replacing each yj in each Fi by linear combination of xt variables defined by A and simplifying the resulting polynomials Ei, f) means for selecting coefficients of all the Ei polynomials and using them as a public key, g) means for generating a message M, h) means for computing the hashed form Hi(M) for i=2, . . . ,m, i) means for selecting a value for y1 in [0,n), j) means for sequentially solving the linear equations in yi derived from Fi(y1, . . . ,yi)=Hi (M) (mod n) for i=2, . . . ,m, k) means for computing X=A -1 Y (mod n) to derive a signature X of the entity to prove its identity, l) means for transmitting to a verifier the modulus n of step a, the public key of step f, the message M of step q and the signature X of step k, m) means for verifying the signature X of the message M by computing the hashed form Hi (M) for i=2, . . . ,m, and verifying that equations Ei(x1, . . . ,xm)=Hi(M)(mod/n) are satisfied for i=2, . . . ,m.
Claim 11
Dependent Claim
14 words
Apparatus according to claim 8, wherein arbitrary values are assigned to several yi variables.
Claim 12
Dependent Claim
24 words
Apparatus according to claim 8, wherein means are provided for determining the values of several yj variables by solving subsystems of simultaneous linearized equations.
Claim 13
Dependent Claim
15 words
Apparatus according to claim 8, wherein the modulus n is provided by a trusted center.
Claim 14
Dependent Claim
19 words
Apparatus according to claim 8, wherein means are provided for applying an invertible k×k matrix B to the coefficients.
Claim 15
Dependent Claim
20 words
Apparatus according to claim 8, wherein means are provided to combine the coefficients during verification, by a secret linear combination.
Claim 16
Dependent Claim
19 words
Apparatus according to claim 8, wherein the modulus n is a small number in the range [2,2 32 ].
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-11-15 | 1997-05-17 | 1997-11-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-11-15 | 2001-05-17 | 2001-11-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-11-15 | 2005-05-17 | 2005-11-16 | $7700.00 | Window Closed / Lapsed |