Paper 2024/1264
Succinct NonSubsequence Arguments
Abstract
Lookup arguments have recently attracted a lot of developments due to their applications in the constructions of succinct noninteractive arguments of knowledge (SNARKs). A closely related topic is subsequence arguments in which one can prove that string $\mathbf{s}$ is a subsequence of another string $\mathbf{t}$, i.e., deleting some characters in $\mathbf{t}$ can achieve $\mathbf{s}$. A dual notion, namely, nonsubsequence arguments, is to prove that $\mathbf{s}$ is not a subsequence of $\mathbf{t}$. These problems have a lot of important applications in DNA sequence analysis, internet of things, blockchains, natural language processing, speech recognition, etc. However, despite their applications, they are not wellstudied in cryptography, especially succinct arguments for nonsubsequences with efficient proving time and sublinear verification time. In this work, we propose the first succinct nonsubsequence argument. Our solution applies the sumcheck protocol and is instantiable by any multivariate polynomial commitment schemes (PCSs). We achieve an efficient prover whose running time is linear in the size of sequences $\mathbf{s}$, $\mathbf{t}$ and their respective alphabet $\Sigma$. Our proof is succinct and the verifier time is sublinear assuming the employed PCS has succinct commitments and sublinear verification time. When instantiating with Sona PCS (EUROCRYPT'24), we achieve proof size $\mathcal{O}(\log_2\mathbf{s} + \log_2\mathbf{t}+\log_2\Sigma)$, prover time $\mathcal{O}(\mathbf{s}+\mathbf{t}+\Sigma)$ and verifier time $\mathcal{O}(\sqrt{\mathbf{s}}+\sqrt{\mathbf{t}}+\sqrt{\Sigma})$. Extending our technique, we can achieve a batch subsequence argument for proving in batch $k$ interleaving subsequence and nonsubsequence arguments without proof size suffering a linear blowup in $k$.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. Minor revision. SCN 2024
 Keywords
 SNARKsumchecklookup
 Contact author(s)

lingsan @ ntu edu sg
khaihanh tang @ ntu edu sg
isevvk @ nus edu sg
hxwang @ ntu edu sg
yanxi @ stu edu xidian cn  History
 20241004: last of 3 revisions
 20240809: received
 See all versions
 Short URL
 https://ia.cr/2024/1264
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/1264, author = {San Ling and Khai Hanh Tang and Khu Vu and Huaxiong Wang and Yingfei Yan}, title = {Succinct NonSubsequence Arguments}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1264}, year = {2024}, url = {https://eprint.iacr.org/2024/1264} }