More Like this

1. An Efficient ZK Compiler from SIMD Circuits to General Circuits

   https://doi.org/10.1007/s00145-024-09531-4  

   Bui, Dung; Chu, Haotian; Couteau, Geoffroy; Wang, Xiao; Weng, Chenkai; Yang, Kang; Yu, Yu (January 2025, Journal of Cryptology)

   Abstract We propose a generic compiler that can convert any zero-knowledge (ZK) proof for SIMD circuits to general circuits efficiently, and an extension that can preserve the space complexity of the proof systems. Our compiler can immediately produce new results improving upon state of the art.By plugging in our compiler to Antman, an interactive sublinear-communication protocol, we improve the overall communication complexity for general circuits from$$\mathcal {O}(C^{3/4})$$ $O\left(C^{3/4}\right)$to$$\mathcal {O}(C^{1/2})$$ $O\left(C^{1/2}\right)$. Our implementation shows that for a circuit of size$$2^{27}$$ $2^{27}$, it achieves up to$$83.6\times $$ $83.6\times$improvement on communication compared to the state-of-the-art implementation. Its end-to-end running time is at least$$70\%$$ $70\%$faster in a 10Mbps network.Using the recent results on compressed$$\varSigma $$ $\Sigma$-protocol theory, we obtain a discrete-log-based constant-round zero-knowledge argument with$$\mathcal {O}(C^{1/2})$$ $O\left(C^{1/2}\right)$communication and common random string length, improving over the state of the art that has linear-size common random string and requires heavier computation.We improve the communication of a designatedn-verifier zero-knowledge proof from$$\mathcal {O}(nC/B+n^2B^2)$$ $O(nC/B+n^2{B}^2)$to$$\mathcal {O}(nC/B+n^2)$$ $O(nC/B+n^2)$.To demonstrate the scalability of our compilers, we were able to extract a commit-and-prove SIMD ZK from Ligero and cast it in our framework. We also give one instantiation derived from LegoSNARK, demonstrating that the idea of CP-SNARK also fits in our methodology. 

   more » « less
2. Shorter ZK-SNARKs from square span programs over ideal lattices

   https://doi.org/10.1186/s42400-024-00215-x  

   Lin, Xi; Cao, Heyang; Liu, Feng-Hao; Wang, Zhedong; Wang, Mingsheng (December 2024, Cybersecurity)

   Abstract Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) are cryptographic protocols that offer efficient and privacy-preserving means of verifying NP language relations and have drawn considerable attention for their appealing applications, e.g., verifiable computation and anonymous payment protocol. Compared with the pre-quantum case, the practicability of this primitive in the post-quantum setting is still unsatisfactory, especially for the space complexity. To tackle this issue, this work seeks to enhance the efficiency and compactness of lattice-based zk-SNARKs, including proof length and common reference string (CRS) length. In this paper, we develop the framework of square span program-based SNARKs and design new zk-SNARKs over cyclotomic rings. Compared with previous works, our construction is without parallel repetition and achieves shorter proof and CRS lengths than previous lattice-based zk-SNARK schemes. Particularly, the proof length of our scheme is around$$23.3\%$$ $23.3\%$smaller than the recent shortest lattice-based zk-SNARKs by Ishai et al. (in: Proceedings of the 2021 ACM SIGSAC conference on computer and communications security, pp 212–234, 2021), and the CRS length is$$3.6\times$$ $3.6\times$smaller. Our constructions follow the framework of Gennaro et al. (in: Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pp 556–573, 2018), and adapt it to the ring setting by slightly modifying the knowledge assumptions. We develop concretely small constructions by using module-switching and key-switching procedures in a novel way. 

   more » « less
