Top

Journal of Cryptology

Published in:

22-10-2015

An Algebraic Framework for Diffie–Hellman Assumptions

Authors: Alex Escala, Gottfried Herold, Eike Kiltz, Carla Ràfols, Jorge Villar

Published in: Journal of Cryptology | Issue 1/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We put forward a new algebraic framework to generalize and analyze Diffie–Hellman like decisional assumptions which allows us to argue about security and applications by considering only algebraic properties. Our \(\mathcal {D}_{\ell ,k}\text{- }\textsf {MDDH}\) Assumption states that it is hard to decide whether a vector in \(\mathbb {G}^\ell \) is linearly dependent of the columns of some matrix in \(\mathbb {G}^{\ell \times k}\) sampled according to distribution \(\mathcal {D}_{\ell ,k}\). It covers known assumptions such as \(\textsf {DDH},\, 2\text{- }\textsf {Lin}\) (Linear Assumption) and \(k\text{- }\textsf {Lin}\) (the k-Linear Assumption). Using our algebraic viewpoint, we can relate the generic hardness of our assumptions in m-linear groups to the irreducibility of certain polynomials which describe the output of \(\mathcal {D}_{\ell ,k}\). We use the hardness results to find new distributions for which the \(\mathcal {D}_{\ell ,k}\text{- }\textsf {MDDH}\) Assumption holds generically in m-linear groups. In particular, our new assumptions \(2\text{- }\textsf {SCasc}\) and \(2\text{- }\textsf {ILin}\) are generically hard in bilinear groups and, compared to \(2\text{- }\textsf {Lin}\), have shorter description size, which is a relevant parameter for efficiency in many applications. These results support using our new assumptions as natural replacements for the \(2\text{- }\textsf {Lin}\) assumption which was already used in a large number of applications. To illustrate the conceptual advantages of our algebraic framework, we construct several fundamental primitives based on any \(\textsf {MDDH}\) Assumption. In particular, we can give many instantiations of a primitive in a compact way, including public-key encryption, hash proof systems, pseudo-random functions, and Groth–Sahai NIZK and NIWI proofs. As an independent contribution, we give more efficient NIZK and NIWI proofs for membership in a subgroup of \(\mathbb {G}^\ell \). The results imply very significant efficiency improvements for a large number of schemes.

previous article Non-malleable Coding Against Bit-Wise and Split-State Tampering

next article Obfuscating Conjunctions

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

We actually assume that k and \(\ell \) are considered as constants, i.e., they do not depend on the security parameter. Otherwise, for a general \(\mathcal {D}_{\ell ,k}\), it is not so easy to solve the \(\mathcal {D}_{\ell ,k}\text{- }\textsf {MDDH}\) problem with the only help of a \((k+1)\)-linear map, because determinants of size \(k+1\) could not be computable in polynomial time.

If k grows linearly with the security parameter, computing determinants of size \(k+1\) in \(\mathbb {G}\) could in general take exponential time. However, for the particular matrices in the forthcoming examples (except for the uniform distribution), the associated determinants are still efficiently computable, and the Matrix DH Assumption is also false in \((k+1)\)-linear groups.

see Lemma 20 in “Appendix 2”.

If \({{\mathbf {{A}}}}\) has full rank (that happens with overwhelming probability), then \({{\mathbf {{L}}}}{{\mathbf {{A}}}}{{\mathbf {{R}}}}\) is uniformly distributed in the set of full-rank matrices in \(\mathbb {Z}_q^{\ell \times k}\), which implies that it is close to uniform in \(\mathbb {Z}_q^{\ell \times k}\).

Actually, it is assumed that \(\mathfrak {d}\ne 0\), i.e., some matrices output by \(\mathcal {D}_{k}\) have full rank. Otherwise, it is not hard finding the polynomial \(\mathfrak {h}\) based on a nonzero maximal minor of \({{\mathbf {{A}}}}(t)\), by adding to it an extra row and the column \(\vec {Z}\).

As a polynomial of total degree at most k, it vanishes with probability at most k / q at a uniformly distributed point.

Actually, to be precise, soundness is based on a computational variant of the \(\mathcal {D}_{m}\)-\(\textsf {MDDH}{}\) Assumption.

For completeness, a detailed comparison for the \(2\text{- }\textsf {Lin}\) case can be found in “Appendix 4”.

A detailed comparison for \(2\text{- }\textsf {Lin}\) case is given in “Appendix 4”. The same results hold for the Symmetric 2-cascade assumption.

Strictly speaking, only those polynomially many elements ever appearing even have a well-defined representation. Note that Q is infinite.

