Blakley

Error

There was an error loading the page.

Contributors

History

○

Julien Ugon 1 year, 6 months ago

Published this.

○

Julien Ugon 1 year, 7 months ago

Created this as a copy of Shamir (Matrix).

There is only one version of this question that you have access to.

There are 2 other versions that do you not have access to.

Question statement

We want to set up a $(\var{k},\var{n})$ Blakley scheme, that is, we want to share a secret between $n=\var{n}$ people so that any $k=\var{k}$ of them can find the secret, but no $\var{k-1}$ alone can (clearly we need $n\geq k$ ). We work modulo the prime $p=\var{p}$ and the secret is $x_0$ .

Our first step is to generate a $\var{k}$ -dimensional point $Q = (x_0,\var{xstring})$ : the first coordinate of this point is the secret $x_0$ , and the other coordinates $(\var{xstring})$ are picked randomly $\pmod{\var{p}}$ .

Each of the $\var{n}$ persons is given the equation of a plane in $\mathbb R^3$ passing through the point $Q= (x_0,\var{xstring})$ : for each plane we generate random coefficients $a_i,b_i\pmod{\var{p}}$ and then set $c_i=z_0-a_ix_0-b_iy_0\pmod{\var{p}}$ . The equation of the plane is $z=a_ix+b_iy+c_i\pmod{\var{p}}$ . The key for Person $i$ is therefore the pair $((a_i,b_i),c_i)$ .

After generating the keys, Alice, Bob and Charles get the keys $\var{keystrings}$ .

Give any introductory information the student needs.

			Name	Type	Generated Value

k	integer	3
n	integer	20
p	number	191
x	polynomial	mod_polynomial(x,191)

			Name	Type	Generated Value

			M		Error evaluating variable m: `map` operation must work over a list or a range, not name
			B		Error evaluating variable b: `map` operation must work over a list or a range, not name
			detm		Error evaluating variable detm: Variable `M` is not defined.
			invdetm		Error evaluating variable invdetm: Variable `detm` is not defined.
			adjm		Error evaluating variable adjm: Variable `M` is not defined.
			invm		Error evaluating variable invm: Variable `invdetm` is not defined.
			sol		Error evaluating variable sol: Variable `invm` is not defined.

			Name	Type	Generated Value

eqn	string	a_\{i,0\}x_0+a_\{i,1\}x_1
a	string	a_\{i,0\},a_\{i,1\}
xstring	string	y_0,z_0

			Name	Type	Generated Value

s	integer	83
Q	list	[ 83, 108, 41 ]
planes	list	List of 20 items
rhs	list	List of 20 items
values		Error evaluating variable values: Can't automatically convert from list to boolean.
keystrings		Error evaluating variable keystrings: Variable `values` is not defined.

Automatically regenerate variables?

Name

Data type

Value

xxxxxxxxxx
 
3

JME function reference

Description

How many people are needed to retrieve the secret.

Describe what this variable represents, and list any assumptions made about its value.

Can an exam override the value of this variable?

Generated value: `integer`

→ Used by:

Q
a
eqn
keystrings
planes
values

This variable doesn't seem to be used anywhere.

Parts

System Gap-fill
1. Gap M Matrix entry
  Add
2. Gap b Matrix entry
  Add
Solving the system Gap-fill
1. Gap inverse of M Matrix entry
  Add
2. Gap coefficients Matrix entry
  Add
Original Message Number entry

Gap-fill

Ask the student a question, and give any hints about how they should answer this part.

Write the linear system $M\textbf x=\textbf{b}$ that Alice, Bob and Charles will need to solve. A row of the matrix $M$ has the form $a_i,b_i,-1$ per plane and the constant vector $\textbf{b}$ has an entry per plane:

$M≡$M$\textbf{b}≡$b$\pmod{\var{p}}$

Advice

System

The equations are given as $a_ix+b_iy-z=-c_i$. So for each of the keys, the corresponding row in the matrix will be $[a_i, b_i, -1]$ and the corresponding coefficient for $b$ will be $-c_i\pmod{\var{p}}$.

Since Alice's key is $(a_1,b_1)=\var{values[0][0][0..k-1]}$ and $c_i=\var{values[0][1]}$, the first row of the matrix have coefficients $\var{transpose(values[0][0])}$, and the right hand side has coefficient $\var{p-values[0][1]}$.
Since Bob's key is $(a_1,b_1)=\var{values[1][0][0..k-1]}$ and $c_i=\var{values[1][1]}$, the first row of the matrix have coefficients $\var{transpose(values[1][0])}$, and the right hand side has coefficient $\var{p-values[1][1]}$.
Since Charles key is $(a_1,b_1)=\var{values[2][0][0..k-1]}$ and $c_i=\var{values[2][1]}$, the first row of the matrix have coefficients $\var{transpose(values[2][0])}$, and the right hand side has coefficient $\var{p-values[2][1]}$.

Inverting the system

The matrix $\var{M}$ has determinant $\var{detm}\pmod{\var{p}}$ and adjoint $\var{adjm}$. So, its inverse is $\var{detm}^{-1}\var{adjm}\pmod{\var{p}} = \var{invm}$.

Solving the system

To solve the system it remains to multiply $M^{-1}$ by the right hand side: \[\var{invm}\var{b} = \var{q}\].

The original message

The original message is simply the first coordinate of this point: $\var{s}$.

Give a worked solution to the whole question.

Use this tab to check that this question works as expected.

There was an error which means the tests can't run:

Part	Test	Passed?
Gap-fill
Gap-fill		Hasn't run yet
Matrix entry
Matrix entry		Hasn't run yet
Matrix entry
Matrix entry		Hasn't run yet
Gap-fill
Gap-fill		Hasn't run yet
Matrix entry
Matrix entry		Hasn't run yet
Matrix entry
Matrix entry		Hasn't run yet
Number entry
Number entry		Hasn't run yet

This question is used in the following exam:

secret-sharing-exam by Guillermo Pineda in SIT281.

Loading...

Error

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

History

Comment

Checkpoint description

Julien Ugon 1 year, 6 months ago

Julien Ugon 1 year, 7 months ago

Error in variable testing condition

Error

Warning

Generated value: `integer`

Parts

Gap-fill

System

Inverting the system

Solving the system

The original message

Loading...

Error

Blakley

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

History

Comment

Checkpoint description

Julien Ugon 1 year, 6 months ago

Julien Ugon 1 year, 7 months ago

Error in variable testing condition

Error

Warning

Generated value: integer

Parts

Gap-fill

System

Inverting the system

Solving the system

The original message

Generated value: `integer`