A compact hash function for paths in PERT networks

This paper presents a method of identifying all directed paths from the source to the sink (called ‘paths’ in this paper) in a directed acyclic network with one source and one sink. Let L be the set of all the paths in this network and N = |L|. A hash function H:L → {0, 1, …, N ? 1} is constructed having the following properties: it is one-to-one and onto, the algorithms to compute H and its inverse are linea in the number of arcs in the network, it has the smallest possible range and produces no collisions. All these properties make it a very useful hash function in writing computer programs which involve storing information about all paths in the network. The techniques described in this paper can be used to construct hash functions for walks in cyclic graphs. An application to simulation of stochastic networks is described and an illustrative example is included.     

On generalized separating hash families

Separating hash families are useful combinatorial structures which are studied in a general form in this paper. Necessary and sufficient conditions for the existence of certain types of generalized hash functions are considered.     

Construction of universal one-way hash functions: Tree hashing revisited

We present a binary tree based parallel algorithm for extending the domain of a universal one-way hash function (UOWHF). For t?2, our algorithm extends the domain from the set of all n-bit strings to the set of all ((2^t-1)(n-m)+m)-bit strings, where m is the length of the message digest. The associated increase in key length is 2m bits for t=2; m(t+1) bits for 3?t?6 and m×(t+⌊log₂(t-1)⌋) bits for t?7.     

A bound on the size of separating hash families

The paper provides an upper bound on the size of a (generalized) separating hash family, a notion introduced by Stinson, Wei and Chen. The upper bound generalizes and unifies several previously known bounds which apply in special cases, namely bounds on perfect hash families, frameproof codes, secure frameproof codes and separating hash families of small type.     

A sequence approach to linear perfect hash families

A linear (q ^d , q, t)-perfect hash family of size s in a vector space V of order q ^d over a field F of order q consists of a set of linear functionals from V to F with the following property: for all t subsets there exists such that is injective when restricted to F. A linear (q ^d , q, t)-perfect hash family of minimal size d(t − 1) is said to be optimal. In this paper, we extend the theory for linear perfect hash families based on sequences developed by Blackburn and Wild. We develop techniques which we use to construct new optimal linear (q ², q, 5)-perfect hash families and (q ⁴, q, 3)-perfect hash families. The sequence approach also explains a relationship between linear (q ³, q, 3)-perfect hash families and linear (q ², q, 4)-perfect hash families.      

Bounds for separating hash families

This paper aims to present new upper bounds on the size of separating hash families. These bounds improve previously known bounds for separating hash families.     

Explicit constructions for perfect hash families

Let k, v, t be integers such that k ≥ v ≥ t ≥ 2. A perfect hash family (N; k, v, t) can be defined as an N × k array with entries from a set of v symbols such that every N × t subarray contains at least one row having distinct symbols. Perfect hash families have been studied by over 20 years and they find a wide range of applications in computer sciences and in cryptography. In this paper we focus on explicit constructions for perfect hash families using combinatorial methods. We present many recursive constructions which result in a large number of improved parameters for perfect hash families. The paper also includes extensive tables for parameters with t = 3, 4, 5, 6 of newly constructed perfect hash families.      

Dispersing hash functions

We define a family of functions F from a domain U to a range R to be dispersing if for every set S ? U of a certain size and random h ∈ F, the expected value of ∣S∣ – ∣h[S]∣ is not much larger than the expectation if h had been chosen at random from the set of all functions from U to R. We give near‐optimal upper and lower bounds on the size of dispersing families and present several applications where using such a family can reduce the use of random bits compared to previous randomized algorithms. A close relationship between dispersing families and extractors is exhibited. This relationship provides good explicit constructions of dispersing hash functions for some parameters, but in general the explicit construction is left open. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Optimal linear perfect hash families with small parameters

A linear (q^d, q, t)‐perfect hash family of size s consists of a vector space V of order q^d over a field F of order q and a sequence ?₁,…,?_s of linear functions from V to F with the following property: for all t subsets X ? V, there exists i ∈ {1,·,s} such that ?_i is injective when restricted to F. A linear (q^d, q, t)‐perfect hash family of minimal size d( – 1) is said to be optimal. In this paper, we prove that optimal linear (q², q, 4)‐perfect hash families exist only for q = 11 and for all prime powers q > 13 and we give constructions for these values of q. © 2004 Wiley Periodicals, Inc. J Comb Designs 12: 311–324, 2004     

On the complexity of the herding attack and some related attacks on hash functions

In this article, we analyze the complexity of the construction of the 2 ^k -diamond structure proposed by Kelsey and Kohno (LNCS, Vol 4004, pp 183–200, 2006). We point out a flaw in their analysis and show that their construction may not produce the desired diamond structure. We then give a more rigorous and detailed complexity analysis of the construction of a diamond structure. For this, we appeal to random graph theory (in particular, to the theory of random intersection graphs), which allows us to determine sharp necessary and sufficient conditions for the message complexity (i.e., the number of hash computations required to build the required structure). We also analyze the computational complexity for constructing a diamond structure, which has not been previously studied in the literature. Finally, we study the impact of our analysis on herding and other attacks that use the diamond structure as a subroutine. Precisely, our results shows the following:

1. The message complexity for the construction of a diamond structure is ${\sqrt{k}}$ times more than the amount previously stated in literature.

1. The time complexity is n times the message complexity, where n is the size of hash value.

