MulBasicIdent

MulBasicIdent is a basic multi -line encryption algorithm based on identification data . ^[1] This algorithm is a generalization of the common key generation method using bilinear pairings ( BasicIdent ) proposed by Dan Boneh and Matthew C. Franklin in 2001. ^[2]

Protocol Settings

The protocol uses the following parameters and groups :

$n$ ${\ displaystyle n}$ $n$ - the number of parties involved in the generation of the common key;
$ID_{i}$ ${\ displaystyle ID_ {i}}$ $ID_{i}$ - unique binary number (identifier) of user with number $i$ ${\ displaystyle i}$ $i$ ;
$G_{1}$ ${\ displaystyle G_ {1}}$ $G_{1}$ - additive cyclic group ;
$G_{2}$ ${\ displaystyle G_ {2}}$ $G_{2}$ - multiplicative cyclic group.

Groups $G_{1}$ ${\ displaystyle G_ {1}}$ $G_{1}$ and $G_{2}$ ${\ displaystyle G_ {2}}$ $G_{2}$ are used to further construct a multi-line mapping.

Algorithm Description

This algorithm solves the problem of encrypting a message for $n$ ${\ displaystyle n}$ $n$ subscribers with ids $ID_{1},\ldots ,ID_{n}$ ${\ displaystyle ID_ {1}, \ ldots, ID_ {n}}$ $ID_{1},\ldots ,ID_{n}$ . ^{[1] The} protocol consists of the initialization stages, obtaining the private key , encryption and decryption. Let be $k\in \mathbb {Z}$ ${\ displaystyle k \ in \ mathbb {Z}}$ $k\in \mathbb {Z}$ - the persistence parameter accepted by the algorithm at the initialization stage.

Initialization

Based $k$ ${\ displaystyle k}$ $k$ The private key generation center (PKG) generates a simple order. $q$ ${\ displaystyle q}$ $q$ groups $G_{1}$ ${\ displaystyle G_ {1}}$ $G_{1}$ and $G_{2}$ ${\ displaystyle G_ {2}}$ $G_{2}$ , $2n$ ${\ displaystyle 2n}$ $2n$ multi-line mapping $\mu \colon \underbrace {G_{1}\times G_{1}\times \ldots \times G_{1}} _{2n}\to G_{2}$ ${\ displaystyle \ mu \ colon \ underbrace {G_ {1} \ times G_ {1} \ times \ ldots \ times G_ {1}} _ {2n} \ to G_ {2}}$ $\mu \colon \underbrace {G_{1}\times G_{1}\times \ldots \times G_{1}} _{2n}\to G_{2}$ and an arbitrary element of the group $P\in G_{1}$ ${\ displaystyle P \ in G_ {1}}$ $P\in G_{1}$ .
PKG randomly selects items $s_{1},\ldots ,s_{n}\in \mathbb {Z} _{q}^{*}$ ${\ displaystyle s_ {1}, \ ldots, s_ {n} \ in \ mathbb {Z} _ {q} ^ {*}}$ $s_{1},\ldots ,s_{n}\in \mathbb {Z} _{q}^{*}$ and computes a set of public keys $P_{pub_{1}}=s_{1}P,\ldots ,P_{pub_{n}}=s_{n}P$ ${\ displaystyle P_ {pub_ {1}} = s_ {1} P, \ ldots, P_ {pub_ {n}} = s_ {n} P}$ $P_{pub_{1}}=s_{1}P,\ldots ,P_{pub_{n}}=s_{n}P$ .
PKG selects cryptographic hash functions $H_{1}\colon \{0,1\}^{*}\to G_{1}^{*}$ ${\ displaystyle H_ {1} \ colon \ {0,1 \} ^ {*} \ to G_ {1} ^ {*}}$ $H_{1}\colon \{0,1\}^{*}\to G_{1}^{*}$ and $H_{2}\colon G_{2}\to \{0,1\}^{l}$ ${\ displaystyle H_ {2} \ colon G_ {2} \ to \ {0,1 \} ^ {l}}$ $H_{2}\colon G_{2}\to \{0,1\}^{l}$ for some $l\in \mathbb {Z}$ ${\ displaystyle l \ in \ mathbb {Z}}$ $l\in \mathbb {Z}$ where $\{0,1\}^{*}$ ${\ displaystyle \ {0,1 \} ^ {*}}$ $\{0,1\}^{*}$ - the set of binary vectors of arbitrary length, and $\{0,1\}^{l}$ ${\ displaystyle \ {0,1 \} ^ {l}}$ $\{0,1\}^{l}$ - set of binary length vectors $l$ ${\ displaystyle l}$ $l$ .

