IACR News item: 03 August 2015
Sebastian E. Schmittner
ePrint Report
We propose a public key encryption scheme based on the Boolean Satisfiability Problem (SAT). The public key is given by a SAT formula and the private key is the satisfying assignment. Encryption is a probabilistic algorithm that takes the bits of the message to randomly generated Boolean functions, represented in algebraic normal form. Those are implied to be true or false by the public key, hence bit-wise decryption is done by applying each function to the private key. Our scheme does not provide signatures.
Additional news items may be found on the IACR news page.