Due to the above two results, the herding attack (Kelsey and Kohno, LNCS, Vol 4004, pp 183–200, 2006) and the second preimage attack (Andreeva et?al., LNCS, Vol 4965, pp 270–288, 2008) on iterated hash functions have increased complexity. We also show that the message complexity of herding and second preimage attacks on “hash twice” is n times the complexity claimed by Andreeva et?al. (LNCS, Vol 5867, pp 393–414, 2009), by giving a more detailed analysis of the attack.     

Increasing the security of hash functions

In this paper, we introduce a solution for ensuring data integrity using cryptographic one-way hash functions. The cryptographic security of such hash functions was estimated by us in detail for different kinds of attacks. We propose several new schemes for increasing the security of one-way hash functions without reformation of its internal algorithms. Also we outline schemes with the best speed and security level. We show that the Schneier method of suffix superposition has a serious drawback. In this article, we also suggest the method of constructing collision resistant one-way hash functions from standard well-known hash functions. Therefore, the proposed schemas can be used to upgrade the majority of cryptographic one-way functions, such as MD4, MD5, RIPEMD, SHA, GOST 34 11-94.     

Riemann boundary value problems for some K-regular functions in clifford analysis

In this paper, we study the R_m (m > 0) Riemann boundary value problems for regular functions, harmonic functions and bi-harmonic functions with values in a universal clifford algebra C(V_n,n). By using Plemelj formula, we get the solutions of R_m (m > 0) Riemann boundary value problems for regular functions. Then transforming the Riemann boundary value problems for harmonic functions and bi-harmonic functions into the Riemann boundary value problems for regular functions, we obtain the solutions of R_m (m > 0) Riemann boundary value problems for harmonic functions and bi-harmonic functions.     

A combinatorial characterization of certain universal classes of hash functions

A new lower bound on the size of ?-almost strongly universal₂ classes of hash functions has recently been obtained by Stinson [8]. In this article we present a characterization of ? ? ASU₂ classes of hash functions meeting the Stinson bound in terms of combinatorial designs. © 1994 John Wiley & Sons, Inc.     

Domain extender for collision resistant hash functions: Improving upon Merkle-Damgård iteration

We study the problem of securely extending the domain of a collision resistant compression function. A new construction based on directed acyclic graphs is described. This generalizes the usual iterated hashing constructions. Our main contribution is to introduce a new technique for hashing arbitrary length strings. Combined with DAG-based hashing, this technique yields a new hashing algorithm. The amount of padding and the number of invocations of the compression function required by the new algorithm is smaller than the general Merkle-Damgård algorithm.     

Monotonicity of some functions involving the gamma and psi functions

Let , where is Euler's gamma function. We determine conditions for the numbers so that the function is strongly completely monotonic on . Through this result we obtain some inequalities involving the ratio of gamma functions and provide some applications in the context of trigonometric sum estimation. We also give several other examples of strongly completely monotonic functions defined in terms of and functions. Some limiting and particular cases are also considered.

     

Remarks on some completely monotonic functions

Applying the Euler-Maclaurin summation formula, we obtain upper and lower polynomial bounds for the function , x>0, with coefficients the Bernoulli numbers Bk. This enables us to give simpler proofs of some results of H. Alzer and F. Qi et al., concerning complete monotonicity of certain functions involving the gamma function Γ(x), the psi function ψ(x) and the polygamma functions ψ(n)(x), n=1,2,… .     

A backtracking method for constructing perfect hash functions from a set of mapping functions

This paper presents a backtracking method for constructing perfect hash functions from a given set of mapping functions. A hash indicator table is employed in the composition. By the nature of backtracking, the method can always find a perfect hash function when such a function does exist according to the composing scheme. Simulation results show that the probability of getting a perfect hash function by the backtracking method is much higher than by the single-pass and multipass methods previously proposed.     

Explicit constructions of separating hash families from algebraic curves over finite fields

Let X be a set of order n and Y be a set of order m. An (n,m,{w ₁, w ₂})-separating hash family is a set of N functions from X to Y such that for any with , |X ₁| = w ₁ and |X ₂| = w ₂, there exists an element such that . In this paper, we provide explicit constructions of separating hash families using algebraic curves over finite fields. In particular, applying the Garcia–Stichtenoth curves, we obtain an infinite class of explicitly constructed (n,m,{w ₁,w ₂})–separating hash families with for fixed m, w ₁, and w ₂. Similar results for strong separating hash families are also obtained. As consequences of our main results, we present explicit constructions of infinite classes of frameproof codes, secure frameproof codes and identifiable parent property codes with length where n is the size of the codes. In fact, all the above explicit constructions of hash families and codes provide the best asymptotic behavior achieving the bound , which substantially improve the results in [ 8, 15, 17] give an answer to the fifth open problem presented in [11].     

一些特殊函数的完全单调性

欧拉Gamma函数是一种非常重要的函数,在数学的许多分支以及物理、工程等学科中都有着十分重要的作用.而完全单调性以及对数完全单调性是Gamma函数的重要性质.主要证明了一些包含Gamma函数和Psi函数在内的特殊函数的完全单调性和对数完全单调性,并由此推出了一些重要的不等式.     

Alternative proofs for inequalities of some trigonometric functions

By using an identity relating to Bernoulli's numbers and power series expansions of cotangent function and logarithms of functions involving sine function, cosine function and tangent function, four inequalities involving cotangent function, sine function, secant function and tangent function are established.