Probability of false positive key matching two plaintext/ciphertext pairs Given a keyspace of $ 2^{80} $ and plaintext space of $2^{64}$. And two plaintext and ciphertext pairs $(x_1, y_1)$ , $(x_2, y_2)$. Now we have $2^{80}/2^{64} = 2^{16}$ keys that encrypt $x_1$ to $y_1$ and another $2^{16}$ keys that encrypt $x_2$ to $y_2$, with only one key that is supposed to be the target key (correct key).
What is the probability that once brute-force identifies a first key ($k_1$) this same key happen by mistake to also encrypt $x_2$ to $y_2$, that is this this key happen to be a False-positive (that is, this key will likely not encrypt $x_3$ correctly). What is the equation used and how is it derived?
Under an ideal cipher model, every key implements a random permutation. A random wrong key that maps $x_1$ to $y_1$ thus maps $x_2\ne x_1$ to a random ciphertext $y_2'$ other than $y_1$. For a $b$-bit block cipher, there are $2^b-1$ such ciphertexts, thus the probability that $y_2'=y_2$ is $1/(2^b-1)$.
The probability that an incorrect key survives two tests is thus $p=1/(2^b\,(2^b-1))$.
A random $k$-bit key has probability $q=2^{-k}$ to be correct. It passes two tests with certainty if correct, with probability $p$ otherwise. Thus a random key has probability $q+(1-q)\,p$ to pass two tests [where the $q$ term is for the correct key, the $(1-q)\,p$ term is for incorrect keys, and obtained as the the probability that a key is incorrect, times the probability that it nevertheless passes the test with $(x_1,y_1)$ and $(x_2,y_2)$ ].
Thus a random key known to pass two tests has probability $q/(q+p\,(1-q))$ to be correct [where the numerator $q$ is the probability for a random key to be correct, and the denominator is the probability that a random key pass two tests]. That simplifies to $1/(1+p\,(1/q-1))$.
The desired probability of a false positive is the complement, that is
$$\begin{align}1-1/(1+p\,(1/q-1))\,&amp;=\,1/(1+1/(p\,(1/q-1)))\\&amp;=\,1/(1+2^b\,(2^b-1)/(2^k-1))\end{align}$$
For $b$ and $k$ at least 7, that's $1/(1+2^{2b-k})$ within 1%. When further $2b-k$ is at least 7, that's $2^{k-2b}$ within 1%, here $2^{-48}$, that is less than one in 280 million million.
More generally, it can be shown that the probability of false positive after testing $n$ distinct plaintext/ciphertext pairs is $1/(1+(2^b)!/((2^b-n+1)!(2^k-1)))$. For common block ciphers like DES and wider, that's very close to $1/(1+2^{n\,b-k})$, and when $n\,b-k$ is at least 7, that's $2^{k-n\,b}$ within 1%.