3. Improved Merlin–Arthur Protocols for Central Problems in Fine-Grained Complexity

   https://doi.org/10.1007/s00453-023-01102-6  

   Akmal, Shyan; Chen, Lijie; Jin, Ce; Raj, Malvika; Williams, Ryan (February 2023, Algorithmica)

   Abstract In a Merlin–Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability 1, and rejects invalid proofs with probability arbitrarily close to 1. The running time of such a system is defined to be the length of Merlin’s proof plus the running time of Arthur. We provide new Merlin–Arthur proof systems for some key problems in fine-grained complexity. In several cases our proof systems have optimal running time. Our main results include:Certifying that a list ofnintegers has no 3-SUM solution can be done in Merlin–Arthur time$$\tilde{O}(n)$$ $\tilde{O}\left(n\right)$. Previously, Carmosino et al. [ITCS 2016] showed that the problem has a nondeterministic algorithm running in$$\tilde{O}(n^{1.5})$$ $\tilde{O}\left(n^{1.5}\right)$time (that is, there is a proof system with proofs of length$$\tilde{O}(n^{1.5})$$ $\tilde{O}\left(n^{1.5}\right)$and a deterministic verifier running in$$\tilde{O}(n^{1.5})$$ $\tilde{O}\left(n^{1.5}\right)$time).Counting the number ofk-cliques with total edge weight equal to zero in ann-node graph can be done in Merlin–Arthur time$${\tilde{O}}(n^{\lceil k/2\rceil })$$ $\tilde{O}\left(n^{\lceil k/2\rceil }\right)$(where$$k\ge 3$$ $k\ge 3$). For oddk, this bound can be further improved for sparse graphs: for example, counting the number of zero-weight triangles in anm-edge graph can be done in Merlin–Arthur time$${\tilde{O}}(m)$$ $\tilde{O}\left(m\right)$. Previous Merlin–Arthur protocols by Williams [CCC’16] and Björklund and Kaski [PODC’16] could only countk-cliques in unweighted graphs, and had worse running times for smallk.Computing the All-Pairs Shortest Distances matrix for ann-node graph can be done in Merlin–Arthur time$$\tilde{O}(n^2)$$ $\tilde{O}\left(n^2\right)$. Note this is optimal, as the matrix can have$$\Omega (n^2)$$ $\Omega \left(n^2\right)$nonzero entries in general. Previously, Carmosino et al. [ITCS 2016] showed that this problem has an$$\tilde{O}(n^{2.94})$$ $\tilde{O}\left(n^{2.94}\right)$nondeterministic time algorithm.Certifying that ann-variablek-CNF is unsatisfiable can be done in Merlin–Arthur time$$2^{n/2 - n/O(k)}$$ $2^{n/2-n/O\left(k\right)}$. We also observe an algebrization barrier for the previous$$2^{n/2}\cdot \textrm{poly}(n)$$ $2^{n/2}·\text{poly}\left(n\right)$-time Merlin–Arthur protocol of R. Williams [CCC’16] for$$\#$$ $\#$SAT: in particular, his protocol algebrizes, and we observe there is no algebrizing protocol fork-UNSAT running in$$2^{n/2}/n^{\omega (1)}$$ $2^{n/2}/n^{\omega \left(1\right)}$time. Therefore we have to exploit non-algebrizing properties to obtain our new protocol.Certifying a Quantified Boolean Formula is true can be done in Merlin–Arthur time$$2^{4n/5}\cdot \textrm{poly}(n)$$ $2^{4n/5}·\text{poly}\left(n\right)$. Previously, the only nontrivial result known along these lines was an Arthur–Merlin–Arthur protocol (where Merlin’s proof depends on some of Arthur’s coins) running in$$2^{2n/3}\cdot \textrm{poly}(n)$$ $2^{2n/3}·\text{poly}\left(n\right)$time.Due to the centrality of these problems in fine-grained complexity, our results have consequences for many other problems of interest. For example, our work implies that certifying there is no Subset Sum solution tonintegers can be done in Merlin–Arthur time$$2^{n/3}\cdot \textrm{poly}(n)$$ $2^{n/3}·\text{poly}\left(n\right)$, improving on the previous best protocol by Nederlof [IPL 2017] which took$$2^{0.49991n}\cdot \textrm{poly}(n)$$ $2^{0.49991n}·\text{poly}\left(n\right)$time. 

   more » « less
