SAT cryptography and small help to understand We have a publication: A SAT-based Public Key Cryptography Scheme.
I do not understand sections: "1.1. Example".
As was generated logical formula $(4) (5) (6) (7)$?
I do not understand well how they were generated $R_{2,3}$, $R_{1,3}$, $R_{1,2}$ - formulas $(8) (9) (10) (11)$ and the method of calculation cipher - a formula $(12a - g)$.
Someone could help?
I know it's quite a lot of questions.
 A: In (4-7) the author is converting the negation of the clauses of (2-3) into Reed-Muller form, which is also known as algebraic normal form.  This is a normal form for Boolean expressions that uses conjunction and exclusive or (no negation and no disjunction).
Wikipedia has a good explanation of how to convert to Reed-Muller and how to manipulate the resulting expressions.  The key observations are that the negation of $a$ is equivalent to $1 \oplus a$ and that conjunction distributes over exclusive or:
$$ a(b \oplus c) = ab \oplus ac. $$
The simplest negation of a clause to convert is $\bar{c}_1$, because the conjunction of a set of positive literals turns into the same conjunction.  At the other end of the spectrum, the conjunction of a set of $n$ negated literals (as in $\bar{c}_3$) produces an expression with $2^n$ terms: one for each subset of the variables.
The $R_{i,j}$s of equations (8-11) are picked randomly.  Details are at the bottom of the second page.  Finally, $g$ is computed according to the expression (12a) to produce (12b-g).