In this algorithm, message spaces and ciphertexts are sets $\vartheta =\{0,1\}^{l}$ ${\ displaystyle \ vartheta = \ {0,1 \} ^ {l}}$ and $C=G_{1}^{*}\times \{0,1\}^{l}$ ${\ displaystyle C = G_ {1} ^ {*} \ times \ {0,1 \} ^ {l}}$ accordingly, the elements $s_{1},\ldots ,s_{n}\in \mathbb {Z} _{q}^{*}$ ${\ displaystyle s_ {1}, \ ldots, s_ {n} \ in \ mathbb {Z} _ {q} ^ {*}}$ are the master keys of subscribers, and the system parameters are set $\langle G_{1},G_{2},\mu ,l,P,P_{pub_{1}},\ldots ,P_{pub_{n}},H_{1},H_{2}\rangle$ ${\ displaystyle \ langle G_ {1}, G_ {2}, \ mu, l, P, P_ {pub_ {1}}, \ ldots, P_ {pub_ {n}}, H_ {1}, H_ {2} \ rangle}$ .

Getting the private key

For subscriber IDs $ID_{1},\ldots ,ID_{n}\in \{0,1\}^{*}$ ${\ displaystyle ID_ {1}, \ ldots, ID_ {n} \ in \ {0,1 \} ^ {*}}$ :

Center calculates $Q_{ID_{1}}=H_{1}(ID_{1})\in G_{1}^{*},\ldots ,Q_{ID_{n}}=H_{1}(ID_{n})\in G_{1}^{*}$ ${\ displaystyle Q_ {ID_ {1}} = H_ {1} (ID_ {1}) \ in G_ {1} ^ {*}, \ ldots, Q_ {ID_ {n}} = H_ {1} (ID_ { n}) \ in G_ {1} ^ {*}}$ .
Center calculates private keys $d_{ID_{1}}=s_{1}Q_{ID_{1}},\ldots ,d_{ID_{n}}=s_{n}Q_{ID_{n}}$ {\ displaystyle d_ {ID_ {1}} = s_ {1} Q_ {ID_ {1}}, \ ldots, d_ {ID_ {n}} = s_ {n} Q_ {ID_ {n}}} where $s_{1},\ldots ,s_{n}$ ${\ displaystyle s_ {1}, \ ldots, s_ {n}}$ - master keys.

Encryption

To encrypt the message $M$ ${\ displaystyle M}$ using ids $ID_{1},\ldots ,ID_{n}\in \{0,1\}^{*}:$ ${\ displaystyle ID_ {1}, \ ldots, ID_ {n} \ in \ {0,1 \} ^ {*}:}$ the subscriber performs the following operations:

Calculates $Q_{ID_{1}}=H_{1}(ID_{1})\in G_{1}^{*},\ldots ,Q_{ID_{n}}=H_{1}(ID_{n})\in G_{1}^{*}$ ${\ displaystyle Q_ {ID_ {1}} = H_ {1} (ID_ {1}) \ in G_ {1} ^ {*}, \ ldots, Q_ {ID_ {n}} = H_ {1} (ID_ { n}) \ in G_ {1} ^ {*}}$ .
Selects a random item. $r\in \mathbb {Z} _{q}^{*}$ ${\ displaystyle r \ in \ mathbb {Z} _ {q} ^ {*}}$ .
Calculates Ciphertext $C=\langle rP,M\oplus H_{2}(g^{r})\rangle$ ${\ displaystyle C = \ langle rP, M \ oplus H_ {2} (g ^ {r}) \ rangle}$ where $g=\mu (Q_{ID_{1}},\ldots ,Q_{ID_{n}},P_{pub_{1}},\ldots ,P_{pub_{n}})\in G_{2}^{*}$ ${\ displaystyle g = \ mu (Q_ {ID_ {1}}, \ ldots, Q_ {ID_ {n}}, P_ {pub_ {1}}, \ ldots, P_ {pub_ {n}}) \ in G_ { 2} ^ {*}}$ .

