Чем лучше сжимать диски TrueCrypt под Linux и Windows ?

Возникает самый наивный вопрос о возможном протоколе:

• Алиса кладёт в «квантовую коробочку» два сообщения s и t, связанные одноразовой памятью посредством conjugate coding или незнамо чего-там внутри под капотом в этом чёрном ящике.
• Алиса посылает квантовую коробочку Бобу обычной почтой.
• Боб открывает сообщение-строку на выбор s или t и посылает от него хэш Алисе. Хэш м.б. инф.-теор. стойкий, с аутентификацией по Вегману-Картеру.
• Алиса определяет по хэшу, какое сообщение из двух открыл Боб и договаривается его использовать в кач-ве гаммы одноразового блокнота.
• Ева в этой схеме вроде как не при делах, так что сообщение-ключ для одноразового блокнота в квантовой одноразовой памяти можно посылать хоть почтой России. Сетевой квантовый канал с волокном и фотонами не нужен. Нужна обычная почта с посылками без требований доверенных курьеров.

В теоретическом плане интереснее его своместная работа по сетям Лэя-Мэсси. Ну также, как Дамгард больше всего известен по хэшам Дамгарда-Меркла.

Бобу же не нужен пароль на извлечение информации? Тогда MITM'им:

Алиса посылает квантовую коробочку Бобу обычной почтой.

А Ева осуществляет то же измерение, что и Боб мог бы, получает одну из строк (s или t). Далее она приготавлиает свой OTM, в котором одна из строк будет та, которую она получила при измерении перехваченного OTM. У Боба будет высокая вероятность получить при измерении тот же секрет, который готовила Ева (если не ещё хуже: Ева может, наверное, сделать так, чтобы Боб всегда получал именно то, что она ему закодировала, детерминистично, хотя Боб будет думать, что получает случайный результат). Соответственно, Боб полшёт обратно Алисе хэш сообщения, который Еве тоже будет известен. В итоге часть информации о ключе в ряде случаев будет утекать к Еве. Даже если предположение в скобках не может быть выполнено, и Алиса с Бобом смогут засекать наличие Евы на канале по ошибкам в нём, то чем это лучше исходного QKD, когда Алиса шлёт не OTM'ы, а кубиты с единичным битом, у которых тоже есть свойство «кто первый померил, тот и съел»? ИМХО, в таком случае это сведётся к тому, что вместо QKD на битах (кубитах) получим QKD на битовых строках (OTM'ах), а смысл будет тот же.

К тому же, на пратике обычно посылается не ящик с кубитами, а лучи света, которые Боб должен померить и вернуть потом какие-то результаты по классическому каналу. Раз это лучи света, там высоки потери и шумы. В традиционном QKD знают, как связан уровень шумов с максимально возможным влиянием Евы, а тут как делать? Выкидывать абсолютно всё, что пришло хотя бы с одной ошибкой? Так скорость вообще около нулевой может оказаться.

Тогда 128…256 ящиков с (ку)битами :) (ну, или с запасом против leakage), тогда только безопасность против перебора.

Тогда действительно хуже.

Тогда только экстрагировать конечный ключ и отказаться от инф.-теор. стойкости и OTP.

Фактически — это аналог шифрования с открытым ключом, головоломки Меркла.

Да и идея физического ящика вместо канала связи была бы интересна сама по себе.

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

Тогда 128…256 ящиков с (ку)битами :) (ну, или с запасом против leakage), тогда только безопасность против перебора.

Сообщения s и t обязаны быть неравны? Если нет, то, независимо от числа ящиков, Ева извлекает всё из ящиков Алисы и пересылает всё это Бобу в ящиках с парами идентичных сообщений. Установить факт их идентичности он ведь по условиям не может.

