Достижение соглашения по секретному значению

Изобретение относится к средствам для достижения соглашения по секретному значению. Технический результат - повышение точности соглашения по секретному значению. Второе устройство содержит приемник, выполненный с возможностью принимать информацию, указывающую сверочные данные h, из первого устройства, процессор, выполненный с возможностью вычислять общий секрет s на основе целочисленного значения b, уравнения и системных параметров. Процессор выполнен с возможностью вычислять b на основе протокола обмена ключами. Первое устройство имеет число a, находящееся в приблизительном соглашении с числом b. Первое устройство содержит процессор, выполненный с возможностью определять общий секрет s на основе целочисленного значения a, уравнения и системных параметров и определять сверочные данные h. Первое устройство дополнительно содержит передатчик, выполненный с возможностью передавать информацию, указывающую сверочные данные h, во второе устройство. 5 н. и 10 з.п. ф-лы, 6 ил., 2 табл.

 

Область техники, к которой относится изобретение

Изобретение относится к способу, осуществляемому посредством первого устройства, для достижения соглашения по секретному значению со вторым устройством.

Изобретение дополнительно относится к способу, осуществляемому посредством второго устройства, для достижения соглашения по секретному значению с первым устройством.

Изобретение дополнительно относится к первому устройству, для достижения соглашения по секретному значению со вторым устройством.

Изобретение дополнительно относится ко второму устройству, для достижения соглашения по секретному значению с первым устройством.

Изобретение дополнительно относится к системе, содержащей второе устройство для достижения соглашения по секретному значению с первым устройством и первым устройством.

Изобретение, в частности, относится к двум устройствам, уже имеющим приблизительное соглашение по секретному значению, чтобы достигать точного соглашения по секретному значению.

Уровень техники

Множество современных приложений используют протокол обмена ключами, в котором две стороны A и B хотят формировать совместно используемое значение. Такие протоколы могут быть связаны с известным протоколом обмена ключами Диффи-Хеллмана. Чтобы противостоять криптоанализу, стороны вводят некоторые небольшие ошибки в вычисления в протоколе. Как результат, стороны A и B могут получать значения, скажем , которые согласуются почти, но не обязательно точно. Чтобы приходить к точному соглашению, одна из сторон, скажем A, отправляет другой стороне, B, битовое значение, скажем h, которое служит признаком секретного значения , которое она вычисляет. Сторона A также вычисляет значение из значения . Сторона B затем вычисляет значение из h и собственного значения . Проектное решение системы может быть таким, что секретные значения и равны, если значения и находятся достаточно близко друг к другу. Пример такой системы раскрыт в работе J. Ding, X. Xie и X. Lin, "A simple provably secure key exchange scheme based on the learning with errors problem", Cryptology ePrint Archive, Report 2012/688, 2012 год, http://eprint.iacr.org/2012/688.pdf (в дальнейшем называется "Ding").

C. Peikert, "Lattice Cryptography for the Internet", Proceedings of the 6th Workshop on Post-Quantum Cryptography, PQ Crypto 2014, Springer LNCS, издание 8772, 2014, стр. 197-219 (в дальнейшем называется "Peikert") раскрывает способ, в котором сформированные секретные совместно используемые значения и являются статистически несмещенными, т.е. равномерно распределены. В компоновке Peikert, секретное значение, полученное посредством двух сторон, составляет один отдельный бит.

Работа Joppe Bos, Craig Costello, Ducas, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Ananth Raghunathan и Douglas Stebila, "Frodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWE", IACR Cryptology ePrint Archive, Report 2016/659, https://eprint.iacr.org/2016/659 (в дальнейшем называется "Bos" или "Frodo"), раскрывает расширение способа Peikert таким образом, что стороны согласуют секретное значение, которое равномерно распределено по набору целых чисел. В противопоставленных способах предшествующего уровня техники, один отдельный сверочный бит отправляется. Как в способе Peikert, так и в способе Bos, если стороны должны согласовывать множество битов, способ применяется параллельно к нескольким экземплярам достижения соглашения. Во всех вышеуказанных ссылочных документах, точное соглашение ключей может достигаться, если первоначально полученные значения , вычисленные посредством двух сторон, не отличаются слишком сильно.

Работа Erdem Alkim, Leo Ducas, Thomas Peter Schwabe, "Post-quantum key exchanges - the new hope", International association for cryptologic research, декабрь 2017 года, стр. 1-33, модифицирует протокол Pekert и предлагает новые параметры и более подходящее распределение ошибок для Ring-LWE и кодирует один бит ключа в четыре координаты зашифрованного текста.

Работа Deguchi Kana, Motohiko Isaka, "Approximate performance bound for coding in secret key agreement from the Gaussian channel", IEEE WCNC, март 2015 года, стр. 458-463, поясняет разновидность асимметричного кодирования Слепяна-Вольфа, показывающую то, что извлеченный предел предоставляет точное прогнозирование вероятности ошибок, когда зашумленный ресурс представляет собой двоичный входной гауссов канал.

Сущность изобретения

Было бы полезно иметь улучшенный способ достижения соглашения между двумя устройствами по секретному значению. Чтобы лучше разрешать эту проблему, первый аспект изобретения предоставляет второе устройство, для достижения соглашения по секретному значению с первым устройством, содержащее:

- приемник, выполненный с возможностью принимать информацию, указывающую сверочные данные h, из первого устройства, при этом , при этом δ является целым числом, большим 1; и

- процессор, выполненный с возможностью вычислять общий секрет s на основе целочисленного значения b и уравнения:

- при этом b удовлетворяет , B является положительным целым числом, и q является целым кратным , при этом q, B, δ и c представляют собой системные параметры.

Поскольку вспомогательные данные находятся в диапазоне , при этом δ является целым числом, большим 1, вспомогательные данные h, которые первое устройство отправляет во второе устройство, состоят из нескольких битов. В этой системе, точное соглашение ключей может достигаться даже при установлении менее строгого условия для приблизительного соглашения между значениями a и b. Изложенное устройство позволяет определять общий секрет s с использованием вспомогательных данных h, которые второе устройство принимает из первого устройства, так что точное соглашение достигается.

