nach oben

Journal of Cryptology

Erschienen in:

01.07.2021

Match Me if You Can: Matchmaking Encryption and Its Applications

verfasst von: Giuseppe Ateniese, Danilo Francati, David Nuñez, Daniele Venturi

Erschienen in: Journal of Cryptology | Ausgabe 3/2021

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We introduce a new form of encryption that we name matchmaking encryption (ME). Using ME, sender S and receiver R (each with its own attributes) can both specify policies the other party must satisfy in order for the message to be revealed. The main security guarantee is that of privacy-preserving policy matching: During decryption, nothing is leaked beyond the fact that a match occurred/did not occur. ME opens up new ways of secretly communicating and enables several new applications where both participants can specify fine-grained access policies to encrypted data. For instance, in social matchmaking, S can encrypt a file containing his/her personal details and specify a policy so that the file can be decrypted only by his/her ideal partner. On the other end, a receiver R will be able to decrypt the file only if S corresponds to his/her ideal partner defined through a policy. On the theoretical side, we define security for ME, as well as provide generic frameworks for constructing ME from functional encryption. These constructions need to face the technical challenge of simultaneously checking the policies chosen by S and R, to avoid any leakage. On the practical side, we construct an efficient identity-based scheme for equality policies, with provable security in the random oracle model under the standard BDH assumption. We implement and evaluate our scheme and provide experimental evidence that our construction is practical. We also apply identity-based ME to a concrete use case, in particular for creating an anonymous bulletin board over a Tor network.

Vorheriger Artikel Editorial

Nächster Artikel On Subversion-Resistant SNARKs

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

See https://en.wikipedia.org/wiki/Dead_drop.

See https://www.news.ucsb.edu/2019/019308/anonymous-yet-trustworthy.

Some PE schemes satisfy a stronger attribute-hiding security definition, i.e., the attribute x remains hidden even when \(f(x)=1\).

Often, and equivalently, FE schemes are parameterized by a function ensemble \(\mathcal {F}= \{f_k:\mathcal {X}\times \mathcal {R}\rightarrow \mathcal {Y}\}_{k\in \mathcal {K}}\).

Note that malleability (and thus the authenticity property considered in our paper) might be a desirable feature in some scenarios, as it implies a form of deniability. It could also be useful in future extensions of ME (e.g., in the spirit of proxy re-encryption).

This is not an issue for an ME that supports arbitrary policies, as in that case, a single policy encodes a large number of attributes.

This attack can be generalized to show that privacy does not hold if the \(\mathsf {PolGen}\) algorithm (and thus the policy key \(\mathsf {kpol}\)) is made public.

This can be achieved, e.g., by setting

https://static-content.springer.com/image/art%3A10.1007%2Fs00145-021-09381-4/MediaObjects/145_2021_9381_IEq1511_HTML.gif

, and by appending to each message the string

https://static-content.springer.com/image/art%3A10.1007%2Fs00145-021-09381-4/MediaObjects/145_2021_9381_IEq1512_HTML.gif

It is important to recall that a similar guarantee does not hold in the identity-based setting, when the receiver is semi-honest (cf. Sect. 5.1).

This choice of parameters does not take into account the quadratic loss depending on the number of queries \(q_R\) and \(q_S\) in Lemmas 7–8. To increase the level of security, we suggest adopting stronger curves such as, e.g., curve SS1024 in Charm that guarantees 112 bits of security.

https://github.com/cygnusv/matchmaking-encryption.

S. Agrawal, M. Chase, A study of pair encodings: predicate encryption in prime order groups, in Theory of Cryptography Conference (Springer, 2016), pp. 259–288

S. Agrawal, M. Chase, Simplifying design and analysis of complex predicate encryption schemes, in Annual International Conference on the Theory and Applications of Cryptographic Techniques. (Springer, 2017), pp. 627–656

S. Agrawal, D.J. Wu, Functional encryption: Deterministic to randomized functions from simple assumptions, in EUROCRYPT (2017), pp. 30–61

J.A. Akinyele, C. Garman, I. Miers, M.W. Pagano, M. Rushanan, M. Green, A.D. Rubin, Charm: A framework for rapidly prototyping cryptosystems. J. Cryptographic Eng. 3(2), 111–128 (2013)

