Гомоморфное кодирование

[vlad_light]

Подскажите, пожалуйста, есть ли такое направление? Гугл ничего не выдает (даже исправляет меня на "гомоморфное шифрование"). Особенно интересует гомоморфизм относительно умножения. Спасибо!

[Xaositect]

Ну, например, линейные коды гомоморфны относительно сложения. А какое именно умножение на сообщениях Вы рассматриваете?

[vlad_light]

Обычное умножение целых чисел. У меня просто возникла такая идея: а что, если перед шифрованием (гомоморфным) предварительно сообщения кодировать, а затем, после перемножения шифртекстов, исправлять шум, который в них вносится. Ну или как-то так
Идея возникла достаточно спонтанно и пока, конечно же, не имеет смысла, поскольку зашифрованный текст не отличает "правильный" от "неправиьного". Тут скорее вопрос философского плана: а можно ли как-нибудь прикрутить кодирование для исправления шума при умножении в гомоморфном шифровании?

[AV_77]

vlad_light в сообщении #686389 писал(а):

а что, если перед шифрованием (гомоморфным) предварительно сообщения кодировать

Это не очень хорошая идея.

[Joker_vD]

Вы предлагает сначала увеличить избыточность открытого текста, заишфровать-передать, на другом конце расшифровать испорченный шифртекст и попытаться восстановить открытый текст? Во-первых, если алгоритм шифрования хороший, то весь расшифрованный текст после первого ошибочного бита не будет иметь с исходным текстом ничего общего. Во-вторых, увеличивая избыточность открытого текста, ты помогаешь врагу! вы облегчаете жизнь криптоаналитику.

Почему бы не кодировать шифртекст?

[vlad_light]

Излагаю свою идею ("на пальцах"):
Пусть $M$ - сообщение, которое мы передаём, $f$ - что-то типа умножения, $C$ - кодирование, $E$ - шифрование, $e$ - ошибки, $*$ - действие. Предполагаются следующие условия:
$C^{-1}*(C*M+e)=M$ - исправление ошибок (1),
$f(C*M)=C*f(M)$ - гомоморфное кодирование (2),
$f(E*M)=E*f(M)+e$ - гомоморфное шифрование (3),
Пусть мы имеем $M$ и хотим получить $f(M)$, но не раскрывая само $M$. Тогда мы передаём наш шифр $E*C*M$ на сервер, где он его обрабатывает $f(E*C*M)$. Из (3) $\Rightarrow f(E*C*M)=E*f(C*M)+e$ и расшифровываем $E^{-1}*(E*f(C*M)+e)=f(C*M)+E^{-1}*e$. Далее из (1) и (2) получаем $C^{-1}*(f(C*M)+E^{-1}*e)=C^{-1}*(C*f(M)+e')=f(M)$.
Теперь интересует, в каком моменте я прокололся.

(Оффтоп)

Я не обижусь, если всё написанное выше окажется полным бредом, напротив, буду рад критике! Единственное, хотелось бы, чтоб вы поняли, что я имею ввиду (мою идею устранения той самой ошибки при умножении шифртекстов) и указали мне на невозможность тех или иных действий. Если у вас есть какие-то интересные идеи (пусть даже такие же бредовые, как и моя) -- пишите их сюда, буду очень благодарен!

[AV_77]

vlad_light в сообщении #686453 писал(а):

Теперь интересует, в каком моменте я прокололся.

Противник дешифрует ваше $E*C*M$, получит какой-то искаженный текст и затем исправит в нем ошибки. Это, пожалуй, очень удобно.

[vlad_light]

Но как он его дешифрует, не зная секретного ключа?

[Joker_vD]

У Алисы есть $M$ и она хочет, чтобы Боб узнал $f(M)$, но не $M$. Для этого она посылает Бобу $f(M)$, но не посылает $M$... однако есть еще Ева, которая сидит посередине и подслушивает. Алиса хочет, чтобы Ева не знала ни $M$, ни $f(M)$, поэтому она передает Бобу $g(M)$ — из которого Боб сможет получить $f(M)$, но не $M$, а Ева вообще ничего из него получить не сможет. Такая задача?

[vlad_light]

Я лучше приведу здесь свою задачу, но мне кажется, что они эквивалентны.
У Алисы есть $M$ и ей нужно получить $f(M)$, но сама она этого делать не умеет. Зато есть сервер (Боб), который может ей в этом помочь. Также, Алиса не хочет, чтоб кто-либо узнал $M$ или $f(M)$. Для этого она шифрует свое сообщение и передаёт уже не $M$, а $E*M$. Но при операциях над $E*M$ возникает проблема: $f(E*M)=E*f(M)+e\neq E*f(M)$, где $e$ - ошибка. Основная проблемма -- как избавиться од данной ошибки.
Более подробно можно прочитать здесь: http://crypto.stanford.edu/craig/craig-thesis.pdf

[vlad_light]

Так что там по поводу гомоморфного кодирования?