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

In general it's hard to calculate the roots of a given polynomial $P(x)$. But the other way back calculating the coefficients is much easier (Vieta's formulas).

If this is a one-way function, is it possible to create a public-key cryptosystem based on these facts? Or does it already exist?

share|improve this question
7  
Actually, it is easy to compute the roots of a polynomial $P(x)$ defined over a finite field. – poncho Mar 19 '14 at 16:58
1  
Ok, but what about non-finite fields? – RomeoAndJuliet Mar 19 '14 at 17:07
8  
With an infinite field, $P(x)$ may not be expressible in a fixed number of bits (or, depending on the field, even a bounded number of bits). That puts rather a crimp in the cryptographical applications. – poncho Mar 19 '14 at 17:44

First, note that having a one-way function is far from enough to construct a public-key encryption scheme (a famous result of Impagliazzo and Rudich actually shows that it is impossible to construct public key schemes from one way functions only).

Second, cryptographic constructions which aim at being implemented at some point rely on the hardness of problems over finite sets in general (this is a vague statement, but quite intuitive). Over finite fields, finding roots of a univariate polynomial is easy.

However, a problem related to what you ask about is that of the difficulty of solving systems of equations of multivariate polynomials. This problem is hard (it is even NP-hard) and was used as the underlying cryptographic assumption for the construction of public key cryptosystems and signatures schemes. Unfortunately, no public key cryptosystem built on such assumption has survived cryptanalysis (to my knowledge); every attempt was proven insecure at some point (this is not true, however, for signature schemes).

Hence, even though it might be possible to construct public key cryptosystem based on problems related to finding roots of (multivariate) polynomials, this has proven to be at least a very hard task. See e.g. the Wikipedia article on Multivariate cryptography for more details on the topic.

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.