Реферат: Доказательства с нулевым знанием - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Доказательства с нулевым знанием

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 15 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

ДОКАЗАТЕЛЬСТВА С НУЛЕВЫМ ЗНАНИЕМ В наше время при таком количестве электроники в мире оч ень важно создать систему шифровки которую нельзя подделать. Старые спо собы шифрования не подходят так как шифр может попасть в чужие руки или м ожет быть “взломан” компьютером. Поэтому своевременно и очень перспективно появления метода Zero Knowledge Proofs (дока зательства с нулевым знанием) позволяющий создать систему шифровки кот орая с данной точностью подтверждает что человек тот за кого он себя выд ает и не дает никакой информации которую можно использовать другому чел овеку. Метод ZKP основан на том что проверяющий знает всегда только половину инфо рмации. Конечно при таком условии нельзя быть уверенным в том что челове к тот за кого он себя выдает. Но проверяющий каждый раз может спросить люб ую часть информации причем несколько раз. Рассмотрим данный метод на примере графов. Граф- конечная совокупность т очек, называемых вершинами; некоторые из них соединены друг с другом лин иями, называемыми ребрами графа. Простейший вид графа - это города соедин енные дорогами на карте. У каждого графа с количеством точек больше двух есть г амильтонов цикл- это способ соединения всех вершин графа одной кривой, п роходящий по его ребрам и не проходящий через одну вершину два раза. Допу стим проверяющему показали гамильтонов цикл графа но он не знает от како й точки к какой идти, если проверяющий убедился в том что у проверяемого н ужный граф то он не видит гамильтонов цикл так как у графа изменились коо рдинаты точек. Каждый вопрос будет понижать шансы на случайный ответ. С начало вероятно сть угадать равна 1/2, потом 1/4 и через сто вопросов вероятность упадет до 1/2 100 . Согласитесь что если человек не з нает правильного графа и гамильтонова цикла то ему будет затруднительн о ответить чтобы хоть раз не ошибиться, а проверка заканчивается при пер вой же ошибке. Как происходит проверка. Допустим Алису проверяет Боб. У Алисы есть граф для которого как она утверждает знает гамильтонов цикл. Сначала Алиса приходит к Бобу с графом у которого закрыты узлы монетами. Она спрашивает боба что ему показать: Гамильтонов цикл или узлы графа. Бо б бросает монету и говорит покажи мне узлы, Алиса снимает монеты и Боб вид ит что действительно Каждая точка графа которая обязательно должна име ть название соединена с другой так как у боба на проверочном графе. Боб говорит ты просто знала что я спрошу. Тогда Алиса отворачивается мен яет расположение точек в пространстве снова их закрывает поворачивает ся и опять спрашивает Боба что ему показать. Боб опять бросает монету и на этот раз говорит покажи мне гамильтонов цикл Алиса соединяет все точки г рафа друг с другом не проходя по ним два раза. Боб убеждается что Алиса дей ствительно знает гамильтонов цикл для данного графа но не знает названи е точки от какой Алиса проводит кривую. Таким образом Спросив Алису сто р аз Боб убеждается что она действительно та за кого себя выдает. При этом Б об так и не узнал Гамильтонов цикл для данного графа так как не знал после довательность точек которые надо соединять а гамильтонов цикл найти дл я граф с десятью вершинами уже не просто, а если у графа 100 вершин то это уже почти невозможно. А если вершин 1000 то подбор гамильтонова цикла на соврем енном компьютере займет несколько сотен лет. Перед Алисой встает таже задача по нахождению гамильтонова цикла для св оего графа. Алиса решает эту задачу так: Алиса рисует любую запутанную кр ивую в точках перигиба кривой Алиса расставляет точки графа. Потом между данными точками проводит еще несколько ребер графа чтоб усложнить его. И получает достаточно сложный граф для которого она знает гамильтонов ц икл. Данный граф передают проверяющему не говоря ему гамильтонов цикл. Чтоб показать вам всю сложность нахождения гамильтонова цикла рассмот рим граф из семи точек, приведенный на рисунке ниже. Если попытаться само му придумать гамильтонов цикл то на это уйдет от 30 минут до нескольких час ов. На рисунке показ ан граф с 7 вершинами; сплошные линии- гамильтонов цикл для данного графа п унктир ребра по которым не прошла кривая гамильтонова цикла. В качестве Боба и Алисы могут выступать компьютер и пл астиковая карточка типа той которая сейчас служит для банковских расче тов. Даже если человек сможет подключится к проверяющему компьютеру то о н все равно не сможет узнать гамильтонов цикл для графа находящегося на карточке. Метод ZKP может использоваться не только для примера с графами но и на мног их других примерах, просто в данном случае легче всего объяснить в чем су ть метода ZKP. Хоть и явны видны преимущества данного вида кодировки нельзя забывать и про систему (PASSWORD)овых шифровок так как если охраняется не очень важный объект то проще и быстрее проверять (PASSWORD) чем проводить проверку ме тодом ZKP. Мы попробовали пройти систему кодировки ZKP. Для примера мы разобрали разные фрагменты графов что бы н айти закономерность в построении гамильтонова цикла .Мы можем найти алг оритм построения гамильтонова цикла на данных фрагментах, что бы в дальн ейшем строить этот цикл на более сложных графах. Пример 1. A A E D C B F S N P G A В данном графе легко можно B построить гамильтонов цик л F G E так как в данном графе есть два S P контура , которые находятся N друг в друге и соединены точками. C D Таким образом построение данного графа является самим гамильтоновым циклом и практически все графы строятся на основе самого гамильтонова ц икла. С добавлением других ребер. Гамильтонов цикл легко искать если граф имеет вид замкнут ых контуров соединенных более чем через две точки друг с другом Пример 2. На данном графе намного сложнее построить гамильтонов ци кл так как не все точки соединены с друг другом А Гамильтонов цикл: Б Л Д Б А Л К В С Е Д Д Е В данном случае мы нашли С его за 7 минут 34 секунды В К и если бы точки Б и В не лежали бы рядом то, это заняло бы у нас намного больше времени. Граф не обязательно должен быть таким , гл авное что граф может растягиваться как угодно ,и точки могут менять свои координаты, главное что бы A соединялось с Б Д Л и тд. Пример 3. Мы можем разбивать сложные графы на более простые, гамильтонов цикл кото рых нам известен .Покажем это на примере ранее рассмотренных графов. А A1 B H B1 H1 G R1 T1 E F E1 Y1 C D 1. C1 F1 2. D1 Мы можем пройти цикл 1. и можем пройти цикл 2.А если представить что у нас ест ь цикл из 1 и 2 когда соединены H и B1, C и D1, то мы можем его пройти его как первый е сли уверены что можем пройти от B1 до C1 по всем точкам , а так как это легко ( B1 R1 A1 T1 H1 Y1 D1 F1 E1 C1) и следовательно мы можем составить для него гамильтонов цикл и таким же образом мы можем составить гамильтонов цикл для многих сложных графов, правда с затратой времени , главное найти начальную (конечную) точ ку и несколько графов , по которым можно пройти так же легко как и по графу в примере . CHECKING PROGRAM Checking program – разновидность верификации , но эта на много удобнее и дешевле . С HEKING PROGRAM заключается в том , что команды , которые посылает программа проходят через специально сделанную внутреннюю программу , которая настроена на новую версию, и она просто изменяет те команды, которые не подходят для да нной версии. При изготовлении ракеты надо делать для нее специальную программу, но ес ли раньше такая программа уже была сделана для похожей ракеты, а теперь п оявились маленькие изменения, то CHECKING PROGRAM будет пропуская через себя команд ы изменять их, если эта команда не изменена, и не будет изменять если данна я команда не требует изменения , таким образом CHECKING PROGRAM экономит время и день ги. Если человек обладает такими навыками то он может зарабатывать на соста влении таких программ неплохие деньги.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Любовь - это когда встаешь пораньше, чтобы сварить ему чашечку кофе... А кофе уже готов!
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по программированию "Доказательства с нулевым знанием", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru