1,720,983 research outputs found
Local limit theorem for large deviations and statistical box-tests
Full text linkLet particles be independently allocated into boxes, where the -th box appears with the probability . Let be the number of boxes with exactly particles and . Asymptotical behavior of such random variables as tends to infinity was studied by many authors. It was previously known that if are all upper bounded and is upper and lower bounded by positive constants, then tends in distribution to a multivariate normal low. A stronger statement, namely
a large deviation local limit theorem for under the same condition, is here proved. Also all cumulants of are proved to be .
Then we study the hypothesis testing that the box distribution is uniform, denoted , with a recently introduced box-test. Its statistic is a quadratic form in variables . For a wide area of non-uniform , an asymptotical relation for the power of the quadratic and linear box-tests, the statistics of the latter are linear functions of , is proved. In particular,
the quadratic test asymptotically is at least as powerful as any of the linear box-tests, including the well-known empty-box test if is in
Algorithm for SIS and MultiSIS problems
Full text linkSIS problem has numerous applications in cryptography. The known algorithms for solving that problem are exponential in complexity. A new algorithm is suggested in this note, its complexity is sub-exponential for a range of parameters
On solving sparse algebraic equations over finite fields II
Full text linkA system of algebraic equations over a finite field is called sparse
if each equation depends on a small number of variables. Finding
efficiently solutions to the system is an underlying hard problem in
the cryptanalysis of modern ciphers. In this paper deterministic
Agreeing-Gluing algorithm introduced earlier by Raddum and Semaev for
solving such equations is studied. Its expected
running time on uniformly random instances of the problem is rigorously estimated. This estimate is at present the best theoretical
bound on the complexity of solving average instances of the above
problem. In particular, it significantly overcomes our previous results. In characteristic 2 we observe an exciting difference
with the worst case complexity provided by SAT solving algorithms
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Experimental Study of DIGIPASS GO3 and the Security of Authentication
Full text linkAbstract. Based on the analysis of 6-digit one-time passwords(OTP) generated by DIGI-PASS GO3 we were able to reconstruct the synchronisation system of the token, the OTP generating algorithm and the verification protocol in details essential for an attack. The OTPs are more predictable than expected. A forgery attack is described. We argue the attack suc-cess probability is 8−5. That is much higher than 10−6 which may be expected if all the digits are independent and uniformly distributed. Under natural assumptions even in a relatively small bank or company with 104 customers the number of compromised accounts during a year may be more than 100.
Improved Agreeing-Gluing Algorithm
Full text linkIn this paper we study the asymptotical complexity of solving a system of sparse algebraic equations over finite fields. An equation is called sparse if it depends
on a bounded number of variables. Finding
efficiently solutions to the system of such equations is an underlying hard problem in
the cryptanalysis of modern ciphers. New deterministic
Improved Agreeing-Gluing Algorithm is introduced.
The expected
running time of the Algorithm on uniformly random instances of the problem is rigorously estimated. The estimate is at present the best theoretical
bound on the complexity of solving average instances of the
problem. In particular, this is a significant improvement over those in our earlier papers [20,21].
In sparse Boolean equations a gap between the present worst case and the average time complexity of the problem has significantly increased. Also we formulate Average Time Complexity Conjecture. If proved that will have far-reaching consequences in the field of cryptanalysis and in computing in general
Summation polynomials and the discrete logarithm problem on elliptic curves
Full text linkThe aim of the paper is the construction of the index calculus
algorithm for the discrete logarithm problem on elliptic curves.
The
construction presented here is based on the problem of finding
bounded solutions to some explicit modular multivariate
polynomial equations. These equations arise from the elliptic
curve summation polynomials introduced here and may be computed
easily. Roughly speaking, we show that given the algorithm for
solving such equations, which works in polynomial or low
exponential time in the size of the input, one finds discrete
logarithms faster than by means of Pollard\u27s methods
New hash function designs
Full text linkWe suggest new hash function design principles. The basic idea is
that the hash value may be a combination of XOR\u27s and modular additions of values independently produced from different parts of the message.
We instantiate this framework with a function for computing the above values based on modular multiplication
On low degree polynomials in 2-round AES
Full text linkRecent observations on polynomial structures of AES-like round functions are analysed in this note. We present computational evidence that input/output bits of AES-like 2-round transform up to -bit, constructed with -bit AES S-boxes, do not satisfy any relations of degree . So it is very unlikely that actual AES 2-round transform admits any relations of degree
- …
