5
$\begingroup$

How to get a strategy $(s_1,...,s_{t-1})$ as mentioned in section 1.3.7 of SIKE spec?

If possible, can anyone give me an example?

And why do we need to compute all leaf point? I though we just need the right most leaf point to get an isogeny of smooth degree ${l_A}^{e_A}$

$\endgroup$
9
$\begingroup$

On page 67 of the same spec, Algorithm 42 does exactly what you are asking for. Here it is again in Python:

def strategy(n, p, q):
    S = { 1: [] }
    C = { 1: 0 }
    for i in range(2, n+2):
        b, cost = min(((b, C[i-b] + C[b] + b*p + (i-b)*q) for b in range(1,i)),
                      key=lambda t: t[1])
        S[i] = [b] + S[i-b] + S[b]
        C[i] = cost
    return S[n+1]

The parameters p and q are used to weigh the strategy, they depend on your implementation of SIKE. Following the definitions of the spec, p is the cost of one multiplication step, q the cost of one isogeny step.

When choosing a strategy, there may be other considerations than those related to the weights p and q. For example, you may prefer a strategy that is slightly more costly, but easier to parallelize. So the algorithm above is by no means a definitive answer: you should choose whatever strategy works best for you, as long as it is a valid one (see page 15 of the spec). If you have no idea what's best for you, choose the ones given in appendix C of the spec, or use a non-optimized strategy.

Regarding your "why" question, each "leaf point" defines the kernel of one ℓ-isogeny step. You want to compute all of them, so you can compute all isogenies, and compose them. This is not a theorem. It is just the best way we know.

$\endgroup$
  • 1
    $\begingroup$ I love when original authors jump in to answer a question :) $\endgroup$ – Mike Ounsworth Apr 17 '18 at 18:21
  • 3
    $\begingroup$ Well, you know. It's called after-sale :) $\endgroup$ – Luca De Feo Apr 18 '18 at 21:56
1
$\begingroup$

Notice that the original Algorithm 42 in SIKE specification takes quadratic time to compute the optimal strategy.
It was recently improved to O(n log n) time complexity and is described in Algorithm 6.2 of Faster Isogeny-based Compressed Key Agreement. It is now fast enough so that the strategy can be computed at runtime instead of being precomputed and stored.

Here is the related python code:

def strategy(n, p, q):
    C = [0 for k in range(0, n+1)]
    P = [0 for k in range(0, n+1)]
    for k in range(2, n+1):
        j, z = 1, k-1
        while j < z:
            m = j + (z - j) // 2
            if C[m] + C[k - m] + (k - m)*p + m*q <= C[m + 1] + C[k - (m + 1)] + (k - (m + 1))*p + (m + 1)*q:
                z = m
            else:
                j = m + 1
        C[k] = C[j] + C[k - j] + (k - j)*p + j*q
        P[k] = j
    print "Cost: ", C[n]
    return P
$\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.