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. Azimuthal correlations of heavy-flavor hadron decay electrons with charged particles in pp and p–Pb collisions at $$\pmb {\sqrt{s_{\mathrm{{NN}}}}}$$ = 5.02 TeV

   https://doi.org/10.1140/epjc/s10052-023-11835-x  

   Acharya, S.; Adamová, D.; Adler, A.; Aglieri Rinella, G.; Agnello, M.; Agrawal, N.; Ahammed, Z.; Ahmad, S.; Ahn, S. U.; Ahuja, I.; et al (August 2023, The European Physical Journal C)

   Abstract The azimuthal ($$\Delta \varphi $$ $\Delta \phi$) correlation distributions between heavy-flavor decay electrons and associated charged particles are measured in pp and p–Pb collisions at$$\sqrt{s_{\mathrm{{NN}}}} = 5.02$$ $\sqrt{s_{\mathrm{NN}}}=5.02$TeV. Results are reported for electrons with transverse momentum$$4<16$$ $4<p_{\text{T}}<16$$$\textrm{GeV}/c$$ $\text{GeV}/c$ and pseudorapidity$$|\eta |<0.6$$ $\left|\eta \right|<0.6$. The associated charged particles are selected with transverse momentum$$1<7$$ $1<p_{\text{T}}<7$$$\textrm{GeV}/c$$ $\text{GeV}/c$, and relative pseudorapidity separation with the leading electron$$|\Delta \eta | < 1$$ $\left|\Delta \eta \right|<1$. The correlation measurements are performed to study and characterize the fragmentation and hadronization of heavy quarks. The correlation structures are fitted with a constant and two von Mises functions to obtain the baseline and the near- and away-side peaks, respectively. The results from p–Pb collisions are compared with those from pp collisions to study the effects of cold nuclear matter. In the measured trigger electron and associated particle kinematic regions, the two collision systems give consistent results. The$$\Delta \varphi $$ $\Delta \phi$distribution and the peak observables in pp and p–Pb collisions are compared with calculations from various Monte Carlo event generators. 

   more » « less
3. zk-Oracle: trusted off-chain compute and storage for decentralized applications

   https://doi.org/10.1007/s10619-024-07444-6  

   Gu, Binbin; Nawab, Faisal (December 2024, Distributed and Parallel Databases)

   Abstract Blockchain and Decentralized Applications (DApps) are increasingly important for creating trust and transparency in data storage and computation. However, on-chain transactions are often costly and slow. To overcome this challenge, off-chain nodes can be used to store and compute data. Unfortunately, this introduces the risk of untrusted nodes. To address this, authenticated data structures have been proposed, however, this ignores the compute of data from the raw data. We tackle this challenge by introducing zk-Oracle, which provides an efficient and trusted compute and storage off-chain. There is a challenge in using zero-knowledge proofs (zk-proof for short), which is the large proof generation time. We aim to overcome it with novel designs in zk-Oracle. zk-Oracle builds on zk-proofs technologies to achieve two goals. First, the computation of data structures from raw data and the corresponding proof generation is improved in terms of performance. Second, the verification on-chain is inexpensive and fast. Our experiments show that we can speed up zk-proof generation by up to$$550 \times $$ $550\times$faster than the baseline method. 

   more » « less
4. 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
5. Probing light scalars and vector-like quarks at the high-luminosity LHC

   https://doi.org/10.1140/epjc/s10052-025-14085-1  

   Qureshi, U S; Gurrola, A; Flórez, A; Rodriguez, C (April 2025, The European Physical Journal C)

   Abstract A model based on a$$U(1)_{T^3_R}$$ $U{\left(1\right)}_{T_R^3}$extension of the Standard Model can address the mass hierarchy between generations of fermions, explain thermal dark matter abundance, and the muon$$g - 2$$ $g-2$,$$R_{(D)}$$ $R_{\left(D\right)}$, and$$R_{(D^*)}$$ $R_{\left(D^{\ast }\right)}$anomalies. The model contains a light scalar boson$$\phi '$$ ${\varphi }^{\prime }$and a heavy vector-like quark$$\chi _\textrm{u}$$ ${\chi }_{\text{u}}$that can be probed at CERN’s large hadron collider (LHC). We perform a phenomenology study on the production of$$\phi '$$ ${\varphi }^{\prime }$and$${\chi }_u$$ ${\chi }_u$particles from proton–proton$$(\textrm{pp})$$ $\left(\text{pp}\right)$collisions at the LHC at$$\sqrt{s}=13.6$$ $\sqrt{s}=13.6$TeV, primarily through$$g{-g}$$ $g-g$and$$t{-\chi _\textrm{u}}$$ $t-{\chi }_{\text{u}}$fusion. We work under a simplified model approach and directly take the$$\chi _\textrm{u}$$ ${\chi }_{\text{u}}$and$$\phi '$$ ${\varphi }^{\prime }$masses as free parameters. We perform a phenomenological analysis considering$$\chi _\textrm{u}$$ ${\chi }_{\text{u}}$final states to b-quarks, muons, and neutrinos, and$$\phi '$$ ${\varphi }^{\prime }$decays to$$\mu ^+\mu ^-$$ ${\mu }^{+}{\mu }^{-}$. A machine learning algorithm is used to maximize the signal sensitivity, considering an integrated luminosity of 3000$$\text {fb}^{-1}$$ ${\text{fb}}^{-1}$. The proposed methodology can be a key mode for discovery over a large mass range, including low masses, traditionally considered difficult due to experimental constraints. 

   more » « less