kiev-security.org.ua-Криптография.Честный протокол для подписания контрактов

M.Ben-Or, O.Goldreich, S.Micali, R.L.Rivest. A Fair Protocol for Signing Contracts//IEEE Trans. on Information Theory, v.36, Э1, 1990, pp.40-46. Честный протокол для подписания контрактов Аннотация. Две стороны, А и В, желают подписать контракт С по сети связи. Для этого они должны "одновременно" обменяться своими обязательствами относительно С. Поскольку одновременный обмен на практике обычно невозможен, необходимо постепенно, по частям уравнивать обязательства при помощи специального протокола обмена. В ходе выполнения протокола та или иная сторона может иметь небольшое преимущество; "честный" протокол удерживает это преимущество в приемлемых границах. Представлен новый протокол, который честен в том смысле, что на любой стадии его реализации выполняется следующее: условная вероятность того, что одна из сторон не может обязать обе стороны выполнить условия договора, а другая может, стремится к нулю. Это справедливо даже в том случае, если вычислительные мощности А и В значительно отличаются, и доказывается при очень слабых криптографических предположениях. Наш протокол имеет следующие дополнительные свойства: * в ходе процедуры стороны обмениваются вероятностными опциями, служащими для принятия обязательств по контракту обеими сторонами; * протокол никогда не завершается в асимметричной ситуации, когда сторона А знает, что сторона В приняла обязательства по договору, а она нет; * протокол в слабой форме использует третью сторону (судью). Если и А, и В честны, судья никогда не призывается. В противном случае он вершит суд путгм выполнения простого вычисления. От судьи не требуется никакого учгта. I.Введение Пусть А, В,.. будут пользователями, которые могут обмениваться сообщениями по сети связи. Например, это могут быть пользователи обычной почтовой системы, телефонной сети или современной вычислительной сети. А. Подписи Мы предположим, что в сети принят метод подписи, обладающий двумя ключевыми свойствами. Первое заключается в невозможности подделки, то есть только пользователь U может создать подпись U для сообщения m. Второе свойство состоит в универсальной проверке, то есть любой другой пользователь может проверить истинность подписи U сообщения m. Примером метода подписи могут служить обычные "ручные" подписи. Считается, что ручные подписи тяжело подделать и можно универсально проверить по образцам, хранящимся у доверенных нотариусов. Другой, более применимый для вычислительных сетей метод - это "метод цифровой подписи". Данное определение было введено Диффи и Хеллманом [5] и впервые внедрено Райвестом и др.[15]. Наиболее сильное определение безопасности для цифровой подписи было предложено и впервые внедрено (на базе слабого и основанного на общей сложности предположения) Голдвассером и др. [11]. Более простой метод, также основанный на предположении общей сложности, был недавно предложен в [3]. Исторический обзор проблемы цифровой подписи можно найти в [11]. В. Проблема подписания контракта Два пользователя А и В обговорили по сети контракт С и желают получить друг от друга обязательства относительно него. Они держат связь, посылая друг другу поочергдно сообщения. Ни одна из сторон не желает принимать на себя обязательства, пока этого не сделает другая сторона. Требуется одновременный обмен обязательствами. Возможно ли это в принципе? Конечно нет, если под обязательством мы понимаем подпись под текстом контракта [8]. Действительно, в нашем дискретном мире нет места одновременности. Следовательно, необходимо ввести протоколы, которые "честны" в том смысле, что ни одна из сторон не может получить преимущества над другой. Конечно, помимо честности обе стороны должны точно выполнять протокол. Тогда по его завершении обе стороны примут на себя обязательства по С. Смысл решения "задачи подписания протокола" зависит от приемлемости определения "честность", на котором оно основано. Рассматривалось два основных подхода к честности. Первый интерпретирует честность на основе равных вычислительных усилий. Второй подход, принятый в этой статье, рассматривает честность с точки зрения высокой вероятностной корреляции. С. Вычислительные подходы к честности Ивен [6], Блюм [1] и Ивен и др. [7] предложили вычислительную интерпретацию честности. Этот подход требует, чтобы на любой стадии выполнения протокола от обеих сторон требовались приблизительно равные вычислительные усилия по получению взаимных обязательств по С. В этом случае вычислительная сложность задачи должна рассматриваться как количество машинных операций, требуемых для завершения задачи. Обычно при выполнении протокола (построенного в соответствии с этим подходом) вычислительная сложность построения обязательства противоположной стороны по С должна уменьшаться (для обеих сторон) на приблизительно равные величины на каждом шаге вплоть до окончания. Преимущество данного подхода в том, что не требуется вмешательство третьей стороны (в любом виде). (Примечание. Когда мы говорим, что метод подписания контракта не требует вмешательства третьей стороны в любом виде, то имеем ввиду вмешательство с простой технической целью определить, правильно или нет был подписан контракт. Этот технический вопрос (принимаемый в наши дни при спорах как разумеющийся) не следует путать с важной ролью доверенной третьей стороны (т.е. судьи как представителя закона) при определении обязательств и возмещений, связанных с контрактом (и подверженных толкованию в терминах закона), и предложении мер по принуждению сторон к выполнению решения суда. К сожалению, этот подход обладает тремя значительными недостатками. Первый недостаток - предположение о равной вычислительной мощи. Это условие честности соотносит вычислительные усилия сторон только через количество операций. Однако если сторона А может выполнить 100000 операций в секунду, а В за секунду выполняет миллиард операций, то понятие "честность" вряд ли приемлемо. (Предположим, что на некотором шаге протокола каждой стороне необходимо 10 в 12-ой степени операций для получения обязательства противоположной стороны по контракту. Тогда А требуется 4 месяца для получения обязательства, а стороне В - менее 17 минут). Следовательно, вычислительный подход к честности имеет смысл только в том случае, если обе стороны предположительно имеют равную вычислительную мощь, что и предполагалось в [1,6,7]. На наш взгляд, предположение о равной вычислительной мощи нереалистично с практической и нежелательно с теоретической точек зрения. В реальной жизни стороны часто могут иметь различные вычислительные мощи (например, большая коммерческая фирма и отдельное лицо). Кроме того, одной стороне тяжело оценить вычислительные способности другой, так как последняя может намеренно их занижать. Опережая события, отметим, что вероятностный подход, как и наш протокол, действует и при различных - но по-прежнему достижимых - вычислительных способностях. Второй недостаток - разрушительный эффект преждевременного завершения. Если одна из сторон преждевременно прекратит подписание контракта, то данный подход гарантирует, что стороны столкнутся с равными вычислительными усилиями. Но подход не определяет действий честной стороны в этом случае. На наш взгляд, этот недостаток неслучаен, поскольку здесь нет разумных альтернатив. Отметим, что сторона А попадает в трудное положение, если контракт определяет для А совершение некоторых действий (например, покупка акций) в течение недели, в то время как В завершил подписание контракта в точке, где А требуется год для вычисления того, взял ли В на себя обязательства. Основная сложность состоит в том, что нет срока, к которому процесс подписания должен определгнно завершаться, причгм либо обе стороны должны быть скреплены контрактом, либо ни одна из них. Третий недостаток - сложность доказательства правильности. Эта сложность может не быть присущей, но в общем случае имеет место. Доказательство того, что некоторые задачи не могут быть эффективно разрешены, представляется весьма сложным. Доказательство того, что вычислительная сложность некоторых задач уменьшается на фиксированную величину при обработке некоторой "частичной информации" представляется ещг более сложным. В типичном случае правильность протокола Ивена и др. [7] следует из предположения, что существуют "идеальные" односторонние перестановки с лазейкой и "равномерно сложные" односторонние функции f. Под этим полагается, что для заданной f(x) и k битов (информации об) x, где x имеет длину n битов, лучший алгоритм для вычисления x по существу состоит в переборе всех 2**(n-k) возможностей для оставшихся битов, что в самом деле является сильным предположением. (Примечание. Протокол Ивена [E] (как и его упрощгнная версия [G]) требует дополнительного нематематического предположения: содержание контракта - это фиксированная и известная величина. Правильность протокола Блюма [B1] основана на предположении, что частная вычислительная задача, связанная (но неизвестно, вычислительно эквивалентная ли?) с разложением целого числа на множители, неразрешима. К сожалению, Хастед и Шамир показали, что эта задача эффективно разрешима [HS].) Напротив, правильность нашего протокола следует из более слабого сложностного предположения - существования односторонних функций f. Не требуется, чтобы такие f были "идеальными" или равномерно сложными. В частности, половину битов x можно легко рассчитать на входной f(x). Мы лишь требуем, чтобы (всг) x не было эффективно вычислимым на входной f(x). Если в качестве сети связи используется вычислительная или телефонная сеть, то требуются особенно сильные методы цифровой подписи. Доказано, что такие методы существуют при простом сложностном предположении [11]. D. Вероятностный подход к честности Рабин [14] предложил обмениваться обязательствами по контракту с помощью доверенной третьей стороны. Предложенная Рабином третья сторона открыто распространяет через регулярные интервалы (скажем, через день) случайно выбранное целое число от 1 до 100. Затем стороны А и В могут "подписывать контракты", договорившись о будущей дате D и обмениваясь подписанными сообщениями вида: "Я принимаю обязательства по С, если целое число i выбрано в дату D". А начинает первым. Сторона B пошлгт свог i-ое сообщение только в том случае, если получит i-ое сообщение от А. Аналогично А посылает свог (i+1)-ое сообщение только после пригма i-ого сообщения от B. Все сообщения должны передаваться до наступления даты D. Сторона B может пойти на обман, не посылая свог i-ое сообщение после пригма i-го сообщения от А. Получаемое при этом преимущество невелико: вероятность того, что она будет иметь при наступлении даты D "подписанный контракт", а А не будет иметь этого, равна 1/100. В этом смысле протокол является "честным". Следует отметить, что вышеуказанные вероятностные заявления производились с учгтом будущих действий третьей стороны. Мы считаем, что обращение к третьей стороне при таких заявлениях является неотъемлемой чертой. Предположим, что А и В одни во всгм мире (т. е. не существует третьей стороны). Следовательно, если сторона А прекращает обмен, то сторона В остагтся предоставленной самой себе. Всг, что В может рассчитать за выполнимое время с момента окончания передачи, по существу равно тому, что она может рассчитать в ближайщее будущее, поскольку не будет приниматься никакой дополнительной информации. Следовательно, В либо имеет обязательства А по С (и может это проверить), либо не имеет их. Положение меняется только при появлении третьей стороны. Третья сторона и ег будущие "непредсказуемые" действия создают основу для вероятностных заявлений (которые можно толковать как принятие во внимание "вердикта" третьей стороны). Таким образом, действия третьей стороны определяют, несгт ли сторона обязательства по С. Поэтому вполне естественно рассматривать третью сторону как судью, а ег действия называть вердиктом. В общем случае будем рассматривать вероятностное пространство, созданное сторонами и, возможно, третьей стороной (судьгй). При этом обычно определяется две случайных переменных: одна ассоциируется с каждой стороной и указывает, что сторона имеет некоторую опцию или возможность, связанную с контрактом (например, наличие обязательства другой стороны или возможность вызова судьи для выполнения сторонами обязательств по контракту). Эти случайные переменные должны быть тесно связаны в ходе выполнения протокола. Точное определение связи между переменными составляет сущность вероятностного толкования честности (см. главу II). В типичном случае вероятность принятия судьгй решения, что А имеет такую опцию или возможность, возрастает в ходе выполнения протокола от нуля до единицы. Это возрастание носит постепенный характер, так что вероятность того, что А имеет такую опцию, всг время приблизительно равна вероятности того, что ег имеет В. Е. Вмешательство третьей стороны В этой статье мы используем вероятностный подход к честности. Как обсуждалось ранее, такой подход требует наличия и возможного вмешательства третьей стороны. Полагаться на наличие третьей стороны - это не лучший выход, но он предпочтительнее вычислительного подхода к честности и присущих ему недостатков, обсуждавшихся в главе I-С. Поскольку в решении задачи подписания контракта мы полагаемся на третью сторону, то качество получаемого решения зависит от роли этой стороны: чем более "незаметна" и эффективна третья сторона, тем лучше решение. Используемая в нашем решении третья сторона - это вероятностный алгоритм, называемый судьгй. Судья бездействует, пока к нему не обратятся. Судья может принять решение о том, несут ли обе стороны обязательства по контракту, в присутствии только одной стороны. Более того, судья призывается только в случае спора и может не хранить старые вердикты. Мягкость вмешательства (третьей стороны) в нашем решении можно показать, сравнивая с другими видами участия доверенных третьих сторон, предложенных в предыдущих решениях "задачи подписания контракта". Простым традиционным решением при подписании контрактов является центр аннулирования, который хранит все недействительные контракты (см. [7]). Стороны принимают обязательства по контракту С, обмениваясь сообщениями вида: "Я несу обязательства по контракту С, пока не передам в центр заявление об аннулировании, помеченное датой D", где D - некоторая будущая дата. На практике это слишком простое решение страдает серьгзными недостатками. Для обеспечения функционирования центра аннулирования требуется громадная бумажная работа. Более неприятным является то, что если А желает проверить действие обязательств по С (B могла аннулировать C, не сообщив A), то должна обращаться в центр. Это справедливо даже в том случае, если А и В честны и желают точно выполнять протокол. Как обсуждалось в главе I-D, Рабин [14] предложил использование доверенной третьей стороны, передающей случайно выбранные целые числа в фиксированное время. Укажем, что такая третья сторона должна постоянно быть активной, независимо от честности всех сторон и от того, ссылаются ли на ег выходные значения. II. Определение честности Предложенный Рабином протокол для подписания контрактов использовал обмен (частичными) обязательствами. В его протоколе всегда возрастает интервал времени, если одна из сторон приняла обязательства по контракту, а другая нет; однако протокол построен так, что стороны не могут узнать этот интервал. Тем не менее, это слабое место в протоколе Рабина, так как если протокол прервать в течение этого интервала, возникнет асимметричная ситуация. В предлагаемом ниже протоколе этот недостаток присутствует в более слабом виде. Это достигается тем, что стороны обмениваются скорее "привилегиями", чем обязательствами, где привилегия - это способность заставить судью принять решение о взаимных обязательствах сторон по контракту. (Будем говорить, что сторона привилегирована, если она способна заставить судью принять такое решение). Вполне справедливо, что в нашем протоколе одна сторона может быть привилегированной, а другая нет; однако привилегированная сторона не знает о своей привилегированности, и более того, эта привилегия просто является причиной, вызывающей симметричную ситуацию. В протоколе Рабина одна сторона может знать о принятии обязательств другой стороной, хотя сама не приняла таких обязательств; в нашем протоколе любая попытка разрешить неопределгнность путгм обращения к судье, приводит к установлению симметричной ситуации. В этой главе мы приводим вероятностное определение честности. Мы предполагаем использование жизнеспособных протоколов в следующем смысле. Определение. Будем называть протокол жизнеспособным, если при его соблюдении обеими сторонами протокол завершается после принятия сторонами обязательств по контракту. Необходим охарактеризовать вероятностное пространство, в котором будут определены все события. В общем случае будем рассматривать пространство, созданное сторонами и, возможно, третьей стороной (судьгй). Определим две случайные переменные, ассоциируемые с состоянием привилегированности каждой из сторон. Эти случайные переменные будут тесно связаны в ходе выполнения протокола. Дадим количественное определение заявления о том, что две {0,1}-случайные переменные "тесно связаны". А. Тесно связанные события: априорность против условной вероятности Вновь сущность вероятностного подхода заключается в требовании, чтобы событие "А привилегирована" и событие "В привилегирована" были тесно связаны. Как представить это в формальном виде? Рассмотрим две разумных альтернативы: 1) потребовать, чтобы вероятность того, что "А привилегирована, а В нет" была всегда мала (аналогично для привилегированной В и непривилегированной А); 2) потребовать, чтобы условная вероятность того, что "В непривилегирована" при заданном "А привилегирована", была всегда мала (за исключением случая, когда событие "А привилегировано" маловероятно). (Аналогично для обратной ситуации). (Без этого допущения никакой жизнестойкий протокол не будет удовлетворять условию, поскольку на некотором шаге одна из сторон получает привилегию с ненулевой вероятностью, в то время как его партнгр привилегирован с нулевой вероятностью). Заметим, что второе требование подразумевает первое. мы считаем, что второе требование является лучшей мерой честности, поскольку оно лучше моделирует интуитивное определение честности как одновременности ("если А привилегирована, то В также привилегирована" и наоборот). Рассмотрим протокол Рабина (см. главу I-D), чтобы показать различие между альтернативами. На каждом этапе протокола вероятность того, что А приняла обязательства, а В нет, равна 1/100. Однако после того, как А отправила i сообщений, но до ответа В, условная вероятность, что "В не приняла обязательств по контракту" при заданном "А приняла обязательства по контракту", равна 1/i (а не 1/100). В. Формальная постановка задачи Пусть v>0 определяет нашу меру "незначительной" вероятности; а именно, мы будем пренебрегать событиями, происходящими с вероятностью, меньшей v.Например, можно выбрать v=2**(-100). Пусть e обозначает верхнюю границу вероятности того, что одна из сторон непривилегирована при заданной привилегированности другой стороны (причгм вероятность последнего события не является незначительной). Определение. Протокол подписания контракта является (v,e)-честным для А, если для любого контракта С при точном выполнении А протокола выполняется следующее. На любом шаге протокола, в котором вероятность, что В привилегирована, больше v, условная вероятность того, что "А непривилегирована" при заданном "В привилегирована", не превышает e. Протокол является (v,e)-честным, если он (v,e)-честен и для А и для В. III. О числе сообщений, передаваемых при обмене в ходе (v,e)-честного протокола В этой главе мы получим нижнюю границу для длины кратчайшего из возможных (v,e)-честных протоколов. Доказательство также дагт оптимальную последовательнсоть вероятностей p1,p2,..., таких, что после i-ой передачи получатель привилегирован с вероятностью p. Протокол обмена привилегиями - это последовательность обмена сообщениями, далее называемых шагами. На каждом шаге одна из сторон посылает другой стороне сообщение. Без потери общности, ни одна из сторон не может послать сообщения в ходе двух последовательных шагов, т.е. каждая сторона поочергдно отправляет и принимает сообщения. Обозначим сторону, отправляющую (соответственно, принимающую) сообщение на шаге i, как Si (соответственно, Ri). Пусть событие Ei означает следующее: "после шага i сторона Ri привилегирована" (т.е. судья, призванный Ri, решит, что обе стороны приняли обязательства по контракту). Анализ проводится на зависимости требования (v,e)-честности от числа шагов в жизнеспособном протоколе. Для простоты предположим, что число шагов не зависит от контракта С и обозначается как #(v,e). По требованию жизнеспособности при окончании протокола каждая из сторон должна быть привилегированной с вероятностью 1. Таким образом, P(E )=1. По определению (v,e)-честности для каждого i, 1<=i<=#(v,e), если P(Ei)>=v, то P(Ei |Ei) >= 1-e. Отсюда следует P(Ei ) >= (1-e)*P(Ei) (так как P(A)/P(B)>=P(A|B) для двух событий A и B). Получаем P(E ) >= (1-e) . Окончательно, P(E )<=v, так что требование честности на первом шаге не нарушается. Таким образом, #(v,e) и P(Ei) легко ограничиваются выражениями, зависящими от v и e, как показано ниже. Теорема 1. Каждый жизнеспособный (v,e)-честный протокол обмена привилегиями имеет длину | log(v) | #(v,e) >= |log(1-e)| +2. Это приблизительно равно (1/e)log(1/v). Более того, вероятность того, что после шага i сторона привилегирована, не превышает v/(1-e) . IV. Предлагаемый метод Наш протокол использует метод подписи, принятый в сети. Нам удобно отделить анализ протокола обмена привилегиями от безопасности метода подписи, используемого при внедрении протокола. Например, ручные подписи нельзя проанализировать математически, но можно использовать в нашем протоколе в обычной почтовой системе. Такое разделение возможно, если предположить, что используемые при внедрении подписи вообще нельзя подделать, а именно для каждого сообщения m и пользователя А вероятность того, что другой пользователь (В) может создать подпись А для m, равна нулю (независимо от вычислительной мощи В). Следует подчеркнуть, что в этом смысле методы цифровой подписи не могут быть неподделываемыми, поэтому при внедрении в протоколе "конкретного" метода цифровой подписи могут возникнуть проблемы. Фактически "безопасность" протокола не может превышать "безопасность" сопутствующего метода подписи, но может быть значительно меньше. Это происходит по той причине, что протокол в конкретной реализации может плохо (в непредсказуемой манере) взаимодействовать с методом подписи. Однако для нашего протокола это не так. Наш протокол остагтся честным при внедрении с методами подписи, которые неподдельны (даже при адаптивной атаке на выбранный текст) [11,3]. Формальное изложение данного заявления и его доказательство опускаются. А. Протокол для А и В Представим протокол для А и В, описывающий обмен их обязательствами по контракту С. В этом протоколе А и В обмениваются подписанными сообщениями вида: "С вероятностью p контракт С будет считаться действительным. (Подпись)." Получатель такого сообщения привилегирован с вероятностью p; т.е. если он обратится к судье с этим сообщением, то судья с вероятностью p решит, что обязательства по контракту несут обе стороны. Сторона А (соответственно В) использует локальную переменную (соотв. ), обозначающую вероятность, упомянутую в самом последнем сообщении, подписанном А (соотв. В). (Процедура тайм-аута. Если протокол нормальным путгм не завершается к дате D, то любая сторона может обратиться к "процедуре ранней остановки", описанной ниже.) * Стороны А и В договариваются, кто "начнгт первым"; предположим, что первым начинает А. Предполагаем, что контракт определяет дату D, к которой процесс подписания должен быть завершгн. * Сторона А выбирает вероятность v, которая "пренебрежимо мала" в том смысле, что А желает иметь шанс v того, что В привилегирована, а А нет. * Сторона А также выбирает значение >1, для которого должно обеспечиваться следующее: на каждом шаге вероятность, что А привилегирована при условии привилегированности В, должна быть по меньшей мере 1/ (за исключением, конечно, случая, когда вероятность привилегированности В 1, отвечающее симметричному условию. * В начале протокола и установлены в ноль. Итерации. Стороны А и В поочергдно выполняют шаги, пока обе не примут и пошлют подписанные сообщения вида "С вероятностью 1 контракт С будет считаться действительным". А-шаг: пусть p будет вероятностью, упомянутой в последнем подписанном сообщении, принятом А (p=0, если такое сообщение не было принято). Сторона А проверяет, является ли p>= ; если нет, то А завершает протокол и считает, что В "рано остановил протокол". Примечание. Сторона А проверяет, не стала ли увеличенная В вероятность больше значения и, в частности, что p= (А даже не знает ). См. главу IV-C-2. Сторона А устанавливает max(v, min(1,p* ) и посылает В подписанное сообщение "С вероятностью контракт С будет считаться действительным. (Подпись А)." В-шаг: пусть p будет вероятностью, упомянутой в последнем подписанном сообщении, принятом В. Сторона В проверяет, является ли p>= ; если нет, то В завершает протокол и считает, что А "рано остановил протокол". Сторона В устанавливает min(1,p* ) и посылает А подписанное сообщение "С вероятностью контракт С будет считаться действительным. (Подпись В)." Процедура ранней остановки. Если протокол не будет завершгн к дате D, сторона X обращается к судье, предоставляя ему контракт С и самое последнее сообщение, принятое от другой стороны Y. В. Процедура для судьи При обращении к судье по поводу контракта С, в котором определена дата D, тот не предпринимает никаких действий до наступления этой даты. Затем он изучает предоставленное сообщение вида: "С вероятностью p контракт С будет считаться действительным. (Подпись Y)" и проверяет истинность подписи Y. Если подпись недействительна, судья ничего не делает; в противном случае, он возобновляет дело. Если до этого по контракту C не выносилось вердикта, то судья выбирает случайное значение Pc в соответсвии с равонмерным распределением на интервале [0,1]. В противном случае, он обращается к ранее рассчитанному значению Pc. Если p>=Pc, судья принимает решение, что C обязателен для сторон и посылает подписанный вердикт обеим сторонам. Если p= |log(1-e)| +2. Более того, эти протоколы можно эффективно построить. V. Повышение ээфективности процедуры для судьи Обратим внимание, что судье всего лишь необходимо с достаточной точностью охарактеризовать Pc и определить, является ли p=Pc. Напомним, что от судьи требуется, чтобы всегда использовалось одно и то же значение Pc для данного контракта С. В противном случае могут создаваться конфликтные вердикты и предоставляться преимущества той стороне, которая многократно обращается в суд по поводу одного и того же контракта. В главе IV предполагалось внедрение протокола путгм однократного выбора Pc, хранения пары (C,Pc) и использования Pc во всех последующих вердиктах по поводу С. Такое решение вряд ли можно считать эффективным, так как судья должен хранить записи всех предыдущих Pc. Наша цель освободить судью от учгта. Это можно сделать, используя "псевдослучайные функции" Голдриха и др.[10]. В [10] показано, как преобразовать некоторую одностороннюю (в слабом смысле [13]) функцию во множество эффективно вычислимых функций, которые "неотличимы от случайных функций". В частности, преобразование определяет отображение множества n-битных последовательностей на множество функций (n-битные последовательности на n-битные последовательности), называемом далее множеством полислучайных функций. n-битная последовательность r отображается на функцию f : {0,1} {0,1} . Преобразование эффективно в том смысле, что существует алгоритм полиномиального времени, для которого входные значения - это индекс r и аргумент x, а выходные - f (x) (т. е. значение f от аргумента x). Эти функции неотличимы от случайных в следующем смысле: не существует алгоритма полиномиального времени, который при обращении к предсказателю для выбора входных значений сможет отличить, выбрал ли оракул истинно случайную функцию или случайно выбранную полислучайную функцию. (Под случайной функцией мы имеем ввиду функцию, случайно выбираемую с равной вероятностью из множества всех функций... Теперь покажем, как использовать этот результат, чтобы освободить судью от учгта. Судья один раз случайно выбирает n-битную последовательность r и хранит ег в секрете. Больше никаких случайных выборов судья не делает, и ему не надо хранить никаких записей, кроме секретного значения r. При обращении по поводу С и других входных значений судья рассчитыает f (С) и использует это значение (вместо бросания монеты) для определения Pc. Примечание. Такие действия существенно поддерживают (v,e)-честность. Можно показать, что условная вероятность того, что "В привилегирована" при заданном "А привилегирована", больше 1-e-1/n для всех постоянных с>0 и достаточно больших n. (Это следует из свойств полислучайных функций, за исключением случая, когда не существует односторонних функций). Подчеркнгм, что (v,e)-честность протокола сохраняется даже, если сторонам задаются P, ассоциируемые с другими контрактами по их выбору. А. Несколько судей В нашем решении допускается несколько судей, которые могут последовательно принимать решение без взаимной координации. В этом случае они должны сообща владеть случайно выбранной n-битной последовательностью r, определяющей функцию f из полислучайной совокупности. Функция используется каждым судьгй как показано выше. В. Контракт может и не иметь длину n Выше мы предположили, что все контракты имеют длину n. Это не является обязательным: достаточно, чтобы каждый контракт начинался с n-битной последовательности S, однозначно с ним ассоциируемой (и также содержащей дату тайм-аута D). Для обеспечения уникальности S она должна содержать (кроме тайм-аута D) имена А и В, уникальную подпоследовательность, выбранную А, и уникальную подпоследовательность, выбранную В. Вместо применения f ко всему тексту C судья рассчитывает Pc=f (S). Поскольку одна из сторон никогда не применяет одну и ту же подстроку для двух разных контрактов, неважно, насколько "хитроумно" вторая сторона выберет свою часть S; сохранится та же степень безопасности. Можно сделать короче сообщения обмена, заменив в них "контракт C" на "контракт с идентификационным номером S". Перед началом ранее определгнного протокола сторонам необходимо обменяться подписанными сообщениями, указывающими, что последовательность S - это согласованный идентификационный номер контракта C. С. Почему используются полислучайные функции Полислучайные функции основаны на результатах Блюма и Микали [4] и Яо [16] относительно псевдослучайных генераторов чисел. Псевдослучайные генераторы чисел - это детерминированные алгоритмы, преобразующие истинно случайное (но короткое) секретное инициализирующее значение в длинную псевдослучайную битовую последовательность, удовлетворяющую статистическим тестам полиномиального времени. Непосредственно такие генераторы могут и не быть применимы в нашем контексте. Например: 1) применение C или его части в качестве входа для генератора недопустимо (стороны могут поступить точно так же и определить Pc); 2) применение побитного сложения по модулю 2 для C и некоторого фиксированного ключа r (случайно и секретно выбранного судьгй) и использование результата в качестве входа для генератора может не сработать. Фактически эти генераторы вырабатывают доказательно "случайные" выходы только для независимо и случайно выбранных входов; нет гарантии, что выходы, полученные для тесно связанных входов, не будут связанными. В рамках нашей задачи знание P, ассоциируемых с предыдущими контрактами, может помочь в предсказании Pc, ассоциируемого с новым контрактом C. VI. Выводы и последующее обсуждение Обобщим свойства нашего решения (которое состоит из двухстороннего протокола и судейской процедуры): 1) оно удовлетворяет требованиям жизнеспособности и честности, не используя предположения о "равной вычислительной мощи". Оно устойчиво перед "ранней остановкой". Более того, в отличие от других наше решение в очень мягком виде требует вмешательства доверенной третьей стороны и механизма "тайм-аута"; 2) третья сторона (судья) вмешивается только в случае спора. В этом случае судья может принять решение даже, если в суде появится только одна из сторон. Кроме того, от судьи не требуется учгт (только запоминиание своего секрета); 3) наше решение позволяет использовать нескольких судей без координации их действий. Для одного и того же дела они вынесут одинаковый вердикт; 4) протокол можно реализовать и доказать его честность при минимально возможном "трудном" предположении - существовании безопасных методов подписи (см. [11]). Судейская процедура, использующая случайные функции, требует слегка отличного предположения: существования односторонних функций (см. [10,13]); 5) протокол легко выполнить. Судейская процедура концептуально проста и требует рассмотрения всего одного сообщения (последнего принятого секрета). (Если в сообщениях на контракт ссылаются по его идентификационному номеру, то судье нет необходимости знакомиться с самим контрактом С); 6) протокол оптимален в том смысле, что использует минимальное число обменов сообщениями для выполнения требования (v,e)-честности.