Кольцевая подпись

В криптографии , кольцо подписи является типом цифровой подписи , которая может быть выполнена любым членом множества пользователей, каждый из которых имеет ключи . Следовательно, сообщение, подписанное кольцевой подписью, одобряется кем-то из определенной группы людей. Одно из свойств безопасности кольцевой подписи состоит в том, что с вычислительной точки зрения невозможно определить, какой из ключей членов набора использовался для создания подписи. Кольцевые подписи аналогичны групповым подписям, но отличаются двумя ключевыми способами: во-первых, нет способа отменить анонимность отдельной подписи, а во-вторых, любой набор пользователей может использоваться в качестве набора для подписи без дополнительной настройки.

Кольцевые подписи были изобретены Роном Ривестом , Ади Шамиром и Яэлем Тауманом Калаи и представлены на ASIACRYPT в 2001 году. ^[1] Название, кольцевая подпись , происходит от кольцевой структуры алгоритма подписи .

Определение [ править ]

Предположим, что у каждого набора объектов есть пары открытого / закрытого ключей, ( P ₁ , S ₁ ), ( P ₂ , S ₂ ), ..., ( P _n , S _n ). Сторона i может вычислить кольцевую подпись σ для сообщения m на входе ( m , S _i , P ₁ , ..., P _n ). Любой может проверить действительность кольцевой подписи с учетом σ, m и задействованных открытых ключей P ₁ , ..., P _n.. Если кольцевая подпись рассчитана правильно, она должна пройти проверку. С другой стороны, любому человеку должно быть сложно создать действительную кольцевую подпись для любого сообщения для любого набора, не зная каких-либо закрытых ключей для этого набора. ^[2]

Приложения и модификации [ править ]

Поведение схемы кольцевой подписи Ривест, Шамир, Тауман

В оригинальной статье Ривест, Шамир и Тауман описали кольцевые подписи как способ утечки секрета. Например, кольцевая подпись может использоваться для предоставления анонимной подписи «высокопоставленного должностного лица Белого дома » без указания того, какое должностное лицо подписало сообщение. Кольцевые подписи подходят для этого приложения, потому что анонимность кольцевой подписи не может быть отменена, и потому что группа для кольцевой подписи может быть импровизирована.

Другое приложение, также описанное в исходном документе, предназначено для запрещенных подписей . Здесь отправитель и получатель сообщения образуют группу для кольцевой подписи, тогда подпись действительна для получателя, но кто-то еще не будет уверен, был ли получатель или отправитель фактическим подписавшим. Таким образом, такая подпись убедительна, но не может быть передана за пределы предполагаемого получателя.

Были разные работы, вводящие новые функции и основанные на разных предположениях:

Пороговые кольцевые подписи: ^[3] В отличие от стандартной пороговой подписи « t- out-of- n », где t из n пользователей должны совместно расшифровать сообщение, этот вариант кольцевой подписи требует, чтобы t пользователей сотрудничали в протоколе подписи. А именно, t сторон ( i ₁ , i ₂ , ..., i _t ) могут вычислить ( t , n ) -кольцевую подпись, σ, в сообщении, m , на входе ( m , S _i_₁ , S _i_₂ , ..., S _{i _t} , P ₁ , ..., P _n ).
Связанные кольцевые подписи: ^[4] Свойство связываемости позволяет определить, были ли какие-либо две подписи созданы одним и тем же членом (под одним и тем же закрытым ключом). Тем не менее личность подписавшего сохраняется. Одним из возможных приложений может быть оффлайн система электронных денег .
Прослеживаемая кольцевая подпись: ^[5] В дополнение к предыдущей схеме раскрывается открытый ключ подписывающей стороны (если они выдают более одной подписи под одним и тем же закрытым ключом). Система электронного голосования может быть реализована с использованием этого протокола.

Эффективность [ править ]

Большинство предложенных алгоритмов имеют асимптотический размер вывода ; т.е. размер результирующей подписи увеличивается линейно с размером ввода (количества открытых ключей). Это означает, что такие схемы неосуществимы для реальных сценариев использования с достаточно большими размерами (например, электронное голосование с миллионами участников). Но для некоторых приложений с относительно небольшим средним размером входных данных такая оценка может быть приемлемой. CryptoNote реализует схему кольцевой подписи Fujisaki и Suzuki ^[5] в p2p-платежах, чтобы обеспечить отсутствие отслеживания отправителя. ${\ Displaystyle О (п)}$ ${\ displaystyle n}$ ${\ Displaystyle О (п)}$