В частности, точное соглашение достигается, когда первое устройство использует число a, находящееся в приблизительном соглашении с числом b, в том смысле, что a≡b+e(mod q), при этом e представляет разность между числами a и b, при этом ограничение |e|≤- обеспечивает относительно большую разность между a и b. Это свойство обеспечивает возможность использования более защищенного алгоритма обмена ключами.

Альтернативно, для данного условия приблизительного соглашения, система может использоваться для того, чтобы достигать точного соглашения по секретному значению s, которое имеет, по меньшей мере, на один бит больше, чем в случае, например, в предшествующем уровне техники, раскрытом в Peikert или Bos.

В конкретном примере, процессор выполнен с возможностью вычислять b на основе протокола обмена ключами. Этот протокол обмена ключами, например, может представлять собой один из протоколов обмена ключами, раскрытых в Ding, Peikert и Bos, либо их разновидность, которая приводит к приблизительному соглашению по ключу. Изложенное устройство позволяет в дальнейшем достигать точного соглашения эффективным способом, как указано выше.

В конкретном примере, q=2m и , при этом m является положительным целым числом. Эта конфигурация обеспечивает возможность достижения соглашения по нескольким битам при использовании относительно небольшого числа сверочных битов.

В конкретном примере, процессор выполнен с возможностью вычислять значение b на основе значения β и уравнения , при этом , при этом N является целым числом, большим 1, и является взаимно простым относительно q. Это позволяет поддерживать ситуацию, в которой приблизительное соглашение между значением α первого устройства и значением β второго устройства присутствует согласно условию , при этом |e|≤-.

Согласно другому аспекту изобретения, раскрыто первое устройство для достижения соглашения по секретному значению со вторым устройством, при этом первое содержит:

- процессор, выполненный с возможностью:

- определять общий секрет s на основе целочисленного значения a и уравнения:

- при этом a удовлетворяет , B является положительным целым числом, q является целым кратным , при этом δ является целым числом, большим 1, при этом q, B, δ и c представляют собой системные параметры, и

- определять сверочные данные h на основе уравнения:

; и

- передатчик, выполненный с возможностью передавать информацию, указывающую сверочные данные h, во второе устройство.

Поскольку вспомогательные данные h находятся в диапазоне , при этом δ является целым числом, большим 1, вспомогательные данные h, которые первое устройство отправляет во второе устройство, состоят из нескольких битов. В этой системе, точное соглашение ключей может достигаться даже при установлении менее строгого условия для приблизительного соглашения между значениями a и b первого устройства и второго устройства. Изложенное устройство позволяет формировать и передавать вспомогательные данные h, которые требуются второму устройству для того, чтобы определять общий секрет s, так что точное соглашение достигается.

В частности, точное соглашение достигается, когда первое устройство использует число a, находящееся в приблизительном соглашении с числом b, в том смысле, что a≡b+e(mod q), при этом e представляет разность между числами a и b, при этом ограничение |e|≤- обеспечивает относительно большую разность между a и b. Это свойство обеспечивает возможность использования более защищенного алгоритма обмена ключами.

Альтернативно, для данного условия приблизительного соглашения, система может использоваться для того, чтобы достигать точного соглашения по секретному значению s, которое имеет, по меньшей мере, на один бит больше, чем в случае, например, в предшествующем уровне техники, раскрытом в Peikert или Bos.

В конкретном примере, процессор выполнен с возможностью вычислять a на основе протокола обмена ключами. Этот протокол обмена ключами, например, может представлять собой один из протоколов обмена ключами, раскрытых в Ding, Peikert и Bos, либо их разновидность, которая приводит к приблизительному соглашению по ключу.

В конкретном примере, q=2^m, при этом m является положительным целым числом, общий секрет s соответствует B старшим битам двоичного расширения (a+c) mod 2^m, и сверочные данные h соответствуют следующим δ битам двоичного расширения. Это является особенно привлекательным представлением компонентов данных, которые вместе формируют a. В еще более конкретном примере, . Это значение позволяет сверять несколько битов сразу, при использовании относительно небольшого числа битов для вспомогательных данных h. Например, это значение δ позволяет сверять на один бит больше, чем при использовании раскрытого способа в Bos6 при идентичных условиях приблизительного соглашения.

В конкретном примере, c=0. В этом случае, общий секрет s равен частному a и (), округленному вниз до ближайшего целого числа.

В конкретном примере, c=. В этом случае, общий секрет s равен частному a и (), округленному до ближайшего целого числа, при этом округление выполняется вверх в случае привязки.

В конкретном примере, c=. В этом случае, общий секрет s равен частному a и (), округленному до ближайшего целого числа, при этом округление выполняется вниз в случае привязки.

В конкретном примере, процессор выполнен с возможностью вычислять значение a на основе значения α и уравнения , при этом , при этом N является целым числом, большим 1, при этом N является взаимно простым относительно q. Это позволяет поддерживать ситуацию, в которой приблизительное соглашение между значением α первого устройства и значением β второго устройства присутствует согласно условию , при этом |e|≤-.

Согласно другому аспекту изобретения, предусмотрена система, которая содержит первое устройство и второе устройство, изложенные выше, при этом число a находится в приблизительном соглашении с числом b, в том смысле, что a≡b+e(mod q), при этом e представляет разность между числами a и b, при этом |e|≤-. Это позволяет двум устройствам, которые имеют приблизительное соглашение в отношении значений a и b, достигать точного соглашения по общему секрету s, посредством передачи сверочных данных h из первого устройства во второе устройство.

Согласно другому аспекту изобретения, способ должен осуществляться посредством второго устройства для достижения соглашения по секретному значению с первым устройством, при этом способ содержит:

- прием информации, указывающей сверочные данные h, из первого устройства, при этом , при этом δ является целым числом, большим 1; и

