Это первая публикация, в которой я намерен объяснить основные ингредиенты, необходимые для понимания криптографии в вопросах машинного обучения с сохранением конфиденциальности. Здесь я расскажу о теории чисел, а код Python можно найти в этой записной книжке.

Машинное обучение с сохранением конфиденциальности (PPML) - это относительно новая область исследований, которая направлена ​​на защиту конфиденциальности данных, а также интеллектуальной собственности в области машинного обучения. Он пытается решить такие проблемы, как избегание вашей модели для сохранения определенной информации, обучение модели на данных, которые вы не видите, или даже предоставление модели, которая будет использоваться для вывода, сохраняя при этом как исходные данные, так и прогноз в тайне.

PPML вызвал интерес в различных академических областях, таких как теория информации и криптография. В этом посте я сосредоточусь на самых основных ингредиентах последней, основной теории чисел. Я намерен опубликовать серию сообщений, чтобы мы могли в конечном итоге понять ключевые концепции криптографии в машинном обучении и безопасных многосторонних вычислениях.

Делимость и наибольший общий делитель

В этом разделе я пишу о делении целых чисел. Это так или иначе будет использоваться во всем этом посте. Учитывая два натуральных числа a и b (последнее ненулевое), мы говорим, что b делит a , если существует другое целое число c, такое что a = b * c. Если, наоборот, мы не можем найти такой c, то если b ‹a, мы можем найти отношение a = b * q + r, где q называется частным, а r остатком. Другими словами, это то, что мы учиться в начальной школе, только немного формализована.

Если есть число d, которое делит оба, a и b, мы также говорим, что d является общим делителем. из a и b. Например, 2 является общим делителем 60 и 80, так как вы можете написать 60 = 30 * 2 и 80 = 40 * 2. Один из способов вычислить наибольший общий делитель (НОД) двух целых чисел - использовать расширенный алгоритм Евклида: заданы два положительных целых числа a и b, выполняется следующее уравнение

Код на Python для решения этого уравнения можно найти здесь. Например, решение для пары (a, b) = (30,27) - это g, u, v = (3, 1, -1), где g - НОД. И последнее определение, a и b, называются взаимно простыми, если gcd (a, b) = 1, то есть наибольшее число, которое делит оба - 1.

Модульная арифметика

Модульная арифметика - это система арифметики для целых чисел, в которой числа «оборачиваются» при достижении определенного значения. Сначала нам нужно зафиксировать значение m, а затем вычислить по модулю целое число a, результатом будет остаток от деления. Например, если m = 7

вы можете видеть, что значение операции остается неизменным для i ‹m, когда оно достигает m, оно« оборачивается »и снова начинается с 0.

Теперь вы можете задаться вопросом… почему это связано с криптографией? Что ж, есть две причины, первая и самая важная - это то, что модульная арифметика позволяет строить простые алгебры, такие как группы или поля, которые являются строительными блоками криптографии. Вторая причина заключается в том, что он определяет конечный набор элементов (не бесконечный, как натуральные и действительные числа) и, следовательно, более управляемый на компьютере.

Операция по модулю определяет алгебраическую группу над суммой, поэтому, если мы возьмем предыдущий пример с m = 7, элементами группы будут (0, 1, 2, 3, 4, 5, 6), а операция будет сумма по модулю m. См. Таблицу умножения для получения информации о сумме операций по модулю:

Группа имеет следующие свойства

  • Закрытие элемента: для любых двух элементов a и b группы их операция возвращает c, который также находится в группа. Например. (5 + 3) (мод 7) = 1
  • Ассоциативность: для любых трех элементов a, b, c соблюдается (a + b) + c = a + (b + c). Очевидно, это происходит в операции суммирования.
  • Существование идентичности: существует элемент e в наборе такой, что для любого a в наборе a + e = a. В этом примере нейтральный элемент равен 0. Например. (5 + 0) (mod 7) = 5.
  • Обратный элемент: для любого элемента в группе a должен быть другой элемент b такой, что a + b = e. Например. обратное 5 равно 2 в нашем примере, потому что (5 + 2) (mod 7) = 0

Если группа коммутативна (т.е. a + b = b + a), то группа также называется коммутативной группой или абелевой.

Модульные операции над продуктом

Операция суммирования по модулю хорошо работает для создания группы, просто выберите m (подойдет любое m натуральных чисел), и вы попадете в область чисел (0, 1, 2,… , m-1) и операции по модулю с добавлением. Но что, если вместо суммы мы выберем продукт для определения группы ?. В этом случае нейтральный элемент равен 1, и мы обнаружим, что иногда мы не можем сформировать группу для произвольного m, например, возьмем m = 10, можете ли вы найти множитель, обратный 2, т. е. найти x такое, что

