3for / Compressed_sigma-protocol

Rust implementation for Compressed Σ-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics
6 stars 1 forks source link

Weak Fiat-Shamir transformation in zk_protocol_7 #1

Open Falicitas opened 1 year ago

Falicitas commented 1 year ago

The paper uses polynomial amortization trick to maintain the communication cost of many nullity checks in a single nullity-check plus one additional $\mathbb Z_q$ element from $\mathcal{V}$ to $\mathcal{P}$ (the challenge $\rho$). Since $\rho$ is generated after committing to secret $\mathbf x$, it should have been appended $[\mathbf x]$ to transcript (applied to FS transformation) before obtaining Pi_NULLITY_Proof. So much for adding P_secure (Essentially equals to P_vec) is enough to convert the code into Strong Fiat-Shamir Transformation. I did some math and ensured that it may has no need to append $L_i$ form to transcript, for $\rho = \operatorname{HASH}([\mathbf x],\cdot)$ is suffice.

TODO: It would also affect zk_amortized_7, but due to lack of research about amortized version of the paper, the pull request related to this issues would only change zk_protocol_7.

Falicitas commented 1 year ago

2 is actually just added lines 81-82, 118-121, 132-134 (lastest version), and other changes have happened by the modification by Rustc formatter LOL.