id: Гость   вход   регистрация
текущее время 09:59 29/03/2024
Автор темы: spinore, тема открыта 12/03/2012 07:38 Печать
http://www.pgpru.com/Форум/Криптография/ВопросыПоКвантовымКаналамИхМоделированиеИПрименение
создать
просмотр
ссылки

Вопросы по квантовым каналам, их моделирование и применение


Начало взято отсюда.


Я ненадёжный товарищ, могу притянуть к тематике сайта почти любой оффтопик :)


Классическая теория информации



Можно сказать, что в общих чертах это верно, и с тех пор ничего не изменилось. Может быть, там не очень понятно написано, но задача в целом предельно ясная. Если у Алисы и Боба есть наборы битов, с какими-то распределениями (у Алисы случайная величина X, у Боба — Y), то считается, что информация, доступная им обоим, вычисляется как взаимная информация между X и Y. Также, взаимная информация — идеальная мера наличия корреляций между ними. Соответственно, если не канале сидит Ева и имеет свою случайную величину Z, то доступная ей информация Алисы, опять же, вычисляется, как взаимная информация между Евой и Алисой (аналогично для случая Алисы и Боба). Если речь идёт не о дискретных распределениях, а о непрерывных, концептуально ничего в этих определениях не меняется. На практике при работе с непрерывными переменными делают какую-то там дискретизацию, а теория рассматривает идеальную модель. Если посмотреть, как формально определяют анонимность, то там опять же будет использоваться взаимная информация (для простоты иногда назвают энтропией):


энтропия описывает информацию (измеренную в битах), содержащуюся в вероятностном распределении, которое описывает связь между множеством субъектов (анонимным множеством) и элементами интересов. В [172] энтропию предлагается рассматривать как меру эффективности размера множества анонимности. Если энтропия нормализована по максимуму, который может обеспечить система (если она совершенна и не даёт утечки информации) для заданного числа пользователей, мы получаем степень анонимности [57], которая даёт меру производительности предоставляемой анонимности.

Вот, мы имеем такую фундаментальную величину — взаимную информацию. Это понятие родом из давно известной классической теории информации. Если Алиса передаёт информацию Бобу по какому-то каналу, то, находя максимально достижимую взаимную информацию между ними (что, естественно, требует задать правила кодирования информации и её извлечения), мы получим пропускную способность классического канала. В английском её называют «capacity», потому слово-паразит «ёмкость канала» стало употребляться наряду с правильным исходным термином «пропускная способность». Шеннон доказал теоремы кодирования, после чего понятие пропускной способности приобрело математическую основу, а не спекулятивную. Конечно, с идеальными каналами всё просто, а вот задача вычислить пропускную способность для канала с шумом, где Боб получает не совсем то, что шлёт Алиса, довольно трудная. В классической теории информации до сих пор решают такие задачи, до сих пор есть куча классических каналов, для которых пропускные способности неизвестны (я плохо представляю теории информацию (ТИ) в целом, классическую ТИ по книгам никогда не изучал, знания обрывочны, но вроде бы я верно передаю суть проблемы). Классические каналы активно используются для передачи информации в куче реальных приборов, потому задача вычисления пропускной способности нужная и вполне инженерная.


Квантовая теория информации


Если же предположить, что у Алисы и Боба не случайные величины с какими-то битами или непрерывные классические распределения, но квантовые состояния, в которые закодирована какая-то информация, то, опять же, можно поставить вопрос: чему равна та информация, которая есть у них обоих одновременно, если квантовые состояния разные? Тут теорема кодирования Шеннона не работает, и требуется ввести её квантовый аналог. Этим аналогом является теорема кодирования Холево3, где роль взаимной информации играет так называемая «граница (bound) Холево» или «информация Холево». Конечно, в обычной речи никто не произносит эти длинные определения, потому на сленге это звучит как «надо сосчитать/найти/вычислить/оценить Холево». Ну, все так говорят, не только русские. В полной аналогии с классической теорией информации пропускная способность квантового канала задаётся максимумом Холево :) А если у нас сидит на канале Ева и снифает, надо оценить Холево между Евой и Алисой, или между Евой и Бобом, что даёт так называемую «private capacity».


Важный момент состоит в том, что граница Холево — теоретический предел. Как его достичь для конкретного типа канала — совершенно не ясно, потому делают следующее: задаются каким-то типом/методом кодирования информации и типом измерения квантовых состояний, извлекающим информацию. Соответственно, взаимная информация (в вполне классическом смысле) между закодированной и измеренной (классической) переменной задаёт (удачного русского термина не знаю) так называемый «rate» — пропускную способность канала при определённых предположениях на метод кодирования и извлечения. Например, для случая непрерывных переменных можно измерять либо магнитную составляющую фотона, либо электрическую, либо обе их вместе, но с ограничениями на точность (в смысле POVM)4, причём и то и то сравнительно легко реализуется на эксперименте. Совместное измерение называется «гетеродинным», а измерение какой-то одной компоненты (она называется «квадратурой поля») — «гомодинным». Применяя эти методы измерения на стороне Боба, можно найти, к примеру, гетеродинный и гомодинный «рейты».


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


До сего момента речь шла о так называемой «классической информации»: хоть для классического, хоть для квантового канала, т.е. о числе классических бит, общих между общающимися сторонами. Но Алиса может пересылать Бобу не биты, а сами состояния квантовых частиц — «телепортировать» их: уничтожать у себя, воскрешая на стороне Боба. Здесь, опять же, нет ничего сложного: есть стандартная схема квантовой телепортации, требующая дополнительный классический канал, по которому Алиса сообщит т состояние, которое было у Алисы изначально. По аналогии такой тип информации называют «квантовым», а то, сколько квантовых состояний Алиса успевает телепортировать Бобу, определяет «квантовую пропускную способность квантового канала» («quantum capacity»). Последняя выражается через так называемую «когерентную информацию».