Из таблицы умножения вы можете видеть, что нет числа, умноженного на 2, которое дает нейтральное число умножения (1) в поле mod 10. Мы можем сказать, что эти элементы не образуют группу, потому что у нас отсутствуют обратные элементы на некоторых (если Вы проверяете, без инверсии - 2, 4, 5, 6, 8). Но хорошие новости: мы можем выбрать те элементы, которые имеют инверсию, и сформировать группу !. Позвольте мне составить таблицу умножения для такой группы в m = 10

Здесь вы можете проверить на глаз, что все элементы имеют другой элемент, умножение которого дает мультипликативную идентичность.

Теперь, есть ли способ узнать, имеет ли элемент обратный по модулю m? "Да"!. Пусть a и m будут целыми числами, например a ‹m, затем a * b (mod m) = 1 для некоторого целого числа b тогда и только тогда, когда gcd (a, м) = 1. На самом деле мы можем использовать расширенный алгоритм Евклида для вычисления обратного:

Если a имеет обратный по модулю m, то из указанного выше:

применив mod m к обеим частям уравнения, мы получим, что

и, следовательно, u является противоположностью a mod m. В особом случае, когда m является простым числом, мы будем обозначать его с этого момента p. В этом случае gcd (a, p) = 1, поскольку p делится только на себя и 1, поэтому все элементы (1, 2, 3,…, p-1) будет иметь инверсию и сформирует группу с произведением по модулю p. Простой способ вычислить мультипликативную обратную величину в группе простых чисел по модулю - использовать малую теорему Ферма: пусть p будет простым числом и пусть a будет любым целым числом, тогда

если a не делится на p, в противном случае указанное выше уравнение равно нулю. Затем, чтобы вычислить обратное к a, нам просто нужно умножить на a ^ (- 1) обе части уравнения.

так что теперь мы можем вычислить обратный по модулю p к a. Это может показаться сложным с точки зрения вычислений, но мы используем алгоритм быстрого включения, реализацию которого можно найти здесь.

Кольца и поля

До сих пор мы видели, как определять математические группы с суммой и умножением по модулю целого числа m. Мы можем построить другие алгебраические структуры, используя обе операции. Кольцо - это алгебраическая структура, состоящая из набора элементов S и двух операций (+, ·), которые удовлетворяют следующим свойствам

  • Множество с первой операцией образуют абелеву группу. т.е. (S, +) абелева
  • По второй операции есть ассоциативность. Т.е. если a, b, c являются элементами S, то (a · b ) · c = a · (b · c).
  • Наличие личности на второй операции. Т.е. существует такой элемент e, что для любого a в наборе a · e = a .
  • Вторая операция является распределительной по отношению к первой. Это a · (b + c) = a · b + a · c и (b + c) · a = b · а + в · а

Множество S = {0, 1, 2, 3} с модульными операциями сложения (+ mod 4) и умножения (· mod 4) является кольцом. Другой пример кольца - это набор матриц размерности 3x3 и вещественных коэффициентов. Вы можете проверить, выполнены ли все вышеперечисленные свойства (упражнение takehome)

Поле - это кольцо, такое, что вторая операция также удовлетворяет всем свойствам абелевой группы (после исключения элемента идентичности первой операции). Поле имеет мультипликативные инверсии, мультипликативную единицу и коммутативно.

Типичным примером поля является набор S = {0, 1, 2, 3,…, p}, где p - простое число, а операции - сложение и умножение по модулю p. Обратите внимание, что, поскольку p является простым числом, все элементы набора имеют мультипликативно обратный и, следовательно, составляют абелеву группу с операцией умножения. Это поле обычно обозначается как Fp. Набор матриц с размерностью 3x3 и действительными коэффициентами не является полем, поскольку некоторые матрицы не имеют мультипликативного обратного.

Выводы

Мы поняли, что такое арифметика по модулю и как с помощью такой операции мы можем определять группы, кольца и поля над конечными наборами элементов. Эти структуры постоянно появляются в криптографии, например, при работе с эллиптическими кривыми или в простых протоколах, таких как обмен ключами Диффи-Хеллмана.

В следующих статьях мы собираемся поработать с определенными алгебраическими структурами, чтобы понять ключевые концепции криптографии и многосторонних вычислений, чтобы окончательно понять немного больше о машинном обучении с сохранением конфиденциальности.

Спасибо за чтение! Если вам понравилась статья, пожалуйста, отметьте мое репо на github и дайте мне несколько аплодисментов в статье.