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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.