Patent US2022264A successfully refreshed from Google Patents.
Patent US5375170A successfully refreshed from Google Patents.
US5375170A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Efficient signature scheme based on birational permutations
Assignee: Yeda Research and Development Co Ltd
•
Filing: 1993-04-19
•
Granted: 1994-12-20
•
Expires: 2013-04-19
Abstract
Abstract A birational permutation is a function f which is a one-to-one and onto mapping over k-tuples of numbers, where both f and its inverse are low degree rational functions. This patent describes a novel digital signature scheme which is based on a new class of birational permutations which have small keys and require few arithmetic operations.
Inventors
- 👤 Adi Shamir
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 07:54
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/30; H04L9/3066; H04L9/3073; H04L9/32; H04L9/3247
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
230 words
A method of generating and verifying digital signatures comprising the steps of: a) selecting a birational mapping (v 1 , . . . , vk)=f(x 1 , . . . , x k ) comprising k>1 rational functions v 1 =f i (x 1 , . . . , v k ); b) selecting first s(1≦s<k) of fi functions and using them as a public key; c) maintaining inverse of f as a private key; d) generating a digital message M; e) computing v 1 =h(M,i) for i=1, . . . , s where h is a publicly known cryptographic hash function; selecting v 1 =r i for i=s+1, . . . , k where r i is a randomly chosen value; g) computing signature (x 1 , . . . , x k ) using inverse of f to satisfy (v 1 , . . . , v k )=f(x 1 , . . . , x k ); h) transmitting to a verifier the digital message M, and the signature of step f); and i) verifying the signature of step f) of message M by computing v 1 =h(M,i) FDR i=1, . . . , s and checking that v 1 =f i (x 1 , . . . , x k ), where f 1 , . . . , f s is the signer's public key.
Claim 2
Independent Claim
230 words
A method of generating and verifying digital signatures comprising the steps of: a) selecting a birational mapping (v 1 , . . . , vk)=f(x 1 , . . . , x k ) comprising k>1 rational functions v 1 =f i (x 1 , . . . , v k ); b) selecting first s(1≦s<k) of fi functions and using them as a public key; c) maintaining inverse of f as a private key; d) generating a digital message M; e) computing v 1 =h(M,i) for i=1, . . . , s where h is a publicly known cryptographic hash function; selecting v 1 =r i for i=s+1, . . . , k where r i is a randomly chosen value; g) computing signature (x 1 , . . . , x k ) using inverse of f to satisfy (v 1 , . . . , v k )=f(x 1 , . . . , x k ); h) transmitting to a verifier the digital message M, and the signature of step f); and i) verifying the signature of step f) of message M by computing v 1 =h(M,i) FDR i=1, . . . , s and checking that v 1 =f i (x 1 , . . . , x k ), where f 1 , . . . , f s is the signer's public key.
Claim 3
Dependent Claim
15 words
The method of claim 1 wherein the f i functions of step a) are non-linear.
Claim 4
Dependent Claim
20 words
The method of claim 2 wherein the equations of step a) are modulo a large public n with secret factorization.
Claim 5
Independent Claim
253 words
A method of generating and verifying digital signatures comprising the steps of: a) selecting a set F of rational functions in k>l variables; b) selecting an algebraic basis G of F with the property that the representation of any f in F can be easily computed in terms of generators g i in G; c) selecting invertible algebraic transformations and maintaining them as a private key; d) transforming the easy basis G into a hard basis G"; e) selecting a proper subset of 1≦s<k generators g" i in G as a public key; f) generating a digital message M; g) assigning to each g" i with i≦s the hashed value v 1 =h(M,i) of M wherein h is a publicly known cryptographic hash function, and to each g" i with i>s a random number v i =r i ; h) expressing each g i in the easy basis G in terms of generators g" j in the hard basis using private key of step d); i) selecting the values x i of the easy generators of step i) as the signature X of M; and j) verifying the signature X by assigning the values x i from the signature to the easy generators g i , computing values v 1 , . . . , v s of the s hard generators g" j of step f), evaluating the s hashed forms of M using h of step h) and checking that v 1 =h(M,i) for all i=1, . . . , s.
Claim 6
Independent Claim
253 words
A method of generating and verifying digital signatures comprising the steps of: a) selecting a set F of rational functions in k>l variables; b) selecting an algebraic basis G of F with the property that the representation of any f in F can be easily computed in terms of generators g i in G; c) selecting invertible algebraic transformations and maintaining them as a private key; d) transforming the easy basis G into a hard basis G"; e) selecting a proper subset of 1≦s<k generators g" i in G as a public key; f) generating a digital message M; g) assigning to each g" i with i≦s the hashed value v 1 =h(M,i) of M wherein h is a publicly known cryptographic hash function, and to each g" i with i>s a random number v i =r i ; h) expressing each g i in the easy basis G in terms of generators g" j in the hard basis using private key of step d); i) selecting the values x i of the easy generators of step i) as the signature X of M; and j) verifying the signature X by assigning the values x i from the signature to the easy generators g i , computing values v 1 , . . . , v s of the s hard generators g" j of step f), evaluating the s hashed forms of M using h of step h) and checking that v 1 =h(M,i) for all i=1, . . . , s.
Claim 7
Dependent Claim
15 words
The method of claim 4 wherein step c is carried out using invertible linear transformations.
Claim 8
Dependent Claim
19 words
The method of claim 5 wherein the computations are carried out modulo a large public n with secret factorization.
Claim 9
Dependent Claim
82 words
The method of claim 6 where F is the set Fd[y 1 , . . . ,y k ] of homogeneous polynomials of degree d in k variables, and G is a set of monomials y 1 e1 y 2 e2 , . . .y k ek with e 1 +e 2 +. . .+e k =d such that any other monomial in Fd[y 1 , . . . ,y k ] can be generated by a sequence of multiplications and divisions.
Claim 10
Dependent Claim
52 words
The method of claim 7 where d=2 and G is either {y 1 y 2 , . . . ,y k-1 y k ,y k y 1 } for odd k or {y 1 2 , y 1 y 1 , . . . ,y k-1 y k } for arbitrary k.
Claim 11
Dependent Claim
209 words
Apparatus for generating and verifying digital signatures comprising a) means for selecting a birational mapping (v 1 , . . . ,v k )=f (x 1 , . . . , x k ) comprising k>l rational functions v 1 =f i (x 1 , . . . ,v k ); means for selecting first 1=≦s<k of f i functions and using them as a public key; c) means for generating a digital message M; d) means for computing v 1 =h(M,i) for i=1, . . . ,s where h is a publicly known cryptographic hash function; e) means for selecting v 1 =ri for i=s+1, . . . , k; f) means for computing signature (x 1 , . . . ,x k ) using inverse of f to satisfy (v 1 , . . . ,v k )=f(x 1 , . . . ,x k ); g) means for transmitting to a verifier the digital message M, the public key of b) and the signature of f); and h) means for verifying the signature of f) of message M by computing v 1 =h(M,i) for i=1, . . . , s and checking that v 1 =f i (x 1 , . . . ,x k ).
Claim 12
Dependent Claim
209 words
Apparatus for generating and verifying digital signatures comprising a) means for selecting a birational mapping (v 1 , . . . ,v k )=f (x 1 , . . . , x k ) comprising k>l rational functions v 1 =f i (x 1 , . . . ,v k ); means for selecting first 1=≦s<k of f i functions and using them as a public key; c) means for generating a digital message M; d) means for computing v 1 =h(M,i) for i=1, . . . ,s where h is a publicly known cryptographic hash function; e) means for selecting v 1 =ri for i=s+1, . . . , k; f) means for computing signature (x 1 , . . . ,x k ) using inverse of f to satisfy (v 1 , . . . ,v k )=f(x 1 , . . . ,x k ); g) means for transmitting to a verifier the digital message M, the public key of b) and the signature of f); and h) means for verifying the signature of f) of message M by computing v 1 =h(M,i) for i=1, . . . , s and checking that v 1 =f i (x 1 , . . . ,x k ).
Claim 13
Dependent Claim
13 words
The apparatus of claim 9 wherein the fi functions of a) are non-linear.
Claim 14
Dependent Claim
19 words
The apparatus of claim 10 wherein the equations of a) are modulo a large public n with secret factorization.
Claim 15
Dependent Claim
264 words
Apparatus for generating and verifying digital signatures comprising: a) means for selecting a set F of rational functions in k>1 variables; b) means for selecting an algebraic basis G of F with the property that the representation of any f in F can be easily computed in terms of generators g i in G; c) means for selecting invertible algebraic transformation and maintaining them as a private key; d) means for transforming the easy basis G into a hard basis G"; e) means for selecting a proper subset of 5 generators g" i in G as a public key; f) means for generating a digital message M; g) means for assigning to each g" i with i≦s the hashed value v i =h(M,i) of M wherein h is a publicly known cryptographic hash function, and to each g" i with i>s a random number v i =n i ; h) means for expressing each g i in the easy basis G in terms of generators g" j in the hard basis using the private key of d); i) means for selecting the values x i of the easy generators of i) as signature X of M; and j) means for verifying the signature X by assigning the values x i from the signature to the easy generators g i , computing v 1 , . . . ,v s of the S hard generators g" j of f), evaluating the S hashed forms of M using h of step h) and checking that v 1 =h (M,i) for all i=1. . . , s.
Claim 16
Dependent Claim
264 words
Apparatus for generating and verifying digital signatures comprising: a) means for selecting a set F of rational functions in k>1 variables; b) means for selecting an algebraic basis G of F with the property that the representation of any f in F can be easily computed in terms of generators g i in G; c) means for selecting invertible algebraic transformation and maintaining them as a private key; d) means for transforming the easy basis G into a hard basis G"; e) means for selecting a proper subset of 5 generators g" i in G as a public key; f) means for generating a digital message M; g) means for assigning to each g" i with i≦s the hashed value v i =h(M,i) of M wherein h is a publicly known cryptographic hash function, and to each g" i with i>s a random number v i =n i ; h) means for expressing each g i in the easy basis G in terms of generators g" j in the hard basis using the private key of d); i) means for selecting the values x i of the easy generators of i) as signature X of M; and j) means for verifying the signature X by assigning the values x i from the signature to the easy generators g i , computing v 1 , . . . ,v s of the S hard generators g" j of f), evaluating the S hashed forms of M using h of step h) and checking that v 1 =h (M,i) for all i=1. . . , s.
Claim 17
Dependent Claim
19 words
Apparatus of claim 12 wherein the means of c) or d) carries out its function using invertible linear transformations.
Claim 18
Dependent Claim
18 words
Apparatus of claim 13 wherein the computations are carried out modulo a large public n with secret factorization.
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) | 1997-12-19 | 1998-06-20 | 1998-12-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-12-19 | 2002-06-20 | 2002-12-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-12-19 | 2006-06-20 | 2006-12-20 | $7700.00 | Window Closed / Lapsed |