Fault attacks on hyperelliptic curve discrete logarithm problem over binary field

In this paper, we present invalid-curve attacks that apply to the hyperelliptic curve scalar multi- plication （HECSM） algorithm proposed by Avanzi et al. on the genus 2 hyperelliptic curve over binary field. We observe some new properties of the HECSM. Our attacks are based on these new properties and the obser- vation that the parameters f0 and fl of the hyperelliptic curve equation are not utilized for the HECSM. We show that with different ＂values＂ for curve parameters f0, fl, there exsit cryptographically weak groups in the Koblitz hyperelliptic curve. Also, we compute the theoretical probability of getting a weak Jacobian group of hyperelliptic curve whose cardinality is an smooth integer.     

Complete subdivision algorithms, II: Isotopic meshing of singular algebraic curves

Given a real valued function f(X,Y), a box region B₀⊆R² and ε>0, we want to compute an ε-isotopic polygonal approximation to the restriction of the curve S=f⁻¹(0)={p∈R²:f(p)=0} to B₀. We focus on subdivision algorithms because of their adaptive complexity and ease of implementation. Plantinga & Vegter gave a numerical subdivision algorithm that is exact when the curve S is bounded and non-singular. They used a computational model that relied only on function evaluation and interval arithmetic. We generalize their algorithm to any bounded (but possibly non-simply connected) region that does not contain singularities of S. With this generalization as a subroutine, we provide a method to detect isolated algebraic singularities and their branching degree. This appears to be the first complete purely numerical method to compute isotopic approximations of algebraic curves with isolated singularities.     

DeMorgan systems with an infinitely many negations in the strict monotone operator case

We give a new representation theorem of negation based on the generator function of the strict operator. We study a certain class of strict monotone operators which build the DeMorgan class with infinitely many negations. We show that the necessary and sufficient condition for this operator class is f_c(x)f_d(x) = 1, where f_c(x) and f_d(x) are the generator functions of the strict t-norm and strict t-conorm.     

Average-case analysis of the Modified Harmonic algorithm

In this paper we analyze the average-case performance of the Modified Harmonic algorithm for on-line bin packing. We first analyze the average-case performance for arbitrary distribution of item sizes over (0,1]. This analysis is based on the following result. Letf ₁ andf ₂ be two linear combinations of random variables {N _i } _i=1 ^k where theN _i 's have a joint multinomial distribution for eachn=σ _i=1 ^k ,N _i . LetE(f ₁) ≠ O andE(f ₂)≠ 0. Then lim_{n →}∞E(max(_{f 1},f ₂ ))/n = lim _n →∞ max(E(f ₁),E(f ₂))/n. We then consider the special case when the item sizes are uniformly distributed over (0,1]. For specific values of the parameters, the Modified Harmonic algorithm turns out to be better than the other two linear-time on-line algorithms—Next Fit and Harmonic—in both the worst case as well as the average case. We also obtain optimal values for the parameters of the algorithm from the average-case standpoint. For these values of the parameters, the average-case performance ratio is less than 1.19. This compares well with the performance ratios 1.333. and 1.2865. of the Next Fit algorithm and the Harmonic algorithm, respectively.     

Yager’s new class of implications Jf and some classical tautologies

Recently, Yager [R. Yager, On some new classes of implication operators and their role in approximate reasoning, Information Sciences 167 (2004) 193-216] has introduced a new class of fuzzy implications, denoted J_f, called the f-generated implications and has discussed some of their desirable properties, such as neutrality, exchange principle, etc. In this work, we discuss the class of J_f implications with respect to three classical logic tautologies, viz., distributivity, law of importation and contrapositive symmetry. Necessary and sufficient conditions under which J_f implications are distributive over t-norms and t-conorms and satisfy the law of importation with respect to a t-norm have been presented. Since the natural negations of J_f implications, given by N_Jf(x)=J_f(x,0), in general, are not strong, we give sufficient conditions under which they become strong and possess contrapositive symmetry with respect to their natural negations. When the natural negations of J_f are not strong, we discuss the contrapositivisation of J_f. Along the lines of J_f implications, a new class of implications called h-generated implications, J_h, has been proposed and the interplay between these two types of implications has been discussed. Notably, it is shown that while the natural negations of J_f are non-filling those of J_h are non-vanishing, properties which determine the compatibility of a contrapositivisation technique.     

