Previous Entry Share Next Entry
2016-01

ICFPC2013 и асимметричная криптография

tl;dr: задача ICFPC этого года эквивалентна построению универсальной ломалки для асимметричной криптографии (восстановить trapdoor-функцию с помощью chosen-plaintext атаки и оракула организаторов) вряд ли это intended, но забавно.

В связи с этим вопрос: есть ли вообще какие-либо статьи по применению SMT солверов для оптимизации решения discrete logarithm или factoring problem?

This entry was originally posted at http://wizzard.dreamwidth.org/298710.html. It has comment count unavailable comments. Please comment there using OpenID.

  • 1
_winnie August 10th, 2013
misread: с помощью chosen-plaintext атаки и подкупа организаторов

_winnie August 10th, 2013
intellince-атака: поискать пейперы организаторов :]
( я не знаю, будет ли полезно, но с некоторой вероятностью они будут петь то, над чем сами работают )

Edited at 2013-08-10 05:21 pm (UTC)

sassa_nf August 11th, 2013
methinks, любой профессор на каком-то этапе развлекается со студиками задачами на равенство двух функций.

wizzard0 August 11th, 2013
Ничего не могу прокомментировать.

sassa_nf August 11th, 2013
а как они, по-твоему, сравнивают, что присланный вариант функционально равен задуманному.

nponeccop August 12th, 2013
диспрувером равенства? их сколько угодно.

Edited at 2013-08-12 08:37 am (UTC)

sassa_nf August 12th, 2013
я думал в общем виде задача неразрешима

wizzard0 August 12th, 2013
ну условие почитай что ли, ссылка в теле поста есть

sassa_nf August 12th, 2013
я не знаю, что не понятно.

Было предложение почитать статьи организаторов. А я продолжаю бла-бла и замечаю, что статьи могут быть на обратную тему: участник отправляет вариант программы, а на том конце нужно делать что? Сравнить, равна ли эта программа задуманной функционально. Это как решить задачу проверки на равенство функций f(x) и g(x) или задать экстенсиональное равенство функций.

(Deleted comment)
nponeccop August 12th, 2013
В общем виде действительно неразрешима, но это не важно :)

Неразрешимость ни о чём нам, промышленным программистам, не говорит. Она всего лишь запрещает строить a decision procedure which is both complete and sound.

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

Во-вторых, если задача разрешима - то это вовсе не значит, что полной процедурой разрешения можно воспользоваться. Всё равно может потребоваться опять же incomplete or unsound polynomial approximation.

Чисто гипотетически, можно надеяться что для данного случая предикат равенства функций разрешим, но разрешимость нам ничего не даёт, см. выше.

Де факто у оргов разрешитель incomplete, но кол-во задач, для которых оракул ответил "не знаю" и зафейлил задачу, не предоставив контрпримера, оказалось ничтожно мало. Я не могу сейчас пруфлинка найти.

wizzard0 August 12th, 2013
http://www.pexforfun.com/ вот, играйся)

nponeccop August 12th, 2013
> эквивалентна построению универсальной ломалки

Отнюдь. Идея trapdoor в том, что её не восстановить по спецификации. Это скорее ломалка наивных шифров с security by obscurity, что-то вроде универсального кейгена (схемы генерации серийников почему-то редко используют научную криптографию).

> есть ли вообще какие-либо статьи

На гугле забанили?

https://www.google.com.ng/search?q=sat+solver+factorization

Edited at 2013-08-12 08:37 am (UTC)

wizzard0 August 12th, 2013
> Отнюдь
Nope.

Я утверждаю, что "найти неизвестную функцию" === "восстановить ключ известного trapdoor'a параметризованного неизвестным ключом"

nponeccop August 12th, 2013
Ну с этим я не спорю, разве что только в деталях (это не эквивалентность а односторонняя импликация).

Я спорю с тем, что использованных оргами примитивов скорее всего не хватит для построения трапдора. Т.е. задачи всего лишь похожи, но многое придется поменять.

wizzard0 August 12th, 2013
Векторы узковаты, да. А так вроде хватает, умножение и возведение в степень сделать можно.

  • 1
?

Log in

No account? Create an account