Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Designs, Codes and Cryptography
Erschienen in: Designs, Codes and Cryptography 3/2015

01.09.2015

Strongly secure authenticated key exchange from factoring, codes, and lattices

verfasst von: Atsushi Fujioka, Koutarou Suzuki, Keita Xagawa, Kazuki Yoneyama

Erschienen in: Designs, Codes and Cryptography | Ausgabe 3/2015

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

An unresolved problem in research on authenticated key exchange (AKE) in the public-key setting is to construct a secure protocol against advanced attacks such as key compromise impersonation and maximal exposure attacks without relying on random oracles. HMQV, a state of the art AKE protocol, achieves both efficiency and the strong security proposed by Krawczyk (we call it the \({\mathrm {CK}}^+\) model), which includes resistance to advanced attacks. However, the security proof is given under the random oracle model. We propose a generic construction of AKE from a key encapsulation mechanism (KEM). The construction is based on a chosen-ciphertext secure KEM, and the resultant AKE protocol is \({\mathrm {CK}}^+\) secure in the standard model. The construction gives the first \({\mathrm {CK}}^+\) secure AKE protocols based on the hardness of integer factorization problem, code-based problems, or learning problems with errors. In addition, instantiations under the Diffie–Hellman assumption or its variant can be proved to have strong security without non-standard assumptions such as \(\pi \)PRF and KEA1. Furthermore, we extend the \({\mathrm {CK}}^+\) model to identity-based (called the \({\hbox {id-CK}^+}\) model), and propose a generic construction of identity-based AKE (ID-AKE) based on identity-based KEM, which satisfies \({\hbox {id-CK}^+}\) security. The construction leads first strongly secure ID-AKE protocols under the hardness of integer factorization problem, or learning problems with errors.
Vorheriger Artikel An investigation of the tangent splash of a subplane of
Nächster Artikel On the automorphisms of designs constructed from finite simple groups
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
HMQV does not provide full perfect forward secrecy (fPFS), which is the same as wPFS except that the adversary can modify messages of the target session. Some schemes [14, 25, 26, 32, 40, 63] have achieved fPFS. However, the schemes [32, 40] are clearly vulnerable to MEX; that is, the session key is computable if an adversary obtains an ephemeral secret key of parties in the target session. The schemes [14, 25, 26] is resilient to MEX, but security is proved in the random oracle model. The other scheme [63] limits instantiations to DH-based. Upgrading wPFS to fPFS is not that difficult; it can be done by simply adding MAC or a signature of ephemeral public keys. Thus, we do not discuss fPFS in this paper.
 
2
Static public keys must be known to both parties in advance. They can be obtained by exchanging them before starting the protocol or by receiving them from a certificate authority. This situation is common for all PKI-based AKE schemes.
 
3
A similar trick is used in the Okamoto AKE scheme [56].
 
