278 ◾ Secure Data Provenance and Inference Control
a class of functions that is learnable in exponentially many steps, then in practice
this class will not be learnable.
e results that have been obtained on learning algorithms show the difficulty
in computing them. Even in very simple cases that deal with monomial functions,
defining plausible learning mechanisms is extremely nontrivial. e main difficulty
is in giving a definition of learning that is both realistic and computationally fea-
sible. From a security point of view, this complexity is very desirable. is is because
as the complexity of the learning algorithm increases, it will be more difficult for an
unclassified user to infer secret rules.
It should be pointed out that the conjectures i ...