Introduction Related Work Attacking IP1S Attacking the full IP Conclusion
84
pages
English
Documents
2010
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe et accède à tout notre catalogue !
Découvre YouScribe et accède à tout notre catalogue !
84
pages
English
Documents
2010
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
- ajk ·
- fqn ?
- ≤j≤n j≤k≤n
- equivalent iff
- full ip
- séminaire crypto
- introduction related
- work attacking
- there exist
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.
