8
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ en.wikipedia.org/wiki/Formal_language $\endgroup$ – Squeamish Ossifrage Feb 18 at 17:17
  • 1
    $\begingroup$ @SqueamishOssifrage thank you! I guess I was missing the word formal and hence always ended up in web searches about programming languages $\endgroup$ – user1936752 Feb 18 at 17:24
  • 1
    $\begingroup$ This doesn't really have anything to do with crypto and would be more at home in the cs stackexchange. $\endgroup$ – Maeher Feb 18 at 18:11
  • 2
    $\begingroup$ @Maeher I agree at least for the example paper, as it seems a rather theoretical definition of a formal language that expresses a program that can be represented by a (non-deterministic) Turing machine. And I guess that is the definition for most crypto papers - but I would like to see some more consent before I'd post it as an answer myself. $\endgroup$ – Maarten Bodewes Feb 18 at 18:24
  • $\begingroup$ I would be very grateful if you could point out how that defintion of language ties in with the case in this sample paper where they talk about the language "admitting an argument system". As I understand it, it isn't too clear to me how it connects the notion of the language and what the language admits to the actual problem they discuss (which seems to be a cryptographic one of giving a zero knowledge proof). $\endgroup$ – user1936752 Feb 18 at 18:33
10
$\begingroup$

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:

Wikipedia BQP:

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.

$\endgroup$
  • 6
    $\begingroup$ Hey-hey, welcome to crypto.SE, simhumileco. Now that's a nice answer to start your contributions! $\endgroup$ – Maarten Bodewes Feb 18 at 19:05
  • $\begingroup$ Thank you for the warm welcome @MaartenBodewes :) $\endgroup$ – simhumileco Feb 18 at 19:06
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you, I think that's a very good point about the decision problem being represented as a language $\endgroup$ – user1936752 Feb 19 at 14:07

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.