Introduction Related Work Attacking IP1S Attacking the full IP Conclusion

Charles Bouillaguet1

Description

Introduction Related Work Attacking IP1S Attacking the full IP Conclusion “Isomorphisms of Polynomials” Charles Bouillaguet1 Jean-Charles Faugere2 Pierre-Alain Fouque1 Ludovic Perret2 1ENS, CNRS, INRIA Cascade 2UMPC (6), CNRS, INRIA Salsa Séminaire Crypto Versailles Jeudi 10 juin 2010

• ajk ·


• fqn ?


• ≤j≤n j≤k≤n


• equivalent iff


• full ip


• séminaire crypto


• introduction related


• work attacking


• there exist

Sujets

• Existential quantification

Informations

• Publié par: pefav
• Publié le: 01 juin 2010
• Nombre de lectures: 8
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Introduction Related Work Attacking IP1S Attacking the full IP Conclusion
“Isomorphisms of Polynomials”
1 2Charles Bouillaguet Jean-Charles Faugere
1 2Pierre-Alain Fouque Ludovic Perret
1ENS, CNRS, INRIA Cascade
2UMPC (6), CNRS, INRIA Salsa
Séminaire Crypto
Versailles
Jeudi 10 juin 2010there exist
S and T in GL (F ) such that:n q
Introduction Related Work Attacking IP1S Attacking the full IP Conclusion
A Generalization of Matrix Equivalence
Two nn matrices a and b over F are equivalent iffq
abIntroduction Related Work Attacking IP1S Attacking the full IP Conclusion
A Generalization of Matrix Equivalence
Two nn matrices a and b over F are equivalent iff there existq
S and T in GL (F ) such that:n q
ab
= T SIntroduction Related Work Attacking IP1S Attacking the full IP Conclusion
A Generalization of Matrix Equivalence
Two nn matrices a and b over F are equivalent iff there existq
S and T in GL (F ) such that:n q
ab
f1
. = . T S.
fn
nf :F !F is a linear form:i q q
X
(x ;:::x )7! a x1 n j j
1jn
a and b vectors of n linear forms in n variables.Introduction Related Work Attacking IP1S Attacking the full IP Conclusion
A Generalization of Matrix Equivalence
Two nn matrices collections of n quadratic forms a and b over
F are equivalent iff there exist S and T in GL (F ) such that:q n q
ab
f1
. = . T S.
fn
nf :F !F is a linear quadratic form:i q q
X
(x ;:::x )7! a x x1 n jjk k
1jn
jkn
a and b vectors of n linear quadratic forms in n variables.Introduction Related Work Attacking IP1S Attacking the full IP Conclusion
(n;u;q;d) “Isomorphism of Polynomials Problem”
ab
= T S
Instances
ua;b2F [x ;:::;x ] with dega = d and degb = d;1 i u.q 1 n i i
Decision Problem
Do there exist S;T2GL (F ) such that b = TaS ?n q
Search Problem
Given a and b, along with the promise that S and T exist, find S
and T.Compute b.
Publish a and b. Keep S and T secret.
Idea b looks random and thus cannot be inverted.
Encrypt Evaluate b on x
Decrypt Invert T, then a, then S.
Introduction Related Work Attacking IP1S Attacking the full IP Conclusion
Cryptographic Relevance of the Search Problem
nGiven x = (x ;:::;x ), it is easy to compute c = b(x)2 (F ) .1 n q
Finding preimages for b = instance of an NP-complete problem.
In practice : very hard for random b (exhaustive search).
a
T S
KeySetup Choose easily invertible a, and random S and T.Publish a and b. Keep S and T secret.
Idea b looks random and thus cannot be inverted.
Encrypt Evaluate b on x
Decrypt Invert T, then a, then S.
Introduction Related Work Attacking IP1S Attacking the full IP Conclusion
Cryptographic Relevance of the Search Problem
nGiven x = (x ;:::;x ), it is easy to compute c = b(x)2 (F ) .1 n q
Finding preimages for b = instance of an NP-complete problem.
In practice : very hard for random b (exhaustive search).
ab
= T S
KeySetup Choose easily invertible a, and random S and T. Compute b.Idea b looks random and thus cannot be inverted.
Encrypt Evaluate b on x
Decrypt Invert T, then a, then S.
Introduction Related Work Attacking IP1S Attacking the full IP Conclusion
Cryptographic Relevance of the Search Problem
nGiven x = (x ;:::;x ), it is easy to compute c = b(x)2 (F ) .1 n q
Finding preimages for b = instance of an NP-complete problem.
In practice : very hard for random b (exhaustive search).
ab
KeySetup Choose easily invertible a, and random S and T. Compute b.
Publish a and b. Keep S and T secret.Introduction Related Work Attacking IP1S Attacking the full IP Conclusion
Cryptographic Relevance of the Search Problem
nGiven x = (x ;:::;x ), it is easy to compute c = b(x)2 (F ) .1 n q
Finding preimages for b = instance of an NP-complete problem.
In practice : very hard for random b (exhaustive search).
ab
KeySetup Choose easily invertible a, and random S and T. Compute b.
Publish a and b. Keep S and T secret.
Idea b looks random and thus cannot be inverted.
Encrypt Evaluate b on x
Decrypt Invert T, then a, then S.