Paper 2012/217
Efficient Dissection of Bicomposite Problems with Cryptanalytic Applications
Itai Dinur, Orr Dunkelman, Nathan Keller, and Adi Shamir
Abstract
In this paper we show that a large class of diverse problems have a
bicomposite structure which makes it possible to solve them with a new
type of algorithm called {\it dissection}, which has much better
time/memory tradeoffs than previously known algorithms. A typical example is the
problem of finding the key of multiple encryption schemes with
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- A major revision of an IACR publication in CRYPTO 2012
- Keywords
- Bicomposite problemsdissection algorithmtime-memory tradeoffcryptanalysismultiple encryptionknapsack problems
- Contact author(s)
- dinuri @ cs bgu ac il
- History
- 2019-06-20: revised
- 2012-04-22: received
- See all versions
- Short URL
- https://ia.cr/2012/217
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2012/217, author = {Itai Dinur and Orr Dunkelman and Nathan Keller and Adi Shamir}, title = {Efficient Dissection of Bicomposite Problems with Cryptanalytic Applications}, howpublished = {Cryptology {ePrint} Archive, Paper 2012/217}, year = {2012}, url = {https://eprint.iacr.org/2012/217} }