Квантовое распределение ключа


Теперь о грустном: несмотря на то, что классическая пропускная способность квантового канала — некая фундаментальная величина, интересная с точки зрения абстрактной математики, с практической точки зрения она сейчас никому не интересна и не имеет никаких непосредственных приложений, даже в рамках QKD. Просто сама идея пересылать с квантовыми состояниями информацию может работать, только, раз она сама по себе не обеспечивает никакой ни безопасности, ни высокой пропускной способности, она остаётся никому не нужной.


QKD — очень сложный протокол, но с точки зрения пропускной способности он наоборот очень прост. Для начала, каждый QKD протокол подразумевает фиксированный набор сигнальных состояний (выбор определённых поляризаций или определённых гауссовых состояний), а секретность строится на том, что Ева не знает когда какое из сигнальных состояний Алиса посылает Бобу (но знает каков класс этих состояний, т.е. во что кодируется информация). Поскольку класс используемых в протоколе состояний очень ограниченный, нет смысла говорить о пропускной способности — достаточно посчитать рейты. И даже считая рейты, оказывается, что не надо их оптимизировать по всевозможным сигнальным состояниям и кодированиям — достаточно подставить фиксированные состояния в известную формулу (других в протоколе нет) и потом получить скорость выбработки ключа. Вот собственно поэтому ни максимально передаваемая информация в смысле рейтов, ни классическая пропускная способность не оказываются интересными (а это именно то, что я вычислял). Что интересно, в задаче о QKD трудных оптимизационных проблем такого рода не возникает вообще, в отличие от задачи вычисления пропускной способности. Есть мысли, что, может быть, где-то как-то можно придумать схему более эффективной атаки Евы, что-то сделать новое относительно известного в QKD, как-то применить к QKD наши результаты, но пока успеха нет. Конечно, при подаче всяких грантов наша тема активно пиарится, как имеющая самое непосредственное отношение к QKD, которое «уже есть и работает», и является самой близкой к нам задачей из всех, интересных индустрии, только вот реальность несколько сложнее :(


Есть и другие мысли: допустим, нас интересует не защищённая передача информации, а надёжная. Тогда, пользуясь предварительно распределёнными между Алисой и Бобом запутанными ЭПР-парами частиц и имея обычный классический канал передачи между Алисой и Бобом, можно попытаться сделать передачу информации более помехоустойчивой, чем просто по одному классическому каналу, как это делается в классической теории информации. Но разработать такой протокол и доказать, что он действительно даёт профит — не просто. В общем, если бы что-то такое получилось, здесь, вероятно, наши наработки нашли бы применение. И безопасность с криптографией оказались бы тут ни при чём :)


Квантовые каналы


Теперь немного возвращаясь к статье: в гауссовых каналах передаются гауссовы функции/распределения. На плоскости квадратур
( q, p ) это такие поверхности-шапочки. Сечение такой шапочки параллельно плоскости квадратур даст эллипс. То, насколько далёк центр эллипса от начала координат, определяет комплексное число α, иногда называемое «амплиудой когерентного состояния» |α〉. Когда гауссово состояние проходит через канал, исходных эллипс Алисы как-то искажается, но остаётся эллипсом. При прохождении через «lossy-канал» (канал с затуханием амплитуды?) происходит уменьшение параметра α, что соответствует потери энергии. При этом центр как посылаемого эллипса, так и полученного Бобом, лежат на одной прямой, проходящей через начало координат. Величину уменьшения амплитуды модулируют проницаемостью η ∈ [0,1].


Модель lossy-канала такова: имеется светоделитель (стеклянная призма), на одну грань посылает луч Алиса, на другую — Ева. Их лучи (квантовые состояния) взаимодействуют, а на выходе получается то, что имеет Боб. Такой системой моделируют передачу сигнала по волокну (проницаемость η связан с длиной оптоволокна). В QKD в непрерывных переменных взаимодействие Евы с системой тоже описывают через lossy-канал. У эллипса Евы есть есть эксцентриситет (степень асимметрии) — его обозначают через s и называют степенью сжатия («squeezing») в середе канала (Ева — это и есть среда). А то, насколько широк эллипс по обоим своим главным осям (добавка к величие обеих осей) определяют «тепловые фотоны» Nenv (тут должен быть EuScript-шрифт LaTeX'а для N). Энергию же на входе в канал обозначают как N.


По классификации Холево есть, кажется, 6(?) канонических типов гауссовых квантовых каналов, но в качестве релевантных эксперименту моделей удобно выделить следуюшие три типа: помимо lossy есть «additive noise»-канал (канал с аддитивным классическим шумом), который просто увеличивает параметр Nenv; и «amplification channel» — такой же как lossy, но вместо уменьшения увеличивает α (η > 1), при этом неминуемо растут и тепловые фотоны. Операция, позволяющая увеличить α при как можно меньшем увеличении тепловых фотонов, называется бесшумным усилителем («noiseless amplifier»). Предполагается, что новые протоколы QKD в непрерывных переменных с использованием «бесшумного усилителя» позволят увеличить дистанцию передачи информации (у нас эту тему разрабатывают).


Пропускная способность гауссова lossy-канала математически оказывается функций 4ёх переменных: C = C(s,η,N,Nenv). На то, чтобы аналитически и численно исследовать эту функцию (она — результат оптимизации, зависит от решения трансцендентного уравнения, т.е. очень неявная), расклассифицировать все случаи, найти характерные критические и «суперкритические» параметры и ушли последние годы. Как видите, всё просто, всё можно объяснить на пальцах. Что касается зависимости от параметров, то тоже всё просто: при росте входной энергии только увеличивается пропускная способность, т.к. это — увеличение отношения сигнала к шуму (что вполне физично). На самом деле, C(N) монотонно растёт и выпукло вверх. Аналогично, чем выше проницаемость, тем большая доля сигнала Алисы доходит до Боба, потому C(η) тоже растёт. Телоповой шум в среде (Nenv) — это именно что шум в его классичнском понимании, он делает передачу информации только хуже, потому C(Nenv) только убывает (реально убывает монотонно и выпукло вниз). И остаётся только один параметр — сжатие s, характеризующее асимметрию между квадратурами в среде. Вот с ним беда: C(s) может иметь локальный максимум, или локальный максимум и минимум, или быть монотонной. Между всеми этими режимами есть переходы, вот я их и оценивал/классифицировал.


Из-за этой немонотонности в многомодовом канале сразу же появляется неаддитивность по среде: раз C(s) имеет максимум, то при фиксированной энергии на все моды канала иногда нужно куда-то загнать излишнюю энергию. Из-за этого возникает «мусорная мода», а оптимальное распределение энергии в среде по модам иногда становится неоднородным. Сейчас стоит задача: найти, когда распределение однородно, а когда нет (получить, что возможно, аналитически).


Смежные задачи


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



Вижу, что тренд постить в /forum/kriptografija топики «помогите решить задачу плииз» стал последнее время очень модным :) потому я решил не отставать от общества. Извините.


