Nova Patents
EP0597481A2

Efficient signature schemes based on birational permutations.

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 application describes novel digital signature schemes which are based on new classes of birational permutations which have small keys and require few arithmetic operations and which are used to encrypt messages, establish public keys and create uniquely verifiable signatures.

EP0597481A2, drawing sheet 1
Sheet 1 of 37

Term

Term ended

Projected expiry passed 11 November 2013, 12.9 years ago.

  1. Priority
  2. Filed
  3. Published
  4. Projected expiry
  5. Today

16 claims: 7 independent, 9 dependent

  1. 1
    A method of generating and verifying digital signatures comprising the steps of:a) selecting a birational mapping (v₁,...,vk)=f(x₁,...,xk) comprising k>1 rational functions v₁=fi(x₁,...,vk);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₁=h(M,i) for i=1,...,s where h is a publicly known cryptographic hash function;f) selecting v₁=ri for i=s+1,...,k where ri is a randomly chosen value;g) computing signature {x₁,...,xk} using inverse of f to satisfy (v₁,...,vk) = f(x₁,...,xk);h) transmitting to a verifier the digital message M, and the signature of step f);andi) verifying the signature of step f) of message M by computing v₁=h(M,i) FDR i=1,...,s and checking that v₁=fi(x₁,...,xk), where f₁,...,fs is the signer's public key.
  2. 4
    A method of generating and verifying digital signatures comprising the steps of:a) selecting a set F of rational functions in k>1 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 gi 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≦ss a random number vi=ri;h) expressing each gi 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 xi of the easy generators of step i) as the signature X of M;andj) verifying the signature X by assigning the values xi from the signature to the easy generators gi, computing values v₁,...,vs 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₁=h(M,i) for all i=1,...,s.
  3. 9
    The method of generating and verifying digital signatures comprising the steps of:a) selecting a modulus n,b) selecting k secret polynomials Fi of degree d (k>1, d>1) where Fi contains variables y₁,....,yi-1 in arbitrary form and yi in linear form,c) selecting two secret kxk matrices A and B with entries in [O,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) mixing the k Ei polynomials by the linear transformation B,g) selecting the coefficients of a proper subset of s<k Ei polynomials and using them as a public key,h) generating a message M, and computing the hashed form Hi(M) for the selected indices i, and applying to them the inverse linear transformation B⁻¹,i) selecting arbitrary values for the yi's,j) sequentially solving the linear equations in yi derived from Fi (y₁,......,yi) = Hi(M)(mod n) for the selected indices i,k) computing X=A⁻¹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 g, the message M of step h and the signature X of step k, andm) verifying the signature X of the message M by computing the hashed form Hi(M) for all the selected indices i, and verifying that equations Ei(x₁,....,xm) = Hi(M)(mod n) are satisfied.
  4. 10
    Apparatus for generating and verifying digital signatures comprising a) means for selecting a birational mapping (v₁,...,vk)=f(x₁,...,xk) comprising k>1 rational functions v₁=fi (x₁,...,vk) ;b) means for selecting first 1=≦s<k of fi functions and using them as a public key;c) means for generating a digital message M;d) means for computing v₁=h(M,i) for i=1,...,s where h is a publicly known cryptographic hash function;e) means for selecting v₁=ri for i=s+1,...,k;f) means for computing signature (x₁,...,xk) using inverse of f to satisfy (v₁,...,vk)=f(x₁,...,xk) ;g) means for transmitting to a verifier the digital message M, the public key of b) and the signature of f);andh) means for verifying the signature of f) of message M by computing v₁=h(M,i) for i=1,...,s and checking that v₁=fi (x₁,...,xk).
  5. 11
    The apparatus of claim to wherein the fi functions of a) are non-linear.
  6. 13
    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 gi 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 vi=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 vi=ni;h) means for expressing each gi 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 xi of the easy generators of i) as signature X of M;andj) means for verifying the signature X by assigning the values xi from the signature to the easy generators gi, computing v₁,...,vs 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₁=h(M,i) for all i=1,...,s.
  7. 16
    Apparatus for generating and verifying digital signatures comprising:i) means for establishing a modulus n, a public key, a message M and a signature X through encryption to enable signature X to be uniquely verifiable including a) selecting a modulus n,b) selecting k secret polynomials Fi of degree d (k>1,d>1) where Fi contains variables y₁,....,yi+1 in arbitrary form and yi in linear form,c) selecting two secret kxk matrices A and B with entries in [O,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) mixing the k Ei polynomials by the linear transformation B,g) selecting the coefficients of a proper subset of s<k Ei polynomials and using them as a public key,h) generating a message M, and computing the hashed form Hi(M) for the selected indices i, and applying to them the inverse linear transformation B⁻¹,i) selecting arbitrary values for the yi's,j) sequentially solving the linear equations in yi derived from Fi (y₁,......,yi) = Hi(M)(mod n) for the selected indices i,k) computing X=A⁻¹Y (mod n) to derive a signature X of message M,ii) means for transmitting to a verifier the modulus n, the public key, the message M, and the signature X to submit same for verification of the signature X, andiii) means for receiving and verifying the signature X of the message M by computing the hashed form Hi(M) for all the selected indices i, and verifying that equations Ei(x₁,....,xm) = Hi(M)(mod n) are satisfied to prove the verification of signature X.
Independent claims7