2
$\begingroup$

I'd like to get just the mechanics of multivariate-quadratic cryptography, so I'm trying to understand the definitions involved. From Wolfram's website, I get that a quadratic map is for example a recurrence of the form $x_{n+1} = 2 + (x_n)^2$. I will need an initial value too, right? I choose $x_0 = 3$. What's the inverse of this map and how do I get it?

I'm guessing an inverse of a quadratic map would be the transformation that takes $x_n$ back to $x_{n-1}$ so the using the example given in the first paragraph, $x_0 = 3, x_1 = 11, x_2 = 123$. So given $x_2 = 123$, I can return to 11 by subtracting 2 and taking square root: that is, $x_{n-1} = \sqrt{x_n - 2}$ is the inverse map of my example.

It's just a guess. I've never seen these things before. Can't find any reference that explains this in baby-steps.

Also, I'm wondering what would be an example of a quadratic map whose input is say a vector. My example is a 1x1 vector. What would it look if my input would be a 2x1 vector?

Improve this question
$\endgroup$
6
  • $\begingroup$ Do you know what a finite field is? Your example makes me think that you work with real numbers instead. If it is so, try understanding finite fields first. $\endgroup$ – j.p. Nov 23 '17 at 7:25
  • $\begingroup$ I have a basic introduction to them. From the top of my mind for instance, I know a field lets me divide and subtract, which means I have multiplicative inverses, excluding the additive identity, I have additive inverses. (I had a feeling commutativity is also required, but couldn't say without looking up.) And being finite just means the set of elements is finite. $\endgroup$ – user53388 Nov 23 '17 at 16:26
  • $\begingroup$ Feel free to ignore my example. Some webpage mentioned the term "quadratic map" and Wolfram's gave me this recurrence relation. But as I read more, I think it's not that kind of quadratic map that's involved. Perhaps they're just quadratic polynomials, no need for recurrence relations at all. Feel free to ignore the example. Let me tell you what I have understood so far. I think the elements involved are a finite field, affine transformations, the inverse of these transformations and a ring of polynomials over the field. I don't yet know how to find an example of a ring of polynomials. $\endgroup$ – user53388 Nov 23 '17 at 16:33
  • $\begingroup$ Do you have access to a university library? If yes, take a look at Neil Koblitz' "Algebraic Aspects of Cryptography". Chapter 3 for some basic math, and chapter 4 for hidden monomial cryptosystems. $\endgroup$ – j.p. Nov 24 '17 at 6:58
  • $\begingroup$ Thanks! Got the book! Will report back in case of any questions! $\endgroup$ – user53388 Nov 27 '17 at 15:43
3
$\begingroup$

In cryptographic applications a quadratic map is generally conceived as a system of n quadratic equations in n variables. Each equation is generally represented as an n-long vector of n variables x and a matrix Mi (for equation i of the system. The equation is then:

(x^T)Mi(x) = ai

Your are then given the n matrices Mi, and a resultant vector of the ai. The inversion you are looking for is to find a vector x such that:

(x^T)Mi(x) = ai for all i

If the Mi are chosen at random then the problem of finding a solution to this problem is believed to be intractably hard (NP-hard in fact). If the Mi are specially chosen (not random at all) one can make inversion easy. Mulivariate Quadratic cryptography tries to take an easy to solve quadratic map and transform it into a seemingly difficult to solve map.

If you look at the Unbalanced Oil and Vinegar schemes:

https://en.wikipedia.org/wiki/Unbalanced_Oil_and_Vinegar

you get an idea of one such system.

Improve this answer
$\endgroup$
0
$\begingroup$

The stream cipher Quad:

https://en.wikipedia.org/wiki/QUAD_(cipher)

is an example of a cryptographic system which uses a random (and therefore hard to invert) quadratic map. The basic structure of Quad was used to create a Deterministic Random Bit Generator for an ISO standard.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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