Decryption

To decrypt ciphertext $C=\langle U,V\rangle$ ${\ displaystyle C = \ langle U, V \ rangle}$ caller ID $ID_{i}$ ${\ displaystyle ID_ {i}}$ using the private key $d_{ID_{i}}\in G_{1}^{*}$ ${\ displaystyle d_ {ID_ {i}} \ in G_ {1} ^ {*}}$ the plaintext is calculated as follows:

V\oplus H_{2}(\mu (Q_{ID_{1}},\ldots ,Q_{ID_{i-1}},d_{ID_{i}},Q_{ID_{i+1}},\ldots ,Q_{ID_{n}},P_{pub_{1}},\ldots ,P_{pub_{i-1}},U,P_{pub_{i+1}},\ldots ,P_{pub_{n}}))=M

{\ displaystyle V \ oplus H_ {2} (\ mu (Q_ {ID_ {1}}, \ ldots, Q_ {ID_ {i-1}}, d_ {ID_ {i}}, Q_ {ID_ {i + 1 }}, \ ldots, Q_ {ID_ {n}}, P_ {pub_ {1}}, \ ldots, P_ {pub_ {i-1}}, U, P_ {pub_ {i + 1}}, \ ldots, P_ {pub_ {n}})) = M}

The correctness of the scheme

The correctness of the algorithm is confirmed by the following equality, the meaning of which is reduced to the substitution in the function argument $H_{2}$ ${\ displaystyle H_ {2}}$ at the stage of decrypting expressions for a private key $d_{ID_{i}}=s_{i}Q_{ID_{i}}$ ${\ displaystyle d_ {ID_ {i}} = s_ {i} Q_ {ID_ {i}}}$ and item $U=rP$ ${\ displaystyle U = rP}$ :

{\begin{aligned}\mu (Q_{ID_{1}},\ldots ,Q_{ID_{i-1}},d_{ID_{i}},Q_{ID_{i+1}},\ldots ,Q_{ID_{n}},P_{pub_{1}},\ldots ,P_{pub_{i-1}},U,P_{pub_{i+1}},\ldots ,P_{pub_{n}})\\=\mu (Q_{ID_{1}},\ldots ,Q_{ID_{n}},P_{pub_{1}},\ldots ,P,\ldots ,P_{pub_{n}})^{s_{i}r}\\=\mu (Q_{ID_{1}},\ldots ,Q_{ID_{n}},P_{pub_{1}},\ldots ,P_{pub_{n}})^{r}=g^{r}\\\end{aligned}}

{\ displaystyle {\ begin {aligned} \ mu (Q_ {ID_ {1}}, \ ldots, Q_ {ID_ {i-1}}, d_ {ID_ {i}}, Q_ {ID_ {i + 1}} , \ ldots, Q_ {ID_ {n}}, P_ {pub_ {1}}, \ ldots, P_ {pub_ {i-1}}, U, P_ {pub_ {i + 1}}, \ ldots, P_ { pub_ {n}}) \\ = \ mu (Q_ {ID_ {1}}, \ ldots, Q_ {ID_ {n}}, P_ {pub_ {1}}, \ ldots, P, \ ldots, P_ {pub_ {n}}) ^ {s_ {i} r} \\ = \ mu (Q_ {ID_ {1}}, \ ldots, Q_ {ID_ {n}}, P_ {pub_ {1}}, \ ldots, P_ {pub_ {n}}) ^ {r} = g ^ {r} \\\ end {aligned}}}

Because $V=M\oplus H_{2}(g^{r})$ ${\ displaystyle V = M \ oplus H_ {2} (g ^ {r})}$ then at the decryption stage we get $M\oplus H_{2}(g^{r})\oplus H_{2}(g^{r})=M$ ${\ displaystyle M \ oplus H_ {2} (g ^ {r}) \ oplus H_ {2} (g ^ {r}) = M}$ .

Cryptographic Strength

