Antisymmetrizer: Difference between revisions
en>Michael Hardy m →Example |
en>John of Reading m →Mathematical definition: Typo fixing, replaced: function function → function using AWB (8686) |
||
| Line 1: | Line 1: | ||
'''Blom's scheme''' is a symmetric threshold [[key exchange]] protocol in [[cryptography]]. The scheme was proposed by the Swedish cryptographer Rolf Blom in a series of articles in the early 1980s.<ref>Rolf Blom. Non-public key distribution. In Proc. CRYPTO 82, pages 231–236, New York, 1983. Plenum Press</ref><ref>R. Blom, "An optimal class of symmetric key generation systems", Report LiTH-ISY-I-0641, Linköping University, 1984 [http://www.csl.mtu.edu/cs6461/www/Reading/blom-eurocrypt84.pdf]</ref> | |||
A trusted party gives each participant a secret key and a public identifier, which enables any two participants to independently create a shared key for communicating. However, if an attacker can compromise the keys of at least k users, he can break the scheme and reconstruct every shared key. Blom's scheme is a form of [[threshold scheme|threshold secret sharing]]. | |||
Blom's scheme is currently used by the [[HDCP]] copy protection scheme to generate shared keys for high-definition content sources and receivers, such as [[HD DVD]] players and [[high-definition television]]s. | |||
==The protocol== | |||
The key exchange protocol involves a trusted party (Trent) and a group of <math>\scriptstyle n</math> users. Let [[Alice and Bob]] be two users of the group. | |||
===Protocol setup=== | |||
Trent chooses a random and secret [[symmetric matrix]] <math>\scriptstyle D_{k,k}</math> over the [[finite field]] <math>\scriptstyle GF(p)</math>, where p is a prime number. <math>\scriptstyle D</math> is required when a new user is to be added to the key sharing group. | |||
For example: | |||
<math>\begin{align} | |||
k &= 3\\ | |||
p &= 17\\ | |||
D &= \begin{pmatrix} 1&6&2\\6&3&8\\2&8&2\end{pmatrix}\ \mathrm{mod}\ 17 | |||
\end{align}</math> | |||
===Inserting a new participant=== | |||
New users Alice and Bob want to join the key exchanging group. Trent chooses public identifiers for each of them; i.e., k-element vectors: | |||
<math>I_{\mathrm{Alice}}, I_{\mathrm{Bob}} \in GF(p)</math>. | |||
For example: | |||
<math>I_{\mathrm{Alice}} = \begin{pmatrix} 3 \\ 10 \\ 11 \end{pmatrix}, I_{\mathrm{Bob}} = \begin{pmatrix} 1 \\ 3 \\ 15 \end{pmatrix}</math> | |||
Trent then computes their private keys: | |||
<math>\begin{align} | |||
g_{\mathrm{Alice}} &= DI_{\mathrm{Alice}}\\ | |||
g_{\mathrm{Bob}} &= DI_{\mathrm{Bob}} | |||
\end{align}</math> | |||
Using <math>D</math> as described above: | |||
<math>\begin{align} | |||
g_{\mathrm{Alice}} &= \begin{pmatrix} 1&6&2\\6&3&8\\2&8&2\end{pmatrix}\begin{pmatrix} 3 \\ 10 \\ 11 \end{pmatrix} = \begin{pmatrix} 85\\136\\108\end{pmatrix}\ \mathrm{mod}\ 17 = \begin{pmatrix} 0\\0\\6\end{pmatrix}\ \\ | |||
g_{\mathrm{Bob}} &= \begin{pmatrix} 1&6&2\\6&3&8\\2&8&2\end{pmatrix}\begin{pmatrix} 1 \\ 3 \\ 15 \end{pmatrix} = \begin{pmatrix} 49\\135\\56\end{pmatrix}\ \mathrm{mod}\ 17 = \begin{pmatrix} 15\\16\\5\end{pmatrix}\ | |||
\end{align}</math> | |||
Each will use their private key to compute shared keys with other participants of the group. | |||
===Computing a shared key between Alice and Bob=== | |||
Now Alice and Bob wish to communicate with one another. Alice has Bob's identifier <math>\scriptstyle I_{\mathrm{Bob}}</math> and her private key <math>\scriptstyle g_{\mathrm{Alice}}</math>. | |||
She computes the shared key <math>\scriptstyle k_{\mathrm{Alice / Bob}} = g_{\mathrm{Alice}}^t I_{\mathrm{Bob}}</math>, where <math>\scriptstyle t</math> denotes [[matrix transpose]]. Bob does the same, using his private key and her identifier, giving the same result: | |||
<math>k_{\mathrm{Alice / Bob}} = k_{\mathrm{Alice / Bob}}^t = (g_{\mathrm{Alice}}^t I_{\mathrm{Bob}})^t = (I_{\mathrm{Alice}}^t D^t I_{\mathrm{Bob}})^t = I_{\mathrm{Bob}}^t D I_{\mathrm{Alice}} = k_{\mathrm{Bob / Alice}}</math> | |||
They will each generate their shared key as follows: | |||
<math>\begin{align} | |||
k_{\mathrm{Alice / Bob}} &= \begin{pmatrix} 0\\0\\6 \end{pmatrix}^t \begin{pmatrix} 1\\3\\15 \end{pmatrix} = 0 \times 1 + 0 \times 3 + 6 \times 15 = 90\ \mathrm{mod}\ 17 = 5\\ | |||
k_{\mathrm{Bob / Alice}} &= \begin{pmatrix} 15\\16\\5 \end{pmatrix}^t \begin{pmatrix} 3\\10\\11 \end{pmatrix} = 15 \times 3 + 16 \times 10 + 5 \times 11 = 260\ \mathrm{mod}\ 17 = 5 | |||
\end{align}</math> | |||
==Attack resistance== | |||
In order to ensure at least k keys must be compromised before every shared key can be computed by an attacker, identifiers must be k-linearly independent: all sets of k randomly selected user identifiers must be linearly independent. Otherwise, a group of malicious users can compute the key of any other member whose identifier is linearly dependent to theirs. To ensure this property, the identifiers shall be preferably chosen from a MDS-Code matrix (maximum distance separable error correction code matrix). The rows of the MDS-Matrix would be the identifiers of the users. A MDS-Code matrix can be chosen in practice using the code-matrix of the [[Reed–Solomon error correction]] code (this error correction code requires only easily understandable mathematics and can be computed extremely quickly). | |||
== References == | |||
{{refbegin}} | |||
* {{cite book | |||
| author = [[Alfred Menezes|Alfred J. Menezes]], [[Paul van Oorschot|Paul C. van Oorschot]] and [[Scott Vanstone|Scott A. Vanstone]] | |||
| year = 1996 | |||
| title = Handbook of Applied Cryptography | |||
| publisher = [[CRC Press]] | |||
| isbn = 0-8493-8523-7 | |||
| url = http://www.cacr.math.uwaterloo.ca/hac/ | |||
}} | |||
{{refend}} | |||
<references/> | |||
[[Category:Secret sharing]] | |||
Revision as of 13:50, 8 February 2013
Blom's scheme is a symmetric threshold key exchange protocol in cryptography. The scheme was proposed by the Swedish cryptographer Rolf Blom in a series of articles in the early 1980s.[1][2]
A trusted party gives each participant a secret key and a public identifier, which enables any two participants to independently create a shared key for communicating. However, if an attacker can compromise the keys of at least k users, he can break the scheme and reconstruct every shared key. Blom's scheme is a form of threshold secret sharing.
Blom's scheme is currently used by the HDCP copy protection scheme to generate shared keys for high-definition content sources and receivers, such as HD DVD players and high-definition televisions.
The protocol
The key exchange protocol involves a trusted party (Trent) and a group of users. Let Alice and Bob be two users of the group.
Protocol setup
Trent chooses a random and secret symmetric matrix over the finite field , where p is a prime number. is required when a new user is to be added to the key sharing group.
For example:
Inserting a new participant
New users Alice and Bob want to join the key exchanging group. Trent chooses public identifiers for each of them; i.e., k-element vectors:
For example:
Trent then computes their private keys:
Each will use their private key to compute shared keys with other participants of the group.
Computing a shared key between Alice and Bob
Now Alice and Bob wish to communicate with one another. Alice has Bob's identifier and her private key .
She computes the shared key , where denotes matrix transpose. Bob does the same, using his private key and her identifier, giving the same result:
They will each generate their shared key as follows:
Attack resistance
In order to ensure at least k keys must be compromised before every shared key can be computed by an attacker, identifiers must be k-linearly independent: all sets of k randomly selected user identifiers must be linearly independent. Otherwise, a group of malicious users can compute the key of any other member whose identifier is linearly dependent to theirs. To ensure this property, the identifiers shall be preferably chosen from a MDS-Code matrix (maximum distance separable error correction code matrix). The rows of the MDS-Matrix would be the identifiers of the users. A MDS-Code matrix can be chosen in practice using the code-matrix of the Reed–Solomon error correction code (this error correction code requires only easily understandable mathematics and can be computed extremely quickly).
References
- 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
My blog: http://www.primaboinca.com/view_profile.php?userid=5889534