MarriageTheoremのこと

_ 代休のためお休み。

_ IACR ePrint 2015/788まで確認済み、ECCC 2003年分まで確認済み

_ 気になった論文：A SAT-based public key encryption scheme, Sebastian E. Schmittner, http://eprint.iacr.org/2015/771

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.