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

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

Пусть $ 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$.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

Информация пока отсутствует
Ссылки
  • 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 с. - С.698-700
    • Copyright OspanovRM © 2025
    ТЕРМИНЫ

    Календарь
    «  Январь 2025  »
    ПнВтСрЧтПтСбВс
      12345
    6789101112
    13141516171819
    20212223242526
    2728293031
    Архив записей
    Статистика
    Онлайн всего: 1
    Гостей: 1
    Пользователей: 0
    Сайт управляется системой uCozЯндекс.Метрика