Связанная проблема
Стандарт Цепочка сложения-вычитания (ASC) для целого числа $к$ определяет порядок операций сложения/вычитания (удвоения), чтобы $к$ наконец достигается, начиная с $1$.
Это особенно полезно в ECC для расчета $k\cdot P$ с помощью добавления/вычитания и удвоения очков EC.
Цель состоит в том, чтобы найти как можно короче ASC, так что используется минимальное количество операций сложения/вычитания/удвоения.
Например., $(1,2,4,8,16,32,31)$ является ASC для $31$ (со многими добавлениями/удвоениями и окончательным вычитанием).
Однако поиск кратчайшего ASC представляется сложной задачей.
Моя проблема
В стандартных ASC сложность удвоения считается эквивалентно сложению/вычитанию, следовательно, длина ASC может быть мерой сложности.
Однако в моем сценарии удвоение "бесплатно".
Это приводит к обобщению (назовем его ASC²), где цепочка содержит не целые числа, а классы эквивалентности из $\{к, 2к, 2^2к, 2^3к \ldots\} =: [к]$ за $к$ нечетное целое.
То есть предыдущий пример можно очень коротко записать в виде $([1],[31])$ поскольку $31 = -1 + 2^5\cdot 1$.
Цель явно состоит в том, чтобы найти кратчайший ASC².
Вопросы)
- Есть ли/не могли бы вы предложить какие-либо (эвристические) метод поиска «хорошего» ASC²?
- Как мог короткие ASC² генерироваться, чтобы их оптимальность гарантировано?
- Существует ли между прочим любая литература об этом?
Мотивация
Реализуя арифметику над зашифрованными целыми числами (побитно), ASC² был бы полезен для скалярного умножения (т. Е. Умножения зашифрованного целого числа на целое число открытого текста).
В таком представлении удвоение зашифрованного текста действительно дешево: это просто добавление тривиального шифрования нуля в наименее значащую позицию.
С другой стороны, добавление очень дорого (поскольку оно использует FHE), поэтому стоит найти наилучший ASC².
