nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Cryptographic Sensing

verfasst von : Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai

Erschienen in: Advances in Cryptology – CRYPTO 2019

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Is it possible to measure a physical object in a way that makes the measurement signals unintelligible to an external observer? Alternatively, can one learn a natural concept by using a contrived training set that makes the labeled examples useless without the line of thought that has led to their choice? We initiate a study of “cryptographic sensing” problems of this type, presenting definitions, positive and negative results, and directions for further research.

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

Vorheriges Kapitel Non-interactive Non-malleability from Quantum Supremacy

Nächstes Kapitel Public-Key Cryptography in the Fine-Grained Setting

The requirement that \(b<1\) is what rules out the trivial solution where h is just the list of labels for the m points in S and forces actual “learning”.

In the case of proper PAC-learning (i.e., when \(\mathcal{H}=\mathcal{F}\)), [18] present a condition (called “closure under exception lists”) on \(\mathcal{F}\) under which PAC still implies OCCAM learning.

Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case/average-case equivalence. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, 4–6 May 1997 (1997)

Alekhnovich, M.: More on average case vs approximation complexity. In: Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), Cambridge, MA, USA, 11–14 October 2003 (2003)

Angluin, D.: Learning regular sets from queries and counterexamples. Inf. Comput. 75(2), 87–106 (1987)MathSciNetCrossRef

Angluin, D., Kharitonov, M.: When won’t membership queries help? (Extended abstract). In: STOC (1991)

Applebaum, B.: Exponentially-hard gap-CSP and local PRG via local hardcore functions. In: FOCS (2017)

Applebaum, B., Avron, J., Brzuska, C.: Arithmetic cryptography. J. ACM 64(2), 10:1–10:74 (2017)MathSciNetCrossRef

Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 595–618. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_35CrossRef

Applebaum, B., Haramaty, N., Ishai, Y., Kushilevitz, E., Vaikuntanathan, V.: Low-complexity cryptographic hash functions. In: ITCS (2017)

Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in NC\({}^{\text{0}}\). In: FOCS (2004)

10.

Applebaum, B., Ishai, Y., Kushilevitz, E.: On pseudorandom generators with linear stretch in NC⁰. In: Díaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX/RANDOM -2006. LNCS, vol. 4110, pp. 260–271. Springer, Heidelberg (2006). https://doi.org/10.1007/11830924_25CrossRef

11.

Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography by cellular automata or how fast can complexity emerge in nature? In: ICS (2010)

12.

Applebaum, B., Ishai, Y., Kushilevitz, E.: How to garble arithmetic circuits. In: IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, 22–25 October 2011 (2011)

13.

Bellare, M., Boldyreva, A., O’Neill, A.: Deterministic and efficiently searchable encryption. IACR Cryptology ePrint Archive 2006/186 (2006)

14.

Bellare, M., et al.: Hedged public-key encryption: how to protect against bad randomness. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 232–249. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_14CrossRef

15.

Bellare, M., Kiltz, E., Peikert, C., Waters, B.: Identity-based (lossy) trapdoor functions and applications. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 228–245. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_15CrossRef

16.

Blum, A., Furst, M.L., Kearns, M.J., Lipton, R.J.: Cryptographic primitives based on hard learning problems. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 278–291. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-48329-2_24CrossRef

17.

Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.K.: Occam’s razor. Inf. Process. Lett. 24(6), 377–380 (1987)MathSciNetCrossRef

18.

Board, R.A., Pitt, L.: On the necessity of Occam algorithms. In: STOC (1990)

19.

Boldyreva, A., Fehr, S., O’Neill, A.: On notions of security for deterministic encryption, and efficient constructions without random oracles. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 335–359. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_19CrossRef

20.

Bootle, J., Delaplace, C., Espitau, T., Fouque, P., Tibouchi, M.: LWE without modular reduction and improved side-channel attacks against BLISS. IACR Cryptology ePrint Archive 2018/22 (2018, to appear in Asiacrypt 2018)

21.

Bshouty, N.H.: Exact learning via the monotone theory (extended abstract). In: FOCS (1993)

