Algebraic Eraser (AE)^{[note 1]} is an anonymouskey agreementprotocol that allows two parties, each having an AE public–private key pair, to establish ashared secret over aninsecure channel.^[1] This shared secret may be directly used as a key, or toderive another key that can then be used to encrypt subsequent communications using asymmetric key cipher. Algebraic Eraser was developed by Iris Anshel, Michael Anshel,Dorian Goldfeld and Stephane Lemieux. SecureRF ownspatents covering the protocol^[2] and unsuccessfully attempted (as of July 2019) to standardize the protocol as part of ISO/IEC 29167-20,^[3] a standard for securingradio-frequency identification devices andwireless sensor networks.

Before two parties can establish a key they must first agree on a set of parameters, called the keyset parameters. These parameters comprise:

• ${\displaystyle N}$, the number of strands in the braid,
• ${\displaystyle q}$, the size of the finite field${\displaystyle {\mathbb{F}}_q}$,
• ${\displaystyle M_{\ast }}$, the initial NxN seed matrix in${\displaystyle {\mathbb{F}}_q}$,
• ${\displaystyle \mathrm{T}}$, a set of${\displaystyle N}$ elements in the finite field${\displaystyle {\mathbb{F}}_q}$ (also called the T-values), and
• ${\displaystyle A,B}$ a set of conjugates in thebraid group designed to commute with each other.

The fundamental operation of the Algebraic Eraser is a one-way function called E-multiplication. Given a matrix, permutation, anArtin generator${\displaystyle \beta }$ in the braid group, and T-values, one applies E-multiplication by converting the generator to acolored Burau matrix and braid permutation,${\displaystyle (CB(\beta ),{\sigma }_{\beta })}$, applying the permutation and T-values, and then multiplying the matrices and permutations. The output of E-multiplication is itself a matrix and permutation pair:${\displaystyle (M^{\prime },{\sigma }^{\prime })=(M,{\sigma }_0)\ast (CB(\beta ),{\sigma }_{\beta })}$.

The following example illustrates how to make a key establishment. SupposeAlice wants to establish a shared key withBob, but the only channel available may be eavesdropped by a third party. Initially, Alice and Bob must agree on the keyset parameters they will use.

Each party must have a key pair derived from the keyset, consisting of a private key (e.g., in the case of Alice)${\displaystyle (m_A,{\mathrm{B}}_a)}$ where${\displaystyle m_A}$ is a randomly selected polynomial of the seed matrix${\displaystyle m_A=\sum _{i=0}^{N-1}{a}_i{M}_{\ast }^i}$ and a braid, which is a randomly selected set of conjugates and inverses chosen from the keyset parameters (A for Alice and B for Bob, where (for Alice)${\displaystyle {\mathrm{B}}_a=\prod _{i=1}^k{A}_i^{\pm 1}}$).

From their private key material Alice and Bob each compute their public key${\displaystyle (Pu{b}_A,{\sigma }_a)}$ and${\displaystyle (Pu{b}_B,{\sigma }_b)}$ where, e.g.,${\displaystyle (Pu{b}_A,{\sigma }_a)=(m_A,id)\ast b_a}$, that is, the result of E-Multiplication of the private matrix and identity-permutation with the private braid.

Each party must know the other party's public key prior to execution of the protocol.

To compute the shared secret, Alice computes${\displaystyle (S_{ab},{\sigma }_{ab})=(m_{A}Pu{b}_B,{\sigma }_b)\ast {\mathrm{B}}_a}$ and Bob computes${\displaystyle (S_{ba},{\sigma }_{ba})=(m_{B}Pu{b}_A,{\sigma }_a)\ast {\mathrm{B}}_b}$. The shared secret is the matrix/permutation pair${\displaystyle (S_{ab},{\sigma }_{ab})}$, which equals${\displaystyle (S_{ba},{\sigma }_{ba})}$. The shared secrets are equal because the conjugate sets${\displaystyle A}$ and${\displaystyle B}$ are chosen to commute and both Alice and Bob use the same seed matrix${\displaystyle M_{\ast }}$ and T-values${\displaystyle \mathrm{T}}$.

The only information about her private key that Alice initially exposes is her public key. So, no party other than Alice can determine Alice's private key, unless that party can solve the Braid Group Simultaneous Conjugacy Separation Search problem. Bob's private key is similarly secure. No party other than Alice or Bob can compute the shared secret, unless that party can solve theDiffie–Hellman problem.

The public keys are either static (and trusted, say via a certificate) or ephemeral.Ephemeral keys are temporary and not necessarily authenticated, so if authentication is desired, authenticity assurances must be obtained by other means. Authentication is necessary to avoidman-in-the-middle attacks. If one of Alice or Bob's public key is static then man-in-the-middle attacks are thwarted. Static public keys provide neitherforward secrecy nor key-compromise impersonation resilience, among other advanced security properties. Holders of static private keys should validate the other public key, and should apply a secure key derivation function to the raw Diffie–Hellman shared secret to avoid leaking information about the static private key.

The security of AE is based on the Generalized Simultaneous Conjugacy Search Problem (GSCSP)^[4] within thebraid group. This is a distinct and different hard problem than the Conjugacy Search Problem (CSP), which has been the central hard problem in what is calledbraid group cryptography.^[5] Even if CSP is uniformly broken (which has not been done to date), it is not known how this would facilitate a break of GSCSP.

The first attack by Kalka,Teicher andTsaban shows a class of weak-keys when${\displaystyle M_{\ast }}$ or${\displaystyle m_A}$ are chosen randomly.^[6] The authors of Algebraic Eraser followed up with a preprint on how to choose parameters that aren't prone to the attack.^[7] Ben-Zvi, Blackburn, and Tsaban improved the first attack into one the authors claim can break the publicized security parameters (claimed to provide 128-bit security) using less than 8 CPU hours, and less than 64MB of memory.^[8] Anshel, Atkins and Goldfeld responded to this attack in January 2016.^[9]

A second attack by Myasnikov and Ushakov, published as a preprint, shows that conjugates chosen with a too-short conjugator braid can be separated, breaking the system.^[10] This attack was refuted by Gunnells, by showing that properly sized conjugator braids cannot be separated.^[4]

In 2016, Simon R. Blackburn andMatthew J. B. Robshaw published a range of practical attacks against the January 2016 draft of the ISO/IEC 29167-20 over-the-air protocol, including impersonation of a target tag with negligible amount of time and memory and full private key recovery requiring 2⁴⁹ time and 2⁴⁸ memory.^[11] Atkins and Goldfeld responded that adding ahash ormessage authentication code to the draft protocol defeats these attacks.^[12]

• Anshel–Anshel–Goldfeld key exchange
• Group-based cryptography
• Non-commutative cryptography

• SecureRF home page

• Key-agreement protocols

• Articles with short description
• Short description is different from Wikidata