I think, the original question has been well answered by Carl Löndahl in the comments. Each of the terms you add does not only consist of "random variables" but may well contain a constant (1).
In fact, section 3.1.2 Constant Term Probability Attack
in the paper exactly addresses your question, by proposing the attack of just looking at the constant term (0 or 1).
When considering the encryption scheme from the article, please also have a look at this article which references a similar SAT based scheme which has a known vulnerability. It is currently unclear whether the same vulnerability also exist in the scheme from the arxive.
Unfortunately, I may not comment:
@Kristina dedndreaj:
Deriving the private from the public key is (exactly) the SAT Problem, hence NP hard, but, whether deriving the clear text from the cipher and public key is hard in any sense is an open question. Showing that this is NP hard is very difficult and there are no-go theorems around (see Yehuda Lindell's Answer).
EDIT (thanks to clarification by Occams_Trimmer in comments):
There are a few schemes which are currently believed to be "post-quantum". This may or may not mean that some NP-Hard Problem is utilized for the cryptosystem in some way. See e.g. https://en.wikipedia.org/wiki/Post-quantum_cryptography . A better Referenz is Bernstein, Buchmann, and Dahmen: Post-Quantum Cryptography
which e.g. has this quote:
A multivariate public key cryptosystem (MPKCs for short) have a set of
(usually) quadratic polynomials over a finite field as its public map.
Its main security assumption is backed by the NP-hardness of the
problem to solve nonlinear equations over a finite field. This family
is considered as one of the major families of PKCs that could resist
potentially even the powerful quantum computers of the future.
in the abstract of Multivariate Public Key Cryptography by Ding and Yang
.