Метод получения случайных чисел

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

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

Профессор компьютерных наук David Zuckerman и аспирант Eshan Chattopadhyay представили исследование об их методике в июне 2015 года на ежегодном симпозиуме по теории вычислений (STOC), ведущей конференции теоретических компьютерных наук Ассоциации вычислительной техники. Приглашение выступить на конференции было основано на строгом процессе рецензирования, чтобы оценить правильность и значимость работы. Их статья станет одной из трех, получивших награду STOC за лучшую работу.

«Это проблема, к которой я возвращался снова и снова более 20 лет», - говорит Zuckerman. «Я очень рад, что решил это».

Chattopadhyay и Zuckerman публично выпустили черновой документ, описывающий их метод создания случайных чисел на онлайн-форуме в 2015 году (eccc.hpi-web.de/report/2015/119/). В области, более привычной к небольшим, постепенным улучшениям, сообщество компьютерных наук приветствовало этот метод, предполагая, что по сравнению с более ранними методами этот метод впереди световых лет. Oded Goldreich, профессор компьютерных наук в Институте науки им. Weizmann в Израиле, отметил, что даже если бы это было лишь умеренное улучшение по сравнению с существующими методами, это оправдало бы «вечеринку на всю ночь».

«Когда я услышал об этом, я не мог уснуть», - говорит Yael Kalai, старший научный сотрудник, работающий в области криптографии в Microsoft Research New England, который также занимался извлечением случайных чисел. «Я был так взволнован. Я не мог в это поверить. Я побежал в (онлайн) архив, чтобы посмотреть на газету. Это действительно шедевр».

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

Новое исследование, кажется, бросает вызов этой старой пословице в компьютерном программировании, «Мусор в мусоре». Фактически, это последнее, самое мощное дополнение к классу методов, которые Zuckerman впервые в 1990-х годах назвал экстракторами случайности.

Предыдущие версии экстракторов случайности были менее практичными, потому что они либо требовали, чтобы одна из двух исходных последовательностей была действительно случайной (что представляет собой проблему с курицей или яйцом), либо чтобы обе исходные последовательности были близки к действительно случайным. Этот новый метод обходит оба эти ограничения и позволяет использовать две последовательности, которые являются лишь слабо случайными.

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

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

«Один из распространенных способов неправильного использования шифрования - это не использовать случайность высокого качества», - говорит Zuckerman. «Так что в этом смысле наши методы могут повысить безопасность, упрощая получение качественной случайности».

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

Веб-сайт, на котором Zuckerman и Chattopadhyay опубликовали свой проект в 2015 году, который называется «Электронный коллоквиум по вычислительной сложности», позволяет исследователям делиться своей работой и получать отзывы до публикации окончательных версий в журналах или на конференциях. Компьютерные ученые и математики внимательно изучают статью, вносят предложения и даже расширяют метод, чтобы сделать его более мощным.

Использованные источники

1. Avishay Tal. Tight bounds on the Fourier spectrum of AC 0. Electronic Colloquium on Computational Complexity (ECCC), 21:174, 2014.

2. Luca Trevisan. Extractors and pseudorandom generators. Journal of the ACM, pages 860–879, 2001.

3. Emanuele Viola. Extractors for circuit sources. SIAM J. Comput., 43(2):655–672, 2014.

4. Xin Li. Extractors for a constant number of independent sources with polylogarithmic min-entropy. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, pages 100–109, 2013.

5. Eshan Chattopadhyay, David Zuckerman. Explicit Two-Source Extractors and Resilient Functions. Electronic Colloquium on Computational Complexity, Report No. 119 (2015)

6. Eshan Chattopadhyay, Vipul Goyal, and Xin Li. Non-malleable extractors and codes, with their many tampered extensions. CoRR, abs/1505.00107, 2015.
   

7. Gil Cohen. Local correlation breakers and applications to three-source extractors and mergers, 2015. To appear in FOCS 2015.

8. Gil Cohen. Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs. Electronic Colloquium on Computational Complexity (ECCC), 2015.

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

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