Рейтинг:3

Какая наименьшая, циклическая в 3-х направлениях, непротиворечивая структура случайных величин может быть скрыта на машине злоумышленников? (некоторое сравнение)

флаг at

Или более общий каждый член может быть частью до трех двумерных локально-евклидовых плоскостей двух разных измерений каждая.
[рис1]
(каждая из этих плоскостей циклична в двух ортогональных направлениях, как тор)

Учитывая только одного члена, это может выглядеть как сеть узлов:
(здесь отображается только один узел с некоторым соседством. У этих соседей снова есть соседи, которые здесь не отображаются)
(слева: 1 плоскость, справа пересечение 2 плоскостей)
введите описание изображения здесь введите описание изображения здесь пересечение 3-х плоскостей:
введите описание изображения здесь


Несмотря на это, должен быть какой-то детерминированный способ сопоставить окрестности узла с планарными графами на этих трех двумерных евклидовых плоскостях (с постоянной плотностью узлов). Таким образом, соседи по соседним узлам, как правило, тоже являются соседями и не имеют $n$-рост соседства, который нуждается, например. гиперболическое пространство для представления.
Начиная с одного узла $n$ и (в основном) следование одному направлению прогрессии снова приведет к тому же узлу после (в лучшем случае) $C_n$ шаги. Так что это циклично с длиной цикла $C_n$. В лучшем случае это одинаково для всех узлов во всех направлениях. Но, чтобы быть менее строгим, возможны некоторые вариации, если длина цикла аналогична ближайшим узлам.

Цель:
Нахождение такой структуры, которая минимизирует длину цикла $С$ (Лучший $\le 2^{50}$) и общее количество узлов $N$ (лучший случай $N=C^3$ или же $\le 2^{150}$), максимально усложняя вычисление отношения между двумя случайными узлами (лучше всего $\ge О(С^2)$ и $O(\sqrt[3]{N^2})$ или в цифрах $\ge 2^{100}$)


Специализируется на криптографических методах:

Насколько мне известно, в криптографии есть только структуры более специализированные или отчасти более общие, чем такая структура, описанная выше.
Если, например. количество соседей от одного узла устанавливается равным фиксированному значению 6, мы получаем такую ​​структуру:
(слева: пересечение 3 плоскостей в одном узле/числе, справа: каждый узел/число имеет здесь эту структуру)
пересечение 3-х плоскостей в одном узле/номере. Каждый генератор равен одному направлению прогрессии. Плоскость - это все возможные значения с использованием двух генераторов кроме как в более общей структуре выше, любое число/узел имеет здесь ту же структуру. Таким образом, каждое число имеет 3 * 2 возможности прогрессии с 3 генераторами и их обратными значениями.
Этого можно достичь с помощью 3 генераторов и подходящего $\bmod P$ как указано ниже.
Для каждого типа я добавлю несколько причин, по которым это не работает, и (мои) связанные темы для более подробной информации.


