Гомоморфное шифрование

  • Гомоморфное шифрование — форма шифрования, позволяющая производить определённые математические действия с зашифрованным текстом и получать зашифрованный результат, который соответствует результату операций, выполненных с открытым текстом. Например, один человек мог бы сложить два зашифрованных числа, не зная расшифрованных чисел, а затем другой человек мог бы расшифровать зашифрованную сумму — получить расшифрованную сумму, не имея расшифрованных чисел. Гомоморфное шифрование позволило бы предоставлять различные услуги, не предоставляя открытые пользовательские данные для каждой услуги.

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

Источник: Википедия

Связанные понятия

Криптосистема Гольдвассер — Микали (GM) — криптографическая система с открытым ключом, разработанная Шафи Гольдвассер и Сильвио Микали в 1982 году. GM является первой схемой вероятностного шифрования с открытым ключом, доказуемо стойкая при стандартных криптографических предположениях. Однако, криптосистема GM является неэффективной, так как шифртекст может быть в сотни раз длиннее, чем шифруемое сообщение. Для доказательства свойств стойкости криптосистемы Голдвассер и Микали ввели широко используемое...
Схема Шнорра (англ. schnorr scheme) — одна из наиболее эффективных и теоретически обоснованных схем аутентификации. Безопасность схемы основывается на трудности вычисления дискретных логарифмов. Предложенная Клаусом Шнорром схема является модификацией схем Эль-Гамаля (1985) и Фиата-Шамира (1986), но имеет меньший размер подписи. Схема Шнорра лежит в основе стандарта Республики Беларусь СТБ 1176.2-99 и южнокорейских стандартов KCDSA и EC-KCDSA. Она была покрыта патентом США 4999082, который истек...
Полностью гомоморфное шифрование — шифрование, позволяющее для данного шифротекста π1,…,πt любому (не только держателю ключа) получить шифротекст любой желаемой функции f(π1,…,πt), до тех пор, пока данная функция может быть эффективно вычислена.
Хеширование (англ. hashing – «превращать в фарш», «мешанина») — преобразование массива входных данных произвольной длины в (выходную) битовую строку установленной длины, выполняемое определённым алгоритмом. Функция, воплощающая алгоритм и выполняющая преобразование, называется «хеш-функцией» или «функцией свёртки». Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования (выходные данные) называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения».
Полный перебор (или метод «грубой силы», англ. brute force) — метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.
Шифрование, сохраняющее формат (англ. format-preserving encryption, FPE) означает шифрование, в котором выходные данные (шифротекст) находятся в таком же формате, что и входные данные (открытый текст). Значение слова «формат» варьируется. Обычно подразумеваются только конечные множества, например...
Быстрая криптосистема с открытым ключом (англ. Fast public-key cryptosystem) или лёгкая криптосистема с открытым ключом (англ. Lightweight public-key cryptosystem) — асимметричная криптосистема, используемая в устройствах с ограниченными ресурсами.
Криптографические хеш-функции — это выделенный класс хеш-функций, который имеет определенные свойства, делающие его пригодным для использования в криптографии.

