ПЛАТНІ РОБОТИ
Банківська справа
БЖД та охорона праці
Біологія і генетика
Бухгалтерський облік та аудит
Державне будівництво і державне управління
Ділова мова та діловодство
Екологія
Економіка (макро-, мікро-, підприємства, теорії і т.п.)
Економіка праці та соціально-трудові відносини
Економічна безпека
Економічна історія
Етика і естетика
Інформатика та комп. техніка
Історія держави і права
Історія економічних вчень
Історія і теорія соціальної роботи
Історія України
Кадрова політика
Комп. мережі
Культурологія
Логіка
Маркетинг
Мат. програмування
Менеджмент
Основи бізнесу
Паблік рілейшнз
Патентознавство
Педагогіка
Політична економія
Політологія
Право (всі види)
Психологія
Релігієзнавство
Різне
РПС (економічна географія)
Система технологій
Системний аналіз
Соціологія
Соціологія праці
Статистика
Страхування
Теорія ймовірності і мат. статистика
Товарознавство
Українська мова
Фізичне виховання і спорт
Філософія
Фінанси
НОВИНИ САЙТУ

26.08.2009
Створена нова колекція БЕЗКОШТОВНИХ високоякісних робіт!

27.08.2009
Як швидко отримати готову платну роботу на цьому сайті?


Яндекс.Метрика
рефераты по законодательству и праву

Метод Zero Knowledge Proofs (доказательства с нулевым знанием)





РЕФЕРАТ НА ТЕМУ ZERO KNOWLEDGE PROOFS ДОКОЗАТЕЛЬСТВА С НУЛЕВЫМ ЗНАНИЕМ

работу выполнили: ученики 10а класса ГОЛИКОВ АНДРЕЙ СИРОКЛИН ВАЛЕНТИН

1998 год В наше время при таком количестве электроники в мире очень важно создать систему шифровки которую нельзя подделать. Старые способы шифрования не подходят так как шифр может попасть в чужие руки или может быть «взломан» компьютером. Поэтому своевременно и очень перспективно появления метода Zero Knowledge Proofs (доказательства с нулевым знанием) позволяющий создать систему шифровки которая с данной точностью подтверждает что человек тот за кого он себя выдает и не дает никакой информации которую можно использовать другому человеку. Метод ZKP основан на том что проверяющий знает всегда только половину информации. Конечно при таком условии нельзя быть уверенным в том что человек тот за кого он себя выдает. Но проверяющий каждый раз может спросить любую часть информации причем несколько раз. Рассмотрим данный метод на примере графов. Граф- конечная совокупность точек, называемых вершинами; некоторые из них соединены друг с другом линиями, называемыми ребрами графа. Простейший вид графа - это города соединенные дорогами на карте. У каждого графа с количеством точек больше двух есть гамильтонов цикл- это способ соединения всех вершин графа одной кривой, проходящий по его ребрам и не проходящий через одну вершину два раза. Допустим проверяющему показали гамильтонов цикл графа но он не знает от какой точки к какой идти, если проверяющий убедился в том что у проверяемого нужный граф то он не видит гамильтонов цикл так как у графа изменились координаты точек. Каждый вопрос будет понижать шансы на случайный ответ. С начало вероятность угадать равна 1/2, потом 1/4 и через сто вопросов вероятность упадет до 1/2100 . Согласитесь что если человек не знает правильного графа и гамильтонова цикла то ему будет затруднительно ответить чтобы хоть раз не ошибиться, а проверка заканчивается при первой же ошибке. Как происходит проверка. Допустим Алису проверяет Боб. У Алисы есть граф для которого как она утверждает знает гамильтонов цикл. Сначала Алиса приходит к Бобу с графом у которого закрыты узлы монетами. Она спрашивает боба что ему показать: Гамильтонов цикл или узлы графа. Боб бросает монету и говорит покажи мне узлы, Алиса снимает монеты и Боб видит что действительно Каждая точка графа которая обязательно должна иметь название соединена с другой так как у боба на проверочном графе. Боб говорит ты просто знала что я спрошу. Тогда Алиса отворачивается меняет расположение точек в пространстве снова их закрывает поворачивается и опять спрашивает Боба что ему показать. Боб опять бросает монету и на этот раз говорит покажи мне гамильтонов цикл Алиса соединяет все точки графа друг с другом не проходя по ним два раза. Боб убеждается что Алиса действительно знает гамильтонов цикл для данного графа но не знает название точки от какой Алиса проводит кривую. Таким образом Спросив Алису сто раз Боб убеждается что она действительно та за кого себя выдает. При этом Боб так и не узнал Гамильтонов цикл для данного графа так как не знал последовательность точек которые надо соединять а гамильтонов цикл найти для граф с десятью вершинами уже не просто, а если у графа 100 вершин то это уже почти невозможно. А если вершин 1000 то подбор гамильтонова цикла на современном компьютере займет несколько сотен лет. Перед Алисой встает таже задача по нахождению гамильтонова цикла для своего графа. Алиса решает эту задачу так: Алиса рисует любую запутанную кривую в точках перигиба кривой Алиса расставляет точки графа. Потом между данными точками проводит еще несколько ребер графа чтоб усложнить его. И получает достаточно сложный граф для которого она знает гамильтонов цикл. Данный граф передают проверяющему не говоря ему гамильтонов цикл. Чтоб показать вам всю сложность нахождения гамильтонова цикла рассмотрим граф из семи точек, приведенный на рисунке ниже. Если попытаться самому придумать гамильтонов цикл то на это уйдет от 30 минут до нескольких часов.

На рисунке показан граф с 7 вершинами; сплошные линии- гамильтонов цикл для данного графа пунктир ребра по
Яндекс.Метрика