O. Blazy, D. Pointcheval, and D. Vergnaud, Round-optimal privacy-preserving protocols with smooth projective hash functions. In R. Cramer, editor, TCC 2012, vol. 7194 of LNCS, pp. 94–111, Taormina, Sicily, Italy, March 19–21, 2012. Springer, Berlin, Germany

D. Boneh, X. Boyen, and E.-J. Goh, Hierarchical identity based encryption with constant size ciphertext. In R. Cramer, editor, EUROCRYPT 2005, vol. 3494 of LNCS, pp. 440–456, Aarhus, Denmark, May 22–26, 2005. Springer, Berlin, Germany

D. Boneh, X. Boyen, and H. Shacham, Short group signatures. In M. Franklin, editor, CRYPTO 2004, vol. 3152 of LNCS, pp. 41–55, Santa Barbara, CA, USA, Aug. 15–19, 2004. Springer, Berlin, Germany

D. Boneh and M. K. Franklin, Identity-based encryption from the Weil pairing. In J. Kilian, editor, CRYPTO 2001, vol. 2139 of LNCS, pp. 213–229, Santa Barbara, CA, USA, Aug. 19–23, 2001. Springer, Berlin, Germany

D. Boneh, S. Halevi, M. Hamburg, and R. Ostrovsky, Circular-secure encryption from decision Diffie–Hellman. In D. Wagner, editor, CRYPTO 2008, vol. 5157 of LNCS, pp. 108–125, Santa Barbara, CA, USA, Aug. 17–21, 2008. Springer, Berlin, Germany

D. Boneh, H. W. Montgomery, and A. Raghunathan, Algebraic pseudorandom functions with improved efficiency from the augmented cascade. In E. Al-Shaer, A. D. Keromytis, and V. Shmatikov, editors, ACM CCS 10, pp. 131–140, Chicago, Illinois, USA, Oct. 4–8, 2010. ACM Press

D. Boneh, A. Sahai, and B. Waters, Fully collusion resistant traitor tracing with short ciphertexts and private keys. In S. Vaudenay, editor, EUROCRYPT 2006, vol. 4004 of LNCS, pp. 573–592, St. Petersburg, Russia, May 28–June 1, 2006. Springer, Berlin, Germany

D. Boneh and A. Silverberg, Applications of multilinear forms to cryptography. Contemporary Mathematics, 324:71–90, 2003

X. Boyen, The uber-assumption family (invited talk). In S. D. Galbraith and K. G. Paterson, editors, PAIRING 2008, vol. 5209 of LNCS, pp. 39–56, Egham, UK, Sept. 1–3, 2008. Springer, Berlin, Germany

10.

J. Camenisch, N. Chandran, and V. Shoup, A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks. In A. Joux, editor, EUROCRYPT 2009, vol. 5479 of LNCS, pp. 351–368, Cologne, Germany, April 26–30, 2009. Springer, Berlin, Germany

11.

D. Cox, J. Little, and D. O’Shea, Ideal, Varieties and Algorithms. Springer, second edition, 1996

12.

R. Cramer and V. Shoup, A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In H. Krawczyk, editor, CRYPTO’98, vol. 1462 of LNCS, pp. 13–25, Santa Barbara, CA, USA, Aug. 23–27, 1998. Springer, Berlin, Germany

13.

R. Cramer and V. Shoup, Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In L. R. Knudsen, editor, EUROCRYPT 2002, vol. 2332 of LNCS, pp. 45–64, Amsterdam, The Netherlands, April 28–May 2, 2002. Springer, Berlin, Germany

14.

R. Cramer and V. Shoup, Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM Journal on Computing, 33(1):167–226, 2003

15.

Y. Dodis, K. Haralambiev, A. López-Alt, and D. Wichs, Cryptography against continuous memory attacks. In 51st FOCS, pp. 511–520, Las Vegas, Nevada, USA, Oct. 23–26, 2010. IEEE Computer Society Press

16.

A. Escala, G. Herold, E. Kiltz, C. Ràfols, and J. Villar, An algebraic framework for Diffie-Hellman assumptions. In R. Canetti and J. A. Garay, editors, CRYPTO 2013, Part II, vol. 8043 of LNCS, pp. 129–147, Santa Barbara, CA, USA, Aug. 18–22, 2013. Springer, Berlin, Germany

17.

M. Fischlin, B. Libert, and M. Manulis, Non-interactive and re-usable universally composable string commitments with adaptive security. In D. H. Lee and X. Wang, editors, ASIACRYPT 2011, vol. 7073 of LNCS, pp. 468–485, Seoul, South Korea, Dec. 4–8, 2011. Springer, Berlin, Germany

18.

D. M. Freeman, Converting pairing-based cryptosystems from composite-order groups to prime-order groups. In H. Gilbert, editor, EUROCRYPT 2010, vol. 6110 of LNCS, pp. 44–61, French Riviera, May 30–June 3, 2010. Springer, Berlin, Germany

