//img.uscri.be/pth/f853b4cb41e3f9c5f5346a433f4c604af5cf03ba
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Introduction Related Work Attacking IP1S Attacking the full IP Conclusion

De
84 pages
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


Voir plus Voir moins

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.