We characterize growth processes (probabilistic amplification) by their initial conditions to derive conditions under which results such as Valiant's [J Algorithms 5 (1984), 363-366] hold. We completely characteri...
详细信息
We characterize growth processes (probabilistic amplification) by their initial conditions to derive conditions under which results such as Valiant's [J Algorithms 5 (1984), 363-366] hold. We completely characterize growth processes that use linear connectives and generalize Savick 's [Discrete Math 147 (1990), 95-103] analysis to characterize growth processes that use monotone connectives. Additionally, we obtain explicit bounds on the convergence rates of several growth processes, including the growth process studied in Savicky. (c) 2005 Wiley Periodicals, Inc.
The goal of this paper is to investigate linear approximations of randomfunctions and permutations. Our motivation is twofold. First, before the distinguishability of a practical cipher from an ideal one can be analy...
详细信息
The goal of this paper is to investigate linear approximations of randomfunctions and permutations. Our motivation is twofold. First, before the distinguishability of a practical cipher from an ideal one can be analysed, the cryptanalyst must have an accurate understanding of the statistical behaviour of the ideal cipher. Secondly, this issue has been neglected both in old and in more recent studies, particularly when multiple linear approximations are being used simultaneously. Traditional models have been based on the average behaviour and simplified using other assumptions such as independence of the linear approximations. Multidimensional cryptanalysis was introduced to avoid making artificial assumptions about statistical independence of linear approximations. On the other hand, it has the drawback of including many trivial approximations that do not contribute to the attack but just cause a waste of time and memory. We show for the first time in this paper that the trivial approximations reduce the degree of freedom of the related chi(2) distribution. Previously, the affine linear cryptanalysis was proposed to allow removing trivial approximations and, at the same time, admitting a solid statistical model. In this paper, we identify another type of multidimensional linear approximation, called Davies-Meyer approximation, which has similar advantages, and present full statistical models for both the affine and the Davies-Meyer type of multidimensional linear approximations. The new models given in this paper are realistic, accurate and easy to use. They are backed up by standard statistical tools such as Pearson's chi(2) test and finite population correction and demonstrated to work accurately using practical examples.
We present here a new and universal approach for the study of random and/or trees, unifying in one framework many different models, including some novel ones not yet understood in the literature. An and/or tree is a B...
详细信息
We present here a new and universal approach for the study of random and/or trees, unifying in one framework many different models, including some novel ones not yet understood in the literature. An and/or tree is a boolean expression represented in (one of) its tree shapes. Fix an integer k, take a sequence of random (rooted) trees of increasing size, say (tn)n1, and label each of these random trees uniformly at random in order to get a randomboolean expression on k variables. We prove that, under rather weak local conditions on the sequence of random trees (tn)n1, the distribution induced on booleanfunctions by this procedure converges as n tends to infinity. In particular, we characterize two different behaviors of this limit distribution depending on the shape of the local limit of (tn)n1 : a degenerate case when the local limit has no leaves;and a non-degenerate case, which we are able to describe in more details under stronger conditions. In this latter case, we provide a relationship between the probability of a given boolean function and its complexity. The examples covered by this unified framework include trees that interpolate between models with logarithmic typical distances (such as random binary search trees) and other ones with square root typical distances (such as conditioned Galton-Watson trees).
There has been some ambiguity about the growth of attractors in Kauffman networks with network size. Some recent work has linked this to the role and growth of circuits or loops of boolean variables. Using numerical m...
详细信息
ISBN:
(纸本)9783540769309
There has been some ambiguity about the growth of attractors in Kauffman networks with network size. Some recent work has linked this to the role and growth of circuits or loops of boolean variables. Using numerical methods we have investigated the growth of structural circuits in Kauffman networks and suggest that the exponential growth in the number of structural circuits places a lower bound on the complexity of the growth of boolean dependency loops and hence of the number of attractors. We use a fast and exact circuit enumeration method that does not rely on sampling trajectories. We also explore the role of structural self-edges, or self-inputs in the NK-model, and how they affect the number of structural circuits and hence of attractors.
暂无评论