Provable Cryptography from Non-commutative Groups [less]
One hallmark of the modern approach to the design of cryptographic protocols has been the focus on explicit computational assumptions. Such protocols come with the guarantee that violating security requires the solving of a computational problem which is believed intractable.
Despite their fundamental role in cryptographic theory, there is little variety in our family of intractability assumptions. Most of the cryptographic constructs which are used in practice today either rely on a small handful of computational assumptions related to factoring and discrete logs (e.g., RSA, Diffie-Hellman), or lack a well-defined assumption altogether (e.g., AES, and any of the SHA functions).
Thus, it is of particular interest to discover viable new sources of intractability which are suitable for cryptography. One seemingly promising source is the theory of non-commutative groups, which is home to many difficult computational problems. However, problems difficult in the worst-case are not sufficient for cryptographic application. Our current research efforts therefore focus on finding problems with a difficult average-case, an area for which much less is understood.
Notable results to date include the generalization of the learning parity with noise (LPN) and learning with errors (LWE) problems to an abstract class of learning problems; an instantiation of this new class of problems based on the theory of finitely generated groups of exponent 3 (Burnside groups of exponent 3); and a symmetric cryptosystem whose security can be provably established based on the conjectured hardness of the Burnside learning problem. These results have been published in [1].
The results in [3] sheds light on the computational hardness of the learning problem at the heart of [1], namely the problem of Learning Burnside-Homomorphism with Noise (B_n-LHN). The key finding of [3] is that the B_n-LHN problem enjoys a strong form of random self-reducibility: solving the problem on a random instance is not any easier than solving the problem on an arbitrary instance. Random self-reducibility properties are a desirable trait of computational problems for several reasons. In terms of cryptographic applications, an immediate benefit is that sampling “hard” instances of a random self-reducible problem boils down to picking one at random, which simplifies greatly the specification of any cryptosystem based on our computational problem. More broadly, random self-reducibility is a distinguishing trait of the computational assumptions that have withstood the test of time, including LPN, LWE, RSA, and the Discrete Logarithm over finite fields or elliptic curves.
[1]
Generalized Learning Problems and Applications to Non-Commutative Cryptography
G. Baumslag, N. Fazio, A. Nicolosi, V. Shpilrain, and W. Skeith
International Conference on Provable Security – ProvSec ’11, LNCS 6980, pp. 324–339, Springer, 2011
[2]
Random Self-Reducibility Properties of Learning Problems over Burnside Groups of Exponent 3
N. Fazio, K. Iga, A. Nicolosi, L. Perret, and W. Skeith
Joint AMS/SAMS International Congress, 2011
[3]
Hardness of Learning Problems over Burnside Groups of Exponent 3
N. Fazio, K. Iga, A. Nicolosi, L. Perret, and W. Skeith
Cryptology e-Print Archive, Report 2011/398, 2011
This research is supported by the National Science Foundation under grant CNS-1117675 (in collaboration with Stevens Institute of Technology, CNS-1117679) and by the CUNY CIRG Program (Round 19).
One hallmark of the modern approach to the design of cryptographic protocols has been the focus on explicit computational assumptions. Such protocols come with the guarantee that violating security requires the solving of a computational problem which is believed intractable.
Despite their fundamental role in cryptographic theory, there is little variety in our family of intractability assumptions. Most of the cryptographic constructs which are used in practice today either rely on a small handful of computational assumptions related to factoring and discrete logs (e.g., RSA, Diffie-Hellman), or lack a well-defined assumption altogether (e.g., AES, and any of the SHA functions).
Thus, it is of particular interest to discover viable new sources of intractability which are suitable for cryptography. One seemingly promising source is the theory of non-commutative groups, which is home to many difficult computational problems. However, problems difficult in the worst-case are not sufficient for cryptographic application. Our current research efforts therefore focus on finding problems with a difficult average-case, an area for which much less is understood.
Notable results to date include the generalization of the learning parity with noise (LPN) and learning with errors (LWE) problems to an abstract class of learning problems; an instantiation of this new class of problems based on the theory of finitely generated groups of exponent 3 (Burnside groups of exponent 3); and a symmetric cryptosystem whose security can be provably established based on the conjectured hardness of the Burnside learning problem. These results have been published in [1].
The results in [3] sheds light on the computational hardness of the learning problem at the heart of [1], namely the problem of Learning Burnside-Homomorphism with Noise (B_n-LHN). The key finding of [3] is that the B_n-LHN problem enjoys a strong form of random self-reducibility: solving the problem on a random instance is not any easier than solving the problem on an arbitrary instance. Random self-reducibility properties are a desirable trait of computational problems for several reasons. In terms of cryptographic applications, an immediate benefit is that sampling “hard” instances of a random self-reducible problem boils down to picking one at random, which simplifies greatly the specification of any cryptosystem based on our computational problem. More broadly, random self-reducibility is a distinguishing trait of the computational assumptions that have withstood the test of time, including LPN, LWE, RSA, and the Discrete Logarithm over finite fields or elliptic curves.
[1]
Generalized Learning Problems and Applications to Non-Commutative Cryptography
G. Baumslag, N. Fazio, A. Nicolosi, V. Shpilrain, and W. Skeith
International Conference on Provable Security – ProvSec ’11, LNCS 6980, pp. 324–339, Springer, 2011
[2]
Random Self-Reducibility Properties of Learning Problems over Burnside Groups of Exponent 3
N. Fazio, K. Iga, A. Nicolosi, L. Perret, and W. Skeith
Joint AMS/SAMS International Congress, 2011
[3]
Hardness of Learning Problems over Burnside Groups of Exponent 3
N. Fazio, K. Iga, A. Nicolosi, L. Perret, and W. Skeith
Cryptology e-Print Archive, Report 2011/398, 2011
This research is supported by the National Science Foundation under grant CNS-1117675 (in collaboration with Stevens Institute of Technology, CNS-1117679) and by the CUNY CIRG Program (Round 19).