Прежде всего, я раньше не видел такого определения предположения 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.