О полных односторонних функциях

Полные конструкции играют важную роль в теоретической информатике. Однако в криптографии до недавних пор полные конструкции либо отсутствовали, либо носили сугубо теоретический характер. В 2003 г. Л. А. Левин предложил идею полной односторонней функции, основанной на комбинаторных соображениях. В настоящей статье представлены две новые полные односторонние функции, основанные на полусистемах Туэ, и полная односторонняя функция, основанная на варианте задачи соответствия Поста. Также формально представлены свойства, которыми должна обладать комбинаторная задача, чтобы на ее основе можно было построить полную одностороннюю функцию. Статья содержит новое доказательство результата Левина.