J. Alwen, M. Barbosa, P. Farshim, R. Gennaro, S. Dov Gordon, S. Tessaro, D.A. Wilson, On the relationship between functional encryption, obfuscation, and fully homomorphic encryption, in International Conference on Cryptography and Coding (2013), pp. 65–84

P. Ananth, A. Jain, D. Khurana, A. Sahai, Indistinguishability obfuscation without multilinear maps: iO from LWE, bilinear maps, and weak pseudorandomness. Cryptology ePrint Archive, Report 2018/615 (2018)

G. Ateniese, J. Kirsch, M. Blanton, Secret handshakes with dynamic and fuzzy matching, in NDSS, vol. 7, pp. 1–19 (2007)

N. Attrapadung, H. Imai, Dual-policy attribute based encryption, in ACNS. (Springer, 2009), pp. 168–185

N. Attrapadung, S. Yamada, Duality in ABE: Converting attribute based encryption for dual predicate and dual policy via computational encodings, in CT-RSA (2015), pp. 87–105

10.

D. Balfanz, G. Durfee, N. Shankar, D. Smetters, J. Staddon, H.-C. Wong, Secret handshakes from pairing-based key agreements, in IEEE S&P (2003), pp. 180–196

11.

C.E.Z. Baltico, D. Catalano, D. Fiore, R. Gay, Practical functional encryption for quadratic functions with applications to predicate encryption, in Annual International Cryptology Conference. (Springer, 2017), pp. 67–98

12.

M. Bellare, A. Boldyreva, A. Desai, D. Pointcheval, Key-privacy in public-key encryption, in ASIACRYPT (2001), pp. 566–582

13.

J. Bethencourt, A. Sahai, B. Waters, Ciphertext-policy attribute-based encryption, in IEEE S&P (2007), pp. 321–334

14.

D. Boneh, M. Franklin, Identity-based encryption from the Weil pairing, in CRYPTO (2001), pp. 213–229

15.

D. Boneh, A. Sahai, B. Waters, Functional encryption: Definitions and challenges, in TCC (2011), pp. 253–273

16.

C. Castelluccia, S. Jarecki, G. Tsudik, Secret handshakes from CA-oblivious encryption, in ASIACRYPT (2004), pp. 293–307

17.

M. Chase, Multi-authority attribute based encryption, in TCC (2007), pp. 515–534

18.

M. Chase, S.S.M. Chow, Improving privacy and security in multi-authority attribute-based encryption, in CCS (2009), pp. 121–130

19.

L. Cheung, C. Newport, Provably secure ciphertext policy abe, in CCS (2007), pp. 456–465

20.

S.S.M. Chow, Removing escrow from identity-based encryption, in International Workshop on Public Key Cryptography. (Springer, 2009), pp. 256–276

21.

C. Costello, D. Stebila, Fixed argument pairings, in LATINCRYPT (2010), pp. 92–108

22.

I. Damgård, H. Haagh, C. Orlandi, Access control encryption: Enforcing information flow with cryptography, in TCC (2016), pp. 547–576

23.

B. Fisch, D. Vinayagamurthy, D. Boneh, S. Gorbunov, Iron: Functional encryption using intel SGX, in CCS (2017), pp. 765–782

24.

G. Fuchsbauer, R. Gay, L. Kowalczyk, C. Orlandi, Access control encryption for equality, comparison, and more, in PKC (2017), pp. 88–118

25.

S.D. Galbraith, K.G. Paterson, N.P. Smart, Pairings for cryptographers, Discrete Appl. Math. 156(16), 3113–3121 (2008)

26.

S. Garg, M. Hajiabadi, M. Mahmoody, A. Rahimi, S. Sekar, Registration-based encryption from standard assumptions, in PKC (2019), pp. 63–93

27.

R. Gay, P. Méaux, H. Wee, Predicate encryption for multi-dimensional range queries from lattices, in IACR International Workshop on Public Key Cryptography. (Springer, 2015), pp. 752–776

28.

S. Goldwasser, S. Dov Gordon, V. Goyal, A. Jain, J. Katz, F.-H. Liu, A. Sahai, E. Shi, H.-S. Zhou, Multi-input functional encryption, in EUROCRYPT (2014), pp. 578–602

