Как найти экстрактор в предположении о знании экспоненты?

От Михир Белларе бумага

Позволять $q$ быть простым таким, что $2q +1$ тоже простое, и пусть $г$ быть генератором порядка $q$ подгруппа ${Z^â}_{2q+1}$. Предположим, нам дан ввод $q$, $г$, $г^а$ и хочу вывести пару $(С, Y)$ такой, что $ Y = С ^ а $. Один из способов сделать это — выбрать несколько $c \в Z_q$, позволять $С = г^с$, и разреши $ Y = (г ^ а) ^ с $. Интуитивно KEA1 можно рассматривать как говорящий, что это «единственный» способ произвести такую ​​пару. Предположение фиксирует это, говоря, что любой противник, выводящий такую ​​пару, должен «знать» показатель степени $с$ такой, что $г^с = С$. Формализация требует наличия «экстрактора», который может возвращать $с$.

Я понимаю, как найти пару $(С, Y)$ такой, что $ Y = С ^ а $ выбрав любой $c \в Z_q$

Однако я не понимаю, что здесь означает «экстрактор». Означает ли это, что пара $(С, Y)$ нужно найти $с$ которая использовалась для расчета $С$? Если да, то как нам найти $с$ дано только что $(С, Y)$?

Или это означает что-то другое?

Если мы посмотрим на ссылки бумага 11, все будет понятнее и так мы читаем бумаги; глядя на ссылки.

Сокращения

• ДГК: предположение Диффи-Хеллмана
• SDHA-1: Сильное предположение Диффи-Хеллмана -1

Допущение 8 относится к тому, о чем говорит KEA1; (СДГА-1). С предложением 9 показано, что при SDHA-1 выполняется DHA ( SDHA-1 $\подразумевает$ ДГК). KEA-1 является повторением этого предложения;

КЕА1: Для любого противника $А$ который принимает входные данные $ д, г, г ^ а $ и возвращается $(С, Y)$ с $ Y = С ^ а $ существует "экстрактор" $\бар{А}$ , который при тех же входных данных, что и $А$ возвращается $с$ такой, что $г^с = С$. т.е. такой $\бар{А}$ называется экстрактором.

То есть слова, если противник $А$ решает SDHA-1, то $\бар{А}$ (так называемый экстрактор) может решить DHA.