19.

D. Galindo, J. Herranz, and J. L. Villar, Identity-based encryption with master key-dependent message security and leakage-resilience. In S. Foresti, M. Yung, and F. Martinelli, editors, ESORICS 2012, vol. 7459 of LNCS, pp. 627–642, Pisa, Italy, Sept. 10–12, 2012. Springer, Berlin, Germany

20.

R. Gennaro and Y. Lindell, A framework for password-based authenticated key exchange. In E. Biham, editor, EUROCRYPT 2003, vol. 2656 of LNCS, pp. 524–543, Warsaw, Poland, May 4–8, 2003. Springer, Berlin, Germany. http://eprint.iacr.org/2003/032.ps.gz

21.

J. Groth and A. Sahai, Efficient noninteractive proof systems for bilinear groups. SIAM J. Comput., 41(5):1193–1232, 2012

22.

D. Hofheinz and T. Jager, Tightly secure signatures and public-key encryption. In R. Safavi-Naini and R. Canetti, editors, CRYPTO 2012, vol. 7417 of LNCS, pp. 590–607, Santa Barbara, CA, USA, Aug. 19–23, 2012. Springer, Berlin, Germany

23.

D. Hofheinz and E. Kiltz, Secure hybrid encryption from weakened key encapsulation. In A. Menezes, editor, CRYPTO 2007, vol. 4622 of LNCS, pp. 553–571, Santa Barbara, CA, USA, Aug. 19–23, 2007. Springer, Berlin, Germany

24.

A. Joux, A one round protocol for tripartite Diffie–Hellman. Journal of Cryptology, 17(4):263–276, Sept. 2004

25.

C. S. Jutla and A. Roy, Shorter quasi-adaptive NIZK proofs for linear subspaces. In K. Sako and P. Sarkar, editors, ASIACRYPT 2013, Part I, vol. 8269 of LNCS, pp. 1–20, Bangalore, India, Dec. 1–5, 2013. Springer, Berlin, Germany

26.

C. S. Jutla and A. Roy, Switching lemma for bilinear tests and constant-size NIZK proofs for linear subspaces. In J. A. Garay and R. Gennaro, editors, CRYPTO 2014, Part II, vol. 8617 of LNCS, pp. 295–312, Santa Barbara, CA, USA, Aug. 17–21, 2014. Springer, Berlin, Germany

27.

J. Katz and V. Vaikuntanathan, Round-optimal password-based authenticated key exchange. In Y. Ishai, editor, TCC 2011, vol. 6597 of LNCS, pp. 293–310, Providence, RI, USA, March 28–30, 2011. Springer, Berlin, Germany

28.

E. Kiltz, A tool box of cryptographic functions related to the Diffie-Hellman function. In C. P. Rangan and C. Ding, editors, INDOCRYPT 2001, vol. 2247 of LNCS, pp. 339–350, Chennai, India, Dec. 16–20, 2001. Springer, Berlin, Germany

29.

E. Kiltz, Chosen-ciphertext security from tag-based encryption. In S. Halevi and T. Rabin, editors, TCC 2006, vol. 3876 of LNCS, pp. 581–600, New York, NY, USA, March 4–7, 2006. Springer, Berlin, Germany

30.

E. Kiltz, K. Pietrzak, M. Stam, and M. Yung, A new randomness extraction paradigm for hybrid encryption. In A. Joux, editor, EUROCRYPT 2009, vol. 5479 of LNCS, pp. 590–609, Cologne, Germany, April 26–30, 2009. Springer, Berlin, Germany

31.

E. Kiltz and H. Wee, Quasi-adaptive NIZK for linear subspaces revisited. In E. Oswald and M. Fischlin, editors, EUROCRYPT 2015, Part II, vol. 9057 of LNCS, pp. 101–128, Sofia, Bulgaria, April 26–30, 2015. Springer, Berlin, Germany

32.

A. B. Lewko, T. Okamoto, A. Sahai, K. Takashima, and B. Waters, Fully secure functional encryption: Attribute-based encryption and (hierarchical) inner product encryption. In H. Gilbert, editor, EUROCRYPT 2010, vol. 6110 of LNCS, pp. 62–91, French Riviera, May 30–June 3, 2010. Springer, Berlin, Germany

33.

A. B. Lewko and B. Waters, Efficient pseudorandom functions from the decisional linear assumption and weaker variants. In E. Al-Shaer, S. Jha, and A. D. Keromytis, editors, ACM CCS 09, pp. 112–120, Chicago, Illinois, USA, Nov. 9–13, 2009. ACM Press

34.

