# Linear Algebra - Authentication Challenge

## 1 - Challenge

$\hat{x}$

over GF(2)

• Send: Computer sends random n-vector a
• Response: Human sends back $a · \hat{x}$

.

Repeated until Computer is convinced that Human knowns password

$\hat{x}$

.

Eve eavesdrops on communication, learns m pairs:

$$\begin{array}{c} a_1,b_1 \\ \vdots \\ a_m,b_m \end{array}$$

such that

$b_i$

is the right response to challenge

$a_i$

(ie

$a · \hat{x}$

).

Then Eve can calculate right response to any challenge in

$Span \{a1, \dots , a_m\}$

Suppose

$a = \alpha_1 a_1 + \dots + \alpha_m a_m$

Then right response is

$\beta_1 . b_1 + \dots + \beta_m . b_m$

Fact: Probably rank [a1, . . . , am] is not much less than m.

Once m > n, probably

$Span \{a_1, \dots , a_m\}$

is all of

$GF(2)^n$

.

So Eve can respond to any challenge

$\hat{x}$

is a solution to:

$$\underbrace{ \begin{bmatrix} \begin{array}{r} a_1 \\ \hline\\ \vdots\\ \hline a_2 \end{array} \end{bmatrix} }_{A} \begin{bmatrix} x \end{bmatrix} = \underbrace{ \begin{bmatrix} \begin{array}{r} b_1 \\ \hline\\ \vdots\\ \hline b_m \end{array} \end{bmatrix} }_{b}$$

Solution set of Ax = b is

$\hat{x}+ \textrm{Null A}$

Once rank A reaches n, columns of A are linearly independent so Null A is trivial, so the only solution is the password

$\hat{x}$

, so we can compute the password using solver.

## 2 - How to improve the scheme ?

The way to make the scheme more secure is to introduce mistakes.

• In about 1/6 of the rounds, randomly, Human sends the wrong dot-product.
• Computer is convinced if Human gets the right answers 75% of the time.

Gaussian elimination (of any other method) does not find the solution when some of the right-hand side values are wrong.