I ask this because it might one of those things that "everybody knows/does", but never gets written or explained anywhere... Is it just a matter of aesthetics (in the mathematical sense of the word), or is there a more specific (read: practical) reason for doing this? (as opposed to say, talking about a priori and a posteriori probabilities, as Claude Shannon did in his Communication Theory of Secrecy Systems?)

PS: This question might be relevant in the broader field of study of Boolean functions, but I am interested in the case of crypto applications.

PS2: I couldn't find a more suitable tag than "randomness", as "boolean-functions" or "random-variable" do not exist...

  • 2
    $\begingroup$ Could you precise the context where "input are modelled as random variables"? $\endgroup$ – Ievgeni Oct 17 '19 at 14:54

Why are inputs to boolean functions usually modelled as random variables?

A bit of clarity is needed here... the Cook–Levin theorem says that it is possible to translate each program into a boolean formula, so it is clear that the input of a program is almost never random.

I believe your question refers to binary satisfiability problems. The formers are extremely important decision problems which are studied in the field of Theoretical Computer Science. Example of such a problem:

Given an instance $\sigma$ of 3SAT (boolean formula in CNF with exactly 3 literals per clause) is there a distribution of variables such that $\sigma = 1$ ? This decision problem is known to be NP-complete.

Why are they so important? well, for so many reasons that it is impossible to list all of them but the main ones are two:

  1. circuit design/algorithm design: Each Boolean formula corresponds to a circuit and to a Turing Machine (algorithm), so it is useful to know which formulas produce results and which ones are blind alleys (contradictions).
  2. NP-completeness: KSAT (with $K \geq 3$) is known to be NP-complete, which means that every other problem in the complexity class NP (nondeterministic polynomial time) can be reduced to an instance of SAT, therefore it is useful to have efficient algorithms for it. Unfortunately, an efficient (polynomial time) algorithm is not yet known. Finding it would prove that P = NP and would guarantee the discoverer a million dollar.

Regarding cryptography, someone has proposed cryptographic methods based on sat but, perhaps taken by enthusiasm, they had not thought that creating a public key based on an instance of SAT could be as expensive and intractable as validating the instance itself.


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