The protocol is persistent in an adaptive attack with a choice of plaintext and assuming the complexity of the multilinear Diffie-Hellman problem ( MDH ). ^[one]

Protocol Attack Description

The security models of broadcast encryption are based on games played by an attacker (an attacking algorithm) with a challenger (challenger).

The game of an attacker conducting an attack on the broadcast encryption algorithm consists of an initialization procedure, 2 stages of conducting requests, setting a task and outputting the result.

Initialization

Requester accepts persistence $k\in \mathbb {N}$ ${\ displaystyle k \ in \ mathbb {N}}$ , starts the algorithm initialization procedure, sends the parameters to the attacking algorithm. $p a r a m s$ ${\ displaystyle params}$ and keeps master keys $master-keys$ ${\ displaystyle master-keys}$ in secret. Identified $G_{1}$ ${\ displaystyle G_ {1}}$ - additive cyclic group of simple order $q$ ${\ displaystyle q}$ forming element $P$ ${\ displaystyle P}$ and $G_{2}$ ${\ displaystyle G_ {2}}$ - multiplicative cyclic group of simple order $q$ ${\ displaystyle q}$ .

Stage 1

Attacking algorithm generates queries $q_{1},\ldots ,q_{m}$ ${\ displaystyle q_ {1}, \ ldots, q_ {m}}$ and sends them to the requestor, where $q_{i}$ ${\ displaystyle q_ {i}}$ is an:

Request Private Key $\langle ID_{i}'\rangle$ ${\ displaystyle \ langle ID_ {i} '\ rangle}$ . In this case, the requestor runs the procedure for generating the private key. $d_{i}'\in G_{1}$ ${\ displaystyle d_ {i} '\ in G_ {1}}$ corresponding to the public key $\langle ID_{i}'\rangle$ ${\ displaystyle \ langle ID_ {i} '\ rangle}$ and transmits $d_{i}'\in G_{1}$ ${\ displaystyle d_ {i} '\ in G_ {1}}$ attacking algorithm.
Request decryption $\langle ID_{i}',C_{i}'\rangle$ ${\ displaystyle \ langle ID_ {i} ', C_ {i}' \ rangle}$ . In this case, the requestor runs the procedure for generating the private key. $d_{i}'\in G_{1}$ ${\ displaystyle d_ {i} '\ in G_ {1}}$ corresponding to the public key $\langle ID_{i}'\rangle$ ${\ displaystyle \ langle ID_ {i} '\ rangle}$ . Next, it starts the ciphertext decryption procedure. $C_{i}'$ ${\ displaystyle C_ {i} '}$ via $d_{i}'$ ${\ displaystyle d_ {i} '}$ and passes the resulting plaintext to the attacking algorithm.

These requests are carried out adaptively, i. every request $q_{i}$ ${\ displaystyle q_ {i}}$ may depend on responses to requests $q_{1},\ldots ,q_{i-1}$ ${\ displaystyle q_ {1}, \ ldots, q_ {i-1}}$ .

After completing stage 1, the attacking algorithm generates 2 open texts $M_{0},M_{1}\in \vartheta$ ${\ displaystyle M_ {0}, M_ {1} \ in \ vartheta}$ equal length and set of caller IDs $ID_{1},\ldots ,ID_{n}$ ${\ displaystyle ID_ {1}, \ ldots, ID_ {n}}$ for which he conducts an attack where $\vartheta$ ${\ displaystyle \ vartheta}$ - A set of open texts of arbitrary length. The only limitation is the fact that $ID_{i}\neq ID_{j}'$ ${\ displaystyle ID_ {i} \ neq ID_ {j} '}$ at $i=1,\ldots ,n,j=1,\ldots ,m$ ${\ displaystyle i = 1, \ ldots, n, j = 1, \ ldots, m}$ during phase 1.

Problem Statement

Requestor randomly selects a bit $b\in \{0,1\}$ ${\ displaystyle b \ in \ {0,1 \}}$ and sends $C_{b}=Encrypt(params,ID_{1},\ldots ,ID_{n},M_{b})$ ${\ displaystyle C_ {b} = Encrypt (params, ID_ {1}, \ ldots, ID_ {n}, M_ {b})}$ to the algorithm.

