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)
- Is there/would you suggest any (heuristic) method for finding a "good" ASC²?
- How could short ASC²'s be generated, so that their optimality is guaranteed?
- Does there btw exist any literature about this?
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².
