How to get an optimal strategy in computing isogenies for SIDH/SIKE

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}$

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)
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.

• I love when original authors jump in to answer a question :) Apr 17 '18 at 18:21
• Well, you know. It's called after-sale :) Apr 18 '18 at 21:56

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