Patent Document ID: 20080013716
Application ID: 11323597
Patent Flag: 0

Claim One:
1. A cryptographic method for application to a multivariate public key cryptosystem (MPKC) to produce new multivariate public key cryptosystems or asymmetric cryptographic communication processes, wherein said multivariate public key cryptosystem is a cryptographic communication process comprising: a) a public transformation which transforms a value (X) represented by a vector of k n , the set or space of (n) elements of a finite field, or ring (k), X=(x 1 ,. .. , x n ), into another value (Y) represented by a vector of k m , the set or space of (m) elements of the finite field or ring (k), Y=(y 1 ,. .. , y m ), through a set of m multivariate polynomials, (ƒ 1 (x 1 ,. .. , x n ),. .. , ƒ m (x 1 ,. .. , x n )) over (k) which are publicly available, have a low degree (d) and the transformation is computed as (ƒ 1 (x 1 ,. .. , x n ),. .. , ƒ m (x 1 ,. .. , x n ))=(y 1 ,. .. , y m ); wherein the public transformation can be used by anyone for encrypting a message or verifying the authenticity of a digital signature or a digital authentication code for a document; b) a secret transformation for obtaining a or the value (X) from the value (Y) by means of inverting the transformation defined by (ƒ 1 (x 1 ,. .. , x n ),. .. , ƒ m (x 1 ,. .. , x n )), with the knowledge of a cryptographic secret, wherein the secret transformation is used by a legitimate user, who has the knowledge of the cryptographic secret, to decrypt a message, or produce a digital signature for a document, or a authentication code for a document; c) wherein a family of new multivariate public key cryptosystems or new asymmetric cryptographic communication process over any priory existing MPKC is produced, comprising the steps: i) adding directly into the prior MPKC internal perturbation through a small number (r ) of randomly or specially chosen internal variables z i = ∑ j = 1 n ⁢ a ij ⁢ x j + b i , i=1,. .. ,r whose linear part without the constant term b i are linearly independent as linear functions of x i ; ii) appending (α) more components, which are randomly or specially chosen polynomials to the already perturbed MPKC, and mixing everything together through composing randomly or specially chosen invertible affine or linear transformations, such that the new MPKC has a new public transformation for transforming a value (X) represented by (n) elements of a finite field, or ring (k), X=(x 1 ,. .. , x n ), into another value (Y + ) represented by (m+α) elements of the finite field or ring (k), Y + =(y 1 ,. .. , y m+α )a through the new set of (m+α) multivariate polynomials (ƒ 1 + (x 1 ,. .. , x n ),. .. , ƒ + m+α (x 1 ,. .. , x n )) over (k); and iii) a secret transformation for obtaining a or the value (X) from the value (Y + ) by means of inverting the transformation defined by (ƒ 1 + (x 1 ,. .. , x n ),. .. , ƒ + m+α (x 1 ,. .. , x n ), with the knowledge of the original cryptographic secret and the secrets in the adding step and appending step.