- вычисление общего секрета s на основе целочисленного значения b и уравнения:

- при этом b удовлетворяет , B является положительным целым числом, и q является целым кратным , при этом q, B, δ и c представляют собой системные параметры.

Согласно другому аспекту изобретения, способ должен осуществляться посредством первого устройства для достижения соглашения по секретному значению со вторым устройством, при этом способ содержит:

- определение общего секрета s на основе целочисленного значения a и уравнения:

- при этом a удовлетворяет , B является положительным целым числом, q является целым кратным , при этом δ является целым числом, большим 1, при этом q, B, δ и c представляют собой системные параметры;

- определение сверочных данных h на основе уравнения:

; и

- передачу информации, указывающей сверочные данные h, во второе устройство.

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

Краткое описание чертежей

Ниже подробнее поясняются эти и другие аспекты настоящего изобретения, со ссылкой на прилагаемые чертежи.

Фиг. 1 показывает блок-схему второго устройства для достижения соглашения по секретному значению с первым устройством.

Фиг. 2 показывает блок-схему первого устройства для достижения соглашения по секретному значению со вторым устройством.

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

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

Фиг. 5 показывает временную диаграмму системы, содержащей первое устройство и второе устройство для достижения соглашения по секретному значению.

Фиг. 6 показывает описание длины в битах идентификатора, используемого в системе.

Подробное описание вариантов осуществления

Нижеприведенное описание со ссылкой на прилагаемые чертежи предоставляется для того, чтобы помогать в полном понимании примерных вариантов осуществления изобретения, заданного посредством формулы изобретения и ее эквивалентов. Оно включает в себя различные сведения, чтобы помогать в этом понимании, но они должны рассматриваться просто как примерные. Соответственно, специалисты в данной области техники должны признавать, что различные изменения и модификации вариантов осуществления, описанных в данном документе, могут осуществляться без отступления от объема изобретения. Помимо этого, описания хорошо известных функций и конструкций могут быть опущены для ясности и краткости.

Следующая система обозначений используется в этом раскрытии сущности: Для любых двух целых чисел x и v, при , в таком случае обозначает целое число, удовлетворяющее:

Кроме того, для любого действительного числа , система обозначений обозначает результат округления вниз до ближайшего целого числа, и система обозначений обозначает результат округления вверх до ближайшего целого числа. Например: , и .

В конкретных вариантах осуществления, две стороны, A и B, используют конкретный протокол, в котором сторона A вычисляет число a, и сторона B вычисляет число b. Протокол должен быть таким, что вследствие способа, которым вычислены a и b, они приблизительно согласуются. Это приблизительное соглашение выражается с точки зрения системных констант q, B и δ, которые известны для A и B, где q, и B являются положительными целыми числами, и q является целым кратным , следующим образом: a и b являются целыми числами в интервале [0,q] и удовлетворяют:

(уравнение 1)

- при этом:

(уравнение 2)

С использованием настоящего раскрытия сущности, две стороны могут приходить к общему B-битовому секрету s посредством инструктирования одной стороне, скажем, стороне A, передавать битов сверочных данных в сторону B. Еще один целочисленный системный параметр c; его релевантность раскрыта далее. Целые числа h и v задаются посредством следующего уравнения:

(уравнение 3)

- при этом и .

В частности:

(уравнение 4)

В частном случае, в котором q=2^m, секретное значение s соответствует B старшим битам двоичного расширения, h соответствует следующим значимым битов двоичного расширения , и v соответствует младших битов .

Посредством рассмотрения уравнения (1) по модулю , из этого следует, что:

(уравнение 5)

Когда , и когда уравнение (2) удовлетворяется, из этого следует, что:

(уравнение 6)

Посредством комбинирования уравнения (5) и уравнения (6), из этого следует, что:

(уравнение 7)

Посредством комбинирования уравнения (1) и уравнения (3), из этого следует, что:

(уравнение 8)

- и из уравнения (8) следует, что:

. (уравнение 9)

Посредством комбинирования уравнения (9) и уравнения (7) и с использованием свойства , из этого следует, что сторона B может вычислять s с использованием уравнения:

(уравнение 10)

Посредством упрощения уравнения (10), из этого следует, что сторона B альтернативно может вычислять с использованием уравнения:

(уравнение 11)

Уравнения (10) и (11) показывают то, что s может вычисляться из b, h и системных параметров q, B и δ. Таким образом, если сторона A отправляет информацию, указывающую h, стороне B, то сторона B может извлекать s, который может использоваться в качестве общего секрета между стороной A и стороной B.

Поскольку уравнение (3) подразумевает , из этого следует, что , так что h может представляться посредством δ битов.

Следует отметить, что, если c=0, уравнение (4) утверждает, что секрет равен частному a и (q/2^B), округленному вниз до ближайшего целого числа. При варианте выбора , секрет s равен частному a и q/2^B, округленному до ближайшего целого числа (по модулю 2^B) (и округленному вверх в случае привязки, т.е. если a равен для некоторого целого числа ). При варианте выбора , секрет s равен частному a и q/2^B, округленному до ближайшего целого числа по модулю 2^B, с округлением вниз в случае привязки. Другие значения c могут использоваться для того, чтобы получать другой результат, требуемым образом. Для этих специальных вариантов выборов для c, может упрощаться вычисление s посредством стороны B. Фактически, сторона B может получать s с использованием уравнения:

(уравнение 12)

- и в качестве:

(уравнение 13)

В случае если q=2^m, общий секрет s может состоять из B старших битов a; вспомогательные данные h состоят из последующих δ битов a. Кроме того, если a равномерно распределен, то общий секрет s с учетом вспомогательных данных h также равномерно распределен. Таким образом, противник не может получать информацию относительно общего секрета s из наблюдения вспомогательных данных h.

Следует отметить, что условие "приблизительного соглашения" может обобщаться. Например, можно заменять уравнение (1) посредством условия:

(уравнение 14)

