# Linear Algebra - Authentication Challenge

### Table of Contents

## 1 - Challenge

Password is an n-vector <math>\hat{x}</math> over GF(2)

- Send: Computer sends random n-vector a
- Response: Human sends back <math>a · \hat{x}</math>.

Repeated until Computer is convinced that Human knowns password <math>\hat{x}</math>.

Eve eavesdrops on communication, learns m pairs: <MATH> \begin{array}{c} a_1,b_1 \\ \vdots \\ a_m,b_m \end{array} </MATH> such that <math>b_i</math> is the right response to challenge <math>a_i</math> (ie <math>a · \hat{x}</math>).

Then Eve can calculate right response to any challenge in <math>Span \{a1, \dots , a_m\}</math>

Suppose <math>a = \alpha_1 a_1 + \dots + \alpha_m a_m</math> Then right response is <math>\beta_1 . b_1 + \dots + \beta_m . b_m</math>

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

Once m > n, probably <math>Span \{a_1, \dots , a_m\}</math> is all of <math>GF(2)^n</math>.

So Eve can respond to any challenge

Also: The password <math>\hat{x}</math> is a solution to: <MATH> \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} </MATH>

Solution set of Ax = b is <math>\hat{x}+ \textrm{Null A}</math> Once rank A reaches n, columns of A are linearly independent so Null A is trivial, so the only solution is the password <math>\hat{x}</math>, 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.