Означает ли «жесткий экземпляр» труднорешаемые проблемы, такие как предположение DDH (Decisional Diffie Hellman)?
В основном да, имеется в виду конкретное пример сложной проблемы - в случае DDH, например, это означает одну конкретную проблему $(г^а, г^б, г^с)$.
Сокращения работают, показывая, что если у вас есть метод/алгоритм для решения одной проблемы (обычно взлома протокола), то вы можете использовать тот же алгоритм для решения такой сложной проблемы, как DDH. Это доказывает, что взломать протокол не менее сложно, чем взломать DDH. И наоборот, если DDH жесткий, то протокол безопасный.
Редукции обычно начинаются с получения экземпляра сложной задачи, например задачи DDH. Тогда вы бы сказали что-то вроде "предположим $\mathcal{А}$ это противник/алгоритм, который может взломать протокол XXX с преимуществом $\эпсилон$". Затем вы должны показать, как вы можете превратить свой экземпляр проблемы DDH в $г^а, г^б, г^с$ в значения, которые вы могли бы дать $\mathcal{А}$, так что что бы $\mathcal{А}$ возвращается, вы узнаете ответ на экземпляр DDH (возможно, с меньшей вероятностью, чем $\эпсилон$, что известно как «потеря герметичности»). Это способ каким-то образом превратить экземпляр DDH во что-то, что вы можете передать $\mathcal{А}$ это называется «встраиванием» экземпляра проблемы DDH в ваш протокол.
Но вы бы рассчитали вероятности, и если бы вы могли показать, что ваше преимущество в решении задачи DDH с использованием $\mathcal{А}$ не является незначительным, если $\эпсилон$ то есть вы успешно продемонстрировали снижение безопасности вашего протокола от DDH.