Интересно отметить, что, прийдя на этот сайт 6 лет назад, я был убеждён, что крипто останется в рамках хобби и развлечений. А теперь информация, почерпнутая отсюда, внезапно оказывается очень полезной и во вполне научных проектах: обоснование их стало более лучше проще писать pgpu.com помогают очень хорошо, т.к. знаешь, что бы хотели услышать классические криптографы :)


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


Разный оффтопик



Ага, вижу. Странно только, что в базе ISI (apps.webofknowledge.com — доступно только при подписке) её почему-то нет. У нас в теме что-то аналогичное тоже есть: Беннет и Шор, «Quantum information theory» (жаль, нигде не смог найти её в свободном доступе). Последнее время редакторами секций квантовой теории информации там были Андреас Винтер, потом Патрик Хайден и сейчас Александр Холево. Поглядел на их статистику: у Винтера там 17 работ, процитированных, соответственно, 0, 1, 4, 19, 8, 9, 11, 8, 4, 12, 20, 54, 29, 5, 36, 18 и 65 раз. У Хайдена (он курировал нашу работу) — 6 статей, процитированных 0, 3, 13, 4, 12 и 54 раз (как правило 0 означает «только что опубликованные»). У Холево там 2 работы: одна процитирована 8 (конференционная статья), а другая 372 раза. У Беннета 6 работ, процитированных 54, 44, 120, 193, 117 и 435 раз. У Питера Шора — 8, процитированных 0, 1, 11, 54, 120, 193, 348 и 11 раз. Его статья по решению задачи факторизации «Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer» опубликована в другом журнале и процитирована 1279 раз. Работа Эль Гамаля «A public key cryptosystem and a signature scheme based on discrete logarithms» (1985) — опубликована там же, в IEEE Tr. Inf. Theor., и процитирована 1492 раза. Текущий Publishing editor журнала имеет в нём всего 4 статьи.


Для сравнения: один из самых сильных результатов в нашей области (Хастингс, 2009 год, Nature Physics) — контрпример, показывающий, что отсутствие памяти в квантовом канале не влечёт за собой его аддитивность — был процитирован 71 раз. Впрочем, все продолжают верить, что в неизвращённых каналах, типа гауссовских, аддитивность (по входной энергии) всё же соблюдается, хотя сей факт не доказан даже в предположении, что гауссовы состояния оптимальны для гауссова квантового канала6. Кстати, эта оптимальность — одна из «hard problem», над которой уже много лет бьётся куча коллективов по всему миру. У нас показали эквивалентность этой задачи некоторой другой. Ранее были ошибочные доказательства7, даже от вполне крупных деятелей.



Наверное, эту (Phys Rev A, 2008). После неё ещё была другая (New J. Phys., 2009), куда меня, я считаю, тупо вписали, т.к. непосредственно моих результатов там нет, но я всё же оказывал существенную консультационную поддержку и задал направление «куда копать». Там глубже исследовалось то, что было найдено (практически случайно) в первой работе. По ISI PRA-статья процитирована 12 раз, NJP — 8. Самоцитирования в ISI по умолчанию учитываются, а автоматически исключить так называемые «ring citations» вообще нет возможности. NJP (английское издательство, не американское) — интересный подход к науке: на бумаге не печатается (только в интернете); импакт-фактор выше, чем у PRA; публикации платны (около тысячи евро за статью — естественно, отбиваются за счёт грантов), но свободны для скачивания всеми.



Кстати, не знал, что автор keccak на марше, первым соавтором :) «Reconciliation of a quantum-distributed Gaussian key» (arXiv, 35 цитирований по ISI).



