×
Yan, Di; Yu, Yu; Liu, Hanlin; Zhao, Shuoyao; Zhang, Jiang

An improved algorithm for learning sparse parities in the presence of noise. (English) Zbl 1504.68088

Theor. Comput. Sci. 873, 76-86 (2021).
Summary: We revisit the Learning Sparse Parities with Noise (LSPN) problem on \(k\) out of \(n\) variables for \(k \ll n\), and present the following findings.
1.
For true parity size \(k = n^u\) for any \(0 < u < 1\), and noise rate \(\eta < 1 / 2\), the first algorithm solves the \((n,k, \eta )\)-LSPN problem with constant probability and time/sample complexity \(\frac{ n^{( 1 - u + o ( 1 ) ) k}}{ ( 1 / 2 - \eta )^2} \).
2.
For any \(1 / 2 < c_1 < 1\), \(k = o(\eta n / \log n)\), and \(\eta \leq n^{- c_1} / 4\), our second algorithm solves the \((n,k, \eta )\)-LSPN problem with constant probability and time/sample complexity \(n^{2 ( 1 - c_1 + o ( 1 ) ) k} \).
3.
We show a “win-win” result about reducing the number of samples. If there is an algorithm that solves \((n, k, \eta)\)-LSPN problem with probability \(\Omega(1)\), time/sample complexity \(n^{O ( k )}\) for \(k = o( n^{1 - c})\), any noise rate \(\eta = n^{1 - 2 c} / 3\) and \(1 / 2 \leq c < 1\). Then, either there exists an algorithm that solves the \((n, k, \mu)\)-LSPN problem under lower noise rate \(\mu = n^{- c} / 3\) using only \(2n\) samples, or there exists an algorithm that solves the \((n, k^\prime, \mu)\)-LSPN problem for a much larger \(k^\prime = n^{1 - c}\) with probability \(n^{- O ( k )} / \mathsf{poly}(n)\), and time complexity \(\mathsf{poly}(n) \cdot n^{O ( k )} \), using only \(n\) samples.
Our algorithms are simple in concept by combining a few basic techniques such as majority voting, reduction from the LSPN problem to its decisional variant, Goldreich-Levin list decoding, and computational sample amplification.

MSC:

68Q32 Computational learning theory
68T05 Learning and adaptive systems in artificial intelligence

Keywords:

learning theory; algorithm analysis; learning parity with noise; learning sparse parity with noise; sample amplification

Software:

McEliece
Cite Review PDF
Full Text: DOI

References:

[1] Angluin, D.; Laird, P. D., Learning from noisy examples, Mach. Learn., 2, 4, 343-370 (1987)
[2] Kearns, M. J., Efficient noise-tolerant learning from statistical queries, (Kosaraju, S. R.; Johnson, D. S.; Aggarwal, A., Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing. Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, San Diego, CA, USA, May 16-18, 1993 (1993), ACM), 392-401 · Zbl 1310.68179
[3] Blum, A.; Furst, M. L.; Kearns, M. J.; Lipton, R. J., Cryptographic primitives based on hard learning problems, (Stinson, D. R., Advances in Cryptology - CRYPTO ’93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings. Advances in Cryptology - CRYPTO ’93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings, Lecture Notes in Computer Science, vol. 773 (1993), Springer), 278-291 · Zbl 0870.94021
[4] Katz, J.; Shin, J. S., Parallel and concurrent security of the HB and HB^+ protocols, (Vaudenay, S., Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006, Proceedings. Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006, Proceedings, Lecture Notes in Computer Science, vol. 4004 (2006), Springer), 73-87 · Zbl 1140.94352
[5] Applebaum, B.; Ishai, Y.; Kushilevitz, E., Cryptography with constant input locality, (Menezes, A., Advances in Cryptology - CRYPTO 2007, 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007, Proceedings. Advances in Cryptology - CRYPTO 2007, 27th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2007, Proceedings, Lecture Notes in Computer Science, vol. 4622 (2007), Springer), 92-110 · Zbl 1215.94029
[6] Berlekamp, E. R.; McEliece, R. J.; van Tilborg, H. C.A., On the inherent intractability of certain coding problems (corresp.), IEEE Trans. Inf. Theory, 24, 3, 384-386 (1978) · Zbl 0377.94018
[7] Blum, A.; Kalai, A.; Wasserman, H., Noise-tolerant learning, the parity problem, and the statistical query model, J. ACM, 50, 4, 506-519 (2003) · Zbl 1325.68114
[8] Lyubashevsky, V., The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem, (Chekuri, C.; Jansen, K.; Rolim, J. D.P.; Trevisan, L., Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings. Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3624 (2005), Springer), 378-389 · Zbl 1142.68399
[9] Alekhnovich, M., More on average case vs approximation complexity, (44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings (2003), IEEE Computer Society: IEEE Computer Society Cambridge, MA, USA), 298-307
[10] Stern, J., A method for finding codewords of small weight, (Cohen, G. D.; Wolfmann, J., Coding Theory and Applications. Coding Theory and Applications, 3rd International Colloquium, Toulon, France, November 2-4, 1988, Proceedings. Coding Theory and Applications. Coding Theory and Applications, 3rd International Colloquium, Toulon, France, November 2-4, 1988, Proceedings, Lecture Notes in Computer Science, vol. 388 (1988), Springer), 106-113 · Zbl 0678.94006
[11] Canteaut, A.; Chabaud, F., A new algorithm for finding minimum-weight words in a linear code: application to mceliece’s cryptosystem and to narrow-sense BCH codes of length 511, IEEE Trans. Inf. Theory, 44, 1, 367-378 (1998) · Zbl 1053.94558
[12] Bernstein, D. J.; Lange, T.; Peters, C., Smaller decoding exponents: ball-collision decoding, (Rogaway, P., Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings. Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings, Lecture Notes in Computer Science, vol. 6841 (2011), Springer), 743-760 · Zbl 1287.94053
[13] Kirchner, P., Improved generalized birthday attack, IACR Cryptol. ePrint Arch., 2011, 377 (2011)
[14] Becker, A.; Joux, A.; May, A.; Meurer, A., Decoding random binary linear codes in 2^n/20: how \(1 + 1 = 0\) improves information set decoding, (Pointcheval, D.; Johansson, T., Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings. Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings, Lecture Notes in Computer Science, vol. 7237 (2012), Springer), 520-536 · Zbl 1291.94206
[15] Feldman, V.; Gopalan, P.; Khot, S.; Ponnuswami, A. K., New results for learning noisy parities and halfspaces, (47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings (2006), IEEE Computer Society), 563-574
[16] Hopper, N. J.; Blum, M., Secure human identification protocols, (Boyd, C., Advances in Cryptology - ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, December 9-13, 2001, Proceedings. Advances in Cryptology - ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, December 9-13, 2001, Proceedings, Lecture Notes in Computer Science, vol. 2248 (2001), Springer), 52-66 · Zbl 1062.94549
[17] Grigorescu, E.; Reyzin, L.; Vempala, S. S., On noise-tolerant learning of sparse parities and related problems, (Kivinen, J.; Szepesvári, C.; Ukkonen, E.; Zeugmann, T., Algorithmic Learning Theory - 22nd International Conference, ALT 2011, Espoo, Finland, October 5-7, 2011. Proceedings. Algorithmic Learning Theory - 22nd International Conference, ALT 2011, Espoo, Finland, October 5-7, 2011. Proceedings, Lecture Notes in Computer Science, vol. 6925 (2011), Springer), 413-424 · Zbl 1348.68194
[18] Reyzin, L., On boosting sparse parities, (International Symposium on Artificial Intelligence and Mathematics. International Symposium on Artificial Intelligence and Mathematics, ISAIM 2014, Fort Lauderdale, FL, USA, January 6-8, 2014 (2014))
[19] Reyzin, L., On boosting sparse parities, (Brodley, C. E.; Stone, P., Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27 -31, 2014, Québec City, Québec, Canada (2014), AAAI Press), 2055-2061
[20] Caruana, R.; Niculescu-Mizil, A., An empirical comparison of supervised learning algorithms, (Cohen, W. W.; Moore, A. W., Machine Learning, Proceedings of the Twenty-Third International Conference. Machine Learning, Proceedings of the Twenty-Third International Conference, ICML 2006, Pittsburgh, Pennsylvania, USA, June 25-29, 2006. Machine Learning, Proceedings of the Twenty-Third International Conference. Machine Learning, Proceedings of the Twenty-Third International Conference, ICML 2006, Pittsburgh, Pennsylvania, USA, June 25-29, 2006, ACM International Conference Proceeding Series, vol. 148 (2006), ACM), 161-168
[21] Reyzin, L.; Schapire, R. E., How boosting the margin can also boost classifier complexity, (Cohen, W. W.; Moore, A. W., Machine Learning, Proceedings of the Twenty-Third International Conference. Machine Learning, Proceedings of the Twenty-Third International Conference, ICML 2006, Pittsburgh, Pennsylvania, USA, June 25-29, 2006. Machine Learning, Proceedings of the Twenty-Third International Conference. Machine Learning, Proceedings of the Twenty-Third International Conference, ICML 2006, Pittsburgh, Pennsylvania, USA, June 25-29, 2006, ACM International Conference Proceeding Series, vol. 148 (2006), ACM), 753-760
[22] Valiant, G., Finding correlations in subquadratic time, with applications to learning parities and juntas, (53rd Annual IEEE Symposium on Foundations of Computer Science. 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012 (2012), IEEE Computer Society), 11-20
[23] Valiant, G., Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem, J. ACM, 62, 2, Article 13 pp. (2015) · Zbl 1333.68235
[24] Goldreich, O.; Levin, L. A., A hard-core predicate for all one-way functions, (Johnson, D. S., Proceedings of the 21st Annual ACM Symposium on Theory of Computing. Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA (1989), ACM), 25-32
[25] Impagliazzo, R., A personal view of average-case complexity, (Proceedings of the Tenth Annual Structure in Complexity Theory Conference. Proceedings of the Tenth Annual Structure in Complexity Theory Conference, Minneapolis, Minnesota, USA, June 19-22, 1995 (1995), IEEE Computer Society), 134-147
[26] Döttling, N., Low noise LPN: KDM secure public key encryption and sample amplification, (Katz, J., Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30 - April 1, 2015, Proceedings. Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30 - April 1, 2015, Proceedings, Lecture Notes in Computer Science, vol. 9020 (2015), Springer), 604-626 · Zbl 1345.94057
[27] Yu, Y.; Steinberger, J. P., Pseudorandom functions in almost constant depth from low-noise LPN, (Fischlin, M.; Coron, J., Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II. Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II, Lecture Notes in Computer Science, vol. 9666 (2016), Springer), 154-183 · Zbl 1400.94178
[28] Kiltz, E.; Masny, D.; Pietrzak, K., Simple chosen-ciphertext security from low-noise LPN, (Krawczyk, H., Public-Key Cryptography - PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina, March 26-28, 2014. Proceedings. Public-Key Cryptography - PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina, March 26-28, 2014. Proceedings, Lecture Notes in Computer Science, vol. 8383 (2014), Springer), 1-18 · Zbl 1335.94059
[29] O’Neill, A.; Peikert, C.; Waters, B., Bi-deniable public-key encryption, (Rogaway, P., Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings. Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings, Lecture Notes in Computer Science, vol. 6841 (2011), Springer), 525-542 · Zbl 1290.94113
[30] Alperin-Sheriff, J.; Peikert, C., Circular and KDM security for identity-based encryption, (Fischlin, M.; Buchmann, J. A.; Manulis, M., Public Key Cryptography - PKC 2012 - 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, May 21-23, 2012. Proceedings. Public Key Cryptography - PKC 2012 - 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, May 21-23, 2012. Proceedings, Lecture Notes in Computer Science, vol. 7293 (2012), Springer), 334-352 · Zbl 1294.94030
[31] Yu, Y.; Gu, D.; Li, X.; Weng, J., (Almost) optimal constructions of UOWHFs from 1-to-1, regular one-way functions and beyond, (Gennaro, R.; Robshaw, M., Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II. Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II, Lecture Notes in Computer Science, vol. 9216 (2015), Springer), 209-229 · Zbl 1351.94074
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.