Edge-bipancyclicity of the k-ary n-cubes with faulty nodes and edges

The k-ary n-cube has been one of the most popular interconnection networks for massively parallel systems. In this paper, we investigate the edge-bipancyclicity of k-ary n-cubes with faulty nodes and edges. It is proved that every healthy edge of the faulty k-ary n-cube with f_v faulty nodes and f_e faulty edges lies in a fault-free cycle of every even length from 4 to kⁿ − 2f_v (resp. kⁿ − f_v) if k ? 4 is even (resp. k ? 3 is odd) and f_v + f_e ? 2n − 3. The results are optimal with respect to the number of node and edge faults tolerated.     

Minkowski sums of point sets defined by inequalities

The existing approaches support Minkowski sums for the boundary, set-theoretic, and ray representations of solids. In this paper, we consider the Minkowski sum operation in the context of geometric modeling using real functions. The problem is to find a real function f₃(X) for the Minkowski sum of two objects defined by the inequalities f₁(X) ≥ 0 and f₂(X) ≥ 0. We represent the Minkowski sum as a composition of other operations: the Cartesian product, resulting in a higher-dimensional object, and a mapping to the original space. The Cartesian product is realized as an intersection in the higher-dimensional space, using an R-function. The mapping projects the resulting object along n coordinate axes, where n is the dimension of the original space. We discuss the properties of the resulting function and the problems of analytic and numeric implementation, especially for the projection operation. Finally, we apply Minkowski sums to implement offsetting and metamorphosis between set-theoretic solids with curvilinear boundaries.     

Robustness of star graph network under link failure

The star graph is an attractive underlying topology for distributed systems. Robustness of the star graph under link failure model is addressed. Specifically, the minimum number of faulty links, f(n, k), that make every (n − k)-dimensional substar S_n−k faulty in an n-dimensional star network S_n, is studied. It is shown that f(n,1)=n+2. Furthermore, an upper bound is given for f(n, 2) with complexity of O(n³) which is an improvement over the straightforward upper bound of O(n⁴) derived in this paper.     

On embedding cycles into faulty twisted cubes

The twisted cube TQ_n is an alternative to the popular hypercube network. Recently, some interesting properties of TQ_n were investigated. In this paper, we study the pancycle problem on faulty twisted cubes. Let f_e and f_v be the numbers of faulty edges and faulty vertices in TQ_n, respectively. We show that, with f_e + f_v ? n − 2, a faulty TQ_n still contains a cycle of length l for every 4 ? l ? ∣V(TQ_n)∣ − f_v and odd integer n ? 3.     

Bernstein-type operators which preserve polynomials

In this paper we present the sequence of linear Bernstein-type operators defined for f∈C[0,1] by B_n(f°τ⁻¹)°τ, B_n being the classical Bernstein operators and τ being any function that is continuously differentiable ∞ times on [0,1], such that τ(0)=0, τ(1)=1 and τ^′(x)>0 for x∈[0,1]. We investigate its shape preserving and convergence properties, as well as its asymptotic behavior and saturation. Moreover, these operators and others of King type are compared with each other and with B_n. We present as an interesting byproduct sequences of positive linear operators of polynomial type with nice geometric shape preserving properties, which converge to the identity, which in a certain sense improve B_n in approximating a number of increasing functions, and which, apart from the constant functions, fix suitable polynomials of a prescribed degree. The notion of convexity with respect to τ plays an important role.     

A measure of information gained through biometric systems

We propose a measure of information gained through biometric matching systems. Firstly, we discuss how the information about the identity of a person is derived from biometric samples through a biometric system, and define the “biometric system entropy” or BSE based on mutual information. We present several theoretical properties and interpretations of the BSE, and show how to design a biometric system which maximizes the BSE. Then we prove that the BSE can be approximated asymptotically by the relative entropy D(f_G(x)∥f_I(x)) where f_G(x) and f_I(x) are probability mass functions of matching scores between samples from individuals and among population. We also discuss how to evaluate the BSE of a biometric system and show experimental evaluation of the BSE of face, fingerprint and multimodal biometric systems.     

Improving bounds on link failure tolerance of the star graph

