This book is rooted in the thesis that complexity theory is extremely rich in conceptual
content, and that this contents should be explicitly communicated in expositions and courses …

Our work addresses the critical issue of distinguishing text generated by Large Language
Models (LLMs) from human-produced text, a task essential for numerous applications …

Cryptography is concerned with the conceptualization, definition, and construction of
computing systems that address security concerns. The design of cryptographic systems …

Cryptography is concerned with the construction of schemes that should maintain a desired
functionality, even under malicious attempts aimed at making them deviate from it. The …

The design of new quantum algorithms has proven to be an extremely difficult task. This
paper considers a different approach to the problem, by studying the problem of'quantum …

We present the first complete problem for SZK, the class of promise problems possessing
statistical zero-knowledge proofs (against an honest verifier). The problem, called Statistical …

We introduce the notion of a Canonical Tester for a class of properties on distributions, that
is, a tester strong and general enough that" a distribution property in the class is testable if …

The two most common ways to design non-interactive zero-knowledge (NIZK) proofs are
based on Sigma protocols and QAP-based SNARKs. The former is highly efficient for …

We construct several new statistical zero-knowledge proofs with efficient provers, ie ones
where the prover strategy runs in probabilistic polynomial time given an NP witness for the …

We describe a cryptanalytical technique for distinguishing some stream ciphers from a truly
random process. Roughly, the ciphers to which this method applies consist of a “non-linear …