Necessary and Sufficient

Whilst many developers have to incorporate a degree of "security" or "crypto" elements into products they build, it recently came to my attention that many developers have a thin grasp of the mathematical concepts that underpin the foundations of cryptography. I guess it shouldn't have surprised me, but none-the-less it did.

For example, many developers will tell you that passwords should not be stored in clear-text in the database, but rather the hash of the password should be stored. That is excellent advice, but when probed on hash functions - what exactly are they, how do they work, what assumptions do they make, etc - you'll quickly find that it is an area that isn't well understood by many developers.

Under the covers hash functions are specialized one way functions. One way functions are a cryptographic primitive that, by definition, are "easy" to compute in one direction but "hard" to calculate in the other direction, that is, finding the inverse.  In this context, "easy" means solvable in polynomial time, and "hard" means, on average, the inverse for some randomly given value is not solvable in polynomial time. That is, easy means ∈ P, and hard means ∈ NP.

An Example

Let me give an example to demonstrate the easy/hard asymmetry that gives the one way function it's power. Consider the following equation:

c ≡ b^e mod m   (1)           [ here b is the "base", e is the "exponent", and m is the "modulus" ]

This is called modular or discrete exponentiation and it is a carefully constructed equation to exhibit qualities that make it a suitable one way function. Essentially, (1) consists of 2 components: an exponentiation operation, b^e, and a modulus operation. It's clear that evaluating b^e requires e-1 multiplication operations. This can also be seen by considering the recurrence relationship :

b^e = b. b^(e-1) (2)

= b. b. b^(e-2)

...

= b. b. b. b.  ... .b

The astute reader will note that we can perform this more efficiently by computing b², and then multiplying that by itself to get b⁴ and so on to get b⁸,  b¹⁶,  b³² and so on. We can see that this approach requires approximately log₂(e) operations. This is called exponentiation by squaring. It should be noted that there is considerable efficiency to be gained in using an Θ(log₂e) algorithm over a Θ(e) algorithm when e is large.

The second component needing evaluation in (1) is the modulus operation. This involves dividing b^e by m and finding the remainder. So overall we can be certain that we have an expression that can be solved in polynomial time. Let's now consider the inverse function. That is, calculating e for given values of c, b and m. The equation is:

e = log_e (b) -> Z_n (3)

This is a discrete logarithm to base e in Z_n and the tractability of such a problem is known to be hard and have no efficient solutions (unless of course, you have a quantum computer). Ergo, modular exponentiation is an elegant construction that can be used as a cryptographic one way function. Indeed, this particular function is the basis of the ElGamal encryption scheme.

Underlying Assumptions

The strength of one-way functions is in the difficulty in calculating the inverse. In the forward direction we have a problem ∈ P, and in the the reverse direction we have a problem ∈ NP. Clearly, we are assuming that:

P ≠ NP (4)

(4) is considered to be one of the most fundamental, yet difficult, open unresolved mathematical equations. Presently this assumption stated in (4) is a safe, albeit unproven, assumption as the majority of mathematicians believe (4) to be true as it has been scrutinized over many years without being disproved. The importance of this assumption is exemplified by the lucrative financial rewards (1 million USD) on offer from the Clay Institute for a formal proof or disproof. To date, however, no one has been able to offer such a proof. Until that happens cryptographers will continue to assume this is the case.

Problem: We are doing an experiment to find the highest floor of a building that we can drop an egg without breaking it. If there are 100 floors and we have only 2 eggs what is the minimum number of egg drops we need to make to be able to definitively identify the lowest egg-breaking floor.

Assumptions:
Before going into a solution it's wise to state our assumptions:

1. Both eggs have identical strength properties.
2. An egg that survives a drop has the same strength properties as an egg that hasn't ever been dropped.
3. If an egg dropped from floor X breaks then it would also break when dropped from all floors above X.
4. If an egg dropped from floor X does not break then it would not break when dropped from all floors below X.

Solution
First, let's consider some variants of this problem to get a better understanding of the problem space.

If we had an unlimited supply of eggs our best strategy would be to employ a binary search as this puzzle is effectively a search for an item in a sorted collection and binary search is asymptotically optimal in this case. So you would go to the 50-th floor and drop an egg. If if breaks go to the 25-th floor. If it doesn't break go to the 75-th floor, etc. At each drop you are halving the number of possible floors that could be the egg-breaking threshold so, as to be expected of many divide-and-conquer approaches, it has a logarithmic expected number of drops before you find the egg-breaking threshold.

If we have only 1 egg available the "cannot re-use a broken egg" constraint forces us to abandon the binary search approach and go with a linear search whereby we start dropping at the first floor and go up one floor at a time until we break the egg. This is the only solution we can employ that definitely tells us which floor is the egg-breaking floor. To determine the worst case analysis for this strategy we need to consider the case that the egg-breaking floor is the top floor. Clearly, for an n-storey building which has n floors, the worst case drop count is n.

But what about the case when we have 2 eggs to play with? Firstly, let's assume that there is an optimal solution and define some terminology.

Let T = the unknown egg-breaking floor. This is an (unknown) constant.
Let n = the no. of floors left to test. Initially = 100.
Let d* = the minimum number of drops required to identify T with absolute certainty with 2 eggs. This is our assumed optimal solution. Clearly, d* <= 100.

Let P(n,d) = the problem of finding T amongst n consecutive floors with d drops using at most 2 eggs.

The initial problem is clearly P(100,d*). So the only course of action available to us on "iteration 1" is to drop an egg at some floor, x₁, where 1 <= x₁ <=100. The only possible outcome is that it breaks or it doesn't break. If it breaks we must proceed to the linear search technique with the second egg starting at the lowest untested floor. In the worst case we will need another x₁-1 drops to determine T definitely giving a total of x₁ drops. Since we defined d* to be the minimum number of drops needed then it follows that x₁ = d*.

If the egg doesn't break T is still unknown and we still have 2 eggs. The only difference is that we now have fewer floors to test and 1 less drop to use, so the problem is now equivalent to P(100-x₁,d*-1). Again, the only course of action available to us on "iteration 2" is to drop an egg at some floor, x₂, where 100-x₁ < x₂ <= 100. If the egg were to break on floor x₂ we would resort to the linear search with the second egg and thus incur x₂ drops in the worst case. Since we know we have at most d*-1 drops left this implies: x₂ <= d*-1. So substituting in for d* we have: x₂ <= x₁-1.

Thus a recursive pattern is observed: on iteration i we drop an egg at the floor x-(i-1) above the lowest untested/unknown floor. We do not know the value of T so we do not know where we are going to get egg breaks, but this strategy ensures that when a break happens we do not incur fewer than d* total drops because that would violate our optimal solution definition.

The recursive pattern mentioned above can also help us identify d*, which is what was asked of us! To see this consider the case when successive egg drops result in "no break" outcomes. The pattern specifies that we need to step up a monotonically-decreasing number of floors: x, x-1, x-2, x-3, x-4, ...,1. So in the worst case when T is the top floor, since n=100 we note that:

The left hand side is the sum of an arithmetic progression which reduces to:

The maximum value of x that we can substitute into this such that this inequality still holds is x = 13 point something but x must be an integer since it is not possible to advance a fractional number of floors, so we settle on x=14=d*. Thus the least possible drops required to definitively find T when n=100 is 14.