Hidden Field Equations - Encryption and Decryption

Encryption and Decryption

The public key is given by the multivariate polynomials over . It is thus necessary to transfer the message from in order to encrypt it, i.e. we assume that is a vector . To encrypt message we evaluate each at . The ciphertext is .

To understand decryption let us express encryption in terms of . Note that these are not available to the sender. By evaluating the at the message we first apply, resulting in . At this point is transferred from so we can apply the private polynomial which is over and this result is denoted by . Once again, is transferred to the vector and the transformation is applied and the final output is produced from .

To decrypt, the above steps are done in reverse order. This is possible if the private key is known. The crucial step in the deciphering is not the inversion of and but rather the computations of the solution of . Since is not necessary a bijection, one may find more than one solution to this inversion (there exist at most d different solutions since is a polynomial of degree d). The redundancy denoted as is added at the first step to the message in order to select the right from the set of solutions . The diagram below shows the basic HFE for encryption.