B. Libert, T. Peters, M. Joye, and M. Yung, Non-malleability from malleability: Simulation-sound quasi-adaptive NIZK proofs and CCA2-secure encryption from homomorphic signatures. In P. Q. Nguyen and E. Oswald, editors, EUROCRYPT 2014, vol. 8441 of LNCS, pp. 514–532, Copenhagen, Denmark, May 11–15, 2014. Springer, Berlin, Germany

35.

B. Libert and M. Yung, Non-interactive CCA-secure threshold cryptosystems with adaptive security: New framework and constructions. In R. Cramer, editor, TCC 2012, vol. 7194 of LNCS, pp. 75–93, Taormina, Sicily, Italy, March 19–21, 2012. Springer, Berlin, Germany

36.

S. Meiklejohn, H. Shacham, and D. M. Freeman, Limitations on transformations from composite-order to prime-order groups: The case of round-optimal blind signatures. In M. Abe, editor, ASIACRYPT 2010, vol. 6477 of LNCS, pp. 519–538, Singapore, Dec. 5–9, 2010. Springer, Berlin, Germany

37.

M. Naor and O. Reingold, Number-theoretic constructions of efficient pseudo-random functions. In 38th FOCS, pp. 458–467, Miami Beach, Florida, Oct. 19–22, 1997. IEEE Computer Society Press

38.

M. Naor and G. Segev, Public-key cryptosystems resilient to key leakage. In S. Halevi, editor, CRYPTO 2009, vol. 5677 of LNCS, pp. 18–35, Santa Barbara, CA, USA, Aug. 16–20, 2009. Springer, Berlin, Germany

39.

M. Naor and M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks. In 22nd ACM STOC, pp. 427–437, Baltimore, Maryland, USA, May 14–16, 1990. ACM Press

40.

T. Okamoto and K. Takashima, Fully secure functional encryption with general relations from the decisional linear assumption. In T. Rabin, editor, CRYPTO 2010, vol. 6223 of LNCS, pp. 191–208, Santa Barbara, CA, USA, Aug. 15–19, 2010. Springer, Berlin, Germany

41.

T. Okamoto and K. Takashima, Achieving short ciphertexts or short secret-keys for adaptively secure general inner-product encryption. In D. Lin, G. Tsudik, and X. Wang, editors, CANS 11, vol. 7092 of LNCS, pp. 138–159, Sanya, China, Dec. 10–12, 2011. Springer, Berlin, Germany

42.

T. Okamoto and K. Takashima, Fully secure unbounded inner-product and attribute-based encryption. In X. Wang and K. Sako, editors, ASIACRYPT 2012, vol. 7658 of LNCS, pp. 349–366, Beijing, China, Dec. 2–6, 2012. Springer, Berlin, Germany

43.

J. H. Seo, On the (im)possibility of projecting property in prime-order setting. In X. Wang and K. Sako, editors, ASIACRYPT 2012, vol. 7658 of LNCS, pp. 61–79, Beijing, China, Dec. 2–6, 2012. Springer, Berlin, Germany

44.

J. H. Seo and J. H, Cheon, Beyond the limitation of prime-order bilinear groups, and round optimal blind signatures. In R. Cramer, editor, TCC 2012, vol. 7194 of LNCS, pp. 133–150, Taormina, Sicily, Italy, March 19–21, 2012. Springer, Berlin, Germany

45.

H. Shacham, A cramer-shoup encryption scheme from the linear assumption and from progressively weaker linear variants. Cryptology ePrint Archive, Report 2007/074, 2007. http://eprint.iacr.org/

46.

J. L. Villar, Optimal reductions of some decisional problems to the rank problem. In X. Wang and K. Sako, editors, ASIACRYPT 2012, vol. 7658 of LNCS, pp. 80–97, Beijing, China, Dec. 2–6, 2012. Springer, Berlin, Germany

47.

S. Wolf, Information-Theoretically and Computionally Secure Key Agreement in Cryptography. Ph.D. thesis, ETH Zuerich, 1999

Title: An Algebraic Framework for Diffie–Hellman Assumptions
Authors: Alex Escala
Gottfried Herold
Eike Kiltz
Carla Ràfols
Jorge Villar
Publication date: 22-10-2015
Publisher: Springer US
Published in: Journal of Cryptology / Issue 1/2017
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-015-9220-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2017

Dynamic Proofs of Retrievability Via Oblivious RAM

Obfuscating Conjunctions

Weak Locking Capacity of Quantum Channels Can be Much Larger Than Private Capacity

Non-malleable Coding Against Bit-Wise and Split-State Tampering

Efficient One-Sided Adaptively Secure Computation

Bounded Tamper Resilience: How to Go Beyond the Algebraic Barrier

Premium Partner