3
$\begingroup$

As I understand the most widely used method to exchange encrypted data over untrusted network is Diffie-Hellman protocol. Protocol itself doesn't define how to encrypt data, but it defines a usage pattern of public/private keys and implementation can vary.

So, original idea was to use big prime numbers (1 number, 1-D) and their combinations as public/private keys. After a while elliptic curves (x and y coordinates, 2-D) was discovered, so now everyone using them.

Do elliptic curves have more cryptographic strength than classical approach because of 2 dimensions? Is there any research related to 3rd (or even more) order polynomial that potentially can provide even more cryptographic strength than elliptic curves?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Encryption schemes are not based on some vector spaces, but on computationally difficult problems in finite algebraic structures $\endgroup$
    – tylo
    Commented Dec 5, 2017 at 11:01

2 Answers 2

Reset to default
4
$\begingroup$

So, i've just started to figure out how encryption works.

From what you've said, I fear that's not true.

As i understand the most widely used method to exchange encrypted data over untrusted network is Diffie-Hellman protocol.

Partially true, as DH is used as key agreement protocol to further derive session encryption & MAC key. DH is asymmetric, where as encryption and MAC (message authentication code) are symmetric.

So, original idea was to use big prime numbers (1 number, 1-D) ... After a while elliptic curves (x and y coordinates, 2-D) was discovered, so now everyone using them.

The original realization of the idea was to use a big prime number, but those numbers that can be represented in binary system have a exploitable structure make possible attacks faster than brutal-force search.

DH is still realized using scalars, except this time, the scalars are points on elliptic curves over finite fields.

Question is - do elliptic curves have more cryptographic strength than classical approach because of 2 dimensions?

No, they are stronger because they don't have the same exploitable structure as (big) integers.

Is there researches related to 3-rd (or even more) order polynomes that potentially can provide even more cryptographic strength than elliptic curves?

Yes, one of my questions here attracted this comment, but I haven't thoroughly comprehended it, I advise you read it with care if you have time.

Improve this answer
$\endgroup$
1
2
$\begingroup$

If we want to set up a hard discrete log problem, we need a cyclic group of order n with a trapdoor isomorphism to $Z_n$. So we want "weird groups".

Elliptic curves are special algebraic constructions over a field, because they combine, geometrically, and hence algebraically, 3 points: the intersection points with a "straight line" and moreover, they have a two-fold symmetry of their points (mirror symmetry in the x-axis). This is what makes that they should be quadratic in y (for the symmetry) and third order in x (to have 3 intersection points).

Why do we need 3 points ? Because a group operation connects a third point (the result) to two given points. C = A + B. And why do we need the symmetry ? To be able to introduce the inverse element: -A that goes with A. It is the fact that we need an inverse element in a group that is responsible for the $y^2$ ; and it is the fact that a group operation maps a couple of elements to a third one, that makes that we have the $x^3 + ...$ polynomial.

The "miracle" is that this operation is, moreover, associative.

I don't know if there are other algebraic constructions over finite fields that have the same properties, with geometrical constructions in more than 2 dimensions and are not just trivial transformations of elliptic curves.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Actually, cyclic groups are just a subset of the finite groups, which can be used as algebraic structure. Not all elliptic curves over finite groups are cyclic (they can also be the direct product of cyclic groups). $\endgroup$
    – tylo
    Commented Dec 5, 2017 at 11:00
  • $\begingroup$ @tylo: true of course, but a discrete log problem needs a cyclic group as far as I understand. You're right that elliptic groups aren't necessarily cyclic, but the cryptographic (sub)group used is cyclic, by choice of a (single) generator. $\endgroup$
    – entrop-x
    Commented Dec 5, 2017 at 12:07
  • $\begingroup$ Well, the DLOG, CDH and DDH problem are defined with a single generator, but that does not mean they are not true outside of this type of construction. Logically speaking, it's an implication and not a biconditional. The question is asking for constructions beyond the common ones, and key exchange (and public key crypto) do not have to be based on those problems. $\endgroup$
    – tylo
    Commented Dec 5, 2017 at 13:34
  • $\begingroup$ @tylo: I assumed that the question was formulated in the frame of DH, which implies a discrete log problem as far as I understand. I don't know how you can formulate a discrete log problem outside of a cyclic group, because you are asking for the power of the generator. How would you even define a discrete logarithm in a group that doesn't have a single generator (isn't cyclic) ? I read the question as what relationship exists between the encryption strength and the dimensionality in which to define a DH key exchange, not about what other ways there could be to establish a common secret. $\endgroup$
    – entrop-x
    Commented Dec 5, 2017 at 15:51
  • $\begingroup$ Thank you for a very helpful answer. All these crypto-things seem so easy at first sight, but the more i read the less i understand. $\endgroup$
    – Alexander Vtyurin
    Commented Dec 5, 2017 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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