Квантовые генераторы случайных чисел, экстракция доказуемо случайных битовых последовательностей из траекторий цепи Маркова

И.М. Арбеков^†^а, С.Н. Молотков^‡^{а, б, в, г}
^аАкадемия криптографии Российской Федерации, а/я 100, Москва, 119331, Российская Федерация
^бИнститут физики твердого тела имени Ю.А. Осипьяна РАН, ул. Академика Осипьяна 2, Черноголовка, Московская обл., 142432, Российская Федерация
^вФакультет вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова, Ленинские горы д. 1, стр. 52, Москва, 119991, Российская Федерация
^гЦентр квантовых технологий Московского государственного университета имени М.В. Ломоносова, Ленинские горы 1, стр. 35, Москва, 119991, Российская Федерация

Исследуется одна из главных проблем в построении квантовых генераторов случайных чисел — получение доказуемо случайной выходной последовательности из результатов физических измерений — исходной последовательности, вырабатываемой физическим генератором случайных чисел. Обсуждаются вопросы о принципиальной возможности и условиях, при которых можно "дотянуться" до случайности, а также то, что понимать под доказуемой случайностью. Рассмотрены методы экстракции доказуемо случайных битовых последовательностей из стационарных цепей Маркова конечного порядка, т.е. в предположении о конечной глубине зависимости результатов физических измерений от предыстории, которое является адекватным приближением к реальной ситуации. Продемонстрировано извлечение выходной доказуемо случайной битовой последовательности из исходной последовательности результатов физических измерений с использованием эффективного метода арифметического кодирования В.Ф. Бабкина. Показано, что даже из первичных последовательностей результатов физических измерений, которые являются зависимыми (коррелированными) на любую конечную глубину (предысторию), можно доказуемо получать случайные битовые последовательности. Цель, которую ставили перед собой авторы, — показать связь различных приближений, которые используются при разработке и описании методов получения случайных битовых последовательностей с фундаментальными физическими ограничениями Природы. Математические доказательства доведены до практических алгоритмов, которые используются в реальных генераторах случайных чисел. Необходимые математические доказательства приводятся на интуитивно понятном для физической аудитории уровне, не требуют предварительных специальных знаний и доступны студентам старших курсов университетов.

Текст pdf (464 Кб)

Скачивая файл я соглашаюсь с условиями использования.

English fulltext is available at DOI: 10.3367/UFNe.2024.02.039658

Ключевые слова: квантовые генераторы случайных чисел, цепи Маркова, случайные битовые последовательности
PACS: 02.50.−r, 03.67.−a, 42.50.Ex (все)
DOI: 10.3367/UFNr.2024.02.039658
URL: https://ufn.ru/ru/articles/2024/9/g/
Web of Science

001343554500006
ADS NASA

2024PhyU...67..919A
Цитата: Арбеков И М, Молотков С Н "Квантовые генераторы случайных чисел, экстракция доказуемо случайных битовых последовательностей из траекторий цепи Маркова" УФН 194 974–993 (2024)

BibTexBibNote ® (generic)BibNote ® (RIS)MedlineRefWorks

Поступила: 25 декабря 2023, доработана: 20 февраля 2024, одобрена в печать: 27 февраля 2024

English citation: Arbekov I M, Molotkov S N “Quantum random number generators, extraction of provably random bit sequences from Markov chain trajectories” Phys. Usp. 67 919–937 (2024); DOI: 10.3367/UFNe.2024.02.039658

Список литературы (19) ↓ Статьи, ссылающиеся на эту (2) Похожие статьи (12)

Paley R, Wiener N Fourier Transforms in the Complex Domain (American Mathematical Society. Colloquium Publ.) Vol. 19 (New York: American Mathematical Society, 1934); Пер. на русск. яз., Винер Н, Пэли Р Преобразование Фурье в комплексной области (М.: Наука, 1964)
Fonda L, Ghirardi G C, Rimini A Rep. Prog. Phys. 41 587 (1978)
Молотков С Н ЖЭТФ 157 442 (2020); Molotkov S N J. Exp. Theor. Phys. 130 370 (2020)
Molotkov S N Laser Phys. Lett. 20 035202 (2023)
Арбеков И М, Молотков С Н УФН 191 651 (2021); Arbekov I M, Molotkov S N Phys. Usp. 64 617 (2021)
Rukhin A et al "A statistical test suite for random and pseudorandom number generators for cryptographic applications" NIST Special Publication 800-22, Revision 1a (Gaithersburg, MD: National Institute of Standards and Technology, 2010)
Ивченко Г И, Медведев Ю И Введение в математическую статистику (М.: Изд-во ЛКИ, 2010)
Turan M S et al "Recommendation for the entropy sources used for random bit generation" NIST Special Publication 800-90B (Gaithersburg, MD: National Institute of Standards and Technology, 2018)
Impagliazzo R, Levin L A, Luby M "Pseudo-random generation from one-way functions" STOC89: 21st Annual ACM Symp. on the Theory of Computing, Seattle, Washington, USA May 14-17, 1989 (New York: Association for Computing Machinery, 1989) p. 12
Bennett C H et al IEEE Trans. Inform. Theory 41 1915 (1995)
Бабкин В Ф Проблемы передачи информации 7 (4) 13 (1971)
Молотков С Н Письма в ЖЭТФ 105 374 (2017); Molotkov S N JETP Lett. 105 395 (2017)
Балыгин К А и др ЖЭТФ 153 879 (2018); Balygin K A et al J. Exp. Theor. Phys. 126 728 (2018)
Balygin K A et al Laser Phys. Lett. 14 125207 (2017)
Балыгин К А и др Письма в ЖЭТФ 106 451 (2017); Balygin K A et al JETP Lett. 106 470 (2017)
Blum M Combinatorica 6 97 (1986)
Zhou H "Randomness and noise in information systems" Ph.D. Thesis (Pasadena, CA: California Institute of Technology, 2013), Defended June 1, 2012
Molotkov S N Laser Phys. 32 055202 (2022)
Ore Ø Theory of Graphs (American Mathematical Society. Colloquium Publ.) Vol. 38 (Providence, RI: American Mathematical Society, 1962); Пер. на русск. яз., Оре O Теория графов (М.: Наука, 1980)