Новый метод создает действительно случайные числа с меньшими вычислительными затратами, чем другие методы, что может обеспечить значительно более высокий уровень безопасности для всего, от транзакций с потребительскими кредитными картами до военной связи.Профессор информатики Дэвид Цукерман и аспирант Эшан Чаттопадхьяй представят исследование своего метода в июне на ежегодном симпозиуме по теории вычислений (STOC), главной теоретической конференции по информатике Ассоциации вычислительной техники. Приглашение выступить на конференции основано на строгом процессе экспертной оценки для оценки правильности и значимости работы.
Их статья станет одной из трех, получивших награду STOC Best Paper Award.«Это проблема, к которой я возвращался снова и снова на протяжении более 20 лет», — говорит Цукерман. «Я очень рад, что решил эту проблему».Чаттопадхай и Цукерман публично опубликовали черновой вариант документа, описывающий свой метод создания случайных чисел, на онлайн-форуме в прошлом году (http://eccc.hpi-web.de/report/2015/119/).
В области, более привыкшей к небольшим, постепенным улучшениям, сообщество компьютерных наук приветствовало этот метод, предполагая, что, по сравнению с более ранними методами, этот метод на световые годы впереди. Одед Гольдрайх, профессор информатики из Института науки Вейцмана в Израиле, заметил, что даже если бы это было лишь умеренное улучшение существующих методов, это оправдало бы «вечеринку на всю ночь».
«Когда я услышал об этом, я не мог заснуть», — говорит Яэль Калаи, старший научный сотрудник, работающий в области криптографии в Microsoft Research New England, которая также занималась извлечением случайности. «Я был так взволнован. Я не мог в это поверить.
Я побежал в (онлайн) архив, чтобы посмотреть газету. Это действительно шедевр».
Новый метод берет две слабо случайные последовательности чисел и превращает их в одну последовательность истинно случайных чисел. Слабо случайные последовательности, такие как температура воздуха и цены на фондовом рынке, выбранные во времени, имеют предсказуемые закономерности.
В истинно случайных последовательностях нет ничего предсказуемого, как в случае подбрасывания монеты.Новое исследование, похоже, опровергает старую пословицу компьютерного программирования: «Мусор на входе, мусор на выходе».
Фактически, это последнее и самое мощное дополнение к классу методов, впервые разработанных Цукерманом в 1990-х годах, которые называются экстракторами случайности.Предыдущие версии экстракторов случайности были менее практичными, потому что либо требовали, чтобы одна из двух исходных последовательностей была действительно случайной (что представляет проблему с курицей или яйцом), либо чтобы обе исходные последовательности были близки к действительно случайным. Этот новый метод обходит оба этих ограничения и позволяет использовать две последовательности, которые лишь слабо случайны.
Важное применение случайных чисел — создание ключей для шифрования данных, которые хакерам сложно взломать. Шифрование данных имеет решающее значение для безопасных покупок по кредитным картам и банковских транзакций, сохранения конфиденциальности личных медицинских данных и защиты военных сообщений от врагов, а также для многих практических приложений.
Цукерман говорит, что, хотя уже существуют методы получения случайных чисел высокого качества, они требуют очень больших вычислительных затрат. Его метод позволяет получить более качественную случайность с меньшими усилиями.
«Один из распространенных способов злоупотребления шифрованием — отказ от высококачественной случайности», — говорит Цукерман. «В этом смысле, упрощая получение высококачественной случайности, наши методы могут повысить безопасность».В их статье показано, как сгенерировать только одно действительно случайное число — сродни одному подбрасыванию монеты — но бывший ученик Цукермана Синь Ли уже продемонстрировал, как расширить его, чтобы создать последовательности из гораздо большего числа случайных чисел.
Веб-сайт, на котором Цукерман и Чаттопадхай опубликовали свой проект прошлым летом, называемый Электронным коллоквиумом по вычислительной сложности, позволяет исследователям делиться своей работой и получать отзывы перед публикацией окончательных версий в журналах или на конференциях. Ученые-информатики и математики внимательно изучали статью, предлагали предложения и даже расширяли метод, чтобы сделать его более мощным.