Ну, наверное, в ящике всё-таки не один (ку)бит, а строка кубитов s (в нашем случае с запасом на экстракцию или хэширование), инвертируя которую, нельзя получить вторую (t). В условиях сказано, что прочесть можно или s, или t. Тогда нужно 256 с запасом таких ящиков со спаренными взаимно-кодированными строками.

Есть вот такие работы, они чисто классические:

• «One-Time Programs» (Goldwasser, Kalai и Rothblum).
• «Founding Cryptography on Tamper-Proof Hardware Tokens» (Goyal, Ishai, Sahai, Venkatesan и Wadia).
• «Adaptively Secure Garbling with Applications to One-Time Programs and Secure Outsourcing» (Bellare, Hoang и Rogaway).

Считается, что у Алисы и Боба есть ящики с определёнными свойствами, которые в рамках модели нерушимы (как их создать — дело другое). Так вот, эти ребята поставили вопрос очень общо: что вообще интересного можно сделать в криптографии, обладая чёрными ящиками с такими свойствами? Оказалось, что практически всё. :-) Особенно вводная часть к «Founding» (второй работе) хорошо написана. Goldwasser на стр. 13 пишет про реализацию протоколов систем голосования, если б такие ящики существовали (см. также его обсуждение чёрных ящиков на стр. 16).

После этого аннтация к квантовой работе по созданию таких ящиков начинает играть другими красками:

Because software can, in principle, be copied, general one-time programs exists only in the hardware token model: it has been shown that any function admits a one-time program as long as we assume access to physical devices called one-time memories. Quantum information, with its well-known property of no-cloning, would, at first glance, prevent the basic copying attack for classical programs. We show that this intuition is false: one-time programs for both classical and quantum maps, based solely on quantum information, do not exist, even with computational assumptions. We complement this strong impossibility proof by an equally strong possibility result: assuming the same basic one-time memories as used for classical one-time programs, we show that every quantum map has a quantum one-time program that is secure in the universal composability framework.

Если нечто позволяет слишком много ништяков, значит, это нечто не может существовать? Интересно было бы понять CS-мораль этих басен.

Современные спекуляции на тему того, что так практичней, чем со светом пересылать:

Furthermore, by employing dynamic decoupling, a coherence time of 370 ± 60 minutes was achieved at 2 kelvin. It has been almost universally assumed that light is the best long-distance carrier for quantum information. However, the coherence time observed here is long enough that nuclear spins travelling at 9 kilometres per hour in a crystal would have a lower decoherence with distance than light in an optical fibre. This enables some very early approaches to entanglement distribution to be revisited, in particular those in which the spins are transported rather than the light.

Ну, и время когерентности уже 6 часов. Правда, при сверхнизких температурах. Пишут, что это всё для построения повторителей нужно.

В самой работе:

The extension of this work to storage and retrieval of optical states would open up the possibility of remote entanglement distribution via the physical transport of memory crystals. A particularly attractive aspect of this idea is that it would allow entanglement distribution between remote locations with minimal permanent infrastructure.

Т.е. Алиса, чтобы расшарить запутанную пару между собой и Бобом, кладёт состояния в коробочку и отсылает её Бобу почтой России. :-)

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

Это скорее форма удачного пиара. Просто на данный момент с переноской ядерных спинов научились делать лучше, чем со светом, но в перспективе всё может поменяться. Понятно, что послать луч света — это намного проще, чем таскать коробочки. Например, когда-то были очень популярны магнитные ловушки для одиночных частиц, а что теперь? Где они? Сейчас вместо них популярны, к примеру, токи в сверхпроводниках (так называемые «сверхпроводящие кубиты») или примеси в алмазах.

По поводу /comment74121.

Меня особо не впечатлило non-malleability в одноразовом блокноте, ну разве что по цифрам в квантах. Можно же просто аутентификацию Вегмана-Картера прикрутить.