В IEEE Tr. Inf. Theor. та же ситуация. Быстрее, чем за 2 года, как правило, опубликоваться там не получается, а для современной науки это длительный срок (в PRA в норме уходит не более полугода, обычно меньше, год — это уже очень долго считается). У нас вообще 3 года ушло, из которых год редактор ждал рецензии от оппонентов (по их правилам крайний срок — 4 месяца), потом полтора года мы тянули с ответом оппонентам, тщательно перерабатывая статью и увеличивая её с 8ми до 39 страниц. На новый год получили подарочное сообщение о принятии (я так понял, посмотрев на весь этот ужас, редактор решил от оппонентов ответа не ждать, а просто согласиться), и вот ещё пол года она будет стоять в списке очереди на публикацию. Понятно, что из-за таких задержек рисковать стоит, только если есть существенная уверенность в том, что статья будет принята. Холево, текущий редактор IEEE Tr. Inf. Theor., говорит, что вообще не понятно, что делать: рецензентам посылаешь статью, а они не отвечают, и никаких средств давления/принуждения нет, поскольку оппонирование статьи — добровольный и неоплачиваемый процесс, даже в таких журналах.


В плане других журналов всё тоже не очень: PRA — рядовой, для средних результатов, процент трэша там неимоверно велик, а народ жалуется (в том числе из других областей), что уровень реферирования там сильно пал. Некоторые шустрые деятели способны выдавать пустые статьи в PRA буквально ежемесячно. NJP лишь немного получше, но имеет те же проблемы, и он платный. PRL (Physical Review Letters) пока всем хорош, кроме одного: там жёсткое ограничение в 4 страницы, и большинство результатов на них даже сжато не изложить — у меня один ввод системы обозначений и переменных 4 страницы занял :( Rev Mod Phys — только для ревью, а не для оригинальных результатов, а так всем хорош. В журналы типа J. of Phys. A и Theor. Mat. Phys. слать можно, но аудитория там не сравнимая с PRA, да и импакт-факторы у них не очень. Всякие совсем профильные журналы, типа J. of. Quant. Inf., имеют вообще низкий фактор, и на них в университетах часто не оформлена подписка (на Physical Review, для сравнения, подписаны почти все), хотя при существовании arXiv'а это уже не проблема. Есть, конечно, и совсем крутые журналы, типа Nature Physics, но для обычных смертных это вообще за гранью достижимого, особенно по теории там опубликоваться (хотя есть прецеденты, когда публикуют там даже результаты своих PhD). Единственный результат в нашей узкой области, наверное, который туда удалось бы пропихнуть — доказательство «Gaussian conjecture», про которое выше написал. Вот так и получается: жуналов много, а опубликоваться негде (журналы либо слишком хорошие для рядовых статей, либо ниже порога отсечения шлака). Если вокруг сидят куча Эль Нашей со статьями, живущими по r-стратегии, а ты живёшь по k-стратегии, конкурировать трудно: обойдут по всем показателям. Ну не писать же в журнал «не публикуйте фигню от таких-то людей», в конце концов. За счёт тонкой границы между тем, что является якобы существенной новизной и ранее известными вещами можно массово пропихивать пустые статьи, а низкий уровень оппонирования, который в частности объясняется дифференциацией и разрастанием науки, этому только способствует.


Конференции тоже катятся вниз: появилось такое понятие, как «junk conferences». И если журналы хоть как-то прижучить можно, то с конференций вообще спрос никакой — это просто бизнес, где обычные участники платят fee, с которых оплачивается карман организаторов и приезд так называемых «приглашённых докладчиков». Чтобы послушать последних, обычные участники платят деньги подобно тому, как они их платят артистам в цирке/театре за посещение концерта — разницы абсолютно никакой. Организаторы конференций при этом наглеют, «приглашают самих себя и своих друзей», устраивают междусобойчики, в одно рыло раздают несколько докладов. Даже если доклад сделан чьим-то подчинённым, то приглашают выступить его номинального руководителя, а не исполнителя. Более того, приглашая громкие фамилии, даже не интересуются, есть ли им что рассказать. Громкие фамилии потом приезжают и рассказывают, что под их крышей было сделано, часто слабо осознавая что же там на самом-то деле делалось. Получаем порочный круг: громкие фамилии приглашают, потому что они рассказывают умные, но чужие по сути, вещи, а рассказывают они их потому, что их приглашают. И некому разомкнуть этот порочный круг. У обываетелй же со стороны при этом создаётся ложное впечатление о том, что 99% науки делает 1% людей. Аргумент же о том, что у каждого только 24 часа в сутках не вразумляет: будь ты хоть нобелевский лауреат, но физически невозможно вести более, чем 2-3 работы параллельно. И потому если у тебя 300 работ, значит на тебя работают рабы и ты мошенник, в лучшем случае, а в худшем — ты просто массово публикуешь шлак. Самостоятельно невозможно по физике в год сделать более, чем 2-3 хороших работы. Грубый лимит при самой идеальнейшей продуктивности получился бы равным 140 статей за всю жизнь (реально он намного ниже), а хороших основополагающих статей хорошо, если удастся сделать штуки 3 за всю жизнь.


Есть ещё такая мысль: наука — это пирамида. Невозможно изучить все труды своих предшественников. Начиная с какого-то момента (пожалуй, он уже наступил) народ будет обречён переизобретать велиспеды. Частично это решается за счёт «пирамиды»: новые люди приходят на новые задачи, в новые области, а в старых остаются те, кто их начинал в молодости. В итоге многообразие приведёт к тому, что у каждого будет своя тема, и 2 человека в соседних кабинетах из одной области даже понимать друг друга не будут. Это приведёт к тому, что эксперт-оценщик и производитель результата — одно лицо, другие просто не поймут, кто что делает. Из-за этого начнётся новый виток падения уровня рецензирования, чем активно воспользуются мошенники, надувая журналы пустыми статьями. Нежелание писать научно-популярные и обзорные статьи приведёт к тому, что никто не будет понимать, что происходит глобально, в целом, даже в его узкой области. Из-за дальнейшей дифференциации понадобятся «междисциплинарные переводчики», которые принципиально не будут заниматься наукой, но будут обязаны заниматься тем, что впитывать ключевые результаты из разных областей, чтобы потом хоть как-то объяснить научной/административной/прочей общественности, что происходит, кто чем занимается, и зачем это нужно. Уже сейчас чётко видно: каждый приходит на свою узкую задачу и не знает ничего ни на шаг вокруг. Проходит много лет, прежде чем такой новичок станет понимать хоть какие-то чужие статьи. И нужны десятилетия, чтобы научиться видеть всю область в целом, умея читать/понимать публикации с журналов/архива так же легко, как обычные новости.



У этого подхода, кстати, есть и обратная сторона. Например, аспиранту ставят неподъёмную трудную задачу в области, «чтобы не публиковать шлак», он над ней 3 года бьётся, а решить не может. Время ушло, публикаций нет, защищаться на чём? Как доказать, что он эти 3 года работал? Такой потом кое-как защищается, полностью разочаровывается в науке, плюёт на всё и идёт учить детей в школу. Лично видел примеры. Никогда не стоит недооценивать неумелое руководство :) Могу сказать, что мне по российской аспирантуре поставили на мой взгляд неподъёмную для моего уровня задачу, решить которую я не смог. Банально даже математической подготовки не хватало, чтобы её толком осознать. По сути я должен был сделать то, что в своё время не смог сделать ни Фок, ни мой шеф, ну не хило, я бы сказал. И с итальянской аспирантурой могло бы получиться подобное: шанс, что задачу решить не удастся, а после меня останутся только тупые графики с численной оптимизацией, был процентов 95. Конечно, на этом тоже можно было бы защититься, с большим скрипом, но это явно не то, чего ждёшь от аспирантуры. Во всяком случае, первые полтора года прогресс по решению был практически нулевой, а сама задача доделывалась существенно позже всяких защит; главный же гвоздь статьи — нахождение фндаментальных констант канала — появился в процессе дописывания текста статьи, когда считалось, что «уже всё готово, надо как можно быстрее довершить и отослать».