В последнее время появились более эффективные алгоритмы. Существуют схемы с сублинейным размером подписи ^[6], а также с постоянным размером. ^[7]

Реализация [ править ]

Исходная схема [ править ]

В исходной статье описывается схема кольцевой подписи на основе RSA , а также схема на основе подписей Рабина . Они определяют заклиненную «функцию объединения» , который принимает ключ , значение инициализации , а также список произвольных значений . Он выводит одно значение . Уравнение разрешимо для любого отдельного входа, но это неосуществимо решить для , если противник не может инвертировать любого из (здесь RSA на основе) люк функций . Функция называется кольцевым уравнением и определяется ниже. Уравнение основано на симметричной функции шифрования : ${\ displaystyle C_ {k, v} (y_ {1}, y_ {2}, \ dots, y_ {n})}$ $k$ $v$ $y_{1},\dots y_{n}$ $z$ $C_{k,v}(y_{1},y_{2},\dots ,y_{n})$ $C_{k,v}(g_{1}(x_{1}),g_{2}(x_{2}),\dots ,g_{n}(x_{n}))$ $x_{1},x_{2},\dots ,x_{n}$ $g_{1},g_{2},\dots ,g_{n}$ $C_{k,v}(y_{1},y_{2},\dots ,y_{n})$ $E_{k}$

C_{k,v}(y_{1},y_{2},\dots ,y_{n})=E_{k}(y_{n}\oplus E_{k}(y_{n-1}\oplus E_{k}(\dots \oplus E_{k}(y_{1}\oplus v)\dots )))=v

В схеме кольцевой подписи выход такой же, как вход. Эта функция тривиально обратима при заданных параметрах. $v$ $n-1$

Генерация подписи [ править ]

Генерация кольцевой подписи включает шесть шагов. Открытый текст обозначается открытыми ключами кольца . $m$ $P_{1},P_{2},\dots ,P_{n}$

Вычислите ключ , используя криптографическую хеш-функцию . Этот шаг предполагает случайный оракул для , поскольку он будет использоваться в качестве ключа для . $k={\mathcal {H}}(m)$ ${\mathcal {H}}$ $k$ $E_{k}$
Выберите случайное значение клея . $v$
Выберите случайным образом для всех участников кольца, кроме вас самих ( будет рассчитано с использованием закрытого ключа s igner), и рассчитайте соответствующий . $x_{i}$ $x_{s}$ $y_{i}=g_{i}(x_{i})$
Решите уравнение кольца для $y_{s}$
Рассчитайте, используя закрытый ключ подписывающей стороны: $x_{s}$ $x_{s}=g_{s}^{-1}(y_{s})$
Кольцевая подпись теперь - пара $(2n+1)$ $(P_{1},P_{2},\dots ,P_{n};v;x_{1},x_{2},\dots ,x_{n})$

Проверка подписи [ править ]

Проверка подписи включает три этапа.

Примените ключ люк общественности на всех : . $x_{i}$ $y_{i}=g_{i}(x_{i})$
Рассчитайте симметричный ключ . $k={\mathcal {H}}(m)$
Убедитесь, что уравнение кольца выполнено . $C_{k,v}(y_{1},y_{2},\dots ,y_{n})=v$

Реализация Python [ править ]

Вот Python- реализация оригинальной статьи с использованием RSA .

