References

• [AGH+13] S. Agrawal, C. Gentry, S. Halevi, and A. Sahai (2013) Discrete gaussian leftover hash lemma over infinite domains. In ASIACRYPT, pp. 97–116. Cited by: §4.2.
• [Ajt96] M. Ajtai (1996) Generating hard instances of lattice problems. In STOC, pp. 99–108. Cited by: §4.11, §4.11, §4.14, §4.14, §4.14, Definition 4.8.4.
• [AS16] N. Alon and J. H. Spencer (2016) The probabilistic method. 4th edition, Wiley. Cited by: Remark 1.6.17, Remark 1.6.39, §3.
• [AHI+17] S. Ames, C. Hazay, Y. Ishai, and M. Venkitasubramaniam (2017) Ligero: lightweight sublinear arguments without a trusted setup. In ACM CCS, pp. 2087–2104. Cited by: §4.4, §4.4.
• [And87] D. André (1887) Solution directe du problème résolu par m. bertrand. Comptes Rendus de l’Académie des Sciences, Paris 105, pp. 436–437. Cited by: Remark 1.13.17.
• [ACK21a] T. Attema, R. Cramer, and L. Kohl (2021) A compressed $\mathrm{\Sigma }$-protocol theory for lattices. In CRYPTO, pp. 549–579. Cited by: §4.14.
• [ACX21b] T. Attema, R. Cramer, and C. Xing (2021) A note on short invertible ring elements and applications to cyclotomic and trinomial number fields. Mathematical Cryptology 1 (1), pp. 45–70. Cited by: §4.12.
• [ALS20] T. Attema, V. Lyubashevsky, and G. Seiler (2020) Practical product proofs for lattice commitments. In CRYPTO, pp. 470–499. Cited by: 3rd item, 4th item, 3rd item, 4th item, 3rd item, 4th item, 3rd item, 3rd item, §4.12, §4.12, §4.12, §4.12, §4.12, §4.12, §4.12, §4.12, §4.12, §4.12, §4.12, Lemma 4.12.4, Lemma 4.12.5, §4.13, §4.13, §4.14, §4.14, §4.14, footnote 25.
• [Azu67] K. Azuma (1967) Weighted sums of certain dependent random variables. Tohoku Mathematical Journal 19 (3), pp. 357–367. Cited by: Theorem 1.13.28, Theorem 1.13.29.
• [Ban93] W. Banaszczyk (1993) New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen 296, pp. 625–635. Cited by: §4.11, Lemma 4.14.3.
• [BBC+18a] C. Baum, J. Bootle, A. Cerulli, R. del Pino, J. Groth, and V. Lyubashevsky (2018) Sub-linear lattice-based zero-knowledge arguments for arithmetic circuits. In CRYPTO, pp. 669–699. Cited by: §4.11, §4.11, §4.11, §4.8, §4.9, §4.9, §4.9, §4.9, §4.9, §4.9, §4.9.
• [BDL+18b] C. Baum, I. Damgård, V. Lyubashevsky, S. Oechsner, and C. Peikert (2018) More efficient commitments from structured lattice assumptions. In SCN, pp. 368–385. Cited by: §4.11, §4.11, §4.11, §4.11, §4.11, §4.11, §4.11, §4.11, §4.11, §4.11, §4.11, §4.11, §4.11, §4.11, §4.12, §4.12, §4.12, §4.14, §4.14, §4.14, §4.14.
• [Bec91] J. Beck (1991) An algorithmic approach to the lovász local lemma. i. Random Struct. Algorithms 2 (4), pp. 343–365. Cited by: Theorem 1.6.52.
• [BG93] M. Bellare and O. Goldreich (1993) On defining proofs of knowledge. In CRYPTO, pp. 390–420. Cited by: §4.11.
• [BS23] W. Beullens and G. Seiler (2023) LaBRADOR: compact proofs for R1CS from Module-SIS. In CRYPTO, pp. 518–548. Cited by: §4.15.
• [BLR93] M. Blum, M. Luby, and R. Rubinfeld (1993) Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences 47 (3), pp. 549–595. Cited by: §1.1.
• [BCS23] J. Bootle, A. Chiesa, and K. Sotiraki (2023) Lattice-based succinct arguments for NP with polylogarithmic-time verification. In CRYPTO, pp. 227–251. Cited by: §4.17.
• [BLN+20] J. Bootle, V. Lyubashevsky, N. K. Nguyen, and G. Seiler (2020) A Non-PCP approach to succinct Quantum-Safe Zero-Knowledge. In CRYPTO, pp. 441–469. Cited by: §4.11, §4.11, §4.11, §4.9, §4.9, §4.9, §4.9, Lemma 4.9.1, §4.9.
• [BLS19] J. Bootle, V. Lyubashevsky, and G. Seiler (2019) Algebraic techniques for short(er) exact lattice-based zero-knowledge proofs. In CRYPTO, pp. 176–202. Cited by: 2nd item, §4.10, §4.11, §4.11, §4.11, §4.11, §4.11, §4.11, §4.11, §4.11, §4.11, §4.11, §4.11, §4.11, §4.11, §4.12, §4.12, §4.13, §4.13, §4.13, §4.13, §4.13, §4.13, §4.14, §4.14, §4.14, footnote 22.
• [BD97] R. Bubley and M. E. Dyer (1997) Path coupling: a technique for proving rapid mixing in markov chains. In FOCS, pp. 223–231. Cited by: Remark 1.12.21, Remark 1.12.39, Theorem 1.12.41.
• [BBB+18] B. Bünz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell (2018) Bulletproofs: short proofs for confidential transactions and more. In IEEE S&P, pp. 315–334. Cited by: 2nd item, §4.7, §4.9, §4.9.
• [CF24] H. Z. B. Chen and B. Fisch (2024) BaseFold: efficient multilinear polynomial commitment schemes from foldable codes. In CRYPTO, pp. 138–169. Cited by: Lemma 4.6.1, §4.6.
• [Cho94] K. P. Choi (1994) On the medians of gamma distributions and an equation of ramanujan. Proceedings of the American Mathematical Society 121 (1), pp. 245–251. Cited by: Theorem 1.5.13.
• [Dam10] I. Damgård (2010) On $\mathrm{\Sigma }$-protocols. Note: Lecture notes, Cryptologic Protocol TheoryCPT 2010, v.2 External Links: Link Cited by: §4.11, §4.11, §4.11, §4.11, §4.11, Lemma 4.8.8, §4.9.
• [DP24] B. E. Diamond and J. Posen (2024) Proximity testing with logarithmic randomness. IACR Communications in Cryptology 1 (1). Cited by: §4.5.
• [Dob40] W. Doblin (1940) Éléments d’une théorie générale des chaînes simples constantes de Markoff. Annales scientifiques de l’École Normale Supérieure 57, pp. 61–111 (fr). External Links: Document, Link Cited by: Remark 1.12.27.
• [Doo40] J. L. Doob (1940) Regularity properties of certain families of chance variables. Transactions of the American Mathematical Society 47 (3), pp. 455–486. Cited by: Definition 1.13.6.
• [Eli72] P. Elias (1972) The efficient construction of an unbiased random sequence. The Annals of Mathematical Statistics 43 (3), pp. 865–870. Cited by: Remark 1.10.30.
• [EL75] P. Erdős and L. Lovász (1975) Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets, A. Hajnal, R. Rado, and V. T. Sós (Eds.), Colloquia Mathematica Societatis János Bolyai, Vol. 10, pp. 609–627. Cited by: Lemma 1.6.41, Lemma 1.6.45.
• [ENS20] M. F. Esgin, N. K. Nguyen, and G. Seiler (2020) Practical exact proofs from lattices: new techniques to exploit fully-splitting rings. In ASIACRYPT, pp. 259–288. Cited by: §4.13, §4.13, §4.13, §4.13, §4.14, §4.14, §4.14, §4.14.
• [EZS+19] M. F. Esgin, R. K. Zhao, R. Steinfeld, J. K. Liu, and D. Liu (2019) MatRiCT: efficient, scalable and post-quantum blockchain confidential transactions protocol. In ACM CCS, pp. 567–584. Cited by: §4.12.
• [Ete81] N. Etemadi (1981) An elementary proof of the strong law of large numbers. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 55 (1), pp. 119–122. Cited by: §1.7.3, §1.7.3, Lemma 1.7.35.
• [FS90] U. Feige and A. Shamir (1990) Witness indistinguishable and witness hiding protocols. In STOC, pp. 416–426. Cited by: footnote 21.
• [Fel68a] W. Feller (1968) An introduction to probability theory and its applications. Vol. 1, John Wiley & Sons. Cited by: Lemma 1.7.30.
• [Fel68b] W. Feller (1968) An introduction to probability theory and its applications. Vol. 2, John Wiley & Sons. Cited by: Theorem 1.7.50.
• [HIL+99] J. Håstad, R. Impagliazzo, L. A. Levin, and M. Luby (1999) A pseudorandom generator from any one-way function. SIAM Journal on Computing 28 (4), pp. 1364–1396. Cited by: §4.1.
• [Hoe63] W. Hoeffding (1963) Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58 (301), pp. 13–30. Cited by: Theorem 1.4.10, Lemma 1.4.8, Theorem 1.4.9.
• [ILL89] R. Impagliazzo, L. A. Levin, and M. Luby (1989) Pseudo-random generation from one-way functions. In STOC, pp. 12–24. Cited by: §4.1.
• [JVV86] M. R. Jerrum, L. G. Valiant, and V. V. Vazirani (1986) Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci. 43, pp. 169–188. Cited by: §1.4.
• [JS89] M. Jerrum and A. Sinclair (1989) Approximating the permanent. SIAM Journal on Computing 18 (6), pp. 1149–1178. Cited by: Definition 1.12.6.
• [Jer95] M. Jerrum (1995) A very simple algorithm for estimating the number of $k$-colorings of a low-degree graph. Random Structures & Algorithms 7 (2), pp. 157–165. Cited by: Remark 1.12.37.
• [Kra49] L. G. Kraft (1949) A device for quantizing, grouping, and coding amplitude-modulated pulses. M.S. thesis, Massachusetts Institute of Technology, Cambridge, MA. External Links: Link Cited by: Remark 1.10.35.
• [KL51] S. Kullback and R. A. Leibler (1951) On information and sufficiency. The Annals of Mathematical Statistics 22 (1), pp. 79–86. Cited by: Definition 1.10.13, Remark 1.4.5.
• [LS15] A. Langlois and D. Stehlé (2015) Worst-case to average-case reductions for module lattices. Des. Codes Cryptogr. 75 (3), pp. 565–599. Cited by: Definition 4.8.3.
• [LMR94] F. T. Leighton, B. M. Maggs, and S. B. Rao (1994) Packet routing and job-shop scheduling in O(congestion + dilation) steps. Combinatorica 14 (2), pp. 167–186. Cited by: Remark 1.4.16.
• [LP17] D. A. Levin and Y. Peres (2017) Markov chains and mixing times. 2 edition, American Mathematical Society, Providence, RI. Note: With contributions by Elizabeth L. Wilmer External Links: Document Cited by: Remark 1.12.27.
• [Lov79] L. Lovász (1979) On the shannon capacity of a graph. IEEE Transactions on Information Theory 25 (1), pp. 1–7. Cited by: Remark 1.10.48.
• [Lub66] D. Lubell (1966) A short proof of sperner’s lemma. Journal of Combinatorial Theory 1, pp. 299. Cited by: Remark 1.6.11.
• [LM06] V. Lyubashevsky and D. Micciancio (2006) Generalized compact knapsacks are collision resistant. In ICALP, pp. 144–155. Cited by: Definition 4.8.3.
• [LNP22] V. Lyubashevsky, N. K. Nguyen, and M. Plançon (2022) Lattice-based zero-knowledge proofs and applications: shorter, simpler, and more general. In CRYPTO, pp. 71–101. Cited by: §4.14, §4.14, §4.14, §4.14, §4.14, §4.14, §4.14.
• [LNS21] V. Lyubashevsky, N. K. Nguyen, and G. Seiler (2021) Shorter lattice-based zero-knowledge proofs via one-time commitments. In PKC, pp. 215–241. Cited by: §4.14.
• [LPR13] V. Lyubashevsky, C. Peikert, and O. Regev (2013) A toolkit for Ring-LWE cryptography. In EUROCRYPT, pp. 35–54. Cited by: §4.12.
• [LS18] V. Lyubashevsky and G. Seiler (2018) Short, invertible elements in partially splitting cyclotomic rings and applications to lattice-based zero-knowledge proofs. In EUROCRYPT, pp. 204–224. Cited by: 1st item, 2nd item, §4.10, §4.10, §4.10, Theorem 4.10.1, Lemma 4.10.4, Lemma 4.10.5, Theorem 4.10.6, §4.10, §4.11, §4.11, §4.11, §4.12, §4.12, Lemma 4.12.1, §4.14.
• [Lyu09] V. Lyubashevsky (2009) Fiat–Shamir with aborts: applications to lattice and factoring-based signatures. In ASIACRYPT, pp. 598–616. Cited by: §4.8.
• [Lyu12] V. Lyubashevsky (2012) Lattice signatures without trapdoors. In EUROCRYPT, pp. 738–755. Cited by: §4.11, §4.11, §4.11, §4.11, §4.11, §4.11, §4.14, §4.14, §4.14, §4.8.
• [Mat88] P. C. Matthews (1988) Covering problems for brownian motion on spheres. Annals of Probability 16 (1), pp. 189–199. Cited by: Lemma 1.7.81.
• [Mcd89] C. McDiarmid (1989) On the method of bounded differences. In Surveys in Combinatorics, 1989, London Mathematical Society Lecture Note Series, Vol. 141, pp. 148–188. Cited by: Definition 1.13.32, Theorem 1.13.33.
• [Mcm56] B. McMillan (1956) Two inequalities implied by unique decipherability. IRE Transactions on Information Theory 2 (4), pp. 115–116. Cited by: Remark 1.10.35.
• [MU17] M. Mitzenmacher and E. Upfal (2017) Probability and computing: randomization and probabilistic techniques in algorithms and data analysis. 2nd edition, Cambridge University Press, Cambridge, UK. Cited by: Exercise 1.1.1, Exercise 1.1.2, Exercise 1.1.3, Exercise 1.10.24, Exercise 1.10.25, Exercise 1.10.26, Exercise 1.10.29, Exercise 1.10.3, Exercise 1.10.31, Exercise 1.10.34, Exercise 1.10.38, Exercise 1.10.39, Exercise 1.10.4, Exercise 1.10.40, Exercise 1.10.41, Exercise 1.10.44, Exercise 1.10.47, Exercise 1.10.49, Exercise 1.10.50, Exercise 1.10.6, Exercise 1.10.8, Exercise 1.12.13, Exercise 1.12.14, Exercise 1.12.16, Exercise 1.12.18, Exercise 1.12.19, Exercise 1.12.20, Exercise 1.12.22, Exercise 1.12.26, Exercise 1.12.32, Exercise 1.12.42, Exercise 1.12.43, Exercise 1.12.44, Exercise 1.13.14, Exercise 1.13.15, Exercise 1.13.23, Exercise 1.13.24, Exercise 1.13.25, Exercise 1.13.26, Exercise 1.13.27, Exercise 1.13.3, Exercise 1.13.30, Exercise 1.13.35, Exercise 1.13.36, Exercise 1.13.37, Exercise 1.13.39, Exercise 1.13.4, Exercise 1.13.41, Exercise 1.13.42, Exercise 1.13.45, Exercise 1.13.5, Exercise 1.13.8, Exercise 1.2.1, Exercise 1.2.2, Exercise 1.2.3, Exercise 1.2.4, Exercise 1.3.1, Exercise 1.3.10, Exercise 1.3.3, Exercise 1.3.4, Exercise 1.3.8, Exercise 1.3.9, Exercise 1.4.1, Exercise 1.4.11, Exercise 1.4.12, Exercise 1.4.13, Exercise 1.4.14, Exercise 1.4.15, Exercise 1.4.2, Exercise 1.4.3, Exercise 1.4.4, Exercise 1.4.6, Exercise 1.4.7, Exercise 1.5.10, Exercise 1.5.11, Lemma 1.5.12, Theorem 1.5.14, Theorem 1.5.15, Theorem 1.5.17, Exercise 1.5.18, Corollary 1.5.19, Exercise 1.5.2, Lemma 1.5.20, Exercise 1.5.22, Theorem 1.5.23, Exercise 1.5.26, Exercise 1.5.29, Lemma 1.5.36, Exercise 1.5.39, Lemma 1.5.4, Theorem 1.5.40, Exercise 1.5.7, Exercise 1.5.8, Lemma 1.5.9, Exercise 1.6.10, Exercise 1.6.15, Exercise 1.6.16, Exercise 1.6.18, Exercise 1.6.19, Exercise 1.6.20, Exercise 1.6.21, Exercise 1.6.22, Exercise 1.6.23, Exercise 1.6.32, Exercise 1.6.33, Exercise 1.6.36, Exercise 1.6.37, Exercise 1.6.38, Exercise 1.6.44, Exercise 1.6.48, Exercise 1.6.50, Exercise 1.6.51, Exercise 1.6.59, Exercise 1.6.8, Exercise 1.6.9, Exercise 1.7.10, Exercise 1.7.11, Exercise 1.7.12, Exercise 1.7.19, Exercise 1.7.5, Exercise 1.7.61, Exercise 1.7.62, Exercise 1.7.63, Exercise 1.7.64, Exercise 1.7.66, Exercise 1.7.68, Exercise 1.7.69, Exercise 1.7.70, Exercise 1.7.72, Exercise 1.7.76, Exercise 1.7.78, Exercise 1.7.8, Exercise 1.7.82, Exercise 1.7.83, Exercise 1.7.84, Exercise 1.7.9, §4.1.
• [MT10] R. A. Moser and G. Tardos (2010) A constructive proof of the general lovász local lemma. J. ACM 57 (2). Cited by: §1.6.7, Theorem 1.6.60, Corollary 1.6.61.
• [Mos09] R. A. Moser (2009) A constructive proof of the lovász local lemma. In STOC, pp. 343–350. Cited by: §1.6.7.
• [Mos12] R. A. Moser (2012) Exact algorithms for constraint satisfaction problems. Ph.D. Thesis, ETH Zurich. External Links: Link Cited by: §1.6.7, Theorem 1.6.58.
• [Mos10] D. Moshkovitz (2010) An alternative proof of the schwartz–zippel lemma. Electron. Colloquium Comput. Complex. 2010, pp. 96. Cited by: §4.3, §4.4, §4.4.
• [NS24] N. K. Nguyen and G. Seiler (2024) Greyhound: fast polynomial commitments from lattices. In CRYPTO, pp. 243–275. Cited by: §4.16.
• [Pap91] C. H. Papadimitriou (1991) On selecting a satisfying truth assignment. In FOCS, pp. 163–169. Cited by: §1.7.2, Lemma 1.7.6.
• [PR06] C. Peikert and A. Rosen (2006) Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In TCC, pp. 145–166. Cited by: Definition 4.8.3.
• [PR07] C. Peikert and A. Rosen (2007) Lattices that admit logarithmic worst-case to average-case connection factors. In STOC, pp. 478–487. Cited by: Lemma 4.10.4.
• [Per92] Y. Peres (1992) Iterating Von Neumann’s procedure for extracting random bits. The Annals of Statistics 20 (1), pp. 590–597. Cited by: Remark 1.10.30.
• [Pós76] L. Pósa (1976) Hamiltonian circuits in random graphs. Discrete Mathematics 14 (4), pp. 359–364. Cited by: Remark 1.5.48.
• [Rag88] P. Raghavan (1988) Probabilistic construction of deterministic algorithms: approximating packing integer programs. J. Comput. Syst. Sci. 37 (2), pp. 130–143. Cited by: Remark 1.6.17.
• [SS87] E. Shamir and J. Spencer (1987) Sharp concentration of the chromatic number on random graphs $G_{n,p}$. Combinatorica 7, pp. 121–129. Cited by: Example 1.13.44.
• [Sha48a] C. E. Shannon (1948) A mathematical theory of communication. The Bell System Technical Journal 27 (3), pp. 379–423. Cited by: Theorem 1.10.46.
• [Sha48b] C. E. Shannon (1948) A mathematical theory of communication. The Bell System Technical Journal 27 (4), pp. 623–656. Cited by: Theorem 1.10.46.
• [Sha56] C. E. Shannon (1956) The zero error capacity of a noisy channel. IRE Transactions on Information Theory IT-2 (3), pp. 8–19. Cited by: Remark 1.10.48.
• [Spe77] J. Spencer (1977) Asymptotic lower bounds for ramsey functions. Discrete Mathematics 20 (1), pp. 69–76. Cited by: Remark 1.6.49.
• [Spe28] E. Sperner (1928) Ein satz über untermengen einer endlichen menge. Mathematische Zeitschrift 27, pp. 544–548. Cited by: Remark 1.6.11.
• [Top07] F. Topsøe (2007) Some bounds for the logarithmic function. In Inequality Theory and Applications, Y. J. Cho, J. K. Kim, and S. S. Dragomir (Eds.), Vol. 4, pp. 137–151. External Links: ISBN 978-1-59454-874-1 Cited by: §1.7.1, Lemma 1.7.2.
• [Tse63] M. L. Tsetlin (1963) Finite automata and models of simple forms of behaviour. Russian Mathematical Surveys 18 (4), pp. 1–27. Cited by: Remark 1.7.71.
• [Vad12] S. P. Vadhan (2012) Pseudorandomness. Now Publishers Inc., Hanover, MA. Cited by: §2.
• [VB81] L. G. Valiant and G. J. Brebner (1981) Universal schemes for parallel communication. In STOC, pp. 263–277. Cited by: §1.4.3.
• [Von51] J. von Neumann (1951) Various techniques used in connection with random digits. In Monte Carlo Method, A. S. Householder, G. E. Forsythe, and H. H. Germond (Eds.), National Bureau of Standards Applied Mathematics Series, Vol. 12, pp. 36–38. Note: Summary written by George E. Forsythe Cited by: Remark 1.10.30.
• [Wal47] A. Wald (1947) Sequential analysis. John Wiley & Sons. Cited by: Theorem 1.13.18.
• [YAZ+19] R. Yang, M. H. Au, Z. Zhang, Q. Xu, Z. Yu, and W. Whyte (2019) Efficient lattice-based zero-knowledge arguments with standard soundness: construction and applications. In CRYPTO, pp. 147–175. Cited by: §4.12.