3«Сделано у нас» в МИАН в 1973ем году: гордимся и восхищаемся! Американцам очень обидно, что они не первые: у них ведь это тоже доказали, но позже. Короче, они компенсируются тем, что называют её Holevo-Schumacher-Westmoreland (HSW) theorem, так что увидите в литературе аббревиатуру HSW — не пугайтесь. Впрочем, в статьях обычно упоминаний Шумахера и Вестморланда не делается. В книгах политкорректности ради называют по 3ём авторам, но всё равно отмечают, что Холево был первым. По правде говоря, Шумахер предоставил альетнативное доказательство, просто ему тут «повезло» оказаться не первым. В плане же других результатов, это вполне известная личность, с вполне заслуженным признанием и блестящими результатами в области квантовой информатики.
4Соотношение неопределённостей не даёт мерить одновременно и точно.
5Термин «тепловые фотоны» следует воспринимать как просто параметр состояния, а не как разные частицы (прозрачная параллель там есть, но неопытного она может запутать).
6Я решил пойти другим путём, и ввёл другой тип аддитивности — по среде канала, который при некоторых параметрах нарушается, а при других нет. Если удастся что-то существенное нарыть в этом направлении, будет замечательно — под задачу подан один из грантов.
7Работа в arXiv'е официально помечена как ошибочная, ошибку нашёл Холево и потом пол года убеждал авторов в её существовании (к счастью, убедил).


 
На страницу: 1, 2, 3 След.
Комментарии
— unknown (12/03/2012 10:30)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Да, spinore, это на данный момент ваш рекордный пост, как по объёму, так и по содержательности! Даже не знаю, что с ним делать — то ли вынести отсюда отдельной темой, то ли приклеить к проблемам QKD. По крайней мере, придётся его ещё неоднократно перечитывать и разбирать по мере наличия времени, потому что так сходу всё не осознать, хотя сами идеи простые, закономерные и логично вписываются в контекст предыдущих обсуждений.

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

А нельзя ли на основе этого создать нечто среднее между шумовой и квантовой криптографией — промежуточный уровень так сказать? Если в обычном шумовом (радио)канале, противник должен быть не слишком близко к передатчику и должна быть аналоговая линия с шумами, то в QKD такая инфраструктура уже есть.

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

В практическом смысле — это могли бы быть какие-то ретрансляторы для QKD, вспомогательные каналы для согласования и аутентификации. Это даже не важно. Некий квантово-шумовой канал с претензией на защищённость, а применение ему уже нашлось бы в ходе других изысканий.
— spinore (12/03/2012 14:31, исправлен 12/03/2012 14:34)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786

