Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm reading about Hidden Field Equations Multivariate scheme. My lecture states that the central map is a univariate polynomial $$P(X)=\sum_{i=0}^{r-1}\sum_{j=0}^{r-1}p_{ij}x^{q^i+q^j} \in K[X]$$ where $K$ is a extension field of the finite field $k=\mathbb{F}_q$ of degree $n$ and $r$ is a small constant chosen in a way such that $P(x)$ can efficiently inverted.

$r$ is a small constant chosen in a way such that $P(x)$ can efficiently inverted.

I would like an example about the last claim please.

share|improve this question
2  
I don't understand what you're asking. The question you appear to be asking can be answered by saying "Let $r=1$", which is surely not what you mean. –  figlesquidge Dec 9 '13 at 18:46
    
I edit my question –  juaninf Dec 9 '13 at 20:21
    
When $r$ is small, the degree of $P$ is at most $2q^{r-1}$. We assume this value is small. You can find several algorithms to find the root of P in textbooks on computer algebra or find programs implementing them; sage, pari, and so on. –  xagawa Dec 10 '13 at 13:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.