Сравнение с протестированными криптографическими методами:

  1. Три генератора $q,r,s$ с $\bmod P = 2\cdot Q \cdot R \cdot S +1$ и $q^Q \эквив r^R \эквив s^S \эквив 1 \bmod P$ $\текст{ } $[1]

    • $-$ $P$ должен быть очень большим, чтобы избежать факторизации $\гг 2^{150}$
    • $-$ зная размеры циклов, это можно свести к гораздо более простой задаче с Алгоритм Полига-Хеллмана
  2. Эллиптические кривые с 3 образующими $F,G,H$ и с этими значениями $i \cdot F + j \cdot G + k \cdot H$ [1] [2]

    • $-$ размер цикла для каждого направления по всему домену
    • $+$ требуется лишь относительно небольшое количество
    • $-$ но все же размер домена/цикла $2^{200}$ требуется (только размер целевого цикла $2^{50}$)
  3. AES или аналогичный блочный шифр:

    • $-$ разделены на несколько циклов с неизвестным размером, известно только распределение [1]
    • $-$ по одному на направление? $\стрелка вправо $ область $2^{300}$ необходимо и может быть сведено к одномерной задаче
    • $-$ объединить 3 AES с одним членом? $\стрелка вправо $ большой $n$-соседство, аналогично простому использованию случайных значений $\стрелка вправо $ совпадение при чередовании AES128 (режим ECB) можно найти после $\приблизительно {2^{64}}$ шаги прогресса [2]
  4. 3-направленная последовательность $ s_ {ijk} знак равно s_0 ^ {\ textstyle \ beta ^ i \ gamma ^ j \ delta ^ k} \ bmod (N = P \ cdot Q) $ - трудно решить, потому что $\фи(N)$ неизвестный

    • за $N=(2\cdot p +1)\cdot (2\cdot q +1)$ с род. $\бета, \гамма, \дельта$ первобытные корни $р,к$ [1]
      • $+$ $O(\sqrt[2]{C^3})$ (насколько мне известно)
      • $-$ но только если $\фи(N)$ неизвестно. Достигать $100$-бит безопасности $N$ нужно быть рядом $2000$-битный размер и с этим $р, д$ и размер цикла также увеличивается
    • за $N=(2\cdot p_s \cdot p_b +1)\cdot (2\cdot q_s \cdot q_b +1)$ спроецировано на $\frac{(p_s-1)}{2}\cdot \frac{(q_s-1)}{2}$ с $\gcd(e,\phi(N)) \ne 1$ но $е$ трудно разложить на множители [2], $\бета,\гамма,\дельта$ связанные с мощностью $е$
      • $+$ $O(\sqrt[2]{C^3})$ (насколько я знаю) если $С$ неизвестный
      • $-$ почти мгновенно, если длина цикла $С$ известно (что легко получить для целевых значений). $С$ нужно было бы $>2^{100}$
  5. Отражение геометрии над конечным полем (треугольники [1], тетраэдр [2] - оба без решения) или более общая цепочка матричного умножения. Чтобы $n$-окрестность не растет слишком быстро, они должны быть инвариантны относительно порядка их умножения. Поэтому их можно сократить до $A^iB^jC^k$ - но пока я не смог найти таких матриц, которые бы тоже делали $ я, у, у $ трудно определить

    • $-$ либо слишком много $n$-соседи или слишком легко вычислить индексы

Вопрос: Можно ли сделать лучше? Может меньше чем $N=2^{200}$ значения распределяются по трем измерениям с размером цикла менее $С=2^{65}$ каждый, в то время как нахождение отношения между двумя членами действительно занимает как минимум $2^{100}$ шаги вычисления (для большинства случаев)?
Для этого нужно быть сложнее, чем $O(\sqrt{N})$$N<2^{200}$ и $С<2^{65}$)