Подробнее: Криптографическая хеш-функция
Компромисс времени и памяти (англ. Space-time trade-off, «выбор оптимального соотношения „место-время“» (англ. space-time trade-off), или, иначе, «выбор оптимального соотношения „время-память“» (англ. time-memory trade-off)) — компромиссный подход к решению ряда задач в информатике, при котором используется обратное соотношение требуемого объёма памяти и скорости выполнения программы: время вычислений может быть увеличено за счёт уменьшения используемой памяти или, наоборот, снижено за счёт увеличения...
Защищённые облачные вычисления — методы, обеспечивающие проведение безопасных передачи, приёма, изменений данных клиента, хранящимися на удалённом «облачном» сервере.
Бло́чный шифр — разновидность симметричного шифра, оперирующего группами бит фиксированной длины — блоками, характерный размер которых меняется в пределах 64‒256 бит. Если исходный текст (или его остаток) меньше размера блока, перед шифрованием его дополняют. Фактически, блочный шифр представляет собой подстановку на алфавите блоков, которая, как следствие, может быть моно- или полиалфавитной. Блочный шифр является важной компонентой многих криптографических протоколов и широко используется для защиты...
Односторонняя функция — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции. Здесь «легко» и «трудно» должны пониматься с точки зрения теории сложности вычислений. Разрыв между сложностью прямого и обратного преобразований определяет криптографическую эффективность односторонней функции. Неинъективность функции не является достаточным условием для того, чтобы называть её односторонней. Односторонние функции могут называться...
Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94).
Быстрая цифровая подпись – вариант цифровой подписи, использующий алгоритм с гораздо меньшим (в десятки раз) числом вычислений модульной арифметики по сравнению с традиционными схемами ЭЦП. Схема быстрой электронной подписи, как и обычная, включает в себя алгоритм генерации ключевых пар пользователя, функцию вычисления подписи и функцию проверки подписи.
Атака на основе открытых текстов (англ. Known-plaintext attack) — вид криптоанализа, при котором в шифротексте присутствуют стандартные отрывки, смысл которых заранее известен аналитику. Во время Второй мировой войны английские криптоаналитики называли такие отрывки «подсказками» (англ. crib — подсказка, шпаргалка).
Криптосистема Накаша — Штерна (англ. Naccache — Stern cryptosystem)— криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи дискретного логарифмирования. В отличии от RSA, гомоморфен по сложению и вычитанию, а не по умножению...
Шифрова́ние — обратимое преобразование информации в целях сокрытия от неавторизованных лиц, с предоставлением, в это же время, авторизованным пользователям доступа к ней. Главным образом, шифрование служит задачей соблюдения конфиденциальности передаваемой информации. Важной особенностью любого алгоритма шифрования является использование ключа, который утверждает выбор конкретного преобразования из совокупности возможных для данного алгоритма.
Протокол Диффи-Хеллмана с использованием суперсингулярной изогении (англ. Supersingular isogeny Diffie–Hellman key exchange, SIDH) — это постквантовый криптографический алгоритм, позволяющий двум и более сторонам получить общий секретный ключ, используя незащищенный от прослушивания канал связи. Это аналог протокола Диффи-Хеллмана, основанный на блуждании в суперсингулярном изогенном графе, который предназначен противостоять криптоаналитической атаке противника, владеющего квантовым компьютером...
В криптографии обмен ключами при обучении с ошибками — криптографический алгоритм, позволяющий двум сторонам создавать и обмениваться секретным ключом, который они используют для шифрования сообщений между собой. RLWE-KEX (англ. Ring Learning with Errors Key Exchange) является одним из алгоритмов с открытым ключом, который предназначен для защиты от противника, обладающего квантовым компьютером. Это важно, потому что криптографические системы с открытым ключом, широко используемые сегодня, легко...
Атака на основе адаптивно подобранного открытого текста — вид атаки в криптоанализе, предполагающий, что криптоаналитик может несколько раз выбирать открытый текст и получать соответствующий ему шифртекст прямо во время атаки. Цель криптоаналитика — получить возможность извлекать информацию из перехваченных шифртекстов этой системы, а в идеале подобрать ключ, сопоставляя открытый текст и полученный шифртекст.
В криптографии протокол конфиденциального вычисления (также безопасное, защищенное или тайное многостороннее вычисление, англ. secure multi-party computation) — криптографический протокол, позволяющий нескольким участникам произвести вычисление, зависящее от тайных входных данных каждого из них, таким образом, чтобы ни один участник не смог получить никакой информации о чужих тайных входных данных. Впервые задача конфиденциального вычисления была поднята Эндрю Яо (англ. Andrew Yao) в 1982 году в...
Сдвиговая атака (англ. slide attack) – криптографическая атака, являющаяся, в общем случае, атакой на основе подобранного открытого текста, позволяющая проводить криптоанализ блоковых многораундовых шифров независимо от количества используемых раундов. Предложена Алексом Бирюковым и Дэвидом Вагнером в 1999 году.
Стандарты шифрования данных — совокупность правил, используемых в мощной алгоритмической технике кодировании информации.
Криптосистема Джентри (от фамилии создателя Крейга Джентри) — первая возможная конструкция для полностью гомоморфной криптосистемы, основанная на криптографии на решетках. Впервые была предложена Крейгом Джентри в 2009 году и являлась темой его докторской диссертации. Схема Джентри поддерживает операции сложения и умножения над шифротекстом, что позволяет построить кольца для реализации любых произвольных вычислений. Впоследствии имела множество доработок и модификаций с целью улучшения её производительности...
Имитовста́вка (MAC, англ. message authentication code — код аутентификации сообщения) — средство обеспечения имитозащиты в протоколах аутентификации сообщений с доверяющими друг другу участниками — специальный набор символов, который добавляется к сообщению и предназначен для обеспечения его целостности и аутентификации источника данных.
Протокол Ди́ффи — Хе́ллмана (англ. Diffie–Hellman, DH) — криптографический протокол, позволяющий двум и более сторонам получить общий секретный ключ, используя незащищенный от прослушивания канал связи. Полученный ключ используется для шифрования дальнейшего обмена с помощью алгоритмов симметричного шифрования.
ГОСТ Р 34.11-2012 «Информационная технология. Криптографическая защита информации. Функция хеширования» — действующий российский криптографический стандарт, определяющий алгоритм и процедуру вычисления хеш-функции. Разработан Центром защиты информации и специальной связи ФСБ России с участием ОАО «ИнфоТеКС» и введен в действие 1 января 2013 года.
Криптосистема Нидеррайтера — криптосистема с открытыми ключами, основанная на теории алгебраического кодирования, разработанная в 1986 году Харальдом Нидеррайтером. В отличие от криптосистемы McEliece, в криптосистеме Нидеррайтера используется проверочная матрица кода. Криптосистема Нидеррайтера позволяет создавать цифровые подписи и является кандидатом для постквантовой криптографии, поскольку устойчива к атаке с использованием алгоритма Шора.
ГОСТ Р 34.11-94 — устаревший российский криптографический стандарт вычисления хеш-функции.
Отрицаемое шифрование (англ. deniable encryption, также двусмы́сленное шифрова́ние) — способ криптографического преобразования, в котором зашифровываются совместно два или более различных сообщения на двух или более различных ключах. Этот метод обеспечивает возможность правдоподобного отрицания наличия одного или группы сообщений как таковых. Сам термин «двусмысленное шифрование» придуман Джулианом Ассанджем и Ральфом Вайманном в ходе работы над Rubberhose в 1997-2000 годах.
Трехэтапный протокол Шамира (англ. Shamir's three-pass protocol) — первый криптографический трехэтапный протокол, разработанный Ади Шамиром около 1980 года. Также протокол называют "протокол с тремя замками". Позволяет двум сторонам безопасно обмениваться сообщениями без необходимости обмена или распространения ключей шифрования. Отправитель и получатель обмениваются тремя зашифрованными сообщениями.
Радужная таблица (англ. rainbow table) — специальный вариант таблиц поиска (англ. lookup table) для обращения криптографических хеш-функций, использующий механизм разумного компромисса между временем поиска по таблице и занимаемой памятью (англ. time-memory tradeoff). Радужные таблицы используются для вскрытия паролей, преобразованных при помощи сложнообратимой хеш-функции, а также для атак на симметричные шифры на основе известного открытого текста. Использование функции формирования ключа с применением...
Криптосистема Крамера–Шоупа (англ. Cramer–Shoup system) — алгоритм шифрования с открытым ключом. Первый алгоритм, доказавший свою устойчивость к атакам на основе адаптивно подобранного шифротекста...
Обучение с ошибками (англ. Learning with errors) — это концепция машинного обучения, суть которой заключается в том, что в простые вычислительные задачи (например, системы линейных уравнений) намеренно вносится ошибка, делая их решение известными методами неосуществимым за приемлемое время.
Криптоана́лиз (от др.-греч. κρυπτός «скрытый» + «анализ») — наука о методах дешифровки зашифрованной информации без предназначенного для этого ключа, а также сам процесс такой дешифровки.
Циклический избыточный код (англ. Cyclic redundancy check, CRC) — алгоритм нахождения контрольной суммы, предназначенный для проверки целостности данных. CRC является практическим приложением помехоустойчивого кодирования, основанным на определённых математических свойствах циклического кода.
В криптографии протокол проверяемых вычислений (англ. verifiable computing) — это криптографический протокол, позволяющий освободить непроизводительный компьютер от сложных вычислений путём их частичного или полного переноса на один или несколько внешних более производительных компьютеров (англ. Outsource), сохраняя возможность проверки корректности возвращённого результата без дополнительного взаимодействия. Исполнители возвращают результат и доказательство корректности вычислений. В качестве внешней...
Сеть Фе́йстеля, или конструкция Фейстеля (англ. Feistel network, Feistel cipher), — один из методов построения блочных шифров. Сеть состоит из ячеек, называемых ячейками Фейстеля. На вход каждой ячейки поступают данные и ключ. На выходе каждой ячейки получают изменённые данные и изменённый ключ. Все ячейки однотипны, и говорят, что сеть представляет собой определённую многократно повторяющуюся (итерированную) структуру. Ключ выбирается в зависимости от алгоритма шифрования/расшифрования и меняется...
Бэкдор, backdoor (от англ. back door — «чёрный ход», буквально «задняя дверь») — дефект алгоритма, который намеренно встраивается в него разработчиком и позволяет получить несанкционированный доступ к данным или удалённому управлению операционной системой и компьютером в целом.
Псевдослучайный алгоритм шифрования — такой алгоритм шифрования, что каждый блок (символ) исходного текста шифруется своим собственным ключом, причём каждый следующий ключ является следующим членом псевдослучайной последовательности, а основной (базовый) ключ — первым элементом этой последовательности.
Перебор по словарю (англ. dictionary attack) — атака на систему защиты, использующая метод полного перебора (англ. brute-force) предполагаемых паролей, используемых для аутентификации, осуществляемого путём последовательного пересмотра всех слов (паролей в чистом виде или их зашифрованных образов) определённого вида и длины из словаря с целью последующего взлома системы и получения доступа к секретной информации.
Поиск клонов в исходном коде - анализ исходного кода с помощью различных алгоритмов, с целью обнаружения клонированного кода, который может иметь вредоносный характер.
Пото́чный или Пото́ковый шифр — это симметричный шифр, в котором каждый символ открытого текста преобразуется в символ шифрованного текста в зависимости не только от используемого ключа, но и от его расположения в потоке открытого текста. Поточный шифр реализует другой подход к симметричному шифрованию, нежели блочные шифры.
Фортра́н (англ. Fortran) — первый язык программирования высокого уровня, получивший практическое применение, имеющий транслятор и испытавший дальнейшее развитие. Создан в период с 1954 по 1957 год группой программистов под руководством Джона Бэкуса в корпорации IBM. Название Fortran является сокращением от FORmula TRANslator (переводчик формул). Фортран широко используется в первую очередь для научных и инженерных вычислений. Одно из преимуществ современного Фортрана — большое количество написанных...
Си (англ. C) — компилируемый статически типизированный язык программирования общего назначения, разработанный в 1969—1973 годах сотрудником Bell Labs Деннисом Ритчи как развитие языка Би. Первоначально был разработан для реализации операционной системы UNIX, но впоследствии был перенесён на множество других платформ. Согласно дизайну языка, его конструкции близко сопоставляются типичным машинным инструкциям, благодаря чему он нашёл применение в проектах, для которых был свойственен язык ассемблера...
Шифрующее программное обеспечение — это программное обеспечение, основной задачей которого является шифрование и дешифрование данных, как правило, в виде файлов (или секторов), жестких дисков и сменных носителей (дискет, компакт-дисков, USB-флеш-накопителей), сообщений электронной почты или в виде пакетов, передаваемых через компьютерные сети.
Ранцевая криптосистема Шора-Ривеста была предложена в 1985 году (Chor, 1985; Chor and Rivest, 1988). В настоящее время она является единственной известной схемой шифрования, основанной на задаче о ранце, которая не использует модульного умножения для маскировки простой задачи о ранце На данный момент создано множество рюкзачных криптосистем, например ранцевая криптосистема Меркла — Хеллмана. Однако практически все существующие на сегодняшний день взломаны или признаны потенциально небезопасными...
Ту́рбокод — параллельный каскадный блоковый систематический код, способный исправлять ошибки, возникающие при передаче цифровой информации по каналу связи с шумами. Синонимом турбокода является известный в теории кодирования термин — каскадный код (англ. concatenated code) (предложен Д. Форни в 1966 году).
Суперкомпиляция, или метакомпиляция, — специальная техника оптимизации алгоритмов, основанная на знании конкретных входных данных алгоритма. Суперкомпилятор принимает исходный код алгоритма плюс некоторые данные о входных параметрах и возвращает новый исходный код, который исполняет свою задачу на этих данных быстрее или является лучше исходного алгоритма по каким-то другим показателям. Очень часто под суперкомпиляцией неверно понимают глобальную оптимизацию программы, то есть эквивалентные преобразования...
Множественная (коллективная) подпись (англ. Aggregate signature) — схема (протокол) реализации электронной подписи (ЭЦП), которая позволяет нескольким пользователям подписывать единый документ.
а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я