Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 1/2015

01-04-2015

Hardness of learning problems over Burnside groups of exponent 3

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

Published in: Designs, Codes and Cryptography | Issue 1/2015

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.
previous article Two families of nearly optimal codebooks
next article Planar functions and perfect nonlinear monomials over finite fields
Footnotes
1
This argument requires the existence of at least one \(g\) such that \(g\cdot s = t\); we are given such a \(g\) by transitivity.
 
2
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.
 
3
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.
 
Literature
1.
Abadi M., Feigenbaum J., Kilian J.: On hiding information from an oracle. J. Comput. Syst. Sci. 39(1), 21–50 (1989).
2.
Angluin D., Laird P.: Learning from noisy examples. Mach. Learn. 2(4), 343–370 (1988).
3.
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).
4.
Babai L.: Random oracles separate pspace from the polynomial-time hierarchy. Inf. Process. Lett. 26(1), 51–53 (1987).
5.
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).
6.
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.
7.
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).
8.
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).
9.
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).
Metadata
Title
Hardness of learning problems over Burnside groups of exponent 3
Authors
Nelly Fazio
Kevin Iga
Antonio R. Nicolosi
Ludovic Perret
William E. Skeith III
Publication date
01-04-2015
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 1/2015
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-013-9892-6

Other articles of this Issue 1/2015

Designs, Codes and Cryptography 1/2015 Go to the issue

OriginalPaper

Demi-matroids from codes over finite Frobenius rings

OriginalPaper

Comment on “Identity-based non-interactive key distribution with forward security”

OriginalPaper

On point-transitive and transitive deficiency one parallelisms of PG

OriginalPaper

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

OriginalPaper

New lower bounds on the aperiodic Hamming correlations of frequency hopping sequences with low hit zone

OriginalPaper

On relative constant-weight codes

Premium Partner

    Image Credits