2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 $300 вознаграждение- вроде это дискретная математика
Сообщение19.09.2013, 11:10 


18/09/13
8
Задача

1. Боб знает пару простых чисел, $x_1,x_2$
2. Алиса знает пару простых чисел, $y_1,y_2$
3. Как Бобу проверить истинность выражения $f(x_1,y_1) \mod 53 == f(x_2,y_2) \mod 53$ с вероятностью $v$ при том, что никто из них не должен узнать пары чисел друг друга, а также значение выражений $f(x_1,y_1) \mod 53$ и $f(x_2,y_2) \mod 53$. Т.е. подобрать функцию $f$, а также протокол проверки.

Примечание:
Под "не должен узнать" подразумевается невозможность узнать за приемлемое время при том, что проверка истинности выражения должна выполняться за приемлемое время. Иными словами сложность алгоритма "узнавания" должна быть экспоненциальная, а сложность алгоритма сравнения - полиноминальная.

Идеи:
В качестве гипотетической надежды на возможность такой схемы послужило наличие схемы Шнорра (http://ru.wikipedia.org/wiki/%D0%A1%D1% ... 1%80%D0%B0). Т.е. направление, куда следует копать, это свойства простых чисел, а также сложность задачи факторизации произведения двух больших простых чисел, сложность вычисления дискретного логарифма при меньшей сложности задачи вычисления $a = b^c \mod n$

skype: easy88easy88

 Профиль  
                  
 
 Re: $300 вознаграждение- вроде это дискретная математика
Сообщение19.09.2013, 11:24 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
Когда предлагают вознаграждение - это сильно подозрительно.

 Профиль  
                  
 
 Re: $300 вознаграждение- вроде это дискретная математика
Сообщение19.09.2013, 11:29 


18/09/13
8
ну могу не предлагать - и что тут может быть подозрительного ?

 Профиль  
                  
 
 Re: $300 вознаграждение- вроде это дискретная математика
Сообщение19.09.2013, 11:39 
Заслуженный участник
Аватара пользователя


18/01/13
12044
Казань
Что вам надо сдавать работу (диплом, скажем) и вы хотите его купить.
Если же предлагаете совместную работу - другое дело.

 Профиль  
                  
 
 Re: $300 вознаграждение- вроде это дискретная математика
Сообщение19.09.2013, 11:41 
Заслуженный участник
Аватара пользователя


19/12/10
1546
RomanS в сообщении #765298 писал(а):
ну могу не предлагать - и что тут может быть подозрительного ?

Подозрительно, что не заплатите :-)

Уж больно модуль (53) маленький.
И что означает N?

 Профиль  
                  
 
 Re: $300 вознаграждение- вроде это дискретная математика
Сообщение19.09.2013, 11:42 


18/09/13
8
предлагаю совместную работу - это не диплом
нужен специалист математик -

могу перевести аванс на администратора форума... если будет решение получите оплату у своего гаранта
тут на форуме я новичек

 Профиль  
                  
 
 Re: $300 вознаграждение- вроде это дискретная математика
Сообщение19.09.2013, 11:50 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
RomanS в сообщении #765303 писал(а):
тут на форуме я новичек
Оно и видно (аж по трём четырём пяти признакам). К сожалению, вы пришли не туда. Здесь помогают each other бесплатно, но при условии, что тот, кто просит помощи, сам готов работать.

 Профиль  
                  
 
 Re: $300 вознаграждение- вроде это дискретная математика
Сообщение19.09.2013, 11:51 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Коли Вы новичок, даю бесплатный совет :D
Начинайте изучать $\TeX$, ибо очень скоро Ваша тема уедет в Карантин.

 Профиль  
                  
 
 Re: $300 вознаграждение- вроде это дискретная математика
Сообщение19.09.2013, 11:54 


18/09/13
8
Aritaborian в сообщении #765305 писал(а):
RomanS в сообщении #765303 писал(а):
тут на форуме я новичек
Оно и видно (аж по трём четырём признакам). К сожалению, вы пришли не туда. Здесь помогают each other бесплатно, но при условии, что тот, кто просит помощи, сам готов работать.