29.

M.C. Gorantla, C. Boyd, J.M.G. Nieto, Attribute-based authenticated key exchange, in ACISP (2010), pp. 300–317

30.

S. Gorbunov, V. Vaikuntanathan, H. Wee, Predicate encryption for circuits from lwe, in Annual Cryptology Conference. (Springer, 2015), pp. 503–523

31.

V. Goyal, A. Jain, V. Koppula, A. Sahai, Functional encryption for randomized functionalities, in TCC (2015), pp. 325–351

32.

V. Goyal, A. Jain, O. Pandey, A. Sahai, Bounded ciphertext policy attribute based encryption, in ICALP (2008), pp. 579–591

33.

V. Goyal, O. Pandey, A. Sahai, B. Waters, Attribute-based encryption for fine-grained access control of encrypted data, in CCS (2006), pp. 89–98

34.

L. Hou, J. Lai, L. Liu, Secret handshakes with dynamic expressive matching policy, in ACISP (2016), pp. 461–476

35.

S. Jarecki, J. Kim, G. Tsudik, Authentication for paranoids: Multi-party secret handshakes, in ACNS (2006), pp. 325–339

36.

S. Jarecki, J. Kim, G. Tsudik, Group secret handshakes or affiliation-hiding authenticated group key agreement, in Cryptographers’ Track at the RSA Conference. (Springer, 2007), pp. 287–308

37.

S. Jarecki, J. Kim, G. Tsudik, Beyond secret handshakes: Affiliation-hiding authenticated key exchange, in CT-RSA (2008), pp. 352–369

38.

S. Jarecki, X. Liu, Unlinkable secret handshakes and key-private group key management schemes, in ACNS (2007), pp. 270–287

39.

J. Katz, A. Sahai, B. Waters, Predicate encryption supporting disjunctions, polynomial equations, and inner products, in Annual International Conference on the Theory and Applications of Cryptographic Techniques. (Springer, 2008), pp. 146–162

40.

S. Kim, D.J. Wu, Access control encryption for general policies from standard assumptions, in ASIACRYPT (2017), pp. 471–501

41.

V. Kolesnikov, H. Krawczyk, Y. Lindell, A. Malozemoff, T. Rabin, Attribute-based key exchange with general policies, in CCS (2016), pp. 1451–1463

42.

M. Manulis, B. Pinkas, B. Poettering, Privacy-preserving group discovery with linear complexity, in International Conference on Applied Cryptography and Network Security. (Springer, 2010), pp. 420–437

43.

M. Manulis, B. Poettering, Affiliation-hiding authentication with minimal bandwidth consumption, in IFIP International Workshop on Information Security Theory and Practices. (Springer, 2011), pp. 85–99

44.

M. Manulis, B. Poettering, Practical affiliation-hiding authentication from improved polynomial interpolation, in Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security (2011), pp. 286–295

45.

M. Manulis, B. Poettering, G. Tsudik, Affiliation-hiding key exchange with untrusted group authorities, in International Conference on Applied Cryptography and Network Security. (Springer, 2010), pp. 402–419

46.

M. Manulis, B. Poettering, G. Tsudik, Taming big brother ambitions: More privacy for secret handshakes, in International Symposium on Privacy Enhancing Technologies Symposium. (Springer, 2010), pp. 149–165

47.

M. Nekrasov, D. Iland, M. Metzger, L. Parks, E. Belding, A user-driven free speech application for anonymous and verified online, public group discourse. J. Internet Services Appl. 9(1), 21 (2018)

48.

T. Nishide, K. Yoneyama, K. Ohta, Attribute-based encryption with partially hidden encryptor-specified access structures, in ACNS (2008), pp. 111–129

49.

T. Okamoto, K. Takashima, Hierarchical predicate encryption for inner-products, in International Conference on the Theory and Application of Cryptology and Information Security. (Springer, 2009), pp. 214–231

50.

R. Ostrovsky, A. Sahai, B. Waters, Attribute-based encryption with non-monotonic access structures, in CCS (2007), pp. 195–203

51.