22.

Bshouty, N.H., Eiron, N., Kushilevitz, E.: PAC learning with nasty noise. In: Watanabe, O., Yokomori, T. (eds.) ALT 1999. LNCS (LNAI), vol. 1720, pp. 206–218. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-46769-6_17CrossRefMATH

23.

Cohen, A., Goldwasser, S., Vaikuntanathan, V.: Aggregate pseudorandom functions and connections to learning. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 61–89. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46497-7_3CrossRef

24.

Dodis, Y., Smith, A.: Entropic security and the encryption of high entropy messages. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 556–577. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30576-7_30CrossRefMATH

25.

Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, 17–20 May 2008 (2008)

26.

Goldreich, O.: Candidate one-way functions based on expander graphs. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation. LNCS, vol. 6650, pp. 76–87. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22670-0_10CrossRef

27.

Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984)MathSciNetCrossRef

28.

Impagliazzo, R., Levin, L.A., Luby, M.: Pseudo-random generation from one-way functions. In: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, STOC 1989 (1989)

29.

Indyk, P.: Sketching via hashing: from heavy hitters to compressed sensing to sparse Fourier transform. In: Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013, New York, NY, USA, 22–27 June 2013 (2013)

30.

Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: FOCS (2000)

31.

Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. In: STOC (2008)

32.

Ishai, Y., Prabhakaran, M., Sahai, A.: Secure arithmetic computation with no honest majority. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 294–314. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00457-5_18CrossRef

33.

Kannan, S., Mossel, E., Sanyal, S., Yaroslavtsev, G.: Linear sketching over f\_2. In: 33rd Computational Complexity Conference, CCC 2018, San Diego, CA, USA, 22–24 June 2018 (2018)

34.

Kasiviswanathan, S.P., Lee, H.K., Nissim, K., Raskhodnikova, S., Smith, A.D.: What can we learn privately? In: FOCS (2008)

35.

Kearns, M.J., Valiant, L.G.: Cryptographic limitations on learning Boolean formulae and finite automata. In: STOC (1989)

36.

Kharitonov, M.: Cryptographic hardness of distribution-specific learning. In: STOC (1993)

37.

Klivans, A.R., Servedio, R.A.: Learning DNF in time \({2}^{\tilde{\text{o }}(\text{ n }^{1/3})}\). In: STOC (2001)

38.

Mahloujifar, S., Diochnos, D.I., Mahmoody, M.: Learning under \(p\)-tampering attacks. In: ALT (2018)

39.

McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. Deep Space Network Progress Report 44, 114–116 (1978)

40.

Micciancio, D., Peikert, C.: Hardness of SIS and LWE with small parameters. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 21–39. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_2CrossRef

41.

Mossel, E., O’Donnell, R., Servedio, R.A.: Learning juntas. In: STOC (2003)

42.

Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, 17–20 May 2008 (2008)

43.

Pitt, L., Valiant, L.G.: Computational limitations on learning from examples. J. ACM 35(4), 965–984 (1988)MathSciNetCrossRef

44.

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC (2005)

45.

Rivest, R.L.: Learning decision lists. Mach. Learn. 2(3), 229–246 (1987)

46.

Russell, A., Wang, H.: How to fool an unbounded adversary with a short key. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 133–148. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46035-7_9CrossRef

47.

Schapire, R.E.: The strength of weak learnability (extended abstract). In: FOCS (1989)

48.

Valiant, L.G.: A theory of the learnable. In: STOC (1984)

49.

Verbeurgt, K.A.: Learning DNF under the uniform distribution in quasi-polynomial time. In: COLT (1990)

Titel: Cryptographic Sensing
verfasst von: Yuval Ishai
Eyal Kushilevitz
Rafail Ostrovsky
Amit Sahai
Verlag: Springer International Publishing
Buch: Advances in Cryptology – CRYPTO 2019
Print ISBN: 978-3-030-26953-1

Electronic ISBN: 978-3-030-26954-8

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-26954-8_19

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"