---
# System prepended metadata

title: VLRGS 3.1
tags: [paper, VLRGS]

---

# VLRGS 3.1
###### tags: `VLRGS` `paper`

在此先說一下,這禮拜會去打疫苗所以進度應該會變少~~絕對不是偷懶的藉口~~。
### Traceability
這部分提到由於在滿足NIZK滿足soundness以及OTS和簽章滿足EUF-CMA security的情況下,要捏造$\mathrm {cert^*}$和⟨$\mathrm{ek^*,vk^*}$⟩是很困難的。
因此Scheme 1滿足traceability。

這裡的證明很搞剛地分成6個cases和5個types,下面基本上分別討論5個cases的狀況。

**Proof 3.5**
NIZK的soundness性質
讓$\mathrm Pr[\mathtt{E_1}]\leq\mathrm{Adv}^{sound}_{\mathcal P_L,\mathcal B1}(\lambda)$,
我的理解是如果那一串state不屬於L,那能騙過NIZK的機率就趨近於0。

**Proof 3.6**
這裡的情況是state屬於L了,
但i是有問題的,也就是$(\mathrm{ek^*,vk^*})\ne(\mathrm{ek_i,vk_i})$
那這裡就不能丟到Sign的oracle 導致
$\mathrm{Pr}[\mathtt{E_2}]\le\mathrm{Adv}^{unforge}_{\mathcal{SIG,B_2}}(\lambda)$,
同樣是在i有問題時要過NIZK也是很難的。

**Proof 3.7**
這裡整段都是**粗體**,害我怕怕的。
如果說3.6針對NIZK,3.7針對Sign,那這裡就是針對OTS了。
值得一提的是這裡還加入了j,也就是query上的關係。
總結就是要挑戰OTS還要先搞對query j。
注意在此處$\mathrm{vk_{ots}}=\mathrm{vk^*_{ots}}$且$(m,\sum)\ne(m^*,\sum^*)$
上面是討論i得出unforge,這裡再討論j得出strong-unforge。
得到$(1/q_\mathtt{GS.Sign})· \mathrm{Pr}[\mathtt{E3}]\le \mathrm{Adv}^{\bf{strong-unforge}}_{\mathcal{OTS,B_3}}$
可以把query那一項移到右邊得到Lemma的式子。

**Proof 3.8**
這段有夠長的= =。

在這裡adversary能知道所有的gsk[$i$]但不能算出gsk[$i^*$]。
跟3.7類似但條件有點差別。

上面是$\mathrm{vk_{ots}}=\mathrm{vk^*_{ots}}$且$(m,\sum)\ne(m^*,\sum^*)$
這裡是$\mathrm{vk_{ots}}\ne \mathrm{vk^*_{ots}}$或$(m,\sum)=(m^*,\sum^*)$

討論$\mathrm {vk^*_{ots}}$不是一個queried即使$(m,\sum)=(m^*,\sum^*)$時。
~~當$i\ne i^*$時adversary會無法issue signing query,
但若$i= i^*$會得到矛盾,所以這種狀況不會發生。
簡單來說這裡i怎麼取都會有問題。(應該是討論and的狀況)~~

隔週回來看一下,應該是$i=i^*$下面的機率才會是1/n。
但這種情況不會在$(i^*,m^*,\sum^*)=(i,m,\sum)\in \mathsf {QL}$下發生。


這裡若$\mathsf {GS.Open}(\mathrm {gpk,grt,m^*,\sum^*})=i^*$那$(\mathrm {vk^*_{ots}},\sigma^*)$是一個偽造的簽章。
$\mathsf {GS.Open}(\mathrm {gpk,grt,m^*,\sum^*})=i^*$的機率是1/n
得到$(1/n) · \mathrm{Pr}[\mathtt {E_4}]\le \mathrm{Adv}^{unforge}_{\mathcal {SIG,B_4}}(\lambda)$

這裡寫得很艱澀...。

**Proof 3.9**
這裡說state不屬於L但$i^*\in \mathrm{RU^*}$。
但這會令$\mathsf{GS.Verify}(\mathrm{gpk,\{grt}[i^*]\},m^*,\sum ^*)=0$導致矛盾。
機率$\mathrm{Pr[\mathtt E_5]=0}$,應該有$i^*\in \mathrm{RU^*}$機率就會是0。

最後加一加就會得到$\mathrm{Adv^{trace}_{\prod_1,\mathcal A}}(\lambda,n)\le\mathrm{Adv}^{sound}_{\mathcal P_L,\mathcal B1}(\lambda)+\mathrm{Adv}^{unforge}_{\mathcal{SIG,B_2}}(\lambda)+q_{\mathsf {GS.Sign  }}·\mathrm{Adv}^{{strong-unforge}}_{\mathcal{OTS,B_3}}+n·\mathrm{Adv}^{unforge}_{\mathcal {SIG,B_4}}(\lambda)$

在滿足NIZK的soundness和digital signature的EUF-CMA security可以滿足traceability。

硬著頭皮寫好像有點寫太長了...
