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