Feebly secure cryptographic primitives

В 1992 г. А. Хильтген построил первые конструкции доказуемо (слабо) надёжных криптографических примитивов, а именно односторонних функций. Эти функции доказуемо сложнее обратить, чем вычислить, но сложность (схемная сложность в базисе из произвольных бинарных гейтов) увеличивается лишь в константное число раз (в конструкциях Хильтгена этот показатель приближается к $2$). В традиционной криптографии, односторонние функции являются основными примитивами для схем с секретным ключом, а схемы с открытым ключом конструируются на основе функций с секретом. Мы развиваем идеи работ Хильтгена и строим примеры функций с секретом, доказуемо надёжных в слабом смысле, в которых схема противника гарантированно больше, чем схемы честных участников (тоже в константное число раз). Мы строим примеры как (более простых) линейных, так и (более надёжных) нелинейных конструкций. Библ. – 25 назв.