nach oben

Journal of Cryptology

Erschienen in:

01.04.2015

Computing on Authenticated Data

verfasst von: Jae Hyun Ahn, Dan Boneh, Jan Camenisch, Susan Hohenberger, Abhi Shelat, Brent Waters

Erschienen in: Journal of Cryptology | Ausgabe 2/2015

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In tandem with recent progress on computing on encrypted data via fully homomorphic encryption, we present a framework for computing on authenticated data via the notion of slightly homomorphic signatures, or \(P\)-homomorphic signatures. With such signatures, it is possible for a third party to derive a signature on the object \(m'\) from a signature of \(m\) as long as \(P(m,m')=1\) for some predicate \(P\) which captures the “authenticatable relationship" between \(m'\) and \(m\). Moreover, a derived signature on \(m'\) reveals no extra information about the parent \(m\). Our definition is carefully formulated to provide one unified framework for a variety of distinct concepts in this area, including arithmetic, homomorphic, quotable, redactable, transitive signatures, and more. It includes being unable to distinguish a derived signature from a fresh one even when given the original signature. The inability to link derived signatures to their original sources prevents some practical privacy and linking attacks, which is a challenge not satisfied by most prior works. Under this strong definition, we then provide generic constructions for all univariate and closed predicates, and specific efficient constructions for a broad class of natural predicates such as quoting, subsets, weighted sums, averages, and Fourier transforms. To our knowledge, these are the first efficient constructions for these predicates (excluding subsets) that provably satisfy this strong security notion.

Vorheriger Artikel An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries

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

We leave it for future work to construct systems for securely quoting from two messages (or possibly more) as defined next.

A substring of \(x_1\ldots x_n\) is some \(x_i\ldots x_j\) where \(i,j\in [1,n]\) and \(i\le j\). We emphasize that we are not considering subsequences. Thus, it is not possible, in this setting, to extract a signature on “I like fish” from one on “I do not like fish”.

Following an analog of [24], selective security for signatures requires the attacker to give the forgery message before seeing the verification key.

As acknowledged in Sect. 2.2 of Boneh-Freeman [15], our definitional notion is stronger than and predates the “weak context hiding” notion of [15]. Indeed, the fact that [15] uses our framework lends support to its generality, and the fact that they could not achieve our context- hiding notion highlights its difficulty. Their “weak” definition, which is equivalent to [19], only ensures privacy when the original signatures remain hidden. In their system, signature derivation is deterministic and therefore once the original signatures become public it is easy to tell where the derived signature came from. Our signatures achieve full context hiding so that derived signatures remain private no matter what information is revealed. This is considerably harder and is not known how to do for the lattice-based signatures in Boneh-Freeman.

Given a signature scheme with a probabilistic signing algorithm, one can convert it to a scheme with a deterministic signing algorithm by: (1) including a pseudorandom function (PRF) seed as part of the secret key, and (2) during the signing algorithm, applying this PRF to the message and using the output as the randomness in the signature. Given any signature scheme, one can also construct a PRF.

We choose our modulus and hash output lengths to obtain \(\lambda \)-bit security based on the recent estimates of [57].

Using non-interactive CS-proofs [44] in the random oracle model may reduce the size of the proof, but we do not know how to avoid leaking the size of the theorem statement which also violates the context-hiding property.