На самом деле, отличие гауссовых классических каналов от квантовых очень простое, если ограничиться рассмотрением только гауссовых состояний: из-за соотношения неопределённостей размер шапочки (что-то типа площади эллипса в сечении) не может быть сделан меньше постоянной Планка h. Потому любой протокол должен учитывать это дополнительное ограничение. В симплектической геометрии на этот счёт есть много интересных теорем, кстати. Подобное «соотношение неопределённостей» вылазит и где-то в классической обработке сигналов (что-то там с частотой/временем/спектром было, уже не помню), потому, может быть, где-то это релевантно и за рамками квантмеха. Короче говоря, трудность в том, что в протоколе надо всё представить гауссианами с размером, не меньше некоторого, даже если это сильно неоптимально. Именно это ограничение приводит к куче сложных матпроблем :(


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



Может быть. А, может быть, тот профит, который тут извлекаем, получается лучше при использовании запутанных пар, предварительно распределённых между Алисой и Бобом. Всякие «entanglement-assisted classical capacity» — это, кажется, что-то с этим связанное (entanglement — запутанность).



Это всё как-то очень абстрактно, т.к. по сути это будет вообще не QKD не только по букве, но даже по духу: это обычная классическая шумовая криптография поверх квантового канала — нечто совсем новое. Но раз такое никто не делает, значит, либо есть существенные трудности, либо показно, что это будет намного хуже QKD (на уровне здорового скепсиса). Но, в принципе, можно над этим подумать. Моё понимание осложняет то, что мне кажется, будто бы QKD и шумовая криптография — слишком концептуально разные подходы к безопасности, но это может быть от непонимания.



Если шумовая криптография — перспективное направление, то, смешивая её с QKD, казалось бы, можно сделать что-то, что будет использовать преимущества обоих подходов — получить более жизнейстойкий их гибрид (это чисто из общих соображений). Из-за полного незнакомства с шумовым крипто трудно свои 5 копеек в эту дискуссию вставить :(





— unknown (12/03/2012 15:38, исправлен 12/03/2012 16:16)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Я так понял из ваших постов, что шумовая криптография была предшественницей квантовой, и теперь стала чем-то в роде маргинального направления с очень неясными перспективами. Я заблуждаюсь?

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


Любопытно, что ни по шумовой криптографии, ни по связанным терминам нет даже статьи в википедии: Noise-based cryptograpy, noisy channels based cryptoprimitives, Wire-Tap channels. Первооткрыватель этого направления в 1975 году был Aaron D. Wyner (не путать со Стивом Визнером).


Среди своих же постов по этой теме наткнулся и на то, что сейчас предложил, якобы как новую идею: японцы уже публиковали это в 2000 году, протокол изобретён (вероятно корейцами) в 1998 году. Обещали скорости в пару мегабит по оптоволокну. Формально это относится к квантовой криптографии, хотя определение по сути такое, как вы дали: "обычная классическая шумовая криптография поверх квантового канала".

— spinore (12/03/2012 18:25)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786
— unknown (12/03/2012 20:58, исправлен 12/03/2012 21:02)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

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


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

— spinore (12/03/2012 23:05)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786

Интересно. У Хироты есть статья с Холево (в архиве её нет, к сожалению) по ёмкости (пропускной способности) квантового гауссова канала с аддитивным шумом, на которую все (и мы в том числе) активно ссылаются.

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


Уже успел чуть не перепутать с Норбертом Винером, широко известным в физике по «винеровским процессам» :)

В общем, ссылки годные, интересные, надо теперь читать и думать. Журнал краптологии насмешил :)
— unknown (13/03/2012 10:42)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Насколько я понял хотя бы из этого, fileэтого и fileэтого, протоколы YK и Y00 — это замена чисто квантовых протоколов BB-84 и B-92 (и их аналогов) на квантово-классические, которые претендуют на новое (смесь нового с хорошо забытым старым), перспективное (каждый своё болото хвалит) направление в QKD.

Упрощается создание сети, которая может быть развёрнута поверх обычной, с обычными оптическими (неквантовыми!) повторителями:
A special feature of YK and Y-00 protocol is that one can design the secure system based on only the abilities
of Eve and Bob for detectability. That is, it is not important how many repeaters are used in communication
channel from Alice to Bob. In general, the present fiber network consists of optical repeaters like fiber
amplifier, and direct detection scheme (intensity detection for on and off ).

Возможно получение гигабитных скоростей на расстояние в сотни километров (это уже показано на экспериментах). И всё это без дорогого оборудования, в котором требовалось бы удерживать количество фотонов в импульсе максимально близким к единице. Принципы кодирования несколько нестандартны для QKD и ближе к обычным сетям:
Yuen protocol (Y-00) and we present an efficient implementation method of physical layer of Y-00 which can support a secure communication and a quantum key distribution (more generally key expansion) by IMDD(intensity modulation/direct detection) or FSK(frequency shift keying) optical fiber communication network with fiber amplifiers as optical repeater,

Возможно, это упоминание про работу с непрерывными переменными (если можно построить канал такого типа, но похоже ни в одной из работ он не рассматривается):
The ciphering angle could have k in general
as discrete or continuous variable determined by distri-
bution of keys.

Пока убедительные доказательства стойкости для всего этого направления отсутствуют, есть только неполные, черновые наработки. Поэтому системы на YK/Y00-протоколах, вероятно, официально не признаются в качестве рекордсменов по дальности/скорости/низкой стоимости и пр. и остаются где-то на периферии.
— Гость (15/03/2012 23:07)   <#>
Как лучше организовать материал на сайте
Я вот всё думаю, почему бы Git использовать не только программистам. :)
— spinore (18/03/2012 03:23, исправлен 18/03/2012 06:04)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786

Это вы про ссылку на антены в /comment16695? Он устарела. Вот нагуглил fileсвежую.



Наверное, всё для того, чтобы сделать шифрование в беспроводных системах связи стойким, а то там всё плохо: и WEP, и WPA, и A5 в GSM.



Для полноты картины и большей понятности ради ещё упомяну /comment35960 про lossy-канал, имевший место несколько лет назад.



Там надо вчитываться в работу и смотреть ссылки в ней. На 1ой стр. говорится:


Since many photons are transmitted to carry one-bit information, the conditions specified above will not be satisfied if the SNR of Eve’s detection is sufficiently high. Eve’s SNR can be increased by using low-noise detection equipment, or simply by moving closer to Alice than Bob (because of the fiber loss.)