импорт  os ,  hashlib ,  random ,  Crypto.PublicKey.RSAclass  Ring :  "" "реализация RSA." ""  def  __init__ ( self ,  k ,  L :  int  =  1024 )  ->  None :  self . k  =  k  self . l  =  L  сам . n  =  len ( k )  self . q  =  1  <<  ( L  -  1 ) def  sign ( self ,  m :  str ,  z :  int ):  "" "Подписать сообщение." ""  self . _permut ( m )  s  =  [ Нет ]  *  self . n  u  =  случайный . randint ( 0 ,  self . q )  c  =  v  =  self . _E ( u )  для  i  в  диапазоне (z  +  1 ,  сам . n )  +  диапазон ( z ):  s [ i ]  =  случайный . randint ( 0 ,  self . q )  e  =  self . _g ( s [ i ],  self . k [ i ] . e ,  self . k [ i ] . n )  v  = я . _E ( v  ^  e )  если  ( i  +  1 )  %  self . n  ==  0 :  c  =  v  s [ z ]  =  себя . _g ( v  ^  u ,  self . k [ z ] . d ,  self . k [ z ] . n )  return  [ c ] +  с def  verify ( self ,  m :  str ,  X )  ->  bool :  "" "Проверить сообщение." ""  self . _permut ( m )  def  _f ( i ):  вернуть  себя . _g ( X [ i  +  1 ],  self . k [ i ] . e ,  self . k [ i ] . n )  y =  map ( _f ,  range ( len ( X )  -  1 ))  def  _g ( x ,  i ):  вернуть  self . _E ( x  ^  y [ i ])  r  =  reduce ( _g ,  range ( self . N ),  X [ 0 ])  return  r  ==  X [ 0 ] def  _permut ( self ,  m ):  self . p  =  int ( hashlib . sha1 ( " % s "  %  m ) . hexdigest (),  16 ) def  _E ( self ,  x ):  msg  =  " % s% s "  %  ( x ,  self . p )  return  int ( hashlib . sha1 ( msg ) . hexdigest (),  16 ) def  _g ( self ,  x ,  e ,  n ):  q ,  r  =  divmod ( x ,  n )  if  (( q  +  1 )  *  n )  <=  (( 1  <<  self . l )  -  1 ):  result  =  q  *  n  +  pow ( r ,  e ,  n )  else :  результат =  x  вернуть  результат

Чтобы подписать и проверить 2 сообщения в кольце из 4 пользователей:

size  =  4 msg1 ,  msg2  =  "привет" ,  "мир!"def  _rn ( _ ):  вернуть  Crypto . PublicKey . RSA . генерировать ( 1024 ,  os . urandom )key  =  map ( _rn ,  range ( размер )) r  =  Кольцо ( ключ ) для  i  в  диапазоне ( размер ):  s1  =  r . знак ( msg1 ,  i )  s2  =  r . sign ( msg2 ,  i )  assert  r . проверки ( msg1 ,  s1 )  и  т . проверять( msg2 ,  s2 ),  а  не  r . проверить ( msg1 ,  s2 )

Криптовалюты [ править ]

Технология CryptoNote использует кольцевые подписи. ^[8] Впервые он был реализован Bytecoin.

ShadowCash [ править ]

Криптовалюта ShadowCash использует отслеживаемую кольцевую подпись для анонимности отправителя транзакции. ^[9] Однако они изначально были реализованы неправильно, что привело к частичной деанонимизации ShadowCash с момента их первой реализации до февраля 2016 года исследователем Monero Research Labs Шеном Нётер. ^[10] К счастью, только 20% всех одноразовых ключей в системе были затронуты этой ошибкой, анонимность отправителя была нарушена, но анонимность получателя осталась неизменной. Своевременно был отправлен патч для устранения ошибки. ^[11]

Monero [ править ]

В период с 10 января 2017 года по 18 октября 2018 года Monero использовала технологию кольцевых конфиденциальных транзакций для сокрытия сумм транзакций в блокчейне. Это позволяло только отправителю и получателю средств узнать истинное количество отправленных средств. ^[12] С тех пор валюта перешла на Bulletproofs. ^[13]

Ссылки [ править ]

