# Addition-Subtraction Chains with cheap or free doubling

### Related Problem

Standard Addition-Subtraction Chain (ASC) for an integer $$k$$ defines the order of addition/subtraction (doubling) operations so that $$k$$ is finally reached, starting with $$1$$. This is particularly useful in ECC to calculate $$k\cdot P$$ via EC point additions/subtractions & doublings. The goal is to find as short ASC as possible, so that minimal number of addition/subtraction/doubling operations is used. E.g., $$(1,2,4,8,16,32,31)$$ is an ASC for $$31$$ (with many additions/doublings and a final subtraction). However, it seems to be a hard problem to find the shortest ASC.

### My Problem

In the standard ASC's, the complexity of doubling is considered to be equivalent to addition/subtraction, hence the length of the ASC can be the complexity measure. In my scenario, however, doubling is "for free". This leads to a generalization (let's call it ASC²), where the chain does not contain integers, but rather equivalence classes of $$\{k, 2k, 2^2k, 2^3k \ldots\} =: [k]$$ for $$k$$ odd integer. I.e., the previous example can be written very shortly as $$([1],[31])$$ since $$31 = -1 + 2^5\cdot 1$$. The goal is clearly to find the shortest ASC².

### Question(s)

1. Is there/would you suggest any (heuristic) method for finding a "good" ASC²?
2. How could short ASC²'s be generated, so that their optimality is guaranteed?

### Motivation

Implementing arithmetics over encrypted integers (bit-by-bit), ASC² would be useful for scalar multiplication (i.e., multiplication of an encrypted integer by a plaintext integer). In such a representation, doubling a ciphertext is indeed cheap: it is just adding a trivial encryption of zero to the least significant position. On the other hand, addition is very expensive (since it is using FHE), hence it is worth finding the best possible ASC².

• I'm not sure about your motivation (the bit-by-bit FHE-encrypted integers per se, but also how do you subtract in this encoding?), but for addition chains with free doubling and without subtraction you can find the start of a theory (don't get confused by the different phrasing of the problem) in ia.cr/2018/103 and papers citing this eprint like dl.acm.org/doi/abs/10.1007/s12095-021-00512-z or link.springer.com/article/10.1007/s12095-022-00600-8 (I didn't find a free reference for the latter two papers, and would be thankful for such.). Mar 1, 2023 at 17:44
• Thanks @garfunkel, that's indeed an interesting and somehow related research topic. However, the algebraic structure of power permutations in GF(2^n) seems too distant from our use-case: on the one hand, the decomposition mentioned in those papers neglects the "affine" terms (powers of two), on the other hand, the "quadratic" or "cubic" terms are combined via multiplication, unlike addition/subtraction that is used in our case. Honestly, I don't see a relation to addition chains, would you please explain more? (N.b., we actually encrypt signed bits -- then subtraction is easy.) Mar 6, 2023 at 15:17
• Sorry, you're right. Taking logarithms you end up using multiplications mod $2^n-1$ with the second factor a power-of-2-multiple of the first factor in the papers I cited, instead of additions. I should have pointed you instead to the earlier paper ia.cr/2013/345 (see Definition 3 therein). Mar 7, 2023 at 13:02
• Actually, if 2 is a generator modulo $q$, then the shortest possible $ASC^2$ is always of length 0 (and can be found by solving a discrete log problem modulo $q$, which given the typical size of $q$, is feasible if not especially cheap) Oct 27, 2023 at 14:20
• Knuth's AoCP vol. 2, The Seminumerical Algorithms, presents some heuristic methods for finding good additive chains. Section 4.6.3 Evaluation of Powers. Feb 24 at 20:09

1. I think that the sliding window method (and its NAF relative) used to construct good ASC representations is still quite good. If we separate doubling actions from heterogeneous adds and subtracts, sliding windows does not reduce the number of doubles and its benefit is in reducing the number of heterogeneous adds and subtracts from $$O(\log k)$$ to $$O(\log k/\log\log k)$$. Conversely, I think that there is a lower bound on the length of an ASC2 of $$\log\log k$$ as the number of occurrences of 01 or 10 in the binary expansion can roughly speaking at most double at each step.