Четверг, 13.06.2024, 00:31
Криптографические протоколы
Главная Регистрация Вход
Приветствую Вас, Гость · RSS
Меню сайта
Форма входа
Поиск
Счетчики
Рейтинг@Mail.ru
 Доказательство принадлежности числа множеству квадратичных невычетов
ДОКАЗАТЕЛЬСТВО ПРИНАДЛЕЖНОСТИ ЧИСЛА МНОЖЕСТВУ КВАДРАТИЧНЫХ НЕВЫЧЕТОВ Протокол QNR
Протокол интерактивного доказательства Протокол доказательства с нулевым разглашением

Постановка задачи

Пусть $ N$ - множество натуральных чисел, $ n \in N$ и $ Z_n^* = \{x\vert 1\leq x < n, (n,x)=1\}$ множество натуральных чисел, меньших чем $ n$ и взаимно простых с $ n$. $ x \in Z_n^*$ называется квадратичным вычетом по модулю $ n$, если существует такой $ y$, что $ y^2 \equiv x\pmod n$. В противном случае, $ x \in Z_n^*$ называется квадратичным невычетом по модулю $ n$.

Пусть $ a$ — целое число, и $ p$ — простое число, отличное от $ 2$. Символ Лежандра $ \left(\frac{a}{p}\right)$ определяется следующим образом:

$ \left(\frac{a}{p}\right)=0$, если $ a$ делится на $ p$;

$ \left(\frac{a}{p}\right)=1$, если $ a$ является квадратичным вычетом по модулю $ p$, то есть $ a$ не делится на $ p$ и существует такое целое $ b$, что $ b^2\equiv a\pmod p$;

$ \left(\frac{a}{p}\right)=-1$, если $ a$ является квадратичным невычетом по модулю $ p$, то есть $ a$ не делится на p и не является квадратичным вычетом по модулю $ p$.

Пусть $ P$ — нечётное, большее единицы число и $ P=p_1p_2\ldots p_n$ — его разложение на простые множители (среди $ p_1,\;\ldots,\;p_n$ могут быть равные). Тогда для произвольного целого числа $ a$ символ Якоби определяется равенством:

$ \left(\frac{a}{P}\right)=\left(\frac{a}{p_1}\right)\left(\frac{a}{p_2}\right)\cdots\left(\frac{a}{p_n}\right)$,

где $ \left(\frac{a}{p_i}\right)$ — символы Лежандра.

По определению считаем, что $ \left(\frac{a}{1}\right)=1$ для всех $ a$.

Пусть $ n \in N$ и $ x \in Z_n^*$. Пусть $ P$ знает, что не существует такой $ y$, что $ y^2 \equiv x\pmod n$. $ P$ хочет доказать $ V$ свое знание, не показывая само доказательство несуществования.

Описание протокола

Основные сведения
Формальное определение

Информация пока отсутствует

Информация пока отсутствует

Информация пока отсутствует

Информация пока отсутствует
Авторы

Информация пока отсутствует

Информация пока отсутствует

Информация пока отсутствует

Информация пока отсутствует
Свойства

Информация пока отсутствует

Информация пока отсутствует

Информация пока отсутствует

Информация пока отсутствует
Атаки

Информация пока отсутствует

Информация пока отсутствует

Информация пока отсутствует

Информация пока отсутствует
Оценка сложности

Информация пока отсутствует

Информация пока отсутствует

Информация пока отсутствует

Информация пока отсутствует

История

Информация пока отсутствует

Информация пока отсутствует

Информация пока отсутствует

Информация пока отсутствует
Применение

Информация пока отсутствует

Информация пока отсутствует

Информация пока отсутствует

Информация пока отсутствует
Исходники

Информация пока отсутствует

Информация пока отсутствует

Информация пока отсутствует

Информация пока отсутствует
Ссылки
  • S.Goldwasser, S.Micali and C.Rackoff. The Knowledge Complexity of Interactive Proof System. In Proceeding of 17th ACM Symposium on the Theory of Computing, pages 291-304, 1985
  • S.Goldwasser, S.Micali and C.Rackoff. The Knowledge Complexity of Interactive Proof System. SIAM Journal on Computing, Vol.18, pages 186-208, 1989
  • Венбо Мао. Современная криптография. Теория и практика = Modern Cryptography: Theory and Practice. — М.: Вильямс, 2005. — 768 с. - С.700
  • Copyright OspanovRM © 2024
    ТЕРМИНЫ

    Календарь
    «  Июнь 2024  »
    ПнВтСрЧтПтСбВс
         12
    3456789
    10111213141516
    17181920212223
    24252627282930
    Архив записей
    Статистика

    Онлайн всего: 1
    Гостей: 1
    Пользователей: 0
    Сайт управляется системой uCozЯндекс.Метрика