Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
A Survey on known algorithms in solving generalization birthday problem (K-List)
Download
index.pdf
Date
2013
Author
Namaziesfanjani, Mina
Metadata
Show full item record
Item Usage Stats
28
views
24
downloads
Cite This
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 bene t 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 classi cation 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
Subject Keywords
Algorithms.
,
Cryptography.
,
Polynomials.
URI
http://etd.lib.metu.edu.tr/upload/12615627/index.pdf
https://hdl.handle.net/11511/22537
Collections
Graduate School of Applied Mathematics, Thesis
Suggestions
OpenMETU
Core
A Randomness test based on postulate r-2 on the number of runs
Şeker, Okan; Doğanaksoy, Ali; Department of Cryptography (2014)
Random values are considered as an indispensable part of cryptography, since they are necessary for almost all cryptographic protocols. Most importantly, key generation is done by random values and key itself should behave like a random value. Randomness is tested by statistical tests and hence, security evaluation of a cryptographic algorithm deeply depends on statistical randomness tests. In this thesis we focus on randomness postulates of Solomon W. Golomb in particular, second postulate which is about r...
A new sure-success generalization of Grover iteration and its application to weight decision problem of Boolean functions
Uyanik, K.; Turgut, Sadi (Springer Science and Business Media LLC, 2013-11-01)
In two recent papers, a sure-success version of the Grover iteration has been applied to solve the weight decision problem of a Boolean function and it is shown that it is quadratically faster than any classical algorithm (Braunstein et al. in J Phys A Math Theor 40:8441, 2007; Choi and Braunstein in Quantum Inf Process 10:177, 2011). In this paper, a new approach is proposed to generalize the Grover's iteration so that it becomes exact and its application to the same problem is studied. The regime where a ...
A QCD Sum Rules Approach to Mixing of Hadrons
Alıyev, Tahmasıb; Özpineci, Altuğ (2010-06-24)
A method for the calculation of the hadronic mixing angles using QCD sum rules is proposed. This method is then applied to predict the mixing angle between the heavy cascade hyperons Xi(Q) and Xi'Q where Q = c or Q = b. It is obtained the theta(b) = 6.4 degrees +/- 1.8 degrees and theta(c) = 5.5 degrees +/- 1.8 degrees.
A Genetic Isometric Shape Correspondence Algorithm with Adaptive Sampling
Sahillioğlu, Yusuf (2018-11-01)
We exploit the permutation creation ability of genetic optimization to find the permutation of one point set that puts it into correspondence with another one. To this end, we provide a genetic algorithm for the 3D shape correspondence problem, which is the main contribution of this article. As another significant contribution, we present an adaptive sampling approach that relocates the matched points based on the currently available correspondence via an alternating optimization. The point sets to be match...
A New Algorithm for Residue Multiplication Modulo 2(521)-1
Ali, Shoukat; Cenk, Murat (2016-12-02)
We present a new algorithm for residue multiplication modulo the Mersenne prime p = 2(521) - 1 based on the Toeplitz matrix-vector product. For this modulus, our algorithm yields better result in terms of the total number of operations than the previously known best algorithm of Granger and Scott presented in Public Key Cryptography (PKC) 2015. We have implemented three versions of our algorithm to provide an extensive comparison - according to the best of our knowledge with respect to the well-known algori...
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
M. Namaziesfanjani, “A Survey on known algorithms in solving generalization birthday problem (K-List),” M.S. - Master of Science, Middle East Technical University, 2013.