 # 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 . 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 . 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 = gx . 2. Computational Diffie-Hellman (CDH) Assumption Given j"sG and gy e G, it is hard to find g** [1 1]. 3. Decision Diffie-Hellman (DDH) Assumption Given gx e G, gv e C and h e G, it is hard to determine if h = gxy or not. . 4. Parallel Decisional Diffie- Hellman (pDDH) Assumption Given gX|, gX!, gx", hi, hi, ■■■, h„ eG, it is hard to determine if hi = gX|X h2 = gX2X ■■■, h„_i = gx',~'x'’, h„ = gx"xi or not . 5. q-Diffie-Hellman Inversion (q-DHI) Assumption Given gx, gx , -■ , gx’ € G, it is hard to compute gx ,[И]. 6. q-Decision Diffie-Hellman Inversion (q-DDHI) Assumption Given gx, gx -■ , gx h e G, it is hard to determine if i h = g* . 7. Linear Assumption Given g",ggx". gr e G; it is hard to find gx*y e G . 8. q-Linear Assumption Let gi. g2. ■". g4. go be the generators of group G. Given g|, g2, ■ • , g,, go. g”, g?. • • -. g,*’ e G; it is hard to find go0 where x0 = XHi x, . 9. Decision Linear (DUN) Assumption Given g", g gxu, g1", h e G; it is hard to determine if h = gx+x.This assumption is used in place of DDH particularly in Bilinear groups where DDH is no more a hard assumption . 10. q-Decision Linear (q-DLIN) Assumption Let gi, gi, - , g4, g,Ti be the generators of group G. Given gi. g2, , g,. g,u. gi gi. ■ ■ •. gqChe G; it is hard to determine if h = gqi-j'*1 . 11. q-Strong Diffie-Hellman (q-SDH) Assumption Given gx, g*2, •• . gx’ 6 G, it is hard to find и eZp and g—. 12. Diffie-Hellman Exponent (DHE) Assumption Given go. gi. gi. gq, 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, gx, gr, Hfg4), Z = {0,1}*“; it is hard to find if Z=H(gxy) .

(Continued)

 Table 4.1 (Continued) S.No. Security Assumption Description 14. Symmetric External Diffie- Hellman (SXDH) Assumption Let e: G| x G2 —» CT be an asymmetric bilinear map between G, and G2. Let j e {1, 2} and g, be the generator of Gy. Given gx, gj, gj0'. hj 6 Gr it is hard to determine if hy = gf . It signifies that DDH is hard in both the groups. 15. Knowledge of Exponents Assumption (KEA) If on input g and gx A ouputs (Z, С): C = Z* then there exists an extractor which on same input returns z: g2 = Z . 16. Bilinear Diffie-Hellman (BDH) Assumption Given g, g gy and g2 £ G, it is hard to find e(g, g)xy2 . 17. Decision Bilinear Diffie- Hellman (DBDH) Assumption Given g, gx, gr, g2 e G and X € Gr, it is hard to determine if X = e(g, g)xy2 . 18. Modified Decisional Diffie- Hellman (MDDH) Assumption This assumption is based on DBDH assumption. Given g, g gr. g2, gxy2 € G and X 6 G, it is hard to determine if X = gx>2 . 19. Bilinear Decision Linear (BDUN) Assumption Given G, Gr, e, {g,, g2, g, g{ eG}, X eGT. x,y, z e Zp, it is hard to determine if X = e(gi, g2)x+/ . 20. q-Bilinear Diffie-Hellman Inversion (q-BDHI) Assumption Given G, Gr, e, {g,x, gx .....gf }i6{i.2), it is hard to find e(gi. Ых . 21. q-Decision Bilinear Diffie- Hellman Inversion (q-DBDHI) Assumption Given G, Gr, e, {gx, g,'2.....gx’b{i.2}, X e Gr, it is hard to determine if X = e(gi, g2)x . 22. q-weak Bilinear Diffie-Hellman Inversion (q-wBDHI) Assumption Given G, Gr, e, {gx, g,'2.....gf, gf}ie{i. 2>. it is hard to find e(g|, g2)x,'V . 23. q-weak Bilinear Decision Diffie-Hellman Inversion (q-wDBDHI) Assumption Given G, Gr, e, {gx, gf.....gf, gJ}i(i{i.2>X 6 GT, it is hard to determine if X = e(gi, g2) y . 24. Multi-Sequence of Exponents Diffie-Hellman (MSEDH) Assumption Given e: Gt x G2 Gr.go. ho be the generators of group Gi,G2 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(g0, ho)4*"’ . 25. Truncated decisional augmented Bilinear Diffie- Hellman (q-ABDHE) Assumption Given g, gx,gx - ,gx’,g2x,g2x''*2 eG and e(g, g)2"’ ', X 6 Gr where x, ze Zp, it is hard to determine if X = e(g, g)"’ .

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 G2 to the target group Gj, where both Gj and G2 are cyclic groups of prime order p such that gb g2 be the generator of Gj and G2 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.