^ Как раскрыть секрет , Рон Ривест , Ади Шамир и Яэль Тауман Калаи , ASIACRYPT 2001. Том 2248 конспектов лекций по информатике, страницы 552–565.
^ Дебнат, Ашмита; Сингаравелу, Прадхипкумар; Верма, Шекхар (19 декабря 2012 г.). «Эффективная схема сохранения пространственной конфиденциальности для сенсорной сети». Центральноевропейский инженерный журнал . 3 (1): 1–10. DOI : 10,2478 / s13531-012-0048-7 . S2CID 137248994 .
^ Э. Брессон; Дж. Стерн; М. Шидло (2002). «Пороговые кольцевые подписи и приложения для специальных групп» (PDF) . Достижения в криптологии: Crypto 2002 . Конспект лекций по информатике. 2442 : 465–480. DOI : 10.1007 / 3-540-45708-9_30 . ISBN 978-3-540-44050-5.
^ Лю, Джозеф К .; Вонг, Дункан С. (2005). Связанные кольцевые подписи: модели безопасности и новые схемы . ICCSA . Конспект лекций по информатике. 2 . С. 614–623. DOI : 10.1007 / 11424826_65 . ISBN 978-3-540-25861-2.
^ а б Фудзисаки, Эйитиро; Судзуки, Котароу (2007). «Прослеживаемая кольцевая подпись». Криптография с открытым ключом : 181–200.
^ Фуджисаки, Eiichiro (2011). «Отслеживаемые кольцевые подписи сублинейного размера без случайных оракулов». CTRSA . 95 (1): 393–415. Bibcode : 2012IEITF..95..151F . DOI : 10.1587 / transfun.E95.A.151 .
^ Ау, Ман Хо; Лю, Джозеф К .; Сусило, Вилли; Юэн, Цз Хон (2006). Связанная кольцевая подпись на основе идентификатора постоянного размера и отзываемая в случае если . Конспект лекций по информатике . 4329 . С. 364–378. DOI : 10.1007 / 11941378_26 . ISBN 978-3-540-49767-7.
^ Технология CryptoNote - Отслеживаемые платежи
^ Shadow - Анонимные распределенные электронные деньги с нулевым разглашением через отслеживаемые кольцевые подписи
^ Сломанная криптовалюта в Shadowcash, заархивированная 27 сентября 2016 года на Wayback Machine
^ https://blog.shadowproject.io/2016/03/07/development-update-march-phoenix/
^ «Простое объяснение механики Монеро против Биткойна на простом английском» .
^ Bunz, Бенедикту (1 ноября 2017). «Bulletproofs: краткие доказательства конфиденциальных транзакций и многое другое» . iarc.org . Проверено 14 февраля 2019 года .

[1] Как раскрыть секрет , Рон Ривест , Ади Шамир и Яэль Тауман Калаи , ASIACRYPT 2001. Том 2248 конспектов лекций по информатике, страницы 552–565.

[2] Дебнат, Ашмита; Сингаравелу, Прадхипкумар; Верма, Шекхар (19 декабря 2012 г.). «Эффективная схема сохранения пространственной конфиденциальности для сенсорной сети». Центральноевропейский инженерный журнал . 3 (1): 1–10. DOI : 10,2478 / s13531-012-0048-7 . S2CID 137248994 .

[3] Э. Брессон; Дж. Стерн; М. Шидло (2002). «Пороговые кольцевые подписи и приложения для специальных групп» (PDF) . Достижения в криптологии: Crypto 2002 . Конспект лекций по информатике. 2442 : 465–480. DOI : 10.1007 / 3-540-45708-9_30 . ISBN 978-3-540-44050-5.

[4] Лю, Джозеф К .; Вонг, Дункан С. (2005). Связанные кольцевые подписи: модели безопасности и новые схемы . ICCSA . Конспект лекций по информатике. 2 . С. 614–623. DOI : 10.1007 / 11424826_65 . ISBN 978-3-540-25861-2.

[FS07-5] а б Фудзисаки, Эйитиро; Судзуки, Котароу (2007). «Прослеживаемая кольцевая подпись». Криптография с открытым ключом : 181–200.

[6] Фуджисаки, Eiichiro (2011). «Отслеживаемые кольцевые подписи сублинейного размера без случайных оракулов». CTRSA . 95 (1): 393–415. Bibcode : 2012IEITF..95..151F . DOI : 10.1587 / transfun.E95.A.151 .

[7] Ау, Ман Хо; Лю, Джозеф К .; Сусило, Вилли; Юэн, Цз Хон (2006). Связанная кольцевая подпись на основе идентификатора постоянного размера и отзываемая в случае если . Конспект лекций по информатике . 4329 . С. 364–378. DOI : 10.1007 / 11941378_26 . ISBN 978-3-540-49767-7.

[8] Технология CryptoNote - Отслеживаемые платежи

[9] Shadow - Анонимные распределенные электронные деньги с нулевым разглашением через отслеживаемые кольцевые подписи

[10] Сломанная криптовалюта в Shadowcash, заархивированная 27 сентября 2016 года на Wayback Machine

[11] ttps://blog.shadowproject.io/2016/03/07/development-update-march-phoenix/

[12] «Простое объяснение механики Монеро против Биткойна на простом английском» .

[13] Bunz, Бенедикту (1 ноября 2017). «Bulletproofs: краткие доказательства конфиденциальных транзакций и многое другое» . iarc.org . Проверено 14 февраля 2019 года .

[1]