Но, во первых можно и сообщение в классике сделать таким же. Я намекнул об этом в /comment74125. Итак, для сообщения размером m нужно две гаммы, одна для подстановок (обычный XOR) размером m, а другая для перестановок всех битов между собой — размером m². Итого, на обе одноразовые гаммы — m³. Для экономии гаммы при больших m сообщение можно разбить на блоки (их даже не надо между собой сцеплять, они рэндомизированные и одноразовые). Зная сообщение, противник не сможет вычислить гамму: подстановка и перестановка не образуют между собой группу. Легко подделать сообщение тоже не получится. Изменение одного бита в шифртексте приведёт к изменению одного бита в открытом тексте, но в непредсказуемом месте. Это конечно не полноценная non-malleability, но там наверное можно что-то классическое сверху прикрутить, наподобие AONT.

Теперь чуть менее тривиальная идея про IT-secure AONT. Упоминалась конструкция японцев. Её IT-стойкий вариант непрактичен, там сильно растёт размер сообщения. Но она ведь IT-стойкая? Обработаем ей сообщение M' = IT-AONT (M). Отрежем от M' 256 бит виде m₀, так что M' = m₀ ║ m₁. Теперь m₀ можно передать по IT-стойкому каналу (например квантовому), а m₁ — по открытому. Ну по квантовому каналу что-то произвольное передать нельзя, можно просто согласовать 256 бит, которые поксорить с m₀ и гнать это уже по открытому. Т.е. мы разменяли гамму крошечного размера на гигантский размер шифртекста. Представляете какие перспективы, с учётом того, что IT-стойкие каналы малопропускные и дорогие, а открытые каналы позволяют дёшево гнать данные с любым оверхэдом?

Тут возникает вопрос, что это какой-то информационный вечный двигатель. Так можно гамму одноразового блокнота любой длины уложить в 256 бит, что является полным абсурдом. Но тут нет никакого противоречия — так и надо делать! Просто это не явлется ни одноразовым блокнотом, ни IT-стойкой безопасностью. Это является строгой вычислительной безопасностью: противник должен подобрать 256 бит именно методом перебора и никаких других методов криптоанализа гарантированно не существует. У нас гарантированно стойкий идеальный потоковый шифр. К нему можно сбрутфорсить короткий ключ, но сокращённых методов криптоанализа быть не может — их существование противоречит IT-стойкой безопасности, они должны идти против теории информации (если абстракции нигде не протекают). Если передавать гамму размером m³, как в начальном примере, то можно соорудить и идеальный блочный шифр на таких IT-подпорках, только он никому нафиг не нужен. Хотя может для каких-то протоколов или для полутеоретических моделей и сгодится.

Теперь, казалось бы, причём тут Беннет, Реннер и кто там ещё был?

Они вам пытались объяснить, что:



Ну я вот это понял и показал на классическом примере, здесь чистая теория информация, квантЫ — это уже тонкости реализации, есть же совсем общие, фундаментальные принципы сохранения информации.


Я так понял, что они намекнули на возможности IT-стойких подпорок для построения доказуемой вычислительно-стойкой криптографии. Там ещё должен быть нюанс: с помощью 256 бит можно передать естественно только один классический OTP по классическому каналу за один сеанс, раздувая его до соответствующего размера через IT-AONT. Один короткий ключ не может повторяться, иначе стойкость всей схемы рухнет. И даже для ключа 256 бит из-за неидеальности всей схемы есть какой-то зазор, хорошо если только в один бит и неизвестно как он может меняться от размера m.

Но согласование OTR через IT-AONT с согласованием маленького кусочка по квантовому каналу и большого OTR по классическому — это уже частности. Можно и сами сообщения сразу гнать через IT-AONT. Большой OTR — это уже так, про запас, когда IT-стойкий канал редко доступен.

Я не понял, как у вас получилось, что количество перестановок всех битов сообщения m — это m².


