Задача о рюкзаке — NP-полная задача комбинаторной оптимизации. Своё название получила от конечной цели: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. С различными вариациями задачи о рюкзаке можно столкнуться в экономике, прикладной математике, криптографии и логистике.
Односторонняя функция — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения теории сложности вычислений. Разрыв между сложностью прямого и обратного преобразований определяет криптографическую эффективность односторонней функции. Неинъективность функции не является достаточным условием для того, чтобы называть её односторонней. Односторонние функции могут называться также трудно обратимыми или необратимыми.
Протокол конфиденциального вычисления — криптографический протокол, позволяющий нескольким участникам произвести вычисление, зависящее от тайных входных данных каждого из них, таким образом, чтобы ни один участник не смог получить никакой информации о чужих тайных входных данных. Впервые задача конфиденциального вычисления была поднята Эндрю Яо в 1982 году в статье. Два миллионера, Алиса и Боб, хотят выяснить, кто же из них богаче, при этом они не хотят разглашать точную сумму своего благосостояния. Яо предложил в своей статье оригинальный способ решения этой задачи, получившей впоследствии название проблема миллионеров. Гораздо позже, в 2004 году Йехуда Линделл и Бенни Пинкас предоставили математически строгое доказательство корректности протокола Яо в статье. Задача конфиденциального вычисления тесно связана с задачей разделения секрета.
Атака «дней рождения» — используемое в криптоанализе название для метода взлома шифров или поиска коллизий хеш-функций на основе парадокса дней рождения.
В теории информации теорема Шеннона об источнике шифрования устанавливает предел максимального сжатия данных и числовое значение энтропии Шеннона.
Криптографическая хеш-функция — всякая хеш-функция, являющаяся криптостойкой, то есть удовлетворяющая ряду требований, специфичных для криптографических приложений.
CBC MAC — в криптографии является технологией построения аутентификационного кода сообщения из блочного шифра. Сообщение шифруется при помощи некоторого блочного алгоритма шифрования в режиме CBC, для создания цепочки блоков с правилом — каждый блок зависит от надлежащего(верного) шифрования предыдущего. Эта взаимозависимость гарантирует, что изменение в любом бите открытого текста приведёт к изменению конечного зашифрованного блока в сторону, которая не может быть предсказана или высчитана в случае, если ключ блочного шифра не известен.
Проблема круга Гаусса — задача определения количества точек целочисленной решётки, попадающих в круг радиуса r с центром в начале координат. Первый успех в решении этой задачи был сделан Гауссом, в честь него и названа проблема.
В математике, приближенная схема полиномиального времени или polynomial-time approximation scheme (PTAS) обозначает класс приближенных полиномиальных по времени выполнения алгоритмов для решения, как правило, NP-трудных оптимизационных задач. Если P = NP, то введение этого понятия теряет смысл. Поэтому далее будем предполагать, что Р не совпадает с NР. И без ограничения общности определим понятие для задачи минимизации.
Молекулярные орбитали — математическая функция, описывающая волновое поведение электронов в молекуле.
MTProto — криптографический протокол, используемый в системе обмена сообщениями Telegram для шифрования переписки пользователей. Протокол был разработан Николаем Дуровым и другими программистами Telegram.
Параметрическая редукция — это техника для разработки эффективных алгоритмов, которые достигают своей эффективности путём препроцессорного шага, в котором вход алгоритма заменяется на меньший вход, называемый «ядром». Результат решения задачи на ядре должен быть либо тем же самым, что и при исходных данных, либо выход решения для ядра должен легко преобразовываться в желаемый выход исходной задачи.
Дифференциальная приватность — совокупность методов, которые обеспечивают максимально точные запросы в статистическую базу данных при одновременной минимизации возможности идентификации отдельных записей в ней.
Основанная на плотности пространственная кластеризация для приложений с шумами — это алгоритм кластеризации данных, который предложили Маритин Эстер, Ганс-Петер Кригель, Ёрг Сандер и Сяовэй Су в 1996. Это алгоритм кластеризации, основанной на плотности — если дан набор точек в некотором пространстве, алгоритм группирует вместе точки, которые тесно расположены, помечая как выбросы точки, которые находятся одиноко в областях с малой плотностью . DBSCAN является одним из наиболее часто используемых алгоритмов кластеризации, и наиболее часто упоминается в научной литературе.
Оккамово обучение в теории вычислительного обучения является моделью алгоритмического обучения, где целью обучения является получение сжатого представления имеющихся тренировочных данных. Метод тесно связан с почти корректным обучением, где учитель оценивает прогнозирующую способность тестового набора.
Вероятно приближённо корректное обучение — схема машинного обучения, использующая понятия асимптотической достоверности и вычислительной сложности. Предложена в 1984 году Лесли Вэлиантом.
В криптографии Full Domaine Hash является схемой подписи на основе RSA, которая следует парадигме хеширования и подписи. Он доказуемо защищён в модели случайного оракула. FDH включает в себя хеширование сообщения с использованием функции, размер изображения которой равен размеру модуля RSA, а затем повышение результата до секретного показателя RSA.
Справедливое разрезание торта — это вид задачи справедливого дележа. Задача вовлекает неоднородный ресурс, такой как торт с различными украшениями, которые предполагаются делимыми — то есть от него можно отрезать произвольно малый кусочек без разрушения полной ценности. Ресурс нужно разделить среди нескольких партнёров, имеющих различные предпочтения к различным частям торта. Например, некоторые люди предпочитают шоколадные украшения, другие предпочитают вишенки, в то время как третьи хотят получить просто кусок побольше. Делёж должен быть субъективно справедливым, каждый участник должен получить кусок, который он/она считает справедливой долей.
Нечёткий экстрактор — способ, который позволяет однозначно восстанавливать секретный ключ из неточно воспроизводимых биометрических данных при участии вспомогательных данных, являющимися открытыми. «Нечёткий» в данном контексте относится к тому факту, что фиксированные значения, требуемые для криптографии, будут извлечены из значений, близких, но не идентичных исходному ключу. Одним из приложений является шифрование и аутентификация записей пользователей, используя биометрические данные пользователя в качестве ключа.
Криптосистема Миччанчо — криптосистема, основанная на схеме шифрования GGH, была предложена в 2001 году профессором Университета Калифорнии в Сан-Диего Даниелем Миччанчо.
