Security/complexity Assumptions And Proof Strategies
The security of searchable encryption schemes is generally proved by embedding the security assumptions into their construction. Security assumptions are well-known hard problems in cryptography. By the reduction approach we reduce our scheme to these hard problems and claim the security of the scheme by that fact that if we cannot break these hard problems then one cannot break our scheme. The security assumptions are broadly categorized into weak and strong assumptions [9]. Weak assumptions ensure security as close as to discrete logarithm (DL) assumption and are also called the standard assumptions. The computational Diffie-Hellman (CDH) assumption is an example of a weak assumption. These are referred to as weak in terms of the time it takes to break these assumptions, which is significantly higher than the strong assumptions. Hence, weak assumptions are hard to break as compared ro strong assumptions. Strong assumptions are those assumptions whose security levels are lower as compared to the DL assumption. Strong assumptions are relatively risky and unreliable [9]. The commonly used security assumptions in literature for developing searchable encryption schemes are given in Table 4.1.
Table 4.1 Commonly used security assumption in the construction of searchable encryption schemes |
||
S.No. |
Security assumption |
Description |
1. |
Discrete Logarithm (DL) Assumption |
Given h e G, it is hard to find x: h = g^{x} [10]. |
2. |
Computational Diffie-Hellman (CDH) Assumption |
Given j"sG and g^{y} e G, it is hard to find g** [1 1]. |
3. |
Decision Diffie-Hellman (DDH) Assumption |
Given g^{x} e G, g^{v} e C and h e G, it is hard to determine if h = g^{xy} or not. [12]. |
4. |
Parallel Decisional Diffie- Hellman (pDDH) Assumption |
Given g^{X|}, g^{X!}, g^{x}", hi, hi, ■■■, h„ eG, it is hard to determine if hi = g^{X|X} h_{2} = g^{X2X} ■■■, h„_i = g^{x}'^{,}~'^{x}'’, h„ = g^{x}"^{xi} or not [12]. |
5. |
q-Diffie-Hellman Inversion (q-DHI) Assumption |
Given g^{x}, g^{x} , -■ , g^{x}’ € G, it is hard to compute g^{x }[13],[И]. |
6. |
q-Decision Diffie-Hellman Inversion (q-DDHI) Assumption |
Given g^{x}, g^{x} -■ , g^{x} h e G, it is hard to determine if i h = g* [13]. |
7. |
Linear Assumption |
Given g",gg^{x}". g^{r} e G; it is hard to find g^{x}*^{y} e G [15]. |
8. |
q-Linear Assumption |
Let gi. g_{2}. ■". g_{4}. go be the generators of group G. Given g|, g_{2}, ■ • , g,, go. g”, g?. • • -. g,*’ e G; it is hard to find go^{0} where x_{0} = XHi x, [15]. |
9. |
Decision Linear (DUN) Assumption |
Given g", g g^{xu}, g^{1}", h e G; it is hard to determine if h = g^{x+x}.This assumption is used in place of DDH particularly in Bilinear groups where DDH is no more a hard assumption [15]. |
10. |
q-Decision Linear (q-DLIN) Assumption |
Let gi, gi, - , g_{4}, g,_{T}i be the generators of group G. Given gi. g_{2}, , g,. g,u. gi gi. ■ ■ •. gqChe G; it is hard to determine if h = gqi-j'*^{1} [15]. |
11. |
q-Strong Diffie-Hellman (q-SDH) Assumption |
Given g^{x}, g*^{2}, •• . g^{x}’ 6 G, it is hard to find и eZ_{p} and g—[13]. |
12. |
Diffie-Hellman Exponent (DHE) Assumption |
Given go. gi. gi. g_{q}, g„_{+}2. - ■ g2, e G, where = «''■^{ic is hard to flnd} *4*i = e [^{|6}]- |
13. |
Hash Diffie-Hellman (HDH) Assumption |
Let H: {0, l}^{x} —> {0,1}^{1ел} be a hash function which returns a binary string of length say len. Given g, g^{x}, g^{r}, Hfg^{4}), Z = {0,1}*“; it is hard to find if Z=H(g^{xy}) [17]. |
(Continued)
Table 4.1 (Continued) |
||
S.No. |
Security Assumption |
Description |
14. |
Symmetric External Diffie- Hellman (SXDH) Assumption |
Let e: G| x G_{2} —» C_{T} be an asymmetric bilinear map between G, and G_{2}. Let j e {1, 2} and g, be the generator of Gy. Given g^{x}, gj, gj^{0}'. hj 6 G_{r} it is hard to determine if hy = gf [18]. It signifies that DDH is hard in both the groups. |
15. |
Knowledge of Exponents Assumption (KEA) |
If on input g and g^{x} A ouputs (Z, С): C = Z* then there exists an extractor which on same input returns z: g^{2} = Z [19]. |
16. |
Bilinear Diffie-Hellman (BDH) Assumption |
Given g, g g^{y} and g^{2} £ G, it is hard to find e(g, g)^{xy2 }[20]. |
17. |
Decision Bilinear Diffie- Hellman (DBDH) Assumption |
Given g, g^{x}, g^{r}, g^{2} e G and X € Gr, it is hard to determine if X = e(g, g)^{xy2} [20]. |
18. |
Modified Decisional Diffie- Hellman (MDDH) Assumption |
This assumption is based on DBDH assumption. Given g, g g^{r}. g^{2}, g^{xy2} € G and X 6 G, it is hard to determine if X = g^{x>2} [21]. |
19. |
Bilinear Decision Linear (BDUN) Assumption |
Given G, G_{r}, e, {g,, g_{2}, g, g{ eG}, X eG_{T}. x,y, z e Z_{p}, it is hard to determine if X = e(gi, g_{2})^{x+/} [22]. |
20. |
q-Bilinear Diffie-Hellman Inversion (q-BDHI) Assumption |
Given G, Gr, e, {g,^{x}, g^{x} .....gf }i_{6}{i.2), it is hard to find e(gi. Ы^{х} [23]. |
21. |
q-Decision Bilinear Diffie- Hellman Inversion (q-DBDHI) Assumption |
Given G, G_{r}, e, {g^{x}, g,'^{2}.....g^{x}’b_{{}i.2}, X e G_{r}, it is hard to determine if X = e(gi, g_{2})^{x} [24]. |
22. |
q-weak Bilinear Diffie-Hellman Inversion (q-wBDHI) Assumption |
Given G, G_{r}, e, {g^{x}, g,'^{2}.....gf, gf}_{ie{}i. _{2}>. it is hard to find e(g|, g_{2})^{x,}'^{V} [24]. |
23. |
q-weak Bilinear Decision Diffie-Hellman Inversion (q-wDBDHI) Assumption |
Given G, G_{r}, e, {g^{x}, gf.....gf, gJ}_{i(i{}i._{2}>X 6 G_{T}, it is hard to determine if X = e(gi, g_{2}) ^{y} [24]. |
24. |
Multi-Sequence of Exponents Diffie-Hellman (MSEDH) Assumption |
Given e: G_{t} x G_{2} Gr.go. ho be the generators of group Gi,G_{2} respectively, /, m, t be three integers and f, g be two co-prime polynomials of order /, m respectively and the following exponentiations:
It is hard to decide if Г = e(g_{0}, ho)^{4}*"’ [25]. |
25. |
Truncated decisional augmented Bilinear Diffie- Hellman (q-ABDHE) Assumption |
Given g, g^{x},g^{x} - ,g^{x}’,g^{2x},g^{2x}''*^{2} eG and ^{e}(g, g)^{2}"’ ', X 6 G_{r} where x, ze Z_{p}, it is hard to determine if X = e(g, g)"’ [26]. |
In the above table, G refers to the cyclic group of prime order p with generator g; and G?-, refers to the asymmetric bilinear map from the source group Gj and G_{2} to the target group Gj, where both Gj and G_{2} are cyclic groups of prime order p such that g_{b} g_{2} be the generator of Gj and G_{2 }respectively and e(g, g) be the generator of Gj-
Random Oracle Model And Standard Model
Most of the encryption schemes including the searchable encryption are proved secure in either the random oracle model or the standard model. These are considered as both the design as well as the proof strategies. In the standard model, the only constraint on the adversary that it considers is of the computational resources i.e. the time and the computational power, and therefore it is also called the computational model. In the standard model only security/complexity assumptions are used to prove the security of a scheme. In the random oracle model, apart from the security assumptions, one more assumption is made about the cryptographic primitives. It considers them as ideal primitives; for example, the cryptographic hashes in the random oracle model are considered as a pure random function. It is efficient and relatively easy to prove the scheme in the random oracle model, but the practitioners focus more on developing the scheme using the standard model because when these idealized primitives are replaced with the actual ones, it may not guarantee the security of the scheme in the practical scenarios.