A well known birthday paradox is one the most important problems in cryptographic
applications. Incremental hash functions or digital signatures in public key cryptography
and low-weight parity check equations of LFSRs in stream ciphers are examples
of such applications which benet from birthday problem theories to run their attacks.
Wagner introduced and formulated the k-dimensional birthday problem and proposed
an algorithm to solve the problem in O(k.m^
1/log k ). The generalized birthday solutions
used in some applications to break Knapsack based systems or collision nding in hash
functions. The optimized birthday algorithms can solve Knapsack problems of dimension
n which is believed to be NP-hard. Its equivalent problem is Subset Sum Problem
nds the solution over Z/mZ. The main property for the classication of the problem
is density. When density is small enough the problem reduces to shortest lattice vector
problem and has a solution in polynomial time. Assigning a variable to each element
of the lists, decoding them into a matrix and considering each row of the matrix as
an equation lead us to have a multivariate polynomial system of equations and all
solution of this type can be a solution for the k- list problem such as F4, F5, another
strategy called eXtended Linearization (XL) and sl. We discuss the new approaches
and methods proposed to reduce the complexity of the algorithms. For particular cases
in over-determined systems, more equations than variables, regarding to have a single
solutions Wolf and Thomea work to make a gradual decrease in the complexity of F5.
Moreover, his group try to solve the problem by monomials of special degrees and
linear equations for small lists. We observe and compare all suggested methods in this
| Identifer | oai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/12615627/index.pdf |
| Date | 01 February 2013 |
| Creators | Namaziesfanjani, Mina |
| Contributors | Ozbudak, Ferruh |
| Publisher | METU |
| Source Sets | Middle East Technical Univ. |
| Language | English |
| Detected Language | English |
| Type | M.S. Thesis |
| Format | text/pdf |
| Rights | To liberate the content for METU campus |
Page generated in 0.002 seconds