Дополнительные примечания:

  • помимо 3-х направлений в прямом направлении также должны существовать их обратные направления в обратном направлении. Все они должны иметь примерно одинаковое время вычислений.
  • в лучшем случае все действительные случайные значения могут генерировать одну и ту же структуру. Но маленький($<\около 10$) также возможен набор непересекающихся подобных структур (как в 4.).
  • в случае использования будет сгенерировано случайное начальное значение и итеративно использовано его ближайшими соседями (после этого соседи соседей и так далее).В конечном итоге они приводят (после (почти) бесконечного времени генерации) к одной и той же последовательной (секретной) структуре. Должно быть как можно сложнее расставить приоритеты в любом направлении развития, чтобы быстрее достичь определенного целевого значения. Так что генерировать просто случайные точки не получится. Следующие сгенерированные значения всегда должны быть близки к тем, которые уже были сгенерированы. Это также означает создание $я-$th следующее значение не требуется (как это обычно можно сделать с генераторами), достаточно одного шага в одном направлении (как в AES/блочном шифре)
  • нет функции растяжения, как только считать каждый $n$-th член как действительный (для повышения безопасности (больший размер члена $N$) с постоянным истинным размером члена $\frac{N}{n}$). Это уже будет использоваться. С технической точки зрения должно быть возможно (если кто-то действительно этого хочет) генерировать полный цикл в одном направлении на стандартном ПК за небольшое количество ЦП-лет. При этом размер цикла должен быть меньше, чем $2^{60}$. Но найти соотношение между любыми двумя целевыми значениями будет невозможно в ближайшие 50 лет. Найти его для некоторых комбинаций — это хорошо, даже хорошо иметь. Насколько я знаю о $2^{100}$ шагов вычислений является подходящей границей для этого.
  • шаг вычисления означает любую базовую операцию (+-*/^), применяемую к двум значениям $<N$
  • эти члены структуры могут быть чем угодно, например, числами, векторами, строками, матрицами, даже художественными изображениями ascii. Должна быть только какая-то функция для генерации псевдослучайного значения без утечки информации, связанной с безопасностью. Создание нескольких из них не должно раскрывать никакой информации об отношениях между ними. Так что-то вроде $g^r$ с генератором $г$ и $г$ случайное значение не сработает. Генерация их не должна быть такой быстрой, $<20$сек на стандартном ПК достаточно.
  • в целевом варианте использования эти члены будут служить в качестве семян для ГСЧ. Структура этих членов как расположение этих семян.Некоторые последовательности случайных чисел, сгенерированные этими ГСЧ, будут лучше, чем другие. Если были найдены отдельные очень хорошие из них, их должно быть как можно сложнее соединить (= вычислить одно из другого).
  • противники будут равны обычному пользователю. У него есть доступ ко всему исходному коду, переменным времени выполнения, ключам, переменным и так далее. Как целевая длина цикла $С$ достаточно мала, мы также можем считать, что она известна противнику.
  • еще несколько проверенных методов: клеточный автомат (без обратного), тесселяция (не детерминированная или слишком простая для решения), гомоморфное шифрование (без переполнения/цикла, не работает, если все на ПК противника).

Обновлять: Связано с комментарием fgrieu:

Нам нужен неориентированный связный граф из N узлов [?с представлением вершины n в виде тройки координат (целые ли координаты?)?]

Да, но эти координаты не имеют глобального происхождения. Если мы хотим найти путь из $n_1$ к $n_2$ мы начинаем в $n_1$ и вычислить его окрестности. Те имеют координаты, связанные с $n_1$. Например. $(0,1,0)$ может означать, что мы начали с $n_1$ и применил прогрессию для 2-го измерения один раз.
Смещение узла между $n_1$ и $n_2$ симметричен и инвариантен для любого $n_i$ мы исходим из.
Поскольку они цикличны в каждом измерении, смещение может быть только $+/-$ половина размера цикла (в евклидовом пространстве) для каждой координаты.
Целые числа не нужны. Действительные числа также работают, поскольку длинные компьютеры могут аппроксимировать их достаточно хорошо, чтобы различать разные узлы.
Сеть лежит на 3-Тор поэтому мы можем интерпретировать смещение также как разницу углов.

Чтобы было ясно, просто генерировать случайные координаты не получится. Они всегда должны быть рядом с уже сгенерированными. Единственным исключением является начальный узел. Они должны быть сгенерированы случайным образом. Учитывая два таких начальных узла (и все внутренние переменные), не должно быть никаких намеков на лучшее направление развития.

Должна быть какая-то процедура для перехода от одного узла к другому вдоль ребер графа, что при повторении приводит к циклу длины $C_n$ при запуске с н

Начинается с $n$ и (в основном) двигаясь вперед в одном направлении (и, например, не так много раз назад), мы можем достичь $n$ снова после $C_n$ шаги. Это должно быть возможно как минимум для 2 ортогональных направлений и не более чем для 3 (вперед и назад каждое).