Information locking позволяет делать то же самое, насколько я помню, но там вместо классической гаммы надо пересылать квантовые состояния, да. По-моему, это как-то даже пытались доразвить до уровня чего-то типа QKD (quantum enigma machines с Ллойдом, я кидал ссылку).


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


Почему не нужен?


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


Вроде я раньше уже писал пост на эту тему, но путаница остаётся. Более того, она прорастает во внутренний сленг, когда говорят одно, а подразумевают другое. Вы тут всё очень правильно терминологически сказали, но я сам часто ошибался, называя безусловную вычислительно стойкую безопасность IT-стойкой, хотя это разные вещи. Я бы сказал так: безопасность есть условная и безусловная (вопрос доказанности предположений); она бывает IT-стойкой и вычислительно стойкой (вопрос наличия ограничений на ресурсы атакующего). Понятно, что всего будет 4 варианта, а вопрос ставился о возможности создать квантовыми средствами безусловную вычислительную стойкость. Я мог использовать неправильные термины в разговоре, но я достаточно ясно изложил идею, что я хочу, так что, думаю, Реннер меня понял правильно.

Про AONT и ERF мне трудно прокомментировать. Я ещё тогда не въехал в тему (как и в Вегмана-Картера). Надо читать и осмыслять работы. Мне это кажется интересным, но некоторые работы по этой теме, на которые вы указывали, не внушают доверия. То ли это просто работы такие, то ли всё направление мутное. Мне порой кажется, что AONT — это такой вечный двигатель, который не может существовать (ну, по крайней мере, идеальный AONT). По ERF, правда, вроде было много работ от серьёзных людей.

Всё возможное количество перестановок — m!. Задание одной перестановки — m². Да, у меня калькулятор глючит, циферки плохо копируются, уже разбирали в /comment89669: m⋅2^m. Можно чуть короче — через номер перестановки в факториальной системе счисления, но это незначительная оптимизация через усложнение. В общем, ракета упала на старте две гаммы, чтобы вторая с перестановками — ничего реалистичного не выйдет.

А может и банально. Может это тупик, который исследовали и от которого негласно отказались.

Нет. Здесь другое:

1. По выводу японцев: если я правильно понял, то Unconditionaly Secure AONT увеличивает размер сообщения в 65535 раз.
2. Из-за отсутствия реального non-malleability нет стойкости к подобранному/известному открытому тексту. Это можно решить наворачиванием аутентификации Картера-Вегмана или даже с помощью какой-то нелинейной перестановки поверх, но это надо разбирать.
3. Полноценный блочный шифр не получится из-за п.-п. 1 — 2.
4. Из-за п.-п. 2 — 3 можно разве что передавать одноразовую гамму, вычислительно безусловно стойко залоченную коротким ключом. Или сразу само сообщение? Может зависеть от свойств IT-канала, но гамму — точно.
5. Нужна пара каналов: IT-стойкий (можно согласование 256-бит по QKD) и открытый.

Оно как бы слишком амбициозно и требует множества неочевидных доказательств мелких тонкостей (например, 256-битный ключ может обеспечивать не 256-бит безусловной вычислительной безопасности, а, скажем, на пару бит меньше из-за каких-то протечек и зазоров), но сходу не опровергается. Так что — в идеале да. Есть шанс именно раз и навсегда доказать, что протокол связи ломается только брутфорсом, если IT-канал действительно обеспечивает IT-стойкость.

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

Я тоже напутал: согласованную таким путём гамму нельзя называть OTP. Здесь ещё два варианта:

1. Через эти два канала гонится само сообщение IT-secure AONT(M).
2. Через эти два канала согласовывается безусловно вычислительно-стойкая гамма в виде IT-Secure AONT(R) для последующего R ⊕ M.

В обоих случаях — это не OTP. Здесь может даже нужно очень аккуратно вводить свою терминологию.

Там их больше и терминология плавает. Я даже зачем-то когда-то поместил это в FAQ, но подозреваю, что зря — непроработано и слишком отвлечённо.