Это всё не очень понятно. Ну и то, что Еву лимитируют какими-то ресурсами... насколько это обосновано с практической точки зрения? Что тогда отражает доказательство безопасности протокола при таких ограничениях, насколько они сильны... Вы в /comment16695 правилно написали:


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

По крайней мере, QKD обеспечивает информационно-теоретическую стойкость, а как тут с шумовой криптографией — не ясно. Она, действительно, скорее к «та же вычислительная сложность, вид сбоку» :) Шумовое крипто мне ещё этим физически неклонируемые функции напоминает.



Некоторые идеи:


Над остальными вашими постами/вопросами в этой ветке надо думать дальше.


Есть такой способ исследования литературы: смотреть, кто на кого сослался. В одну сторону — это задача лёгкая (узнать, кого цитируют в данной статье), а в другую — вычислительно технически сложная (узнать, кто её процитировал). Помимо коммерческих закрытых баз типа ISI (которые arxiv не индексируют принципиально, как нерецензируемое издание) для архива есть такой общедоступный сервис http://citebase.org, который индексирует цитирования, но только по архиву. Вот, например, по этой ссылке видно, что нашу работу уже процитировали дважды. Unknown, есть ли аналогичный citebase'у сервис для iacr'а?


— unknown (18/03/2012 15:08)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
для того, чтобы сделать шифрование в беспроводных системах связи стойким, а то там всё плохо: и WEP, и WPA, и A5 в GSM.

Сомнительно, что там внедрить Noisy crypto будет легче и менее ресурсозатратнее, чем обычные стойкие классические алгоритмы. Причины того, что всё плохо — чисто коммерческие. Во-первых, оградить свою поляну патентами и занять её международным консорциумом-монополистом, который проталкивает закрытые решения и даёт к ним доступ ограниченному числу производителей оборудования. Во-второых, безопасность там не так существенна, ею всегда жертвуют ради экономии и вспоминают про неё только когда грозит полный фэйл.

Теперь полнее дошло, почему вы разместили в форуме задачу :) Оптимизация используется в проектировании и разработке атак в построении систем анонимной связи. Хотя есть какие-то области, где вероятно это ещё более активно развито. Вообще говоря, а где этого нет? Хоть в классической инженерной механике (если по всем принципам проектировать с нуля как мост построить, двигатель разработать), хоть в квантовой.
Ну и то, что Еву лимитируют какими-то ресурсами... насколько это обосновано с практической точки зрения? Что тогда отражает доказательство безопасности протокола при таких ограничениях, насколько они сильны...

Ну я чисто интуитивно "почувствовал" (принял на веру, понял на уровне примитивных представлений), как вы говорите "физичность", думал вы и объясните (правильно или ошибочно такое представление?).

После согласования ключа в шумовом канале, коррекции ошибок между A и B, но вероятностно несовпадающих с E, производится сжатие ключа для усиления приватности. Для Евы должна получиться ситуация невозможности восстановить такой ключ. Доказательство строится на том, что для перехвата ей потребуется построить приёмник, существование которого запрещено законами физики (с уровнем шумов меньше собственного уровня сколь-угодно идеальных составных элементов, естественного уровня шумов окружающей среды, меньше каких-то квантовых пределов). Алиса и Боб могут проводить до разумного значения сколь угодно много раундов согласования (им это практически ничего не стоит в плане ресурсов), так что для Евы с каждым раундом требования для перехвата должны увеличиваться экспоненциально вплоть до наступления предела до недоступных по законам физики значений. Основная задача — правильно смоделировать этот канал и решить оптимизационную задачу по количеству раундов и прочим параметрам. Это будет и доказательством стойкости.

А в физически неклонируемых функциях не просматривается сходимости к принципиальной невозможности построения вычислительно-моделирующего устройства. Хотя бы из-за того, что там всё строится на выигрыше по времени, Поэтому количество раундов ограничено, на извлечение информации из PUF тоже уходит время (это сугубое ИМХО и догадки, спецификой вопроса не владею).

Собственно, интересно ваше небольшое мнение и всё. Ну и раз вы намекали, что в обоснованиях к своим исследованиям (возможно для улучшения финансирования) вы пишете (возможно ваши коллеги, руководители, да хоть вообще посторонние люди, занимающиеся чем-то похожим), что это имеет отношение к QKD (хотя вроде как слегка за уши притянуто, если копнуть специфику). Ничего плохого в этом нет, особенно если исследования по классификации/моделированию/изучению квантовых каналов будут ещё лучше обоснованы как имеющие перспективы для QKD. Необяхательно даже самому заниматься объединением изучений каналов и "Noisy QKD", достаточно упомянуть и дать хотя бы поверхностное, но честное обоснование, если такая возможность действительно существует.

Есть ещё http://citeseerx.ist.psu.edu
Torproject использует gitweb — доки, багрепорты, тикеты.
— spinore (18/03/2012 21:35, исправлен 18/03/2012 21:51)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786

Это не так просто сделать/понять, особенно для меня :) Ваше (и то, что в статьях) объяснение принципа работы звучит вполне правдоподобно на уровне общих суждений. Работы Maurer'а, включая «Unconditional Security Against Memory-Bounded Adversaries», вполне признаются квантовым сообществом; тем более, что у него есть и совместные работы с такими авторитетами, как R. Renner. Maurer делает что-то подобное вашему описанию, где безопасность следует из невозможности для Евы оцифровать весь шум идеально и хранить его сколько угодно долго. Я склоняюсь к тому, что «здесь есть рыба» и эти статьи/работы стоит поизучать поподробнее. Если удастся сделать что-то на стыке квантовой и шумовой криптографии, то отлично, если появятся идеи8, показывающие полезность наших результатов для каких-то квантово-шумовых вещей, то тоже неплохо. В крайнем случае, могут быть какие-то общие идеи и математические методы в шумовой криптографии, которые окажутся полезными для квантовой или натолкнут на какие-то мысли. Так что, несмотря на весь скептицизм, то, что я не считаю всё это контрпродуктивным — это точно :)



