The Fundamental Justification

On epistemology and logic.

Mort Yao

2017-02-06

I don’t have much to write about this week. My plan was to finish the sections on statistics and machine learning in my wiki before I can move on to more rigorous mathematics and logic, but that turned out to be an impossible task (shortly after the exam week a new, incredibly tenser semester is right under the nose). I wanted to write more about cryptography and information theory as a brush-up account of previous courses I’ve taken, and that’s infeasible too (although the very introductory parts are done in #3 and #4).

Still, I have thought of many fun things I could do with statistical learning: image classification and face recognition (I always want a photo management application to be like that! I take and collect so many photos each day), a CBIR tool (like “Search by Image” in Google Images, but works locally on my computer), a GIMP Script-Fu that does tricks like image synthesis via ConvNets, etc. The good part about applying learning methods in image processing is that, once you can extract feature descriptors, everything becomes statistically learnable (and you as a programmer don’t really need to have prior knowledge about what an object visually is: an apple, or a pen?).

Cryptography, from what I learned, is a differently fun story. For a perfectly secure encryption scheme: \[\Pr[M=m\,|\,C=c] = \Pr[M=m]\] that is, knowing the ciphertext \(c\) will not update any attacker’s belief about whatever the underlying message \(m\) is. Even if you have a statistical training model, it cannot learn anything from purely observations of ciphertexts. But this unbreakable level of security comes with a price: The key space must expose substantial entropy that is as high as the message space, thus the key length can be no shorter than the message length (given by Shannon’s theorem). In practice, the messages we sent do not usually have the highest entropy possible, and we can safely assume that the attackers’ computation ability is bounded by polynomial-time algorithms, thus, we as the cryptosystem designers need only to make up schemes that are assumed to be unbreakable (i.e., breakable with only a negligible probability) for any polynomial-time attackers. As we don’t know yet if there actually are any polynomial unsolvable cases (e.g., is P ≠ NP?), the proof of security would eventually rely on some unproven computational hardness assumptions: one-way functions exist, integer factorization is hard, discrete logarithm is hard, etc. If one can construct a provably secure scheme, it is guaranteed that statistical cryptanalysis would be theoretically impossible within polynomial time (except for side-channel attacks); of course, if the hardness assumption we made is proved invalid, then nothing but the one-time pad can be secure.

I might be writing one or two blog posts about cryptographic security from an information-theoretic perspective and some basic cryptanalysis on insecure schemes, but now is the time to move on with my unfinished courses about logic and programming. Before that, I feel that I should add a little bit philosophy to my wiki so as to refresh my viewpoint and methodology. And here it is.

(Philosophy is a sophisticated, highly arguable subject, so pardon me if there’s any inconsistency with your textbook.)

We can talk about the philosophy of science (particularly, philosophy of mathematics and statistics) with the understanding of epistemology and logic: Are you a logician or a statistician? If a logician, does set theory or type theory suit you the best? If a statistician, are you a Bayesian or a frequentist?

(As a personally opinionated note, I often find myself subscribe to the skepticism the most. But that doesn’t mean that logical reasoning and statistical inference aren’t useful to me; they are. Extremely. So as not to go too far with this subjective topic, I’ll be focusing more on classical / modal logic in the next few weeks.)

References and further reading

Papers:

[1] E. L. Gettier, “Is justified true belief knowledge?” analysis, vol. 23, no. 6, pp. 121–123, 1963.