Determination of the minimum number of faulty links, f(n,k), that make every n-k-dimensional sub-star graph S_n-k faulty in an n-dimensional star network S_n, has been the subject of several studies. Bounds on f(n,k) have already been derived, and it is known that f(n,1)=n+2. Here, we improve the bounds on f(n,k). Specifically, it is shown that f(n,k)?(k+1)F(n,k), where F(n,k) is the minimum number of faulty nodes that make every S_n-k faulty in S_n. The complexity of f(n,k) is shown to be O(n²k) which is an improvement over the previously known upper bound of O(n³); this result in a special case leads to f(n,2)=O(n^↑2), settling a conjecture introduced in an earlier paper. A systematic method to derive the labels of the faulty links in case of f(n,1) is also introduced.     

Properties of a hierarchical network based on the star graph

This paper introduces a new class of interconnection networks named star-pyramid. An n-level star-pyramid is formed by piling up star graphs of dimensions 1 to n in a hierarchy, connecting any node in each i-dimensional star, 1 < i ? n, to a node in the (i − 1)-dimensional star whose index is reached by removing the i symbol from the index of the former node in the i-dimensional star graph. Having extracted the properties of the new topology, featuring topological properties, a minimal routing algorithm, a simple but efficient broadcast algorithm, Hamiltonicity and pancyclicity, we then compare the network properties of the proposed topology and the well-known pyramid topology. We show that the star-pyramid has some more attractive properties than its equivalent pyramid. Finally, we propose two variants of star-pyramid, namely the generic star-pyramid and wrapped star-pyramid, as topologies with improved scalability, fault-tolerance, and diameter.     

One-Way Functions Using Algorithmic and Classical Information Theories

We prove several results relating injective one-way functions, time-bounded conditional Kolmogorov complexity, and time-bounded conditional entropy. First we establish a connection between injective, strong and weak one-way functions and the expected value of the polynomial time-bounded Kolmogorov complexity, denoted here by?E(K ^t (x|f(x))). These results are in both directions. More precisely, conditions on?E(K ^t (x|f(x))) that imply that?f is a weak one-way function, and properties of?E(K ^t (x|f(x))) that are implied by the fact that?f is a strong one-way function. In particular, we prove a separation result: based on the concept of time-bounded Kolmogorov complexity, we find an interval in which every function?f is a necessarily weak but not a strong one-way function. Then we propose an individual approach to injective one-way functions based on Kolmogorov complexity, defining Kolmogorov one-way functions and prove some relationships between the new proposal and the classical definition of one-way functions, showing that a Kolmogorov one-way function is also a deterministic one-way function. A relationship between Kolmogorov one-way functions and the conjecture of polynomial time symmetry of information is also proved. Finally, we relate?E(K ^t (x|f(x))) and two forms of time-bounded entropy, the unpredictable entropy?H ^unp, in which ??one-wayness?? of a function can be easily expressed, and the Yao⁺ entropy, a measure based on compression/decompression schema in which only the decompressor is restricted to be time-bounded.     

Connections among nonlinearity,avalanche and correlation immunity

Nonlinear Boolean functions play an important role in the design of block ciphers, stream ciphers and one-way hash functions. Over the years researchers have identified a number of indicators that forecast nonlinear properties of these functions. Studying the relationships among these indicators has been an area that has received extensive research. The focus of this paper is on the interplay of three notable nonlinear indicators, namely nonlinearity, avalanche and correlation immunity. We establish, for the first time, an explicit and simple lower bound on the nonlinearity N_f of a Boolean function f of n variables satisfying the avalanche criterion of degree p, namely, N_f⩾2ⁿ⁻¹−2^{n−1−(1/2)p}. We also identify all the functions whose nonlinearity attains the lower bound. As a further contribution of this paper, we prove that except for very few cases, the sum of the degree of avalanche and the order of correlation immunity of a Boolean function of n variables is at most n−2. The new results obtained in this work further highlight the significance of the fact that while avalanche property is in harmony with nonlinearity, both go against correlation immunity.     

Fast error estimates for indirect measurements: applications to pavement engineering

