Как открытый ключ GGH с плохой базой защищен от ортогонализации Грама-Шмидта?

Tarick Welling

31.05.2023, 13:47

Я читаю о криптографии на основе решетки. Когда я читал, я читал об ортогонализации Грам-Шмидта. Что позволяет превратить плохой базис в хороший или хотя бы ортогональный.

Теперь я читаю, что в схеме шифрования GGH хорошая основа используется в качестве закрытого ключа, а плохая основа используется в качестве открытого ключа.

Однако я думаю, что если открытый ключ известен, мы можем применить ортогонализацию Грама-Шмидта к этой плохой основе, чтобы сформировать лучшую, которая позволит нам найти точку, которая передается.

Как это может быть безопасно? Чего мне не хватает в моих мыслях?

Похоже, проблема в том, что с грамм-шмидтом у нас $О(п!)$ вычисления, потому что нам нужно сделать $n-1$ проекции для каждого добавленного измерения. И, как $О(п!)$ хуже, чем $ О (2 ^ п) $ мы все еще не находимся в полиномиальном времени в отношении наших вычислений.

0 + 0

решетка-крипто

Chris Peikert

31.05.2023, 19:40

Результатом процесса GSO является набор ортогональных векторов, но обычно они не являются *базисом решетки*. Применительно к «плохому» базису ортогональные векторы обычно имеют быстро уменьшающуюся длину. Это не позволяет им успешно восстановить ближайшую точку решетки к точке зашифрованного текста.

Ответить

Admin

Этот вопрос на других языках:

EN: How is GGH's bad basis public key safe from gram–schmidt orthogonalization?

TH: คีย์สาธารณะที่มีพื้นฐานไม่ดีของ GGH จะปลอดภัยจากการปรับมุมฉากด้วยแกรมมาได้อย่างไร

RO: Cum este protejată cheia publică de bază proastă a lui GGH de ortogonalizarea gramâschmidt?

RU: Как открытый ключ GGH с плохой базой защищен от ортогонализации Грама-Шмидта?

VI: Khóa công khai cơ sở xấu của GGH được an toàn như thế nào trước quá trình trực giao hóa gramâschmidt?

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

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