Stage 2

The attacking algorithm generates and sends additional requests to the requestor. $q_{m+1},\ldots ,q_{l}$ ${\ displaystyle q_ {m + 1}, \ ldots, q_ {l}}$ where $q_{i}$ ${\ displaystyle q_ {i}}$ is an:

Request Private Key $\langle ID_{j}'\rangle$ ${\ displaystyle \ langle ID_ {j} '\ rangle}$ where $ID_{i}\neq ID_{j}'$ ${\ displaystyle ID_ {i} \ neq ID_ {j} '}$ for $i=1,\ldots ,n,j=m+1,\ldots ,l$ ${\ displaystyle i = 1, \ ldots, n, j = m + 1, \ ldots, l}$ . The interrogator responds in the same way as during stage 1.
Request decryption $\langle ID_{j}',C_{j}'\rangle$ ${\ displaystyle \ langle ID_ {j} ', C_ {j}' \ rangle}$ where $\langle ID_{j}',C_{j}'\rangle \neq \langle ID_{i}',C_{i}'\rangle$ ${\ displaystyle \ langle ID_ {j} ', C_ {j}' \ rangle \ neq \ langle ID_ {i} ', C_ {i}' \ rangle}$ for $i=1,\ldots ,n,j=m+1,\ldots ,l$ ${\ displaystyle i = 1, \ ldots, n, j = m + 1, \ ldots, l}$ . The interrogator responds in the same way as during stage 1.

These requests can be carried out adaptively, as during phase 1.

Result

Attacking algorithm returns a bit $b'\in \{0,1\}$ ${\ displaystyle b '\ in \ {0,1 \}}$ and wins the game if $b=b'$ ${\ displaystyle b = b '}$ .

Winnings of the attacker $A$ ${\ displaystyle A}$ on the algorithm $E$ ${\ displaystyle E}$ called the next function parameter of persistence $k\in \mathbb {N}$ ${\ displaystyle k \ in \ mathbb {N}}$ : $Adv_{E,A}(k)=\left|Pr[b=b']-{\frac {1}{2}}\right|$ {\ displaystyle Adv_ {E, A} (k) = \ left | Pr [b = b '] - {\ frac {1} {2}} \ right |} where $Pr[b=b']$ ${\ displaystyle Pr [b = b ']}$ - the probability of an event consisting in the coincidence of the values of bits $b$ ${\ displaystyle b}$ and $b^{'}$ ${\ displaystyle b '}$ .

Improve

Based on the MulBasicIdent algorithm using the Fujisaki-Okamoto method, a complete broadcast encryption algorithm was built based on the MulFullIdent identification data.

Notes

↑ ¹ ² ³ Kosolapov D. O. Construction of multi-sided multilinear algorithms in different security models: Diss .. Cand. Phys.-Mat. sciences. - M. , 2010.
↑ Boneh D. and Franklin M. Identity-based encryption from the Weil Pairing, Crypto'2001 // Springer-Verlag: Lecture Notes in Computer Science. - 2001.

Literature

Kosolapov D.O. Construction of multilateral multilinear algorithms in different security models. - 2010.
Kosolapov D.O., Kharin E.A., Goncharov S.M., Kornyushin P.N. Multilinear cryptosystems in asymmetric cryptography (Rus.) : An article in a journal is a scientific article. - Tomsk: Tomsk State University of Control Systems and Radioelectronics, 2008. - № 2-1 (18) . - pp . 51-53 . - ISSN 1818-0442 .

[diss-1] ¹ ² ³ Kosolapov D. O. Construction of multi-sided multilinear algorithms in different security models: Diss .. Cand. Phys.-Mat. sciences. - M. , 2010.

[2] Boneh D. and Franklin M. Identity-based encryption from the Weil Pairing, Crypto'2001 // Springer-Verlag: Lecture Notes in Computer Science. - 2001.

MulBasicIdent

Protocol Settings

Algorithm Description

Initialization

Getting the private key

Encryption

Decryption

The correctness of the scheme

Cryptographic Strength

Protocol Attack Description

Initialization

Stage 1

Problem Statement

Stage 2

Result

Improve

Notes

Literature

More articles: