Konstantin Ziegler

Konstantin Ziegler

bits of cryptography and machine learning


All is fair in war, love, and mathematics.
-- Eric Temple Bell

Cryptographic Protocols

Alice and Bob are two millionaires. They want to determine who is richer, but do not want to disclose their actual wealth. A possible solution is to provide a trusted third party with their accounts' balances and let this party announce who is richer. The use this crutch is unsatisfactory and leaves every cryptographer with an uncomfortable feeling. Through secure multi-party computations, we provide Alice and Bob with a protocol to jointly compute the answer to their question using cryptographic primitives instead of a trusted third party.

Cryptography's model of users is quite simplistic: every user is either good or bad. Game theory offers a more nuanced version: every participant is trying to achieve his or her individual goals and behaves "rationally" in order to do so. We revisit multi-party computations with such rational players and arrive at surprising results.

By the way, the example above is the classic Yao's Millionaires' Problem. A recent application is the Bitcoin cryptocurrency, where the users jointly compute the "history" of transactions.

Machine Learning

All models are wrong, but some are useful.
-- George Box

The majority of attacks on cryptosystems is statistical, ranging from frequency analysis (of human languages) to correlations (of bit patterns). Differential and linear cryptanalysis are prime examples of the latter.

The classic field of statistics has gotten a fresh impulse from the emergence of artificial intelligence/machine learning in the last century. Both being based on huge amounts of data, they offer different perspectives. We take this as inspiration to attack cryptosystems using machine-learning methods.

Polynomials over Finite Fields

Polynomials appear all over mathematics and computer science. They inherit many basic notions from the integers, e.g. primality and squarefreeness. But the absence of carries for sums and products of polynomials makes them more accessible.

In the business of understanding polynomials, we measure our success by our ability to count the ones with certain properties -- approximately and exactly. From this point of view, I approached:

The decomposition of polynomials has many applications.