# 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.