Cryptographic Limitations on Polynomial-Time a Posteriori Query Learning

摘要

We investigate the polynomial-time learnability by using examples and membership queries. Angluin and Kharitonov proved that various concept classes (e.g., Boolean formulae, non-deterministic finite automata) are not polynomial-time learnable in this learning model based on a public-key encryption scheme with a certain security (i.e., IND-CCA1). As a stronger learning model, we consider an a posteriori query learning model, and show that it is indeed stronger than the above learning model if a one-way function exists. Nevertheless, from a secure encryption scheme, we prove that many natural classes containing Boolean formula concept class is not polynomial-time learnable even in this stronger learning model. The security of an encryption scheme used in this paper is weaker than the one used by Angluin and Kharitonov.