2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Гомоморфное кодирование
Сообщение20.02.2013, 20:57 


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

 Профиль  
                  
 
 Re: Гомоморфное кодирование
Сообщение20.02.2013, 21:54 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Гомоморфное кодирование
Сообщение20.02.2013, 22:25 


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

 Профиль  
                  
 
 Re: Гомоморфное кодирование
Сообщение20.02.2013, 22:32 
Заслуженный участник


11/11/07
1198
Москва
vlad_light в сообщении #686389 писал(а):
а что, если перед шифрованием (гомоморфным) предварительно сообщения кодировать

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

 Профиль  
                  
 
 Re: Гомоморфное кодирование
Сообщение20.02.2013, 23:08 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Гомоморфное кодирование
Сообщение21.02.2013, 00:46 


07/03/11
690
Излагаю свою идею ("на пальцах"):
Пусть $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)$.
Теперь интересует, в каком моменте я прокололся.

(Оффтоп)

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

 Профиль  
                  
 
 Re: Гомоморфное кодирование
Сообщение21.02.2013, 07:36 
Заслуженный участник


11/11/07
1198
Москва
vlad_light в сообщении #686453 писал(а):
Теперь интересует, в каком моменте я прокололся.

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

 Профиль  
                  
 
 Re: Гомоморфное кодирование
Сообщение21.02.2013, 12:17 


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

 Профиль  
                  
 
 Re: Гомоморфное кодирование
Сообщение21.02.2013, 13:04 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Гомоморфное кодирование
Сообщение21.02.2013, 13:47 


07/03/11
690
Я лучше приведу здесь свою задачу, но мне кажется, что они эквивалентны.
У Алисы есть $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

 Профиль  
                  
 
 Re: Гомоморфное кодирование
Сообщение23.02.2013, 17:10 


07/03/11
690
Так что там по поводу гомоморфного кодирования?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group