4
Actually, \(F_{{\sigma _A}}(r_{A}) \oplus F_{r'_{A}}'(\sigma _A')\) can be replaced with \(F_{{\sigma _A}}(r_{A}) \oplus F_{r'_{A}}'(1^\kappa )\). This modification has no influence to the security proof.
 
5
The BCGNP construction with an additional exchange of a DH value (called Protocol 2 in [12, 13]) can be proved in the CK model, and it satisfies wPFS and resistance to KCI. We can extend the security of Protocol 2 to the \({\mathrm {CK}}^+\) security with the twisted PRF trick. If IND-CPA KEM in \({\mathsf {GC}}\) is instantiated with the ElGamal KEM, our scheme is the same as Protocol 2 with the twisted PRF trick. Thus, our scheme can also be seen as a generalization of the BCGNP construction.
 
6
The hardness of the (ring-)LWE problems are reduced to the worst-case hardness of the (ideal) lattice problems.
 
Literatur
1.
Agrawal S., Boneh D., Boyen, X.: Efficient lattice (H)IBE in the standard model. In: EUROCRYPT 2010, pp. 553–572 (2010).
2.
Agrawal S., Boneh D., Boyen X.: Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. In: CRYPTO 2010, pp. 98–115 (2010).
3.
Ajtai M.: Generating hard instances of lattice problems (extended abstract). In: STOC 1996, pp. 99–108 (1996).
4.
Banerjee A., Peikert C., Rosen A.: Pseudorandom functions and lattices. In: EUROCRYPT 2012, pp. 719–737 (2012).
5.
Bellare M., Rogaway P.: Entity authentication and key distribution. In: CRYPTO 1993, pp. 232–249 (1993).
6.
Bernstein D.J., Lange T., Peters C.: Wild McEliece. In: SAC 2010, pp. 143–158 (2010).
7.
Bernstein D.J., Lange T., Peters C.: Smaller decoding exponents: ball-collision decoding. In: CRYPTO 2011, pp. 743–760 (2011).
8.
Boneh D., Boyen X.: Efficient selective-ID secure identity-based encryption without random oracles. In: EUROCRYPT 2004, pp. 223–238 (2004). See also Cryptology ePrint Archive-2004/172.
9.
Boneh D., Boyen X., Shacham H.: Short group signatures. In: CRYPTO 2004, pp. 41–55 (2004).
10.
Boneh D., Canetti R., Halevi S., Katz J.: Chosen-ciphertext security from identity-based encryption. SIAM J. Comput. 36(5), 1301–1328 (2007).
11.
Boneh D., Franklin M.K.: Identity-based encryption from the weil pairing. In: CRYPTO 2001, pp. 213–229 (2001).
12.
Boyd C., Cliff Y., González Nieto J.M., Paterson K.G.: Efficient one-round key exchange in the standard model. In: ACISP 2008, pp. 69–83 (2008).
13.
Boyd C., Cliff Y., González Nieto J.M., Paterson K.G.: One-round key exchange in the standard model. In: IJACT 1(3), pp. 181–199 (2009).
14.
Boyd C., González Nieto J.M.: On forward secrecy in one-round key exchange. In: IMA Int. Conf. 2011, pp. 451–468 (2011).
15.
Boyen X., Mei Q., Waters B.: Direct chosen ciphertext security from identity-based techniques. In: ACM Conference on Computer and Communications Security 2005, pp. 320–329 (2005).
16.
Canetti R., Goldreich O., Halevi S.: The random oracle methodology, revisited (preliminary version). In: STOC 1998, pp. 131–140 (1998).
17.
Canetti R., Krawczyk H.: Analysis of key-exchange protocols and their use for building secure channels. In: EUROCRYPT 2001, pp. 453–474 (2001).
18.
Cash D., Hofheinz D., Kiltz E., Peikert C.: Bonsai trees, or how to delegate a lattice basis. In: EUROCRYPT 2010, pp. 523–552 (2010).
19.
Chen L., Cheng Z., Smart N.P.: Identity-based key agreement protocols from pairings. Int. J. Inf. Secur. 6(4), 213–241 (2007).
20.
Chevallier-Mames B., Joye M.: Chosen-ciphertext secure RSA-type cryptosystems. In: ProvSec 2009, pp. 32–46 (2009).
21.
Cramer R., Shoup V.: A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In: CRYPTO 1998, pp. 13–25 (1998).
22.
Cramer R., Shoup V.: Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM J. Comput. 33, 167–226 (2004).
23.
Cremers C.J.F.: Session-state reveal is stronger than ephemeral key reveal: attacking the NAXOS authenticated key exchange protocol. In: ACNS 2009, pp. 20–33 (2009).
24.
Cremers C.J.F.: Examining indistinguishability-based security models for key exchange protocols: the case of CK, CK-HMQV, and eCK. In: ASIACCS 2011, pp. 80–91 (2011).
25.
Cremers C.J.F., Feltz M.: One-round strongly secure key exchange with perfect forward secrecy and deniability. In: Cryptology ePrint Archive: 2011/300 (2011).
26.
Cremers C.J.F., Feltz M.: Beyond eCK: perfect forward secrecy under actor compromise and ephemeral-key reveal. In: ESORICS 2012, pp. 734–751 (2012).
27.
Dachman-Soled D., Gennaro R., Krawczyk H., Malkin T.: Computational extractors and pseudorandomness. In: TCC 2012, pp. 383–403 (2012).
28.
Damgård I.: Towards practical public key systems secure against chosen ciphertext attacks. In: CRYPTO 1991, pp. 445–456 (1991).
29.
Dowsley R., Müller-Quade J., Nascimento A.C.A.: A CCA2 secure public key encryption scheme based on the McEliece assumptions in the standard model. In: CT-RSA 2009, pp. 240–251 (2009).
30.
Fiore D., Gennaro R.: Making the Diffie–Hellman protocol identity-based. In: CT-RSA 2010, pp. 165–178 (2010).
31.
Fujioka A., Suzuki K., Ustaoglu B.: Ephemeral key leakage resilient and efficient ID-AKEs that can share identities, private and master keys. In: Pairing 2010, pp. 187–205 (2010).
32.
Gennaro R., Krawczyk H., Rabin T.: Okamoto-Tanaka revisited: fully authenticated Diffie–Hellman with minimal overhead. In: ACNS 2010, pp. 309–328 (2010).
33.
Gennaro R., Shoup V.: A note on an encryption scheme of Kurosawa and Desmedt. In: Cryptology ePrint Archive: 2004/194 (2004).
34.
Gorantla M.C., Boyd C., González Nieto J.M., Manulis M.: Generic one round group key exchange in the standard model. In: ICISC 2009, pp. 1–15 (2009).
35.
Hanaoka G., Kurosawa K.: Efficient chosen ciphertext secure public key encryption under the computational Diffie–Hellman assumption. In: ASIACRYPT 2008, pp. 308–325 (2008).
36.
Haralambiev K., Jager T., Kiltz E., Shoup V.: Simple and efficient public-key encryption from computational Diffie–Hellman in the standard model. In: Public Key Cryptography 2010, pp. 1–18 (2010).
37.
Hofheinz D., Kiltz E.: Practical chosen ciphertext secure encryption from factoring. In: EUROCRYPT 2009, pp. 313–332 (2009).
38.
Hofheinz D., Kiltz E.: The group of signed quadratic residues and applications. In: CRYPTO 2009, pp. 637–653 (2009).
39.
Huang H., Cao Z.: An ID-based authenticated key exchange protocol based on bilinear Diffie–Hellman problem. In: ASIACCS 2009, pp. 333–342 (2009).
40.
Jeong I.R., Katz J., Lee D.H.: One-round protocols for two-party authenticated key exchange. In: ACNS 2004, pp. 220–232 (2004).
41.
Kiltz E.: Chosen-ciphertext secure key-encapsulation based on gap hashed Diffie–Hellman. In: Public Key Cryptography 2007, pp. 282–297 (2007).
42.
Kiltz E., Mohassel P., O’Neill A.: Adaptive trapdoor functions and chosen-ciphertext security. In: EUROCRYPT 2010, pp. 673–692 (2010).
43.
Krawczyk H.: HMQV: A high-performance secure Diffie–Hellman protocol. In: CRYPTO 2005, pp. 546–566 (2005).
44.
Krawczyk H.: Cryptographic extraction and key derivation: The HKDF Scheme. In: CRYPTO 2010, pp. 631–648 (2010).
45.
Kurosawa K., Desmedt Y.: A new paradigm of hybrid encryption scheme. In: CRYPTO 2004, pp. 426–442 (2004).
46.
LaMacchia B.A., Lauter K., Mityagin A.: Stronger security of authenticated key exchange. In: ProvSec 2007, pp. 1–16 (2007).
47.
Langlois A., Stehle D.: Hardness of decision (R)LWE for any modulus. In: Cryptology ePrint Archive: 2012/091 (2012).
48.
Lyubashevsky V., Micciancio D.: Generalized compact knapsacks are collision resistant. In: ICALP (2) 2006, pp. 144–155 (2006).
49.
Lyubashevsky V., Peikert C., Regev O.: On Ideal lattices and learning with errors over rings. In: EUROCRYPT 2010, pp. 1–23 (2010).
50.
McEliece R.J.: A public-key cryptosystem based on algebraic coding theory. In: Deep Space Network progress Report (1978).
51.
Mei Q., Li B., Lu X., Jia D.: Chosen ciphertext secure encryption under factoring assumption revisited. In: Public Key Cryptography 2011, pp. 210–227 (2011).
52.
Micciancio D., Peikert C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: EUROCRYPT 2012, pp. 700–718 (2012).
53.
Micciancio D., Regev O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267–302 (2007).
54.
Naor M.: On cryptographic assumptions and challenges. In: CRYPTO 2003, pp. 96–109 (2003).
55.
Nojima R., Imai H., Kobara K., Morozov K.: Semantic security for the McEliece cryptosystem without random oracles. Des. Codes Cryptogr. 49(1–3), 289–305 (2008).
56.
Okamoto T.: Authenticated key exchange and key encapsulation in the standard model. In: ASIACRYPT 2007, pp. 474–484 (2007).
57.
Peikert C.: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: STOC 2009, pp. 333–342 (2009).
58.
Peikert C., Rosen A.: Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In: TCC 2006, pp. 145–166 (2006).
59.
Peikert C., Waters B.: Lossy trapdoor functions and their applications. In: STOC 2008, pp. 187–196 (2008).
60.
Regev O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 139–160 (2009).
61.
Sarr A.P., Elbaz-Vincent P., Bajard J.C.: A new security model for authenticated key agreement. In: SCN 2010, pp. 219–234 (2010).
62.
Stehlé D., Steinfeld R., Tanaka K., Xagawa K.: Efficient public key encryption based on ideal lattices. In: ASIACRYPT 2009, pp. 617–635 (2009).
63.
Yoneyama K.: One-round authenticated key exchange with strong forward secrecy in the standard model against constrained adversary. In: IWSEC 2012, pp. 69–86 (2012).
64.
Yoneyama K.: Generic construction of two-party round-optimal attribute-based authenticated key exchange without random oracles. IEICE Trans. 96A(6), 1112–1123 (2013).
65.
Yoneyama K.: One-round authenticated key exchange with strong forward secrecy in the standard model against constrained adversary. IEICE Trans. 96A(6), 1124–1138 (2013).
Metadaten
Titel
Strongly secure authenticated key exchange from factoring, codes, and lattices
verfasst von
Atsushi Fujioka
Koutarou Suzuki
Keita Xagawa
Kazuki Yoneyama
Publikationsdatum
01.09.2015
Verlag
Springer US
Erschienen in
Designs, Codes and Cryptography / Ausgabe 3/2015
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-014-9972-2

Weitere Artikel der Ausgabe 3/2015

Designs, Codes and Cryptography 3/2015 Zur Ausgabe

OriginalPaper

Practical-time attacks against reduced variants of MISTY1

OriginalPaper

Differential cryptanalysis of PRESENT-like cipher

OriginalPaper

Enhanced Boolean functions suitable for the filter model of pseudo-random generator

OriginalPaper

Plateaued functions and one-and-half difference sets

OriginalPaper

On a 5-design related to a putative extremal doubly even self-dual code of length a multiple of 24

OriginalPaper

Codes over rings and Hermitian lattices