Continuous stirred-tank reactor

2014-01-29T14:09:39Z

131.174.15.128:

{{cleanup|date=January 2009}}

'''Hidden Fields Equations (HFE)''' is a [[public key]] [[cryptosystem]] which was introduced at [[Eurocrypt]] in 1996 and proposed by {{fr icon}} [[:fr:Jacques Patarin|Jacques Patarin]] following the idea of the [[Matsumoto]] and [[Imai]] system. '''HFE''' is also known as HFE trapdoor function. It is based on [[polynomials]] over [[finite fields]] <math>\mathbb{F}_q </math> of different size to disguise the relationship between the [[private key]] and [[public key]]. '''HFE''' is in fact a family which consists of basic '''HFE''' and combinatorial versions of '''HFE'''. The HFE family of cryptosystems is based on the hardness of the problem of finding solutions to a system of multivariate [[quadratic equations]] (the so-called MQ problem) since it uses private [[affine transformations]] to hide the extension field and the private [[polynomials]]. Hidden Field Equations also have been used to construct digital signature schemes, e.g. Quartz and Sflash.<ref name="autogenerated2">[http://eprint.iacr.org/2001/029.pdf Christopher Wolf and Bart Preneel, Asymmetric Cryptography: Hidden Field Equations]</ref>

== Mathematical background ==
One of the central notions to understand how Hidden Field Equations work is to see that for two extension fields <math>\mathbb{F}_{q^n} </math> <math>\mathbb{F}_{q^m} </math> over the same base field <math>\mathbb{F}_q</math> one can interpret a system of <math>m</math> multivariate [[polynomials]] in <math>n</math> variables over <math>\mathbb{F}_q</math> as a function <math>\mathbb{F}_{q^n} \to \mathbb{F}_{q^m} </math> by using a suitable [[basis (linear algebra)|basis]] of <math>\mathbb{F}_{q^n} </math> over <math>\mathbb{F}_q</math>. In almost all applications the polynomials are quadratic, i.e. they have degree 2.<ref name="autogenerated1">[http://eprint.iacr.org/2001/029.pdf Nicolas T. Courtois On Multivariate Signature-only public key cryptosystems]</ref> We start with the simplest kind of polynomials, namely monomials, and show how they lead to quadratic systems of equations.

Let us consider a [[finite fields|finite field]] <math> \mathbb{F}_q</math>, where <math> q </math> is a power of 2, and an extension field <math>K</math>. Let <math>\beta_1,...,\beta_n</math> to be a [[basis (linear algebra)|basis]] of <math> K </math> as an <math>\mathbb{F}_q </math> [[vector space]]. Let <math> 0<h<q^n </math> such that <math> h=q^{\theta}+1 </math> for some <math>\theta</math> and [[Greatest common divisor of two polynomials|gcd]]<math> (h,q^n-1)=1 </math> and take a random element <math> u\in \mathbb{F}_{q^n}</math>. We represent <math>u</math> with respect to the basis as <math>u=(u_1,...,u_n)</math>. Define <math>v\in \mathbb{F}_{q^n}</math> by

:<math> v=u^{q^\theta} u \ \ \ \ (1)</math>

The condition [[Greatest common divisor of two polynomials|gcd]]<math> (h,q^n-1) =1 </math> is equivalent to requiring that the map <math> u \to u^h </math> on <math> K </math> is one to one and its inverse is the map <math> u \to u^{h'} </math> where <math> h' </math> is the multiplicative inverse of <math> h \ \bmod q^n-1 </math>. Choose two secret affine transformation, i.e. two invertible <math>n\times n</math> matrices <math> S=\{S_{ij}\} </math> and <math> T=\{T_{ij}\} </math> with entries in <math>\mathbb{F}_q </math> and two vectors <math> c=(c_1,...,c_n) </math> and <math> d=(d_1,...,d_n) </math> of length <math>n</math> over <math>\mathbb{F}_q </math> and define <math>x</math> and <math>y</math> via:

:<math> u=Sx+c \ \ \ \ v=Ty+d \ \ \ \ (2) </math>

Let <math> A^{(k)}={a_{ij}^{(k)}} </math> be the matrix of linear transformation in the basis <math>\beta_1,...,\beta_n</math> such that

:<math> \beta_{i}^{q^k}=\sum_{j=1}^{n} a_{ij}^{k}\beta_{j},\ \ a_{ij}^{k}\in\mathbb{F}_q</math>

for <math> 1\le i,k\le n </math>. Write all products of basis elements in terms of the basis, i.e.:

:<math> \beta_i\beta_j=\sum_{l=1}^{n}m_{ijl}\beta_{l},\ \ m_{ijl}\in\mathbb{F}_q</math>

for each <math> 1\le i,j\le n </math>. The system of <math> n </math> equations which is explicit in the <math> v_i </math> and quadratic in the <math> u_j </math> can be obtain by expanding (1) and equating to zero the coefficients of the <math> \beta_i </math>. By using the affine relations in (2) to replace the <math> u_j, v_i </math> with <math> x_k,y_l </math>, the system of <math> n </math> equations is [[linear]] in the <math> y_l </math> and of degree 2 in the <math> x_k </math>. Applying [[linear algebra]] it will give <math> n </math> explicit equations, one for each <math> y_l</math> as polynomials of degree 2 in the <math> x_k </math>.<ref name="autogenerated4">[http://eprint.iacr.org/2003/061.pdf Ilia Toli Hidden Polynomial Cryptosystems]</ref>

== Multivariate cryptosystem ==

The basic idea of the HFE family of using this as a multivariate [[cryptosystem]] is to build the secret key starting from a [[polynomial]] <math> P </math> in one unknown <math> x </math> over some [[finite field]] <math>\mathbb{F}_{q^n} </math> (normally value <math> q=2 </math> is used). This [[polynomial]] can be easily inverted over <math>\mathbb{F}_{q^n} </math>, i.e. it is feasible to find any solutions to the equation <math> P(x)=y </math> when such solution exist. The secret transformation either [[decryption]] and/or [[Digital signature|signature]] is based on this inversion. As explained above <math>P</math> can be identified with a system of <math>n</math> equations <math> (p_1,...,p_n) </math> using a fixed basis. To build a [[cryptosystem]] the [[polynomial]] <math> (p_1,...,p_n) </math> must be transformed so that the public information hides the original structure and prevents inversion. This is done by viewing the [[finite fields]] <math>\mathbb{F}_{q^n} </math> as a [[vector space]] over <math>\mathbb{F}_q </math> and by choosing two linear [[affine transformation]]s <math> S </math> and <math> T </math>. The triplet <math> (S,P,T) </math> constitute the private key. The private [[polynomial]] <math> P </math> is defined over <math>\mathbb{F}_{q^n} </math>.<ref name="autogenerated2"/><ref name="autogenerated3">[http://www.ssi.gouv.fr/fr/sciences/fichiers/lcr/fajo03.pdf Jean Charles Faugere and Antoine Joux, Algebraic Cryptanalysis of Hidden Field Equations (HFE) Cryptosystems Using Grobner Bases]</ref> The public key is <math> (p_1,...,p_n) </math>. Below is the diagram for MQ-trapdoor <math> (S,P,T) </math> in HFE
:<math>\text{input} x\to x=(x_1,...,x_n)\overset{\text{secret}: S}{\to}x'\overset{\text{secret}: P}{\to}y'\overset{\text{secret}: T}{\to}\text{output} y</math>

== HFE polynomial ==

The private [[polynomial]] <math> P </math> with degree <math> d </math> over <math> \mathbb{F}_{q^n} </math> is an element of <math> \mathbb{F}_{q^n}[x] </math>. If the terms of [[polynomial]] <math> P </math> have at most [[quadratic polynomial|quadratic]] terms over <math> \mathbb{F}_{q} </math> then it will keep the public polynomial small.<ref name="autogenerated2"/> The case that <math>P</math> consists of monomials of the form <math> x^{q^{s_i}+q^{t_i}}</math>, i.e. with 2 powers of <math>q</math> in the exponent
is the basic version of '''HFE''', i.e. <math> P </math> is chosen as

:<math> P(x)=\sum c_i x^{q^{s_i}+q^{t_i}} </math>

The degree <math> d </math> of the [[polynomial]] is also known as security parameter and the bigger its value the better for security since the resulting set of quadratic equations resembles a randomly chosen set of quadratic equations. On the other side large <math>d</math> slows down the deciphering. Since <math> P </math> is a [[polynomial]] of degree at most <math> d </math> the inverse of <math> P </math>, denoted by <math> P^{-1} </math> can be computed in <math> d^2(\ln d)^{O(1)} n^2 \mathbb{F}_q </math> operations.<ref>Nicolas T. Courtois, "The Security of Hidden Field Equations"</ref>

== Encryption and decryption ==
The public key is given by the <math>n</math> multivariate polynomials <math> (p_1,...,p_n) </math> over <math>\mathbb{F}_q</math>. It is thus necessary to transfer the message <math> M </math> from <math> \mathbb{F}_{q^n} \to \mathbb{F}_q^n </math> in order to encrypt it, i.e. we assume that <math> M </math> is a vector <math> (x_1,...,x_n)\in \mathbb{F}_q^n </math>. To encrypt message <math> M </math> we evaluate each <math>p_i</math> at <math>(x_1,...,x_n)</math>. The ciphertext is <math>(p_1(x_1,...,x_n), p_2(x_1,...,x_n), ... ,p_n(x_1,...,x_n))\in \mathbb{F}_q^n</math>.

To understand decryption let us express encryption in terms of <math> S, T, P </math>. Note that these are ''not'' available to the sender. By evaluating the <math>p_i</math> at the message we first apply <math> S </math>, resulting in <math> x' </math>. At this point <math> x' </math> is transferred from <math> \mathbb{F}{q^n} \to \mathbb{F}_{q^n} </math> so we can apply the private polynomial <math> P </math> which is over <math> \mathbb{F}_{q^n} </math> and this result is denoted by <math> y'\in \mathbb{F}_{q^n} </math>. Once again, <math> y' </math> is transferred to the vector <math> (y_1',...,y_n') </math> and the transformation <math> T </math> is applied and the final output <math> y\in \mathbb{F}_{q^n} </math> is produced from <math> (y_1,...,y_n)\in \mathbb{F}_q^n </math>.

To decrypt <math> y </math>, the above steps are done in reverse order. This is possible if the private key <math> (S,P,T) </math> is known. The crucial step in the deciphering is not the inversion of <math> S </math> and <math> T </math> but rather the computations of the solution of <math> P(x')=y' </math>. Since <math> P </math> is not necessary a bijection, one may find more than one solution to this inversion (there exist at most d different solutions <math> X'=(x_1',...,x_d')\in\mathbb{F}_{q^n} </math> since <math> P </math> is a polynomial of degree d). The redundancy denoted as <math> r </math> is added at the first step to the message <math> M </math> in order to select the right <math> M </math> from the set of solutions <math> X'</math>.<ref name="autogenerated2"/><ref name="autogenerated4"/><ref>[http://www.cryptosystem.net/hfe.pdf Jacques Patarin, Hidden Field Equations (HFE) and Isomorphic Polynomial (IP): two new families of asymmetric algorithm]</ref> The diagram below shows the basic HFE for encryption.
:<math>M\overset{+r}{\to}x\overset{\text{secret}: S}{\to}x'\overset{\text{secret}: P}{\to}y'\overset{\text{secret}: T}{\to}y</math>

== HFE variations ==

Hidden Field Equations has four basic variations namely '''+,-,v and f''' and it is possible to combine them in various way. The basic principle is the following:

:01. The '''+''' sign consists of linearity mixing of the public equations with some random equations.
:02. The '''-''' sign is due to Adi Shamir and intends to remove the redundancy 'r' of the public equations.
:03. The '''f''' sign consists of fixing some <math> f </math> input variables of the public key.
:04. The '''v''' sign is defined as a construction and sometimes quite complex such that the inverse of the function can be found only if some v of the variables called vinegar variables are fixed. This idea is due to Jacques Patarin.

The operations above preserve to some extent the trapdoor solvability of the function.

HFE- and HFEv are very useful in signature schemes as they prevent from slowing down the signature generation and also enhance the overall security of HFE whereas for [[encryption]] both HFE- and HFEv will lead to a rather slow [[decryption]] process so neither too many equations can be removed (HFE-) nor too many variables should be added (HFEv). Both HFE- and HFEv were used to obtain Quartz.

For encryption, the situation is better with HFE+ since the [[decryption]] process takes the same amount of time, however the public key has more equations than variables.<ref name="autogenerated2"/><ref name="autogenerated1"/>

== HFE attacks ==

There are two famous recent attacks on HFE:

01. Shamir-Kipnis: Recover the Private Key.

The key point of this attack is to recover the private key as sparse univariate polynomials over the extension field <math> \mathbb{F}_{q^n} </math>. The attack only works for basic HFE and fails for all its variations.

02. Faugere: Fast Gröbner Bases.

The idea of Faugere's attacks is to use fast algorithm to compute a [[Gröbner basis]] of the system of polynomial equations. Faugere broke the HFE challenge 1 in 96 hours in 2002 and in 2003 Faugere and Joux worked together on the security of HFE.<ref name="autogenerated2"/>

== References ==
{{Reflist}}
* [http://eprint.iacr.org/2002/138 Nicolas T. Courtouis, Magnus Daum and Patrick Felke, On the Security of HFE, HFEv- and Quartz]
* [http://www.win.tue.nl/~asidoren/HFE2004.pdf Andrey Sidorenko, Hidden Field Equations, EIDMA Seminar 2004 Technische Universiteit Eindhoven]
* Yvo G. Desmet, Public Key Cryptography-PKC 2003, ISBN 3-540-00324-X

==External links==
* [http://www.minrank.org/hfe/ Nicolas Courtois HFE page]
{{Cryptography navbox | public-key}}

[[Category:Public-key encryption schemes]]
[[Category:Finite fields]]
[[Category:Multivariate cryptography]]

Passive matrix addressing

2011-01-07T10:03:30Z

131.174.15.233:

Roberto is the name I love to be called with although it definitely is not the name on my birth certificate. I am a [http://photobucket.com/images/cashier cashier]. My friends say it's not really for me but the language I love doing is considered to be to drive but I have been taking on new-found things lately. My house is now in Vermont. I've been working on individual website for some period now. Check it competeing here: http://circuspartypanama.com<br><br>my web blog - [http://circuspartypanama.com clash of clans Hack no Survey download]

formulasearchengine - User contributions [en]

Continuous stirred-tank reactor

Passive matrix addressing