Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I don't have much formal background, and I could not find a suitable explanation for this after searching on Google/Wikipedia.
What is the meaning of the term "language" as used in cryptographic protocols?
Sample sentence from a recent paper:
Every language in BQP admits a classical-verifier, quantum-prover zero-knowledge argument system which is sound against quantum polynomial-time provers and zero-knowledge for classical(and quantum) polynomial-time verifiers.
The concept of language has been systematized. For example here you can become familiar with this in an accessible way.
In the article you are reading the language has such meaning:
A language L is in BQP if and only if and only if and only if there exists a polynomial-time uniform family of quantum circuits $\{Q_n:n \in \mathbb{N}\}$, such that
- For all $n \in \mathbb{N}$, ''Qn'' takes ''n'' qubits as input and outputs 1 bit
- For all ''x'' in ''L'', $\mathrm{Pr}(Q_{|x|}(x)=1)\geq \tfrac{2}{3}$
- For all ''x'' not in ''L'', $\mathrm{Pr}(Q_{|x|}(x)=0)\geq \tfrac{2}{3}$
Alternatively, one can define BQP in terms of quantum Turing machines. A language L is in BQP if and only if there exists a polynomial quantum Turing machine that accepts L with an error probability of at most 1/3 for all instances.
This question is concerned with the definition of the term "language" as it appears in the definition of a complexity class; thus we can look for the answer in a reference work on complexity theory. One such work is the book of Arora and Barak, where one can read (the set $\{0,1\}^*$ having been previously defined as the set of all finite binary strings)
An important special case of functions mapping strings to strings is the case of Boolean functions, whose output is a single bit. We identify such a function $f$ with the subset $L_f = \{x : f(x) = 1\}$ of $\{0,1\}^*$ and call such sets languages or decision problems (we use these terms interchangeably).
Thus a language in this context is simply a subset of $\{0,1\}^*$, i.e., a set of finite binary strings. It is equivalent to the (perhaps more intuitive) notion of a decision problem, which is basically a question to which the answer is "yes" or "no". To such a problem we can associate the language consisting of the strings for which the answer is "yes"; for example the language associated to the question "Given an integer, is it prime?" is the language whose elements are precisely (the binary representations of) the prime integers.
