Рейтинг:0

Что означают звездочки и PPT в этой статье?

флаг eg

Я очень новичок в криптографии. Мне нужно прочитать газету.

введите описание изображения здесь

введите описание изображения здесь

Я совершенно не понимаю. Во-первых, что означает звездочка в $H:\{0,1\}^*\стрелка вправо \{0,1\}^k ?$.

Во-вторых, что здесь означает PPT? (Я искал в Интернете, но не получил удовлетворительного ответа.)

В-третьих, почему, если $b=1, s\leftarrow H(g^{ab})$, еще $s\leftarrow \{0,1\}^k$? Я понимаю шаги 1,2,3, но не понимаю шаги 4,5,6.

Может ли кто-нибудь помочь мне объяснить это? Я буду очень признателен.

PS: документ представляет собой «Практическое безопасное агрегирование для машинного обучения с сохранением конфиденциальности». https://eprint.iacr.org/2017/281.pdf

введите описание изображения здесь

JAAAY avatar
флаг us
Можете ли вы также опубликовать статью, которую вы читаете, потому что я хочу получить больше информации об этой хэш-функции $H$?
user900476 avatar
флаг eg
@JAAAY Конечно. Я отредактировал свой вопрос.
JAAAY avatar
флаг us
Честно говоря, я не могу понять, зачем использовать $H$.
user900476 avatar
флаг eg
@JAAAY Традиционно говорится, что предположение Диффи-Хеллмана не связано напрямую с хэш-функцией H на странице 3. Но я очень новичок в криптографии.
kelalaka avatar
флаг in
Вы когда-нибудь возглавляли [Kleene Star] (https://crypto.stackexchange.com/q/89067/18298) и видели на [Вики-странице] (https://en.wikipedia.org/wiki/Kleene_star)
Рейтинг:1
флаг us

Прежде всего, я раньше не видел такого определения предположения DDH. Вероятно, это что-то вроде предположения Hashed-DDH. Если у кого-то есть дополнительная информация для добавления или лучший ответ, я был бы рад прочитать об этом. Я отвечу на вопрос, не принимая во внимание существование $Ч$. Однако я отвечу на обозначения, используемые для его определения.

Во-первых, что означает звездочка в $H:\{0,1\}^ââ\{0,1\}^k$?

Он используется для определения хеш-функции $Ч$ который принимает на вход двоичную строку произвольной длины и возвращает двоичную строку постоянной длины. $*$ символ - это Клини звезда.

РРТ

Это означает алгоритм вероятностного полиномиального времени.

В-третьих, почему, если $b=1,sH(габ)$, еще $s{0,1}^k$? Я понимаю шаги 1,2,3, но не понимаю шаги 4,5,6

Здесь DDH определяется в терминах игры в неразличимость (IND-Game). Он производит два распределения вероятностей на основе того, является ли $b$ является $0$ или же $1$. Если $б=0$ то у противника $ млн $ ввод $(\mathcal{G}', g, q, H, g^{a}, g^{b}, g^{ab})$ иначе, если $б=1$ ввод противника $(\mathcal{G}', g, q, H, g^{a}, g^{b}, s \overset{\$}{\leftarrow} \{0,1\}^k) $. Как видите, единственная разница во входных данных противника — это последний аргумент. Определение рассматривает входные данные злоумышленника как распределения вероятностей и предполагает, что эти распределения неразличимы для противников PPT или, что то же самое, что их статистическое расстояние незначительно для противников PPT.

user900476 avatar
флаг eg
Большое спасибо! Не могли бы вы сказать мне, что означает поставить \$ на стрелку влево?
JAAAY avatar
флаг us
Это для равномерной выборки.
user900476 avatar
флаг eg
Большое спасибо! Я могу понять такие концепции, как обмен ключами Диффи-Хеллмана. Но это кажется намного сложнее, включая некоторые новые понятия, такие как противник для меня.
JAAAY avatar
флаг us
В зависимости от вашего фона вы можете начать https://toc.cryptobook.us/
user900476 avatar
флаг eg
Большое спасибо. Могу я спросить, почему противник знает G', g, q, H, $g^a$ и $g^b$? И если он знает g, q, $g^a$ и $g^b$, разве он не должен знать $g^{ab}$ (что отличается от случайного s)?
JAAAY avatar
флаг us
Нет. Если он знает, например, $x=g^a$ и $y=g^b$ в мультипликативной группе простого порядка, он не может вывести $x^b$ или $y^a$. В этом вся концепция вычислительного предположения Диффи Хеллмана. Здесь будьте осторожны $x \cdot y = g^a \cdot g^b = g^{a+b}$. Также будьте осторожны, поскольку в вашем примере у вас есть Децизионное предположение Диффи Хеллмана, которое является аналогичным, но более сильным предположением.Вы можете прочитать больше [здесь] (https://crypto.stackexchange.com/questions/1493/what-is-the-relation-between-discrete-log-computational-diffie-hellman-and-deci).
user900476 avatar
флаг eg
Я понял, противник знает только $x=g^a$ и $y=g^b$, но не знает $G', g, q, H$, верно? Я увидел функцию на шаге 5 $M(G', g, q, H, g^a, g^b, s)$ и подумал, что противник знает все параметры.
JAAAY avatar
флаг us
Нет, $Gâ²,g,q,H$ являются общедоступными параметрами. Согласно принципам Керкхоффов, он имеет к ним доступ. Единственное, чего он не знает, это $a$ и $b$, поэтому он не может вывести $g^{ab}$.
JAAAY avatar
флаг us
Проще говоря, в $x=g^a$. $x$ — это открытый ключ, а $a$ — это закрытый ключ. Противник имеет доступ к общедоступной информации.
Manish Adhikari avatar
флаг us
Я почти уверен, что определение предположения DDH не использует этот хэш. Однако это определение кажется более непосредственно связанным с безопасностью обмена ключами DH, чем с предположением CDH.
JAAAY avatar
флаг us
Спасибо за ваше подтверждение, потому что я немного волновался. Хотя это странное обозначение и определение, статья принята IACR :|

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

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