M. Pirretti, P. Traynor, P. McDaniel, B. Waters, Secure attribute-based systems. J. Comput. Secur. 18(5), 799–837 (2010)

52.

Y. Rouselakis, B. Waters, Efficient statically-secure large-universe multi-authority attribute-based encryption, in International Conference on Financial Cryptography and Data Security. (Springer, 2015), pp. 315–332

53.

A. Sahai, B. Waters, Fuzzy identity-based encryption, in EUROCRYPT, vol. 3494 (2005), pp. 457–473

54.

E. Shen, E. Shi, B. Waters, Predicate privacy in encryption systems, in Theory of Cryptography Conference. (Springer, 2009), pp. 457–473

55.

E. Shi, B. Waters, Delegating capabilities in predicate encryption systems, in International Colloquium on Automata, Languages, and Programming. (Springer, 2008), pp. 560–578

56.

A. Sorniotti, R. Molva, Secret handshakes with revocation support, in ICISC (2009), pp. 274–299

57.

A. Sorniotti, R. Molva, A provably secure secret handshake with dynamic controlled matching. Comput. Secur. 29(5), 619–627 (2010)

58.

P. Syverson, R. Dingledine, N. Mathewson, Tor: The second generation onion router, in Usenix Security (2004)

59.

G. Tan, R. Zhang, H. Ma, Y. Tao, Access control encryption based on lwe, in International Workshop on ASIA Public-Key Cryptography (2017), pp. 43–50

60.

Tor. Onion service protocol (2018). https://www.torproject.org/docs/onion-services.html.en

61.

G. Tsudik, S. Xu, A flexible framework for secret handshakes, in PETS (2006), pp. 295–315

62.

D. Vergnaud, Rsa-based secret handshakes, in Coding and Cryptography (2006), pp. 252–274

63.

B. Waters, Ciphertext-policy attribute-based encryption: An expressive, efficient, and provably secure realization, in PKC, vol. 6571 (2011), pp. 53–70

64.

H. Wee, Dual system encryption via predicate encodings, in Theory of Cryptography Conference (Springer, 2014), pp. 616–637

65.

H. Wee, Attribute-hiding predicate encryption in bilinear groups, revisited, in Theory of Cryptography Conference. (Springer, 2017), pp. 206–233

66.

C. Xu, H. Guo, Z. Li, Y. Mu, Affiliation-hiding authenticated asymmetric group key agreement based on short signature. Comput. J. 57(10), 1580–1590 (2014)

67.

C. Xu, L. Zhu, Z. Li, F. Wang, One-round affiliation-hiding authenticated asymmetric group key agreement with semi-trusted group authority. Computer J. 58(10), 2509–2519 (2015)

68.

S. Xu, M. Yung, K-anonymous secret handshakes with reusable credentials, in CCS (2004), pp. 158–167

69.

S. Yamada, N. Attrapadung, G. Hanaoka, N. Kunihiro, Generic constructions for chosen-ciphertext secure attribute based encryption, in PKC (2011), pp. 71–89

70.

S. Yu, K. Ren, W. Lou, Attribute-based content distribution with hidden policy, in Secure Network Protocols (2008), pp. 39–44

71.

S. Yu, K. Ren, W. Lou, Attribute-based on-demand multicast group setup with membership anonymity. Comput. Netw. 54(3), 377–386 (2010)

72.

S. Yu, K. Ren, W. Lou, J. Li, Defending against key abuse attacks in kp-abe enabled broadcast systems, in SecureComm (2009), pp. 311–329

Titel: Match Me if You Can: Matchmaking Encryption and Its Applications
verfasst von: Giuseppe Ateniese
Danilo Francati
David Nuñez
Daniele Venturi
Publikationsdatum: 01.07.2021
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 3/2021
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-021-09381-4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2021

Watermarking Cryptographic Functionalities from Standard Lattice Assumptions

On the Tight Security of TLS 1.3: Theoretically Sound Cryptographic Parameters for Real-World Deployments

Fine-Grained Cryptography Revisited

Is There an Oblivious RAM Lower Bound for Online Reads?

Secure Communication Channel Establishment: TLS 1.3 (over TCP Fast Open) versus QUIC

Round-Optimal Secure Multi-party Computation

Premium Partner