# Introduction Related Work Attacking IP1S Attacking the full IP Conclusion

-

Documents
84 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

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 Ajouté le 01 juin 2010 Nombre de lectures 8 Langue English
Signaler un abus

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
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 iﬀq
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 iﬀ 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 iﬀ 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 iﬀ 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, ﬁnd 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.