We got sketch of algorithm for public key encryption based on satisfiability of hidden boolean formula. It is easy to break in its current form, but we are interested if it can be improved.
Alice chooses boolean formula $\phi$ on variables $x_1...x_n$ with a known satisfying assignment $S$ and another boolean for formula $\psi$ on variables $x_1...x_k,y_1..y_m$.
Let $\Phi=(\psi \land \lnot \phi) \oplus y_1$.
Observe that $\Phi(S)=y_1$.
Alices' public key is $\Phi$ and her private key is $S$.
To encode one bit of message $m$ set $Y_1=m$ and the rest of $y_i$ random bits.
The encryption is $\Phi'=\Phi(Y_i)$, boolean formula only on variables $x_i$.
The decryption is $\Phi'(S)=m=Y_1$.
So far we have not defined in what form $F$ the boolean formulas are given, which is critical.
- $F$ must hide the location of $Y_1$ in the cypher text.
- $F$ must not allow easily find solution of $\phi$, which appears in the public key. (It might be even hard to recognize $\phi$ from the public key).
Candidates for $F$ are read several times binary decision diagrams BDD, branching program.
Question:
Is it known that this won't work?
Is the form $F$ BDD known to fail?