согласен на бесплатную помощь и я сам готов работать

просто лучше ресурса по математике не нашел . с живым форумом как тут

 Профиль  
                  
 
 Re: $300 вознаграждение- вроде это дискретная математика
Сообщение19.09.2013, 11:55 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
RomanS в сообщении #765307 писал(а):
я сам готов работать
Так начинайте! Какие есть идеи?

 Профиль  
                  
 
 Re: $300 вознаграждение- вроде это дискретная математика
Сообщение19.09.2013, 11:59 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Ну раз сами согласны работать, то начните с того, что приведите все свои формулы в соответствие с правилами форума то есть в $\TeX$
http://dxdy.ru/topic8355.html
http://dxdy.ru/topic183.html

 Профиль  
                  
 
 Re: $300 вознаграждение- вроде это дискретная математика
Сообщение19.09.2013, 12:02 


18/09/13
8
whitefox в сообщении #765309 писал(а):
Ну раз сами согласны работать, то начните с того, что приведите все свои формулы в соответствие с правилами форума то есть в $\TeX$
http://dxdy.ru/topic8355.html
http://dxdy.ru/topic183.html


хорошо сеичас разберусь и исправлю

 Профиль  
                  
 
 Posted automatically
Сообщение19.09.2013, 12:21 
Супермодератор
Аватара пользователя


20/11/12
5728
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

RomanS, наберите все формулы и термы $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
вернул

 Профиль  
                  
 
 Re: $300 вознаграждение- вроде это дискретная математика
Сообщение19.09.2013, 19:48 
Заслуженный участник
Аватара пользователя


19/12/10
1546
RomanS

(Оффтоп)

Для бинарной операции $\mod$ лучше использовать код
Код:
\bmod
http://dxdy.ru/post443191.html#p443191
Например,
Код:
f(x_1,y_1)\bmod 53=f(x_2,y_2)\bmod 53 или a=b^c\bmod n
$f(x_1,y_1)\bmod 53=f(x_2,y_2)\bmod 53$ или $a = b^c \bmod n$

В порядке занудства ещё один вопрос -- Вы избегаете прописных букв по религиозным идеологическим убеждениям?

Поймите правильно, я не против, но точка посреди потока строчных букв обескураживает
RomanS в сообщении #765307 писал(а):
просто лучше ресурса по математике не нашел . с живым форумом как тут
Приходится затрачивать несколько лишних наносекунд на понимание того, что это конец предложения.

Вы настаиваете на модуле 53?
Не помешает ли такой маленький модуль криптостойкости протокола?

 Профиль  
                  
 
 Re: $300 вознаграждение- вроде это дискретная математика
Сообщение19.09.2013, 21:13 


18/09/13
8
whitefox в сообщении #765476 писал(а):
RomanS

(Оффтоп)

Для бинарной операции $\mod$ лучше использовать код
Код:
\bmod
http://dxdy.ru/post443191.html#p443191
Например,
Код:
f(x_1,y_1)\bmod 53=f(x_2,y_2)\bmod 53 или a=b^c\bmod n
$f(x_1,y_1)\bmod 53=f(x_2,y_2)\bmod 53$ или $a = b^c \bmod n$

В порядке занудства ещё один вопрос -- Вы избегаете прописных букв по религиозным идеологическим убеждениям?

Поймите правильно, я не против, но точка посреди потока строчных букв обескураживает
RomanS в сообщении #765307 писал(а):
просто лучше ресурса по математике не нашел . с живым форумом как тут
Приходится затрачивать несколько лишних наносекунд на понимание того, что это конец предложения.

Вы настаиваете на модуле 53?
Не помешает ли такой маленький модуль криптостойкости протокола?


Модуль 53 - обязательное условие. Это константа. Криптостойкость должна оставаться на приемлемом уровне, несмотря на это условие. Точнее она должна зависеть от разрядности чисел $x_1,x_2,x_3,x_4$.

Также решением может являться доказательство невозможности подобного.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

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



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

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


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

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