Technically, our predicate \(P(m,m')\) will take the quote from the first occurrence of substring \(m'\) in \(m\), but for the moment imagine that we allowed quoting from anywhere in \(m\).

The lowest row is intentionally not assigned a number. The second lowest row is row 0. We do this so that row \(i\) can correspond to a jump of length \(2^i\).

One can build a contrived example that does not support key reduction. For instance, suppose we took an existing CP-ABE scheme and added a standard signature (from the authority) on the set \(S\) of attributes associated with the key. Then add to the decryption algorithm a check for the existence of a valid signature on the key and that the key matches this signature before proceeding with decryption.

We mean that it is possible to efficiently sample elements from the set uniformly at random.

Recall, the signature on \(\epsilon \) is the output the KeyGen algorithm.

Recall that in unique signatures [43] in addition to the regular unforgeability requirement there is an additional uniqueness property: for any honestly generated public key \( pk \) and any message \(m\) in the message space, there do not exist values \(\sigma _1,\sigma _2\) such that \(\sigma _1 \ne \sigma _2\) and yet \(\mathbf {Verify}( pk ,m,\sigma _1) = \mathbf {Verify}( pk ,m,\sigma _2)=1\).

G. Ateniese, D.H. Chou, B. de Medeiros, G. Tsudik, Sanitizable signatures, in ESORICS ’05. LNCS, vol. 3679 (2005), pp. 159–177

N. Attrapadung, B. Libert, Homomorphic network coding signatures in the standard model, in Public Key Cryptography—PKC 2011, vol. 6571 (2011), p. 17

N. Attrapadung, B. Libert, T. Peters, Computing on authenticated data: New privacy definitions and constructions, in ASIACRYPT (2012), pp. 367–385

N. Attrapadung, B. Libert, T. Peters, Efficient completely context-hiding quotable and linearly homomorphic signatures, in Public Key Cryptography (2013), pp. 386–404

A. Beimel, Secure Schemes for Secret Sharing and Key Distribution. PhD thesis, Israel Institute of Technology, Technion, Haifa, Israel (1996)

M. Bellare, O. Goldreich, S. Goldwasser, Incremental cryptography: the case of hashing and signing, in CRYPTO ’94. LNCS, vol. 839 (1994), pp. 216–233

M. Bellare, D. Micciancio, B. Warinschi, Foundations of group signatures: formal definitions, simplified requirements, and a construction based on general assumptions, in EUROCRYPT (2003), pp. 614–629

M. Bellare, G. Neven, Transitive signatures based on factoring and RSA, in ASIACRYPT ’02. LNCS, vol. 2501 (2002), pp. 397–414

M. Bellare, G. Neven, Transitive signatures: new schemes and proofs. IEEE Transactions on Information Theory, 51:2133–2151 (2005)

10.

J. Bethencourt, A. Sahai, B. Waters, Ciphertext-policy attribute-based encryption, in IEEE Symposium on Security and Privacy (2007), pp. 321–334

11.

M. Blum, A. De Santis, S. Micali, G. Persiano, Noninteractive zero-knowledge. SIAM J. Comput., 20(6):1084–1118 (1991)

12.

D. Boneh, X. Boyen, Efficient selective-ID secure identity-based encryption without random oracles, in Advances in Cryptology—EUROCRYPT ’04. vol. 3027 (2004), pp. 223–238

13.

D. Boneh, X. Boyen, H. Shacham, Short group signatures, in CRYPTO ’04. LNCS, vol. 3152 (2004), pp. 45–55

14.

D. Boneh, M.K. Franklin, Identity-based encryption from the Weil pairing. SIAM J. Comput., 32(3) (2003)

15.

D. Boneh, D. Freeman, Homomorphic signatures for polynomial functions, in Proc. of Eurocrypt. Cryptology ePrint Archive, Report 2011/018 (2011)

16.

D. Boneh, D. Freeman, Linearly homomorphic signatures over binary fields and new tools for lattice-based signatures, in Proc. of PKC. LNCS, Cryptology ePrint Archive, Report 2010/453. vol. 6571 (2011), pp. 1–16

17.

D. Boneh, D. Freeman, J. Katz, B. Waters, Signing a linear subspace: signature schemes for network coding, in Public-Key Cryptography—PKC ’09. LNCS, vol. 5443 (Springer, Berlin, 2009), pp. 68–87

18.

D. Boneh, M. Hamburg. Generalized identity based and broadcast encryption schemes, in ASIACRYPT. (2008), pp. 455–470

19.

C. Brzuska, H. Busch, O. Dagdelen, M. Fischlin, M. Franz, S. Katzenbeisser, M. Manulis, C. Onete, A. Peter, B. Poettering, D. Schröder, Redactable signatures for tree-structured data: definitions and constructions, in Applied Cryptography and Network Security (ACNS) ’08. LNCS, vol. 6123 (2010), pp. 87–104

20.

C. Brzuska, M. Fischlin, T. Freudenreich, A. Lehmann, M. Page, J. Schelbert, D. Schröder, F. Volk, Security of sanitizable signatures revisited, in Public Key Cryptography. LNCS, vol. 5443 (2009), pp. 317–336

21.

C. Brzuska, M. Fischlin, A. Lehmann, D. Schröder, Santizable signatures: how to partially delegate control for authenticated data, in BIOSIG 2009 (2009), pp. 117–128

22.

C. Brzuska, M. Fischlin, A. Lehmann, D. Schröder, Unlinkability of sanitizable signatures, in Public Key Cryptography (PKC) ’10. LNCS, vol. 6056 (2010), pp. 444–461

23.

J. Camenisch, A. Lysyanskaya, Signature schemes and anonymous credentials from bilinear maps, in Advances in Cryptology—CRYPTO ’04. vol. 3152 (2004), pp. 56–72

24.

R. Canetti, S. Halevi, J. Katz, A forward-secure public-key encryption scheme, in EUROCRYPT (2003), pp. 255–271

25.

E. Chang, C.L. Lim, J. Xu, Short redactable signatures using random trees, in CT-RSA ’09: Proceedings of the The Cryptographers’ Track at the RSA Conference 2009 on Topics in Cryptology (2009), pp. 133–147

26.

D. Charles, K.J. K. Lauter, Signatures for network coding. International Journal of Information and Coding Theory, 1(1):3–14 (2009)

27.

M. Chase, M. Kohlweiss, A. Lysyanskaya, S. Meiklejohn, Malleable signatures: complex unary transformations and delegatable anonymous credentials. Cryptology ePrint Archive, Report 2013/179 (2013). http://eprint.iacr.org/. Accessed 17 Mar 2014

28.

D. Chaum, E. van Heyst, Group signatures, in EUROCRYPT. LNCS, vol. 547 (1991), pp. 257–265

29.

B. Deiseroth, V. Fehr, M. Fischlin, M. Maasz, N.F. Reimers, R. Stein, Computing on authenticated data for adjustable predicates. Cryptology ePrint Archive, Report 2013/217 (2013). http://eprint.iacr.org/. Accessed 17 Mar 2014

30.

W. Diffie, M. Hellman, New directions in cryptography. IEEE Transactions on Information Theory, 22:644–654 (1976)

31.

C. Fragouli, E. Soljanin, Network Coding Fundamentals (Now Publishers Inc., Hanover, MA, 2007)

32.

R. Gennaro, J. Katz, H. Krawczyk, T. Rabin, Secure network coding over the integers, in Public Key Cryptography—PKC ’10. LNCS, vol. 6056 (Springer, Berlin, 2010), pp. 142–160

33.

C. Gentry, A fully homomorphic encryption scheme. PhD thesis, Stanford University (2009)

34.

O. Goldreich, S. Goldwasser, S. Micali, How to construct random functions (extended abstract), in FOCS (1984), pp. 464–479

35.

S. Goldwasser, S. Micali, R.L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput., 17(2):281–308 (1988)

36.

S. Haber, Y. Hatano, Y. Honda, W. Horne, K. Miyazaki, T. Sander, S. Tezoku, D. Yao. Efficient signature schemes supporting redaction, pseudonymization, and data deidentification, in ASIACCS ’08 (2008), p. 353–362

37.

A. Hevia, D. Micciancio, The provable security of graph-based one-time signatures and extensions to algebraic signature schemes, in ASIACRYPT ’02. LNCS, vol. 2501 (2002), pp. 379–396

38.

S. Hohenberger, B. Waters, Realizing hash-and-sign signatures under standard assumptions, in EUROCRYPT ’09. LNCS, vol. 5479 (2009), pp. 333–350

39.

R. Johnson, D. Molnar, D. Song, D. Wagner, Homomorphic signature schemes, in CT-RSA (Springer, Berlin, 2002), pp. 244–262

40.

M. Krohn, M. Freedman, D. Mazieres. On-the-fly verification of rateless erasure codes for efficient content distribution, in Proc. of IEEE Symposium on Security and Privacy (2004), pp. 226–240

41.

A.B. Lewko, T. Okamoto, A. Sahai, K. Takashima, B. Waters. Fully secure functional encryption: attribute-based encryption and (hierarchical) inner product encryption, in EUROCRYPT (2010)

42.

A.B. Lewko, B. Waters, New techniques for dual system encryption and fully secure HIBE with short ciphertexts, in TCC ’10. LNCS, vol. 5978 (2010), pp. 455–479

43.

A. Lysyanskaya, Unique signatures and verifiable random functions from the DH-DDH separation, in CRYPTO (2002), pp. 597–612

44.

S. Micali, Computationally sound proofs. SIAM J. Comput., 30(4):1253–1298 (2000)

45.

S. Micali, R.L. Rivest, Transitive signature schemes, in CT-RSA ’02. LNCS, vol. 2271 (2002), pp. 236–243

46.

K. Miyazaki, G. Hanaoka, H. Imai, Digitally signed document sanitizing scheme based on bilinear maps, in ASIACCS ’06: Proceedings of the 2006 ACM Symposium on Information, computer and communications security (2006), pp. 343–354

47.

K. Miyazaki, M. Iwamura, T. Matsumoto, R. Sasaki, H. Yoshiura, S. Tezuka, H. Imai, Digitally signed document sanitizing scheme with disclosure condition control. IEICE Trans. Fundam., E88-A(1):239–246 (2005)

48.

K. Miyazaki, S. Susaki, M. Iwamura, T. Matsumoto, R. Sasaki, H. Yoshiura, Digital document sanitizing problem. IEICE Technical, Report, 103:61–67 (2003)

49.

D. Naccache, Is theoretical cryptography any good in practice? CHES 2010 invited talk (2010). www.iacr.org/workshops/ches/ches2010. Accessed 13 Jun 2012

50.

G. Neven, A simple transitive signature scheme for directed trees. Theor. Comput. Sci., 396(1–3):277–282 (2008)

51.

R. Rivest, Two signature schemes. Slides from talk given at Cambridge University (2000). http://people.csail.mit.edu/rivest/Rivest-CambridgeTalk.pdf. Accessed 13 Jun 2012

52.

R.L. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM, 21(2):120–126 (1978)

53.

R.L. Rivest, A. Shamir, Y. Tauman, How to leak a secret: theory and applications of ring signatures, in Essays in Memory of Shimon Even (2006), pp. 164–186

54.

S.F. Shahandashti, M. Salmasizadeh, J. Mohajeri, A provably secure short transitive signature scheme from bilinear group pairs, in Security and Communication Networks. LNCS, vol. 3352 (2005), pp. 60–76

55.

A. Shamir, On the generation of cryptographically strong pseudorandom sequences. ACM Trans Comput Syst, 1:38–44 (1983)

56.

N.P. Smart, F. Vercauteren, Fully homomorphic encryption with relatively small key and ciphertext sizes, in Public Key Cryptography—PKC ’10. LNCS, vol. 6056 (Springer Berlin, 2010), pp. 420–443

57.

N. Smart. ECRYPT2 Yearly Report on Algorithms and Keysizes (2008–2009), Revision 1.0. Edited by Smart (2009). http://people.csail.mit.edu/rivest/Rivest-CambridgeTalk.pdf. Accessed 13 Jun 2012

58.

R. Steinfeld, L. Bull, Y. Zheng, Context extraction signatures, in Information Security and Cryptology (ICISC). LNCS, vol. 2288 (2001), pp. 285–304

59.

M. van Dijk, C. Gentry, S. Halevi, V. Vaikuntanathan, Fully homomorphic encryption over the integers, in Advances in Cryptology—EUROCRYPT ’10. LNCS, vol. 6110 (Springer, Berlin, 2010), pp. 24–43

60.

B. Waters, Efficient identity-based encryption without random oracles, in Advances in Cryptology—EUROCRYPT ’05. vol. 3494 (2005), pp. 320–329

61.

B. Waters, Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions, in Advances in Cryptology—CRYPTO ’09. vol. 5677 (2009), pp. 619–636

62.

B. Waters, Ciphertext-policy attribute-based encryption: an expressive, efficient, and provably secure realization, in Public Key Cryptography—PKC ’11 (2011), pp. 53–70

63.

L. Wei, S.E. Coull, M.K. Reiter, Bounded vector signatures and their applications, in ASIACCS ’11. (2011), pp. 277–285

64.

X. Yi, Directed transitive signature scheme, in CT-RSA ’07. LNCS, vol. 4377 (2007), pp. 129–144

65.

F. Zhao, T. Kalker, M. Médard, K. Han, Signatures for content distribution with network coding, in Proc. Intl. Symp. Info. Theory (ISIT) (2007)

Titel: Computing on Authenticated Data
verfasst von: Jae Hyun Ahn
Dan Boneh
Jan Camenisch
Susan Hohenberger
Abhi Shelat
Brent Waters
Publikationsdatum: 01.04.2015
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 2/2015
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-014-9182-0

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 2/2015

The Rebound Attack and Subspace Distinguishers: Application to Whirlpool

An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries

From Non-adaptive to Adaptive Pseudorandom Functions

Efficient Recursive Diffusion Layers for Block Ciphers and Hash Functions

New Attacks on IDEA with at Least 6 Rounds