Ну вот чтобы «дать хотя бы поверхностное, но честное обоснование» как раз и надо поразбираться с предметной областью и почитать статьи :) За ссылки и идеи вам стоит сказать отдельное и большое спасибо! На кое-какие новые идеи они уже натолкнули, правда, не в контексте QKD, а в контексте QRNG.



Абсолютно согласен.




Да, теория оптимизации — огромная область в прикладной математике, которой занимается большое число математиков-прикладников. Большая часть применений находит в экномике и финансах, в инженерии, в теории информации. Для физики как таковой теория оптимизации нехарактерна9, а теория информации даётся в рамках пары лекций как часть спецкурсов10.


Существенная часть всей теории оптимизации — выпуклая. По ссылке есть довольно толстая обстоятельная книжка по методам. А ещё добрые люди написали fileобзорную статью, чтобы неспециалисты знали, что вообще есть в этой области, какая терминология и куда копать. Мораль статьи в том, что есть класс задач выпуклой оптимизации, которые хорошо изучены. Если же задача невыпуклая, то надо разбивать на области выпуклости, а всё, что принципиально невыпукло (это не мой случай 100%), требует разработки специальных методов, часто эвристических, и может оказаться NP-сложной задачей11. Короче, всё делится на два класса: «выпуклое» и «всё остальное».



8Хотя бы на уровне ссылок на работы.
9Из-за этого мне трудно разбираться: я никогда теорию оптимизации не изучал, помимо стандартного метода множителей Лагранжа, идущего вприкуску к матанализу и лекциям/семинарам по экономике (сделали её обязательной для физиков, увы). Одним словом, не буду скрывать, что глубинный провал в знании оптимизационных методов очень больно бьёт по всем, кто пришли из теоретической квантовой механики в квантовую теории информации — я тут не один такой. Впрочем, прогноз благоприятен: изучать с нуля теорию оптимизацию проще, чем квантовую механику, потому по сравнению с теми, кто пришёл из классической теории информации, у нас немного более выгодное положение.
10У нас оно, к примеру, относилось к вводным лекциям по «методам экспериментальной физики», где в том числе освещаются вопросы по обработке экспериментальных данных.
11Например, типа комивояжёровской. Кстати, даже квадратичная оптимизация принадлежит NP-полным задачам — интересно, есть ли тут какая-то связь с ECC?

— Гость (28/03/2012 12:22)   <#>
я прочитал одну толковую методичку, где каких-то жалких 10-20 страниц навели полный порядок в голове.
А не подскажете ли ссылку, или может выложите где?

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

Несколько ссылок "в помощь популяризаторам квантовой механники" :)
Фейнман. КЭД – странная теория света и вещества
Гордон. Кухаренко. Рязанов. Стрела времени
Доронин. Квантовая магия
Извиняйте коль не в тему.
— falkenberg (28/03/2012 20:19)   профиль/связь   <#>
комментариев: 20   документов: 1   редакций: 12
Чет по поводу Доронина чего только не пишут... Вообще я не специалист, но как-то сразу чем-то нехорошим повеяло. Попробовал погуглить на его имя – и сразу море негативных отзывов. Приводить ссылки не буду, желающие найдут сами.
— Гость (29/03/2012 01:32)   <#>
Чет по поводу Доронина чего только не пишут..

Нет чтоб самому в предисловии у Доронина прочитать:
Надеюсь, что читатель сумеет отделить приведенные в книге факты и сами физические результаты от моей трактовки и моего личного мнения на этот счет.

По моему он замечательный популяризатор! Очень привлекательный подход, побуждающий молодое поколение (и не только) к изучению квантовой физики. Журнал вот уже 8 лет выпускает. Ну а кому трактовка совсмем не нравится, могут прямо читать книги из библиографии: вот и вот
А то что, что таковые будут, в этом же журнале и написано ;)
— falkenberg (29/03/2012 13:21)   профиль/связь   <#>
комментариев: 20   документов: 1   редакций: 12
Да я ничего такого не говорю, как я признался я – не специалист и мне негоже критиковать кандидата наук, работающего в действующем институте. Но у популяризаторов есть опасность: с одной стороны скатиться на уровень, что будет непонятен неподготовленному читателю, с другой – к слишком вульгарной подачи материала, искажающей действительность до полного ее перевирания. Читатель же, способный отличить результаты от трактовок не нуждается в популярных книжках, он вполне освоит и учебники и способен читать научные статьи. Поэтому грань, по которой ходит популяризатор очень тонка. Ее очень легко перешагнуть, вольно ли или невольно. Тех, кто это делает сознательно, желая дешевой популярности или просто денег сейчас полным-полно (это не относится к Доронину, я про него слишком мало знаю чтоб что-то говорить. Хотя некие подозрения по стилю изложения у меня возникли срану). Ну или просто сумасшедших ученых :) Это все крайне осложняет положение неподготовленного читателя, желающего что-то понять, при этом не желающего чтобы ему ездили по мозгам. Если бы меня попросили назвать хорошего популяризотра на эту тему, я бы вспомнил Дэвида Дойча.
На страницу: 1, 2, 3 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3