- для некоторого целого числа N, которое является взаимно простым относительно q, т.е. наибольший общий делитель N и q равен единице. Условие относительно абсолютного значения e, как указано в уравнении (2), может поддерживаться идентичным:

(уравнение 2)

Например, если q=2^m для некоторого целого числа m, то N может быть любым нечетным числом. В таком случае, вычисление секрета и вспомогательных данных может выполняться с использованием следующего извлечения. Пусть является целым таким числом, что . Такое целое число существует, поскольку q и N являются взаимно простыми. Пусть и . Тогда, . Таким образом, стороны могут согласовывать секрет , как пояснено выше, с использованием α и β вместо a и b, соответственно.

Для δ=1 и q=2^m и получения секрета s в качестве целого числа, ближайшего к частному a и 2^m-B, отправляется один сверочный бит h, и стороны могут согласовывать B-битовый секрет s каждый раз, когда, например, . Если q=2^m и , стороны могут согласовывать B-битовый секрет s каждый раз, когда . Посредством увеличения числа сверочных битов, стороны в силу этого могут согласовывать секретное значение, которое составляет на один бит больше.

С использованием технологий, описанных в данном документе, можно достигать соглашения в отношении секрета без обмена информацией относительно младших битов a. Посредством варьирования δ, можно достигать компромисса между требованиями по полосе пропускания для отправки сверочных данных и требованиями по аппроксимации для успешного точного соглашения.

Фиг. 1 показывает блок-схему примера второго устройства 150 для достижения соглашения по секретному значению с первым устройством 250. Второе устройство 150 содержит антенну 100, приемник 101, процессор 102 и запоминающее устройство 105. Антенна 100 соединяется с приемником 101 для приема сигнала. При работе, запоминающее устройство 105 содержит блок 103 хранения данных и вычислительный блок 104. Антенна 100 может использоваться для отправки и/или приема сигналов в беспроводном режиме с использованием соответствующего стандарта связи. В альтернативной реализации, антенна 100 может заменяться посредством проводного (сетевого) соединения. Хотя в настоящем раскрытии сущности, требуется только приемник 102, практические реализации также могут содержать передатчик для передачи сигналов, например, с использованием антенны 100. Процессор 102 управляет работой устройства, включающего в себя приемник 101 и запоминающее устройство. Блок 103 хранения данных запоминающего устройства 105 может использоваться для того, чтобы сохранять различные данные, в том числе, но не только, системные параметры (например, q, B, δ и c), секрет s, принимаемые сверочные данные h, значение b и другие данные, такие как контент, который должен шифроваться или дешифроваться. Вычислительный блок 104 может содержать выполняемый машинный код, который реализует, по меньшей мере, способ, чтобы достигать соглашения по секретному значению с другим устройством (например, первым устройством 250).

Приемник 101 выполнен с возможностью принимать информацию, указывающую сверочные данные h, из первого устройства, при этом , при этом δ является целым числом, большим 1. Процессор 102 выполнен с возможностью вычислять общий секрет s на основе целочисленного значения b и уравнения:

s≡ .

Например, s может выбираться в качестве значения, для которого является справедливым вышеприведенное уравнение, при этом .

Значение b удовлетворяет , системный параметр B является положительным целым числом, и системный параметр q является целым кратным . Эти системные параметры, например, могут предварительно программироваться в устройстве или приниматься из доверенной стороны. Эти системные параметры не обязательно держатся в секрете.

Процессор 102 может быть выполнен с возможностью вычислять b до вычисления общего секрета s. Такое вычисление может быть основано на протоколе обмена ключами. С этой целью, второе устройство 150 может обмениваться дополнительной информацией с первым устройством 250 или другим устройством, таким как сторонний посредник (не показан), через свой приемник 102 или необязательный передатчик, в соответствии с протоколом обмена ключами. Подробности этого протокола обмена ключами выходят за пределы объема настоящего раскрытия сущности. Свойство второго устройства заключается в том, что оно может определять общий секрет s с использованием сверочных данных h, если первое устройство 250 вычисляет сверочные данные h, как раскрыто далее со ссылкой на фиг. 2, при условии, что первое устройство 250 использует число a, находящееся в приблизительном соглашении с числом b, в том смысле, что a≡b+e(mod q), при этом e представляет разность между числами a и b, при этом |e|≤-.

Для конкретных значений c, вычисление общего секрета s может упрощаться (см. также уравнения 12 и 13). Процессор 102 второго устройства может быть выполнен с возможностью вычислять s посредством оценки формулы:

если

Кроме того, процессор 102 второго устройства может быть выполнен с возможностью вычислять s посредством оценки формулы:

если

- которая может реализовываться альтернативно следующим образом:

если

В конкретном примере, q=2^m и , при этом m является положительным целым числом. В данном документе, >B+3.

В другом примере, процессор 102 выполнен с возможностью вычислять значение b на основе значения β и уравнения , при этом , при этом N является целым числом, большим 1, и является взаимно простым относительно q. Это позволяет поддерживать большую разность между a и b, к примеру, как пояснено выше относительно уравнения 14.

Фиг. 2 показывает блок-схему, иллюстрирующую пример первого устройства 250 для достижения соглашения по секретному значению со вторым устройством 150. Первое устройство 250 содержит антенну 200, передатчик 201, процессор 202 и запоминающее устройство 205. Антенна 200 соединяется с передатчиком 201 для приема сигнала. При работе, запоминающее устройство 205 содержит блок 203 хранения данных и вычислительный блок 204. Антенна 200 может использоваться для отправки и/или приема сигналов в беспроводном режиме с использованием соответствующего стандарта связи. В альтернативной реализации, антенна 200 может заменяться посредством проводного (сетевого) соединения. Хотя для описания настоящего раскрытия сущности, требуется только передатчик 202, практические реализации также могут содержать приемник для приема сигналов, например, с использованием антенны 200. Процессор 202 управляет работой устройства, включающего в себя передатчик 201 и запоминающее устройство 205. Блок 203 хранения данных запоминающего устройства 205 может использоваться для того, чтобы сохранять различные данные, в том числе, но не только, системные параметры (например, q, B, δ и c), секрет s, сверочные данные h, значение b и другие данные, такие как контент, который должен шифроваться или дешифроваться. Вычислительный блок 204 может содержать выполняемый машинный код, который реализует, по меньшей мере, способ, чтобы достигать соглашения по секретному значению с другим устройством (например, вторым устройством 150).