Учитывая две случайные вершины, должно быть трудно найти путь между ними, требуя усилий на мелодии. $\Омега(\sqrt[3]{N^2})$

Это также может быть сложнее, но я думаю, что это невозможно в обычных криптографических структурах с фиксированным соседством. В общих сетях может быть сложнее. Основная проблема заключается в том, чтобы найти то, что не сводится к одномерной проблеме размера. $С$ поскольку целевое значение слишком мало для этого. Это также означает $С$ известен противнику (поскольку его можно быстро проверить).
Но если я не путаю обозначения, это должно быть $о(С^2+С)$ (для фиксированной окрестности всегда возможно пересечение линии и плоскости) и $\Омега(\sqrt{N})$ и $\Омега(С^{1.5})$ (среднее количество шагов) еще $Н,С$ нужно быть слишком большим.

$C_n$ нужно быть в тонусе $O(\sqrt[3]{N})$ [но это верхняя граница или нижняя граница для Cn?].

Обе. Не так, как показанный метод с использованием EC, где $N\ок C_n$ а не как метод с использованием двух AES, где $C_n$ может быть $1$.
Может быть что-то вроде $O(\sqrt[3]{N}\cdotf(\log(N)))$. Основная цель – получить $\max(C_n) < 2^{65}$$\мин(C_n)\ge 2^{50}$ (иначе легко afaik)) с $N<2^{200}$ и нахождение из случайных $n_1$ к $n_2$ должно занять (в большинстве случаев) не менее $2^{100}$ шагов прогрессии (но возможно, до $\около 10$ подмножества в порядке).


связанный комментарий JAAAY:

евклидова локальность или гиперболические плоскости

Другими словами, рост района не может быть слишком быстрым.
Имея (много свободного времени), мы могли бы нарисовать структуру соседства на листах бумаги (=евклидова плоскость).
Мы можем измерить (евклидово) расстояние между узлами с помощью нашей линейки. Независимо от того, сколько соседей соседей мы рисуем, среднее расстояние между узлами должно оставаться (примерно) равным.
Если мы свяжем два противоположных края бумаги вместе, мы сможем имитировать свойство цикличности для одного направления. С учетом этой опции (минимальное) расстояние между двумя конкретными узлами всегда равно - независимо от того, где мы начали рисовать эту структуру. (После рисования полного цикла в двух направлениях мы должны обрезать бумагу до нужного размера. На границе мы продолжаем измерение на противоположной границе бумаги).

Один узел может находиться не более чем на 3 листах. Если несколько чисел находятся на двух разных листах (2-тора), то все они лежат на одной линии (1-тор) — как на пересечении двух 2-торов.

J. Doe avatar
флаг at
также приветствуются вопросы о деталях или о том, что имеется в виду, советы по лучшему/краткому описанию проблемы или идеям, которые могут сработать.
fgrieu avatar
флаг ng
Предварительное резюме/просьба о разъяснении. Нам нужен неориентированный связный граф из $N$ узлов [?с представлением вершины $n$ в виде тройки координат (целые ли координаты?)?]. Учитывая две случайные вершины, должно быть трудно найти путь между ними, требуя усилий в размере $\Omega(\sqrt[3]{N^2})$. Должна быть какая-то процедура перехода от одного узла к другому по ребрам графа, которая при повторении приводит к циклу длины $C_n$ при запуске из $n$. $C_n$ должно быть равно $\mathcal O(\sqrt[3]N)$ [но это верхняя или нижняя граница для $C_n$?].
JAAAY avatar
флаг us
Ответ на комментарий @fgrieu очень поможет.
JAAAY avatar
флаг us
Кроме того, вы, кажется, имеете математическое образование, и я не думаю, что большинство людей здесь смогут понять термины евклидовой локальности или гиперболических плоскостей, которые вы упоминаете:/
J. Doe avatar
флаг at
(сделал некоторые обновления, связанные с комментарием)

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.