Abstract. We present a practical construction of an additively homomorphic commitment scheme
based on structured lattice assumptions, together with a zero-knowledge proof of opening knowledge.
Our scheme is a design improvement over the previous work of Benhamouda et al. in that it is not
restricted to being statistically binding. While it is possible to instantiate our scheme to be statistically
binding or statistically hiding, it is most efficient when both hiding and binding properties are only
computational. This results in approximately a factor of 4 reduction in the size of the proof and a factor
of 6 reduction in the size of the commitment over the aforementioned scheme
5.3 Further Improvements
It is possible to reduce the size of the proofs of the protocols in Figures 4 and 6 by using the
compression techniques in [GLP12,BG14]. The main idea in those works is that the prover does
not need to send the part of the proof that gets multiplied by the identity matrix part of A1, and
the verifier only checks an approximate equality. A very rough calculation shows that one could
reduce the proof size in the optimal protocol in Figure 4 to 4.4KB and to 15.8KB in the protocol
from [BKLP15].
One can also use technique from [DKL+18] to reduce the size of the commitment in our optimal
protocol in Figure 4 (it’s unclear if this can also be applied to [BKLP15]). The idea is that one
can drop the low-order bits of the commitment c1 and the SKS2/ SIS problems would still remain
almost as hard as before. This technique can reduce the commitment size to around 6KB.
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
相关推荐: Codeforces Round #375 (Div. 2) — C. Polycarp at the Radio（水题）
大体题意： 给你n 个数，要求1~m每个数出现次数的最小值尽可能大，要求你修改n个数，要改的次数尽可能小，输出最小值的最大可能和最少修改次数，并把改的数组输出出来！ 思路： 开始没看到次数尽可能少，wa了一次！ 想一想就知道，最大可能值肯定是 n/m 那么直接…
