Given a the complete universe of positive and negative examples, find the smallest computer program which will classify them perfectly.
Some compression possibilities: Bloom filter, Decision tree.
Assume there is no structure among the examples for machine learning methods to discover; the examples are distributed randomly. (One could imagine they are the cryptographic hashes of the content of actual examples.)
A device usable offline has a list of all good and revoked public subkeys, plus a master public key by which all subkeys are signed with. Reject if a subkey is known revoked or unknown with a signature failing the master key. The device periodically updates its list of revoked subkeys and master key when network is available.
The scheme fails for revocations it does not yet know about. The scheme fails if the master key is revoked.
A credit card terminal usable offline.
No comments :
Post a Comment