Это примитивщина, поэтому я и японцам доверяю не в плане результатов, а в плане того, что это простая вещь, которую легко проверить. Их IT-secure AONT — это вариант IT-стойкого разделения секрета по Шамиру, которое известно с 70-хх годов. Ну ещё теория кодов там на это завязана. Да и они не первые — они оптимизировали IT-secure AONT Стинсона и показали якобы, что их вариант оптимален и является близким приближением к теоретическому пределу. Но поскольку цель их работы — не IT-secure AONT, а вычислительный, то IT-secure вариант рассмотрен мало.

Я не могу это распарсить. Какой там реально рост размера в итоге?

Unfortunately, Theorem 1 means that an unconditionally secure AONT is not practical. Let us consider the following example. Suppose that the total size of message blocks is 1 MBytes (= 8388608 bits). When the size of m_i is 128 bits, the number of blocks, s is 65536, and the total size of pseudo-message blocks is 65536 MBytes. When the size of m_i, is 2048 bits, the total size of pseudo-message blocks is 4096 MBytes.

К сожалению, из Теоремы 1 следует непрактичность безусловно стойкого AONT. Давайте рассмотрим такой пример. Предположим, что общий размер блоков сообщения составляет 1 МБ (т.е. 8388608 бит). Если размер m_i — 128 бит, количество блоков s будет составлять 65536, а общий размер блоков псевдо-сообщения — 65536 МБ. Если же размер m_i составляет 2048 бит, то размер блоков псевдо-сообщения будет 4096 МБ.

ЯННП, но, вероятно, потому, что саму работу не читал.

8388608 бит = 2²³, 65536 = 2¹⁶. У них там нет общей формулы, может там с увеличением длины сообщения растёт всё сразу: и размер блоков, и их количество, и показатель степени. А алгоритм я не разобрал, чтобы вывести это самостоятельно. Смотрю только пример. Но если слать не сообщение, а одноразовую гамму блоками по 1MБ, то можно ориентироваться на этот пример. Тогда на каждые 1MБ гаммы надо новое пересогласование ключа в 256 бит. Может есть какой-то оптимум, но по этому примеру вот такой вот компромиссный размен IT-стойкости на безусловную одноразовую вычислительную. Т.е. 256 бит позволяют зашифровать стойко 1МБ, без учёта накладных расходов на аутентификацию и за счёт передачи 65535 МБ по классическому каналу.

Вся идея может не иметь никакой ценности, если существуют другие, более признанные, более правильные, возможно более оптимальные протоколы преобразования Unconditionaly IT-Secure → Unconditionaly Computational Secure. И даже все оптимумы чудес не творят и перекладывают слишком много нагрузки на классический канал.

В реальности, если есть QKD-линия м.б. приемлемее и проще менять на каждый мегабайт AES-ключ и не заморачиваться доказательностью решения. Ну это как вместо правильных экстракторов «взять всё и похэшировать» обычным SHA.

Навскидку, m > n. Передаём по открытому каналу R размером m у которого заксорено общим секретом k 256 бит после согласования в IT-канале. Ещё 256 бит — на аутентификацию самого R. Затем некоей функцией (экстрактором?) преобразуем R_m → R_n и это используем как одноразовую гамму, размером n > 256 бит. В отличие от обычного симметричного крипто все зазоры можно информационно-стойко посчитать и исключить сокращённые варианты криптоанализа.

Вариант {IT-secure-AONT (R) ⊕ k ║ R ⊕ M} требует очевидно в два раза больше расхода на классический канал, чем сразу {IT-secure-AONT (M) ⊕ k}. Вариант с экстрактором m → n {R_m ⊕ k ║ R_n ⊕ M} — вообще неочевиден по оптимальности. Вот если собрать все варианты, посчитать оптимизации и убедиться, что это так и есть, то какая-то новизна работы может и будет. И то, не уверен.

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