В практической реализации, процессор 202 может быть выполнен с возможностью определять общий секрет s на основе целочисленного значения a и уравнения:

Это альтернативно может записываться следующим образом:

- при этом значение a удовлетворяет , системный параметр B является положительным целым числом, системный параметр q является целым кратным , и системный параметр δ является целым числом, большим 1.

До или после определения общего секрета s (или одновременно), процессор 202 может определять сверочные данные h на основе уравнения:

Это альтернативно может записываться следующим образом:

Передатчик 201 может быть выполнено с возможностью передавать, под управлением процессора 202, информацию, указывающую сверочные данные h, во второе устройство. Например, информация, указывающая сверочные данные h, может быть двоичным представлением сверочных данных h или кодированным представлением сверочных данных h.

В конкретном примере, процессор 202 выполнен с возможностью вычислять a на основе протокола обмена ключами. С этой целью, первое устройство 250 может обмениваться дополнительной информацией со вторым устройством 150 или другим устройством, таким как сторонний посредник (не показан), в соответствии с протоколом обмена ключами, с использованием передатчика 201 или необязательного приемника. Подробности этого протокола обмена ключами выходят за пределы объема настоящего раскрытия сущности. Свойство первого устройства 250 заключается в том, что оно может предоставлять второму устройству 150 дополнительные сверочные данные h. Второе устройство 150 может определять общий секрет s с использованием сверочных данных h посредством комбинирования сверочных данных h с числом b способом, описанным в данном документе со ссылкой на фиг. 1, при условии, что первое устройство 250 использует число a, находящееся в приблизительном соглашении с числом b, которое используется посредством второго устройства 150, в том смысле, что a≡b+e(mod q), при этом e представляет разность между числами a и b, при этом

В конкретном примере реализации, q=2^m, при этом m является положительным целым числом, общий секрет s соответствует B старшим битам двоичного расширения (a+c) mod 2^m, и сверочные данные h соответствуют следующим старшим δ битам двоичного расширения (a+c) mod 2^m. Например, может предоставлять относительно большое число битов, которые могут сверяться при обеспечении относительно нестрогого ограничения касательно того, насколько приблизительным должно быть соглашение между a и b, и передачи относительно небольшого числа битов сверочных данных δ. Тем не менее, это значение представляется только в качестве примера.

Секрет s может извлекаться из значения a несколькими различными способами. Например, различное поведение может быть реализовано посредством варьирования системного параметра c. Идентичное значение системных параметров (включающих в себя c) должно использоваться в первом устройстве и во втором устройстве для оптимальной производительности. Например, c=0 может выбираться таким образом, что общий секрет s равен частному a и (), округленному вниз до ближайшего целого числа. Альтернативно, может выбираться таким образом, что общий секрет s равен частному a и (), округленному до ближайшего целого числа, при этом округление выполняется вверх в случае привязки. Еще альтернативно, выбирается таким образом, что общий секрет s равен частному a и (), округленному до ближайшего целого числа, при этом округление выполняется вниз в случае привязки.

В конкретном примере реализации, процессор выполнен с возможностью вычислять значение a на основе значения α и уравнения , при этом , при этом N является целым числом, большим 1, при этом N является взаимно простым относительно q. Это позволяет поддерживать большую разность между a и b, к примеру, как пояснено выше относительно уравнения 14.

Процессоры 102 и 202 могут представлять собой любой тип процессора компьютера, допускающего выполнение программы, сохраненной в запоминающем устройстве, и управляющего периферийными устройствами, такими как передатчик, приемник, запоминающее устройство и т.п. Например, процессор 102 или 202 может представлять собой микроконтроллер или микропроцессор. Такой процессор представляет собой электронное устройство, которое известно в данной области техники. Кроме того, процессор 102, 202 может содержать множество подпроцессоров, которые могут взаимодействовать с возможностью выполнять определенные задачи параллельно. Запоминающее устройство 105 или 205 может представлять собой любой тип запоминающего устройства, которое допускает сохранение цифровых данных, энергозависимым или энергонезависимым способом. Запоминающее устройство 105 или 205 является машиночитаемым и может использоваться посредством соответствующего процессора 102, 202, чтобы извлекать и/или сохранять данные. Такое запоминающее устройство 105, 205 представляет собой электронное устройство. Известные примеры включают в себя флэш-память, оперативное запоминающее устройство (RAM), постоянное запоминающее устройство (ROM) и накопитель на магнитных или оптических дисках. Комбинация этих типов запоминающего устройства может использоваться в каждом устройстве.

В конкретном примере, одно устройство содержит все компоненты и функциональность как первого устройства, так и второго устройства. Например, устройство может переключать роли между ролью первого устройства и второго устройства.

Передача данных из первого устройства во второе устройство может осуществляться посредством прямой связи. Альтернативно, передача может выполняться через сеть, и сверочные данные могут проходить через несколько узлов в сети перед достижением второго устройства. Например, передача данных может использовать технологию на основе Wi-Fi-, Bluetooth-, 3G-, 4G-, LTE-сетей передачи данных.

Фиг. 3 иллюстрирует способ, осуществляемый посредством второго устройства для достижения соглашения по секретному значению с первым устройством. Фиг. 4 иллюстрирует способ, осуществляемый посредством первого устройства для достижения соглашения по секретному значению со вторым устройством. Фиг. 5 иллюстрирует то, как, первое устройство 501 и второе устройство 502 могут взаимодействовать с возможностью достигать соглашения. Этапы, проиллюстрированные на фиг. 5, которые соответствуют этапам, проиллюстрированным на фиг. 3 и фиг. 4, указаны с использованием идентичных ссылок с номерами.