4. Search for supersymmetry in final states with missing transverse momentum and three or more b-jets in 139 fb$$^{-1}$$ of proton–proton collisions at $$\sqrt{s} = 13$$ TeV with the ATLAS detector

   https://doi.org/10.1140/epjc/s10052-023-11543-6  

   Aad, G.; Abbott, B.; Abbott, D. C.; Abeling, K.; Abidi, S. H.; Aboulhorma, A.; Abramowicz, H.; Abreu, H.; Abulaiti, Y.; Abusleme Hoffman, A. C.; et al (July 2023, The European Physical Journal C)

   Abstract A search for supersymmetry involving the pair production of gluinos decaying via off-shell third-generation squarks into the lightest neutralino$$(\tilde{\chi }^0_1)$$ $\left({\tilde{\chi }}_1^0\right)$is reported. It exploits LHC proton–proton collision data at a centre-of-mass energy$$\sqrt{s} = 13$$ $\sqrt{s}=13$TeV with an integrated luminosity of 139 fb$$^{-1}$$ ${}^{-1}$collected with the ATLAS detector from 2015 to 2018. The search uses events containing large missing transverse momentum, up to one electron or muon, and several energetic jets, at least three of which must be identified as containingb-hadrons. Both a simple kinematic event selection and an event selection based upon a deep neural-network are used. No significant excess above the predicted background is found. In simplified models involving the pair production of gluinos that decay via off-shell top (bottom) squarks, gluino masses less than 2.44 TeV (2.35 TeV) are excluded at 95% CL for a massless$$\tilde{\chi }^0_1.$$ ${\tilde{\chi }}_1^0.$Limits are also set on the gluino mass in models with variable branching ratios for gluino decays to$$b\bar{b}\tilde{\chi }^0_1,$$ $b\overline{b}{\tilde{\chi }}_1^0,$$$t\bar{t}\tilde{\chi }^0_1$$ $t\overline{t}{\tilde{\chi }}_1^0$and$$t\bar{b}\tilde{\chi }^-_1/\bar{t}b\tilde{\chi }^+_1.$$ $t\overline{b}{\tilde{\chi }}_1^{-}/\overline{t}b{\tilde{\chi }}_1^{+}.$ 

   more » « less
5. Ultracold neutron storage in a bottle coated with the fluoropolymer CYTOP

   https://doi.org/10.1140/epja/s10050-022-00791-x  

   Neulinger, Thomas; Beck, Douglas; Connolly, Euan; Degenkolb, Skyler; Fierlinger, Peter; Filter, Hanno; Hingerl, Jürgen; Nordin, Pontus; Saerbeck, Thomas; Zimmer, Oliver (July 2022, The European Physical Journal A)

   Abstract The fluoropolymer CYTOP was investigated in order to evaluate its suitability as a coating material for ultracold neutron (UCN) storage vessels. Using neutron reflectometry on CYTOP-coated silicon wafers, its neutron optical potential was measured to be 115.2(2) neV. UCN storage measurements were carried out in a 3.8 l CYTOP-coated aluminum bottle, in which the storage time constant was found to increase from 311(9) s at room temperature to 564(7) s slightly above 10 K. By combining experimental storage data with simulations of the UCN source, the neutron loss factor of CYTOP is estimated to decrease from 1.1(1)$$\times 10^{-4}$$ $\times {10}^{-4}$to 2.7(2)$$\times 10^{-5}$$ $\times {10}^{-5}$at these temperatures, respectively. These results are of particular importance to the next-generation superthermal UCN source SuperSUN, currently under construction at the Institut Laue-Langevin, for which CYTOP is a possible top-surface coating in the UCN production volume. 

   more » « less