nach oben

Designs, Codes and Cryptography

Erschienen in:

01.04.2015

Hardness of learning problems over Burnside groups of exponent 3

verfasst von: Nelly Fazio, Kevin Iga, Antonio R. Nicolosi, Ludovic Perret, William E. Skeith III

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

Einloggen, um Zugang zu erhalten

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

search-config

KI-gestützte Suche

Aus

Abstract

In this work, we investigate the hardness of learning Burnside homomorphisms with noise (\(B_{n} \hbox {-}\mathsf {LHN}\)), a computational problem introduced in the recent work of Baumslag et al. This is a generalization of the learning with errors problem, instantiated with a particular family of non-abelian groups, known as free Burnside groups of exponent 3. In our main result, we demonstrate a random self-reducibility property for \(B_{n} \hbox {-}\mathsf {LHN}\). Along the way, we also prove a sequence of lemmas regarding homomorphisms of free Burnside groups of exponent 3 that may be of independent interest.

Vorheriger Artikel Two families of nearly optimal codebooks

Nächster Artikel Planar functions and perfect nonlinear monomials over finite fields

This argument requires the existence of at least one \(g\) such that \(g\cdot s = t\); we are given such a \(g\) by transitivity.

We recall that the size of \(B_{r}\) is independent of the security parameter. Thus, enumerating all elements of \(B_{r}\) takes \({\mathcal {O}}(1)\) time.

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation, and should not be interpreted as representing the official policies, either expressed or implied, of the U.S. Army Research Laboratory, the U.S. Government, the U.K. Ministry of Defence or the U.K. Government. The U.S. and U.K. Governments are authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation hereon.

Abadi M., Feigenbaum J., Kilian J.: On hiding information from an oracle. J. Comput. Syst. Sci. 39(1), 21–50 (1989).

Angluin D., Laird P.: Learning from noisy examples. Mach. Learn. 2(4), 343–370 (1988).

Arora S., Ge R.: New algorithms for learning in presence of errors. In: International Colloquium on Automata, Languages and Programming–ICALP, pp. 403–415 (2011).

Babai L.: Random oracles separate pspace from the polynomial-time hierarchy. Inf. Process. Lett. 26(1), 51–53 (1987).

Baumslag G., Fazio N., Nicolosi A. R., Shpilrain V., Skeith III, W.E.: Generalized learning problems and applications to non-commutative cryptography. In: International Conference on Provable Security–ProvSec, LNCS, pp. 324–339. Springer, Heidelberg (2011).

Baumslag G., Fazio N., Nicolosi A. R., Shpilrain V., Skeith III, W.E.: Generalized learning problems and applications to non-commutative cryptography. Cryptology ePrint Archive, Report 2011/357, 2011. Full version of [5]. http://eprint.iacr.org/2011/357.

Beaver D., Feigenbaum J.: Hiding instances in multioracle queries. In: Symposium on Theoretical Aspects of Computer Science–STACS, Lecture Notes in Computer Science, Vol. 415, pp. 37–48. Springer, Berlin (1990).

Beaver D., Feigenbaum J., Kilian J., Rogaway P.: Security with low communication overhead. In: Advances in Cryptology–CRYPTO, Lecture Notes in Computer Science, Vol. 537, pp. 62–76. Springer, Berlin (1990).

Blum A., Kalai A., Wasserman H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. Altern. Complement. Med. 50(4), 506–519 (2003).

10.

Blum M., Kannan S.: Designing programs that check their work. J. Altern. Complement. Med. 42(1), 269–291 (1995).

11.

Feigenbaum J., Fortnow L.: On the random-self-reducibility of complete sets. In: Structure in Complexity Theory Conference, pp. 124–132 (1991).

12.

Goldreich O., Levin L. A.: A hard-core predicate for all one-way functions. In: Symposium on Theory of Computing Conference–STOC, pp. 25–32. ACM Press, New York (1989).

13.

Goldwasser S., Micali S., Rackoff C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989).

14.

Hall M.: The Theory of Groups. Macmillan Company, New York (1959).

15.

Kearns M.: Efficient noise-tolerant learning from statistical queries. In: Symposium on Theory of Computing Conference–STOC, pp. 392–401. ACM Press, New York (1993).

16.

Lyubashevsky V., Peikert C., Regev O.: On ideal lattices and learning with errors over rings. In: Advances in Cryptology–EUROCRYPT, Lecture Notes in Computer Science, Vol. 6110, pp. 1–23. Springer, Berlin (2010).

17.

Magnus W., Karrass A., Solitar D.: Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations. Interscience, New York (1966).

18.

Peikert C.: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: Symposium on Theory of Computing Conference–STOC, pp. 333–342. ACM Press, New York (2009).

19.

Regev O.: On lattices, learning with errors, random linear codes, and cryptography. In: Symposium on Theory of Computing Conference–STOC, pp. 84–93. ACM Press, New York (2005).

Titel: Hardness of learning problems over Burnside groups of exponent 3
verfasst von: Nelly Fazio
Kevin Iga
Antonio R. Nicolosi
Ludovic Perret
William E. Skeith III
Publikationsdatum: 01.04.2015
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 1/2015
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-013-9892-6

Springer Professional

Hardness of learning problems over Burnside groups of exponent 3

Abstract

Premium Partner

Springer Professional

Abstract

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

Weitere Artikel der Ausgabe 1/2015

Xing–Ling codes, duals of their subcodes, and good asymmetric quantum codes

Speeding up deciphering by hypergraph ordering

Perfect codes in the discrete simplex

Demi-matroids from codes over finite Frobenius rings

Optimal three-dimensional optical orthogonal codes of weight three

On point-transitive and transitive deficiency one parallelisms of PG

Premium Partner