2012 | OriginalPaper | Buchkapitel
From Multiple Encryption to Knapsacks – Efficient Dissection of Composite Problems
verfasst von : Orr Dunkelman
Erschienen in: Progress in Cryptology - INDOCRYPT 2012
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this talk, we show some interesting relations between the problem of attacking multiple encryption schemes and attacking knapsack systems. The underlying relation, of problems of a bicomposite nature, allows introducing a series of algorithms for the
dissection
of these problems, thus offering significantly better time/memory tradeoffs than previously known algorithms.
For the case of finding the keys used in a multiple-encryption scheme with
r
independent
n
-bit keys, previous error-free attacks required time
T
and memory
M
satisfying
TM
= 2
rn
. Our new technique yields the first algorithm which never errs and finds all the possible keys with a smaller product of
TM
(e.g., for 7-encryption schemes in time
T
= 2
4
n
and memory
M
= 2
n
). The improvement ratio we obtain increases in an unbounded way as
r
increases, and if we allow algorithms which can sometimes miss solutions, we can get even better tradeoffs by combining our dissection technique with parallel collision search (offering better complexities than the parallel collision search variants).
After discussing multiple encryption, we show that exactly the same algorithm can be used to offer attacks on knapsacks, which work for any knapsack, that offer the best known time-memory tradeoff curve. This algorithm can be used to handle also more general types of knapsacks, involving a combination of modular additions, XORs, and any T-functions.