In many real-life situations, we have the following problem: we want to know the value of some characteristicy that is difficult to measure directly (e.g., lifetime of a pavement, efficiency of an engine, etc.). To estimatey, we must know the relationship betweeny and some directly measurable physical quantitiesx ₁,...,x _n . From this relationship, we extract an algorithmf that allows us, givenx _i , to computey: y=f(x ₁, ...,x _n ). So, we measurex _i , apply an algorithmf, and get the desired estimate. Existing algorithms for error estimate (interval mathematics, Monte-Carlo methods, numerical differentiation, etc.) require computation time that is several times larger than the time necessary to computey=f(x ₁, ...,x _n ). So, if an algorithmf is already time-consuming, error estimates will take too long. In many cases, this algorithmf consists of two parts: first, we usex _i to determine the parametersz _k of a model that describes the measured object, and second, we use these parameters to estimatey. The most time-consuming part is findingz _k ; this is done by solving a system of non-linear equations; usually least squares method is used. We show that for suchf, one can estimate errors repeating this time-consuming part off only once. So, we can compute bothy and an error estimate fory with practically no increase in total computation time. As an example of this methodology, we give pavement lifetime estimates.     

Barycentric formulae for some optimal rational approximants involving blaschke products

We want to approximate the valueLf of some bounded linear functionalL (e.g., an integral or a function evaluation) forf∈H ² by a linear combination Σ _j=0 ^j=0 a _j f _j , wheref _j:=f(z _j) for some pointsz _j in the unit disk and the numbersa _j are to be chosen independent off _j. Using ideas of Sard, Larkin has shown that, for the errorLf?Σ _j=0 ^j=0 a _j f _j to be minimal,a _j must be chosen such that Σ _j=0 ^j=0 a _j f _j =Lf ^⊥ for the rational function \(f^ \bot (z) = \sum\nolimits_{j = 0}^n {\{ \prod\nolimits_{k = 0}^n {(1 - \bar z_k z_j )/\prod\nolimits_{k = 0}^n {(1 - \bar z_k z)} } \} l_j } (z)f_j \) , in whichl _j (z) are the Lagrange polynomials. Evaluatingf ^⊥ as given above requriesO(n ²) operations for everyz. We give here formulae, patterned after the barycentric formulae for polynomial, trigonometric and rational interpolation, which permit the evaluation off ^⊥ inO(n) operations for everyz, once some weights (that are independent ofz) have been computed. Moreover, we show that certain rational approximants introduced by F. Stenger (Math. Comp., 1986) can be interpreted as special cases of Larkin's interpolants, and are therefore optimal in the sense of Sard for the corresponding points.     

The F5 criterion revised

The purpose of this work is to generalize part of the theory behind Faugère’s “F5” algorithm. This is one of the fastest known algorithms to compute a Gröbner basis of a polynomial ideal I generated by polynomials f₁,…,f_m. A major reason for this is what Faugère called the algorithm’s “new” criterion, and we call “the F5 criterion”; it provides a sufficient condition for a set of polynomials G to be a Gröbner basis. However, the F5 algorithm is difficult to grasp, and there are unresolved questions regarding its termination.This paper introduces some new concepts that place the criterion in a more general setting: S-Gröbner bases and primitive S-irreducible polynomials. We use these to propose a new, simple algorithm based on a revised F5 criterion. The new concepts also enable us to remove various restrictions, such as proving termination without the requirement that f₁,…,f_m be a regular sequence.     

Treatment of the initial value in Time-Memory-Data Tradeoff attacks on stream ciphers

Time-Memory Tradeoff (TMTO) attacks on stream ciphers are a serious security threat and the resistance to this class of attacks is an important criterion in the design of a modern stream cipher. TMTO attacks are especially effective against stream ciphers where a variant of the TMTO attack can make use of multiple data to reduce the off-line and the on-line time complexities of the attack (given a fixed amount of memory).In this paper we present a new approach to TMTO attacks against stream ciphers using a publicly known initial value (IV): We suggest not to treat the IV as part of the secret key material (as done in current attacks), but rather to choose in advance some IVs and apply a TMTO attack to streams produced using these IVs. We show that while the obtained tradeoff curve is identical to the curve obtained by the current approach, the new technique allows to mount the TMTO attack in a larger variety of settings. For example, if both the secret key and the IV are of length n, it is possible to mount an attack with data, time, and memory complexities of ²4n/5, while in the current approach, either the time complexity or the memory complexity is not less than n².