Addition-Subtraction Chains with cheap or free doubling

ph flag

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


  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?
  3. Does there btw exist any literature about this?


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

ye flag
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 and papers citing this eprint like or (I didn't find a free reference for the latter two papers, and would be thankful for such.).
ph flag
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.)
ye flag
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 (see Definition 3 therein).
ru flag
  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.

  2. Optimality is likely to hard to show. It is known for example that computing optimal ASCs for a set of exponents is NP-hard (see "Computing Sequences with Addition Chains", Peter Downey, Benton Leong, and Ravi Sethi).

  3. The wider literature on ASC chains will cover some of this. I would recommend starting with Donald Knuth's authoritative "Art of Computer Programming" Vol. 2 section 4.6.3


Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.