5
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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.). $\endgroup$
    – garfunkel
    Mar 1, 2023 at 17:44
  • $\begingroup$ 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.) $\endgroup$
    – fakub
    Mar 6, 2023 at 15:17
  • $\begingroup$ 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). $\endgroup$
    – garfunkel
    Mar 7, 2023 at 13:02
  • $\begingroup$ 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) $\endgroup$
    – poncho
    Oct 27, 2023 at 14:20
  • $\begingroup$ Knuth's AoCP vol. 2, The Seminumerical Algorithms, presents some heuristic methods for finding good additive chains. Section 4.6.3 Evaluation of Powers. $\endgroup$
    – hardmath
    Feb 24 at 20:09

1 Answer 1

0
$\begingroup$
  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

$\endgroup$
2
  • $\begingroup$ After some search, I found that TNAF method [1] by Solinas also enjoys cheap "doubling" (a mapping tau for which tau²-tau+2=0, instead of tau-2=0 for std doubling). However, then they apply the sliding window method and no optimal ASC is searched in that representation, though the number of additions might be improved, I believe. This line of research seems to be the closest to my question, in fact rising the same question for TNAF. However for now, the combination of NAF and sliding window seems to be the best solution. [1] link.springer.com/chapter/10.1007/978-1-4757-6856-5_6 $\endgroup$
    – fakub
    Jun 22, 2022 at 11:23
  • $\begingroup$ Technical note ad 2: "computing optimal ASCs for a set of exponents" is not formally NP (hence cannot be NP-complete). What you mean is the decision problem whether there exists a length-l ASC for a set of exponents - this is an NP-complete decision problem (also noted in the book Elliptic and Hyperelliptic Curve Cryptography by Avanzi et al, pg. 159). $\endgroup$
    – fakub
    Jun 22, 2022 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.