0
$\begingroup$

In use-case we have a (random) generator $g_1$ and perform operations $g_1^{a}$ for known $a$ inside a safe elliptic curve modulo $p$.

Is there any function $f$ which gives us a new (most likely different) generator $g_2$ out of $g_1$ and $a$: $$f(g_1,a) = g_2$$ and the inverse given a generator $g_2$ (which can also be random) deliver us a generator $g_*$ and an exponent $a_*$: $$f^{-1}(g_2) = (g_*,a_*)$$ $$(g_{*},a_*) \in \{ f(g_{°},a_{°}) = g_2\}$$ So $f^{-1}$ only need to deliver one combination $g_*,a_*$ out of all $g_°,a_°$ with $f(g_°,a_°) = g_2$.


About security:

For such $g_1,a,g_2$ it should be infeasible to compute $b$: $$g_1^b \equiv g_2 \mod{p} \text{ (the elliptic curve)}$$ or computing $a_2$ (also true for random $g_1,g_2$): $$g_1^{a} \equiv g_2^{a_2} \mod{p}$$ Given random generators $g_3,g_4$ it should be infeasible to find $a_3$: $$f(g_3,a_3) = g_4$$

The amount off different solutions for all parameter $|\{f(g_°,a_°)\}|$ and $|\{f^{-1}(g_°)\}|$ should be as big as possible.


Special cases:

It would be nice if those $g$ are always generators of the max (prime) cycle length and $a > 2^{200}$ ($f^{-1}$ of a random $g$ (with max cycle length)) in elliptic curve modulo $p > 2^{220}$. But if I'm not mistaken we should almost always get a long enough cycle length and a big enough $a$ if we allow all results. ($p = n_s \cdot p_l +1, n_s\ll p_l$)


All operations including calculation of $f,f^{-1}$ are applied at the local device. The relations noted in security-section should still be unknown for everyone.

$\endgroup$
4
  • 2
    $\begingroup$ $f^{-1}(g_2) = (g_1,a)$; if $q$ is the order of the group, then there are $q$ possible inputs and more than $q$ possible pairs of $g_1, a$. Do you mean that all this inverse operation is required to do is find some $g_1, a$ pair s.t. $f(g_1, a) = g_2$ and not necessarily the same $g_1, a$ pair originally used to generate $g_2$? $\endgroup$
    – poncho
    Jul 17, 2023 at 12:34
  • $\begingroup$ @poncho Oh, you are right. Rewrote it. And yes the inverse only need to find some $g_{*},a_*$ with $f(g_{*},a_*) = g_2$ Don't need to be the same. $\endgroup$
    – J. Doe
    Jul 17, 2023 at 13:11
  • $\begingroup$ Something like the elligator map might help here elligator.org/map. It should be straightforward to compose such a mapping with some additions or subtractions in either the scalar or point domain to implement $f()$ and $f^{-1}()$. $f^{-1}()$ requiring choosing from $q$ possible $f()$input pairs. One problem is half the EC points can't be mapped to scalars. $\endgroup$ Jul 17, 2023 at 21:53
  • $\begingroup$ @RichardThiessen thanks for the hint but I haven't found a way to define $f, f^{-1}$ yet. $f$ with input generator $g=(g_x,g_y)$ (on the elliptic curve) and the current scalar exponent $a$ should lead to a new generator $g'$ as output. In this direction it is not so important if only half (or similar) work. $f^{-1}$ only has a generator $g'$ as input and delivers a generator $g$ and a scalar $a$ as output. This should always be defined. So in total $f$ maps 3 scalars to 2 with the first two on each side laying at the EC. The linked mapping only maps 1 scalar to 2 which lay at the EC. $\endgroup$
    – J. Doe
    Jul 18, 2023 at 2:06

1 Answer 1

1
$\begingroup$

This turns out to be quite simple. We define a reversible permutation f(G,a)-->(G',a') that is a permutation on the set of all (G,a) pairs. The function can be the forward permutation with the a' discarded. The inverse function is the reverse permutation with the a' value set to either a fixed, random, or chosen value.

We define two functions, hash_P2s(P)=s and hash_s2P(s)=P, which take either a point P or a scalar s and pseudorandomly map it to the other type of thing.

The first can be as simple as:

def hash_P2s(P):
    h=sha512(curve.encode(P))
    return bytes_to_int(h)%curve.order

The second (hash to curve) is covered by this IETF document. The simplest option here is to generate random encoded points until one is valid.

Any good hash to curve function generates points whose discrete log is unknown.

def hash_s2P(s):
    i=0
    while 1:
        h=sha512(s2bytes(s)+i.to_bytes(4,"little"))
        #truncate to correct length
        candidate=h[:EC_POINT_ENCODED_LEN]
        #if the result is a valid point, we're done
        if curve.is_valid_point(candidate):
            return curve.decode(candidate)
        #increment and try again
        i+=1

Finally, we put these together into a Feistel-like permutation where a point and a scalar are used to generate another (point,scalar) pair.

def f(G,a):
    G=curve.add(G,hash_s2P(a))
    a=(a+hash_P2s(G))%curve.order
    G=curve.add(G,hash_s2P(a))
    return G,a

The output a value can be discarded but if fed into the inverse function the original (point,scalar) pair will be produced.

def f_inverse(G,a):
    G=curve.sub(G,hash_s2P(a))
    a=(a-hash_P2s(G))%curve.order
    G=curve.sub(G,hash_s2P(a))
    return G,a

If you feed an output G and a random scalar into the inverse function you'll get a random (G,a) input pair of course.

preventing non-generator outputs

The input and output domains of the permutation include all valid points including the zero point which is not a generator. An attacker can find $(G,a)=f^{-1}(0)$ which when run through the function give a non-generator.

One easy way to solve this is to map the zero point to something else at the end of f(). The inverse function won't care since it's not necessarily deterministic.

Security

This is similar to a Feistel network in that we take some state split into two parts (G,a) and use pseudorandom functions that map between the part domains to alternately modify each side.

The GaG modification sequence ensures the function cannot be solved to find a f(G,a)=xG DLOG relation. aG and aGa both allow an attacker to find such a DLOG relationship trivially. GAG is the smallest sequence that does not without a birthday type attack in the point or scalar domain which is as hard as just solving the DLOG problem directly.

$\endgroup$
10
  • $\begingroup$ thanks for the answer(?). Will need some more time thinking about it before marking it as one. GaG is a nice idea. But it need to be deterministic. No (real) random is involved. Each user will get the same results every time. So for $f^{-1}$ it will be a constant $a=1$ or $0$. $\endgroup$
    – J. Doe
    Jul 19, 2023 at 14:03
  • $\begingroup$ But being deterministic would not change anything about the security, right? $\endgroup$
    – J. Doe
    Jul 19, 2023 at 14:29
  • $\begingroup$ Nope, you can obviously just fix the a' input to some arbitrary value. $\endgroup$ Jul 19, 2023 at 15:09
  • $\begingroup$ No impact on security. $\endgroup$ Jul 19, 2023 at 15:13
  • 1
    $\begingroup$ It is very important here that the domain of G and a are very large (~2^256). While this approach to defining a permutation is common in format preserving encryption, when the domain of the two halves is small, you will need more rounds, Even with two halves of 128 bits each, that still allows for meet in the middle attacks using 2^64 work. Three rounds then is insufficient. $\endgroup$ Jul 19, 2023 at 22:47

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.