q-PKE
暗号仮定のひとつ。
例えば、有限体$ \Bbb{F}上の楕円曲線上の点$ P_i, \alpha P_i
を与えた時に、$ \alphaを知らずに点$ Q, \alpha Qを作ることを考えます。
もし$ \alphaの値を知っていたとすると、適当な点$ Sから$ \alpha Sを作ることが可能であるが、証明者には$ \alphaに関
して$ \alpha Pしか情報が与えられていません。(マスクしてあるので、ふたつの数に分けることはできない)
したがって、有限巡回群上の離散対数問題により点$ S, \alpha Sを作ることは困難であることがわかります
$ \alphaを知らずに点$ Q, \alpha Qを作る方法は一つだけ存在します。
それは、「$ P_i, \alpha P_iの線形結合からなる点$ Q, \alpha Qを作ること」です。
$ a_i \in \Bbb{F}を用いて、$ Q = a_1P_1 + a_2P_2 + \dots + a_qP_qとなる線形結合を作り、これより$ \begin{aligned} \hat{Q} &= a_1(\alpha P_1) + a_2(\alpha P_2) + \dots + a_q(\alpha P_q) \\ &= \alpha(a_1P_1 + a_2P_2 + \dots + a_qP_q) = \alpha Q \end{aligned}
が得られます。したがって$ \alphaを知らずに点$ Q, \alpha Qを作ることができました。
つまり、点$ Q, \alpha Qを作るには、与えられた点$ P_i, \alpha P_iの線形結合で作ることに制限されます。
以上がq-PKEの満たす仮定であり、この仮定の下で多項式評価の検証を行います。
再現ができるにしても、証明者が実際に$ g^{h(s)}を送ることを保証できていません。
Pinocchio Protocol
https://gyazo.com/0a6f3ce1848cb7832303dfdfce77e3f0
このプロトコルでは、使われるq-PDHやq-SDH、q-PKEはそれぞれDH、SDH、KEA仮定を一般化した離散対数問題です。q-SDHは現代のペアリングベース暗号の基礎になっており、qによってパラメータ化されたこれらの仮定は解くことがより難しいと知られています。これらの暗号学的仮定に依拠しながらzk-SNARKsを構築することで、安全かつ効率的な証明プロセスを実現することができます。
q型仮定
Pinocchioプロトコルはq型仮定の暗号学的仮定を用いています。従来の標準的な仮定（DDH、CDHなど）はパラメーター化されておらず、常に一定のサイズ（静的）です。
一方、非静的な$ q型仮定は$ qによってパラメーター化されています。証明が非静的なものに依存している場合、$ qは通常、攻撃者が行うクエリの数、入力サイズ、またはプロトコルに必要な計算ステップの数に関連します。クエリの数が多ければ多いほど仮定が強くなり、攻撃者がその仮定を破ることがより難しいと言われてるからです。
https://gyazo.com/621f94f08da2e9eeb1c699624f2ccd9c