Ссылаясь на фиг. 3 и фиг. 5, второе устройство начинает способ на этапе 301. Начало может быть инициировано, например, посредством соответствующего внутреннего или внешнего сигнала или ввода, предоставленного пользователем. Например, способ начинается, когда первое устройство пытается устанавливать связь со вторым устройством. На этапе 302, системные параметры q, B, δ и c определяются. Например, эти системные параметры извлекаются из запоминающего устройства 103. Необязательно, как указано посредством стрелки 503, этот этап может заключать в себе соглашение между первым и вторым устройством по системным параметрам, которые должны использоваться; например, можно обмениваться сообщениями относительно набора параметров, который поддерживается посредством обоих устройств. B является положительным целым числом, δ является целым числом, большим 1, и q является целым кратным . На этапе 303, число b определяется. Например, это число вычисляется из данных, которые задаются доступными для второго устройства. Альтернативно, число b принимается из внешнего источника, например, доверенной стороны, предпочтительно в зашифрованной форме. Число b может получаться в качестве части протокола обмена ключами на основе решеток. Как указано посредством стрелки 504, значение b находится в приблизительном соглашении с соответствующим значением a первого устройства 501. На этапе 304, второе устройство принимает информацию, указывающую сверочные данные h, как указано посредством стрелки 505. Информация, например, может передаваться во второе устройство в зашифрованной форме и дешифроваться посредством второго устройства. Сверочные данные находятся в диапазоне . На этапе 305, второе устройство вычисляет s на основе уравнения:

Например:

Другие представления s также являются возможными.

На этапе 306, необязательно ключ определяется на основе общего секрета s. Затем способ завершается на этапе 307. Необязательно, второе устройство может теперь начинать использование общего секрета s и/или ключа на основе общего секрета s. Возможные варианты применения могут представлять собой любой один или более из множества вариантов применения, включающих в себя криптографическую обработку данных, таких как контент, например, шифрование, дешифрование, создание и верификацию цифровой подписи. Например, общий секрет s может использоваться для защищенного обмена сообщениями между первым устройством и вторым устройством, как указано посредством стрелки 506. Кроме того, общий секрет s и/или ключ, извлекаемый из него, могут сохраняться в запоминающем устройстве второго устройства для последующего использования.

Ссылаясь на фиг. 4 и фиг. 5, первое устройство начинает способ на этапе 401. Начало может быть инициировано, например, посредством соответствующего внутреннего или внешнего сигнала или ввода, предоставленного пользователем. Например, способ начинается, когда второе устройство пытается устанавливать связь с первым устройством. На этапе 402, системные параметры q, B, δ и c определяются. Например, эти системные параметры извлекаются из запоминающего устройства. Необязательно, как указано посредством стрелки 503, этот этап может заключать в себе соглашение между первым и вторым устройством по системным параметрам, которые должны использоваться; например, можно обмениваться сообщениями для того, чтобы определять набор параметров, который поддерживается посредством обоих устройств. B является положительным целым числом, δ является целым числом, большим 1, и q является целым кратным . На этапе 403, первое устройство определяет число a. Это определение может быть основано, например, на протоколе обмена ключами. Например, это число a вычисляется из данных, которые задаются доступными для первого устройства. Альтернативно, число a принимается из внешнего источника, например, доверенной стороны, предпочтительно в зашифрованной форме. Число a может получаться в качестве части протокола обмена ключами на основе решеток. Как указано посредством стрелки 504, значение a находится в приблизительном соглашении с соответствующим значением b второго устройства 502. На этапе 404, первое устройство определяет сверочные данные h. Эти сверочные данные могут быть основаны на уравнении:

Сверочные данные могут находиться в диапазоне . На этапе 405, первое устройство передает информацию, указывающую сверочные данные h, как указано посредством стрелки 505, во второе устройство. Информация, например, может шифроваться посредством первого устройства, чтобы передавать информацию во второе устройство в зашифрованной форме. На этапе 406, первое устройство определяет общий секрет s. Этот этап может выполняться перед другими этапами. В альтернативной реализации, общий секрет s может определяться до определения числа a, при этом первое устройство может извлекать число a из общего секрета s. Общий секрет s может вычисляться на основе уравнения:

В другой системе обозначений:

Другие представления s также являются возможными. На этапе 407, необязательно ключ определяется на основе общего секрета s. Альтернативно, общий секрет s может быть основан на ключе, определенном заранее. Затем способ завершается на этапе 408. Необязательно, первое устройство может использовать общий секрет s и/или ключ. Возможные варианты применения могут представлять собой любой один или более из множества вариантов применения, включающих в себя криптографическую обработку данных, таких как контент, например, шифрование, дешифрование, создание и верификацию цифровой подписи. Например, общий секрет s или ключ может использоваться для защищенного обмена сообщениями между первым устройством и вторым устройством, как указано посредством стрелки 506. Кроме того, общий секрет s и/или ключ могут сохраняться в запоминающем устройстве второго устройства для последующего использования.

Фиг. 6 показывает пример, иллюстрирующий концептуально возможную взаимосвязь между a, s, h, m, B и q для конкретного случая q=2^m и c=0. На чертеже, проиллюстрировано двоичное представление a, от старшего бита (слева) к старшему биту (справа). В ссылке с номером 601, проиллюстрировано то, что общий секрет s представляется посредством B старших битов a. В ссылке с номером 602, проиллюстрировано то, что сверочные данные h представляются посредством (B+1)-го - -го старших битов a. В ссылке с номером 603, проиллюстрировано то, что оставшиеся -ый - q-тый биты, т.е. младших битов a, не представляются ни в общем секрете s, ни в сверочных данных h. Этот признак может обеспечивать возможность экономии данных относительно числа битов сверочных данных h и/или увеличенного допуска относительно приблизительного соглашения между a и b.

