0
$\begingroup$

Is there any quantum resistant public key cryptography with similar properties of elliptic curves?

Assuming lowercase for scalars and uppercase for points. The properties I'm interested are:

  1. Reusing the same public key.
  2. Given $k = a + b$ then $k \times G = (a + b) \times G$
  3. Distributive Scalars: $(a + b) \times G = a \times G + b \times G$
  4. Distributive Points: $k \times (A + B) = k \times A + k \times B$
  5. Commutative Sum: $(a + b) \times G = (b + a) \times G$
  6. Commutative Mul: $a \cdot b \times G = b \cdot a \times G$

How existing solutions map to the same properties? I'm interested in the direct applications not how it fundamentally works.

| improve this question | |
$\endgroup$
  • $\begingroup$ What were you hoping to do with such a beast, if it were to exist? $\endgroup$ – Squeamish Ossifrage Oct 23 '19 at 15:27
  • $\begingroup$ @SqueamishOssifrage: I have many useful schemes and ideas that combine (n,t)-threshold cryptography with ECC (i.e. pseudonymisation and break-the-glass). $\endgroup$ – shumy Jan 29 at 13:15
1
$\begingroup$

Is there any quantum resistant public key cryptography with similar properties of elliptic curves?

Not at the level you're asking about.

The issue is that Shor's algorithm can generically solve the problem "given $A, x \times A$, recover $x$" for any finite group (and going to an infinite group looks problematic for large $x$). Hence, we'd need to base the algorithm on a different hard problem, and I don't know of any suitable one that fits in the framework you're looking for.

In any case, basing things on a different hard problem would imply that the crypto would look quite different (even if it happens to satisfy the identities you're looking for)

How existing solutions map to the same properties?

They don't satisfy those identities; instead, they use different properties to provide public key encryption and signatures (and more advanced primitives, such as IBE and PAKE).

| improve this answer | |
$\endgroup$
  • $\begingroup$ I was hoping for a way to migrate custom schemes to new post-quantum schemes. But these rely heavily on those math properties. $\endgroup$ – shumy Oct 23 '19 at 15:56
  • $\begingroup$ I was hoping that random walks in Supersingular Isogeny could map to $x \times A$, but I dont understand its properties enough. Does it have any subset of the requirements? $\endgroup$ – shumy Oct 23 '19 at 16:01
  • 1
    $\begingroup$ @shumy: well, I don't know of good way to add either 'two random walks' or 'two elliptic curves' (in a way that preserves the properties), so relations 2-6 are out. Safe key reuse is possible, but tricky. That leaves 7 (which SIDH depends on). $\endgroup$ – poncho Oct 24 '19 at 2:35
  • 1
    $\begingroup$ Sophism time! "The issue is that Shor's algorithm can generically solve the problem "given A,x×A, recover x" for any finite group". If you look at CSIDH, you realize this statement is not accurate: it depends on the way you "represent" elements of the group. But the representation in CSIDH takes away the possibility of adding elements (basically what you are saying about "adding random walks"), and actually it even takes away the possibility of saying who the identity element is. $\endgroup$ – Luca De Feo Oct 24 '19 at 9:56
  • $\begingroup$ @LucaDeFeo: I was using the meaning $x \times A = A + A + A + … + A$ ($x$ times). I believe (and you would be the expert, so feel free to correct me) that CSIDH uses a different meaning of $\times$, and so my statement doesn't apply. For that matter, if you don't have an 'identity element', then you don't have a 'group'... $\endgroup$ – poncho Oct 24 '19 at 13:30

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.