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 Multivariate Cryptography and would like to know why we use two affine transformations to scramble the central map?

Why not use only one?

share|improve this question

2 Answers 2

In the majority of multivariate cryptographic schemes (MQ) the encryption/signature function $E$ is a composition of secret affine invertible transformations $A,B$ and a nonlinear transformation $P$ (can be secret or public): $$ E = B\circ P\circ A $$

$P$ is typically invertible, and the goal of the scheme is to make $E$ non-invertible even though it is fully exposed to an attacker as a polynomial.

The mere fact that $P$ is invertible explains why we need both $A$ and $B$. Indeed, suppose that $A$ is missing, then in the equation $$ E(x) = B(P(x)) $$ we substitute $$ x = P^{-1}(y) $$ and obtain $$ E(P^{-1}(y)) = B(y), $$ so we know $B$ and are able to invert $B$.

This is the simplest case; there are other variants, where $P$ is secret, or its inverse is not available in the closed form, or some of the output polynomials are dropped (OK for signatures). In some of these variants both $A$ and $B$ are still required as otherwise you could invert the scheme just by looking at the structure of the polynomial and comparing monomials of $E$ with monomials of $P$. However, say, if $P$ is secret, then both $A$ and $B$ can be considered as part of $P$.

share|improve this answer
    
thanks, ... but for obtain $x=P^{-1}{y}$ the attacker precise know $P$ and this is private, How the attacker will able to obtain $x=P^{-1}{y}$? –  juaninf Dec 2 '13 at 9:51
    
note that, in some signature schemes like UOV, the proposers omit $B$. –  xagawa Dec 2 '13 at 9:55
    
I am not exactly correct in the last sentence, let me change it. –  Dmitry Khovratovich Dec 2 '13 at 10:39
    
@DmitryKhovratovich Do you have any reference where $P$ is public? My references have $P$ always than private. –  juaninf Dec 2 '13 at 10:52
    
@DmitryKhovratovich Can you show Why is necessary $A$ and $B$ when $P$ is secret please? –  juaninf Dec 2 '13 at 11:30

Probably because they figured that using only one affine map might not be secure.

Also, be warned that the Wikipedia article you are citing has serious problems. It is written as though there is a single scheme called "Multivariate Cryptography" with a specific form -- but that is wrong. In fact, multivariate cryptography refers to a class of schemes that happen to use multivariate polynomials in some way. There are many schemes that could be considered multivariate cryptographic schemes. Therefore, I would not trust anything you read in that Wikipedia article. Instead, go read some primary sources.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.