В этом раскрытии сущности, предусмотрен способ сверки, который может отправлять более одного сверочного бита. Технологии, раскрытые в данном документе, могут использоваться, например, для того, чтобы инструктировать сторонам согласовывать конкретное число битов, при установлении менее строгих условий для того, "насколько приблизительным" должно быть приблизительное соглашение. Обеспечение менее строгих условий относительно приблизительного соглашения позволяет повышать безопасность системы. Альтернативно, при приблизительно идентичных условиях аппроксимации (т.е. при аналогичных гарантиях безопасности), экземпляр способа позволяет двум сторонам согласовывать секретное значение, которое составляет на один бит больше. В дальнейшем в этом документе, некоторые преимущества способа и его влияние раскрыты посредством числовых примеров.

Bos раскрывает способ квантового защищенного обмена ключами. Одна сторона отправляет в другую сторону небольшое инициирующее число и матрицу с элементами из . В ответ, отправляются матрица и двоичная матрица со сверочными битами. Стороны конструируют матрицу ; из каждого элемента упомянутой матрицы, извлекаются B общих битов. Общее число извлеченных битов (помечено как "длина" в нижеприведенных таблицах) в силу этого равно , в то время как общее число передаваемых битов равно:

Таблица 1 является уплотненной версией предложенных созданий экземпляра в таблице 2 Bos.

Схема	N	Q	B			Длина	Полоса пропускания
Соревновательная	352		1	8	8	64	7,57 Кбайт
Классическая	592		2	8	8	128	14,22 Кбайт
Рекомендованная	752		4	8	8	256	22,57 Кбайт
Параноидальная	864		4	8	8	256	25,93 Кбайт

Табл. 1. Варианты выбора параметров из работы Bos

Согласно Bos, в случае если отправляется один сверочный бит, гарантируется то, что стороны согласуют общий B- битовый секрет, если их числа отличаются менее чем на (где m является таким, что q=2^m. Результаты для технологий, раскрытых в данном документе, показывают то, что при идентичных условиях, две стороны могут согласовывать - битовый секрет, если отправляются сверочных битов. Объем сверочных данных в силу этого равен битов в расчете на элемент матрицы, и полная используемая полоса пропускания равна . Поскольку в технологиях, раскрытых в данном документе, число битов, которое согласовано, больше, чем в раскрытии сущности Bos, можно уменьшать и/или и за счет этого уменьшать полное использование полосы пропускания. С использованием технологий, раскрытых в данном документе, получены результаты в таблице 2. Самый правый столбец (помечен "Отношение") показывает отношение используемой полосы пропускания предложенной схемы сверки и используемой полосы пропускания системы, раскрытой в Bos.

Схема	n	q	B			Длина	Полоса пропускания	Отношение
Соревновательная	352		2	6	6	72	5,84 Кбайт	0,76
Классическая	592		3	7	7	147	12,48 Кбайт	0,88
Рекомендованная	752		5	7	8	280	21,22 Кбайт	0,94
Параноидальная	864		5	7	8	280	24,37 Кбайт	0,94

Табл. 2. Улучшение, которое может достигаться посредством схемы сверки, раскрытой в данном документе

Следует принимать во внимание, что изобретение также применимо к компьютерным программам, в частности, к компьютерным программам на носителе, адаптированном с возможностью осуществлять изобретение на практике. Программа может иметь форму исходного кода, объектного кода, кода, промежуточного между исходным и объектным кодом, к примеру, частично компилированную форму, либо любую другую форму, подходящую для использования при реализации способа согласно изобретению. Также следует принимать во внимание, что эта программа может иметь множество различных вариантов архитектурного проектирования. Например, программный код, реализующий функциональность способа или системы согласно изобретению, может подразделяться на одну или более вложенных процедур. Множество различных способов распределения функциональности между этими вложенными процедурами должны становиться очевидными для специалистов в данной области техники. Вложенные процедуры могут сохраняться совместно в одном исполняемом файле, чтобы формировать автономную программу. Такой исполняемый файл может содержать машиноисполняемые инструкции, например, инструкции процессора и/или инструкции интерпретатора (например, инструкции Java-интерпретатора). Альтернативно, одна или более или все вложенные процедуры могут сохраняться, по меньшей мере, в одном внешнем файле библиотеки и связываться с основной программой статически или динамически, например, во время выполнения. Основная программа содержит, по меньшей мере, один вызов, по меньшей мере, одной из вложенных процедур. Вложенные процедуры также могут содержать вызовы друг друга. Вариант осуществления, связанный с компьютерным программным продуктом, содержит машиноисполняемые инструкции, соответствующие каждому этапу обработки, по меньшей мере, одного из способов, изложенных в данном документы. Эти инструкции могут подразделяться на вложенные процедуры и/или сохраняться в одном или более файлов, которые могут связываться статически или динамически. Другой вариант осуществления, связанный с компьютерным программным продуктом, содержит машиноисполняемые инструкции, соответствующие каждому из средств, по меньшей мере, одной из систем и/или продуктов, изложенных в данном документе. Эти инструкции могут подразделяться на вложенные процедуры и/или сохраняться в одном или более файлов, которые могут связываться статически или динамически.

Носитель компьютерной программы может представлять собой любой объект или устройство, допускающее перенос программы. Например, носитель может включать в себя носитель хранения данных, такой как ROM, например, CD-ROM или полупроводниковое ROM, или магнитный носитель записи, например, флэш-накопитель или жесткий диск. Более того, носитель может представлять собой передающую среду, такую как электрический или оптический сигнал, который может передаваться через электрический или оптический кабель либо по радиосвязи или по другому средству. Когда программа осуществлена в этом сигнале, носитель может состоять из такого кабеля либо другого устройства или средства. Альтернативно, носитель может представлять собой интегральную схему, в которой осуществлена программа, причем интегральная схема адаптирована с возможностью работать или использоваться при осуществлении соответствующего способа.

Следует отметить, что вышеуказанные варианты осуществления иллюстрируют, а не ограничивают изобретение, и специалисты в данной области техники должны иметь возможность разрабатывать множество альтернативных вариантов осуществления без отступления от объема прилагаемой формулы изобретения. В формуле изобретения, все ссылки с номерами, помещенные в круглые скобки, не должны рассматриваться как ограничивающие формулу изобретения. Использование глагола "содержит" и его спряжений не исключает наличия элементов или этапов, отличных от элементов или этапов, изложенных в формуле изобретения. Артикль "a" или "an" перед элементом не исключает наличия множества таких элементов. Изобретение может реализовываться посредством аппаратных средств, содержащих несколько отдельных элементов, и посредством надлежащим образом запрограммированного компьютера. В пункте формулы изобретения на устройство, перечисляющем несколько средств, некоторые из этих средств могут быть осуществлены посредством идентичного элемента аппаратных средств. Простой факт того, что определенные меры упомянуты в различных зависимых пунктах формулы изобретения, не означает того, что комбинация этих мер не может использоваться с выгодой.

1. Второе устройство для достижения соглашения по секретному значению с первым устройством, содержащее:

- приемник (101), выполненный с возможностью принимать информацию, указывающую сверочные данные h, из первого устройства, при этом , при этом δ является целым числом, большим 1; и

- процессор (102), выполненный с возможностью вычислять общий секрет s на основе целочисленного значения b и уравнения:

s ≡ ,

- при этом b удовлетворяет , B является положительным целым числом, и q является целым кратным , при этом q, B, δ и c представляют собой системные параметры, причем c является целочисленным системным параметром.

2. Второе устройство по п. 1, в котором процессор (102) выполнен с возможностью вычислять b на основе протокола обмена ключами.

3. Второе устройство по п. 1, в котором первое устройство имеет число a, находящееся в приблизительном соглашении с числом b, в том смысле, что a≡b+e(mod q), при этом e представляет разность между числами a и b, при этом |e| ≤ -.

4. Второе устройство по п. 1, в котором q=2^m и , при этом m является положительным целым числом.

5. Второе устройство по п. 1, в котором процессор (102) выполнен с возможностью вычислять значение b на основе значения β и уравнения , при этом , при этом N является целым числом, большим 1, и является взаимно простым относительно q.

6. Система для достижения соглашения по секретному значению, содержащая второе устройство по п. 1 и первое устройство, при этом первое устройство содержит:

- процессор (202), выполненный с возможностью:

- определять общий секрет s на основе целочисленного значения a и уравнения:

s = ,

- при этом a удовлетворяет , B является положительным целым числом, q является целым кратным , при этом δ является целым числом, большим 1, при этом q, B, δ и c представляют собой системные параметры, причем c является целочисленным системным параметром,

- определять сверочные данные h на основе уравнения:

; и

- передатчик (201), выполненный с возможностью передавать информацию, указывающую сверочные данные h, во второе устройство,

- при этом число a находится в приблизительном соглашении с числом b, в том смысле, что a≡b+e(mod q), при этом e представляет разность между числами a и b, при этом |e| ≤ -.

7. Первое устройство для достижения соглашения по секретному значению со вторым устройством, содержащее:

- процессор (202), выполненный с возможностью:

- определять общий секрет s на основе целочисленного значения a и уравнения:

s = ,

- при этом a удовлетворяет , B является положительным целым числом, q является целым кратным , при этом δ является целым числом, большим 1, при этом q, B, δ и c представляют собой системные параметры, причем c является целочисленным системным параметром,

- определять сверочные данные h на основе уравнения:

; и

- передатчик (201), выполненный с возможностью передавать информацию, указывающую сверочные данные h, во второе устройство.

8. Первое устройство по п. 7, в котором процессор (202) выполнен с возможностью вычислять a на основе протокола обмена ключами.

9. Первое устройство по п. 7, в котором второе устройство имеет число b, находящееся в приблизительном соглашении с числом a в том смысле, что a≡b+e (mod q), при этом e представляет разность между числами a и b, при этом |e| ≤ -.

10. Первое устройство по п. 7, в котором q=2^m, при этом m является положительным целым числом, общий секрет s соответствует B старшим битам двоичного расширения (a+c) mod 2^m, и сверочные данные h соответствуют следующим δ битам двоичного расширения.

11. Первое устройство по п. 10, в котором .

12. Первое устройство по п. 7, в котором, по меньшей мере, одно из следующего:

- c=0, так что общий секрет s равен частному a и (), округленному вниз до ближайшего целого числа;

- , так что общий секрет s равен частному a и (), округленному до ближайшего целого числа, при этом округление выполняется вверх в случае привязки; и

- , так что общий секрет s равен частному a и (), округленному до ближайшего целого числа, при этом округление выполняется вниз в случае привязки.

13. Первое устройство по п. 7, в котором процессор (202) выполнен с возможностью вычислять значение a на основе значения α и уравнения , при этом , при этом N является целым числом, большим 1, при этом N является взаимно простым относительно q.

14. Способ, осуществляемый посредством второго устройства, для достижения соглашения по секретному значению с первым устройством, при этом способ содержит этапы, на которых:

- принимают (304) информацию, указывающую сверочные данные h, из первого устройства, при этом , при этом δ является целым числом, большим 1; и

- вычисляют (305) общий секрет s на основе целочисленного значения b и уравнения:

,

- при этом b удовлетворяет , B является положительным целым числом, и q является целым кратным , при этом q, B, δ и c представляют собой системные параметры, причем c является целочисленным системным параметром.

15. Способ, осуществляемый посредством первого устройства, для достижения соглашения по секретному значению со вторым устройством, при этом способ содержит этапы, на которых:

- определяют (406) общий секрет s на основе целочисленного значения a и уравнения:

,

- при этом a удовлетворяет , B является положительным целым числом, q является целым кратным , при этом δ является целым числом, большим 1, при этом q, B, δ и c представляют собой системные параметры, причем c является целочисленным системным параметром;

- определяют (404) сверочные данные h на основе уравнения:

; и

- передают (405) информацию, указывающую сверочные данные h, во второе устройство.