We propose an authentication scheme where the verifier makes the decision based on the value of the metric function, which is assigned depending on the type of the vector stored in the database at the enrollment stage. The scheme has a better performance than the maximum likelihood verification algorithm even for binary symmetric channels.

An algorithm for estimating the entropy, which is based on the representation of the entropy function as the sum of two polynomial terms, called the polynomial approximation function and the remainder, is proposed. We construct an accurate and unbiased estimate of the value of the polynomial approximation function and use the known Bayesian approach to estimate the remainder. The combined estimator essentially reduces the bias of the constructed estimate as compared to the known estimators. Simulation results that confirm the claim are presented.

Abstract We consider the verification problem when the verifier receives a pair of binary vectors (a, b) and makes the acceptance or the rejection decision. The acceptance decision has to be made if the vector b is the result of transmission of the vector a over a known memoryless channel. An attacker substitutes a vector b generated by a stationary Bernoulli source. We design the verification algorithm with the metric depending on the weight of the vector a. The attacker knows the weight of the vector a and the verification algorithm, but we can restrict his possibilities in such a way that the best strategy becomes the flipping of a fair coin. The performance of the algorithm is essentially better than the performance of the scheme, which is based on the maximum likelihood decision for the known channel. We also show that the algorithm is a special case of a general verification scheme for an arbitrary memoryless channel. Copyright © 2010 John Wiley & Sons, Ltd.

Verification of the person's identity using the database, which contains outcomes of his biometric measurements, is considered. The verification algorithm is proposed and its performance is evaluated with the assumption that the input data represent the vector of values of a random variable generated according to the Gaussian probability distribution and observed under an additive white Gaussian noise. The evaluation of the false acceptance rate includes an analysis of the possibilities of attackers, called wolves, who generate fixed vectors that have the best chance for the verifier's acceptance decision when the biometrics of the person is unknown.

We present a simple combinatorial construction for the mapping of the biometric vectors to short strings, called the passwords. A verifier has to decide whether a given vector can be considered as a corrupted version of the original biometric vector whose password is known or not. The evaluations of the compression factor, the false rejection/acceptance rates, are derived, and an illustration of a possible implementation of the verification algorithm for the DNA data is presented. © 2010 Vladimir B. Balakirsky and A. J. Han Vinck.

We present a combinatorial algorithm for transformation of long input binary strings to short codewords called the passwords. Having received the password and another long binary string, the decoder has to decide whether it can be considered as a corrupted version of the input string or not. In the presented examples, the length of strings is 10 Kbytes, the code rate has the order of magnitude 10-4, the decision about the closeness of strings has to be made if the Hamming distance is less than 4096, and the decoding error probabilities that can be attained by the algorithm have the order of magnitude 2-17. The algorithm is derived on the basis of random coding arguments and the proposed probabilistic data reduction scheme, which show that an efficient authentication can be organized with the use of passwords having much smaller length than the length of the original data.

Abstract We propose a probabilistic model for constructing passwords on the basis of outcomes of biometrical measurements. An algorithm for the transformation of biometrical data to passwords is given. Performance of the authentication scheme is evaluated by the compression factor, the false acceptance/rejection rates, the probability distribution over the set of passwords, and the probability of a correct guess of the input biometrical data mapped to the known password. An application of the results to the DNA measurements is presented. Copyright © 2009 John Wiley & Sons, Ltd.

We present an algorithm for testing the independence of two non-stationary random processes, which is based on the transformation of realizations of the processes to q-ary vectors whose components are uniformly distributed over the set {0, . . . , q - 1}. An application of the algorithm to the biometric authentication problem brings the false acceptance rate that does not depend on the probability distribution over the templates space and exponentially decreases with the number of independent biometric parameters available to an observer.

We analyze communication schemes over bus systems that are of interest for creating effective data transmission algorithms when the destination can be hardly reached by the sender in one round, and some number of intermediate repeaters should be included. Possible strategies are investigated for Reed-Solomon codes under assumption that a certain maximum number of errors always has to be corrected.

Hashing of databases is considered from the point of view of information and coding theory. The records of a database are represented as binary vectors of the same length stored in the external memory of a computer. The task is formulated as follows: given a pattern and a fixed size of working memory, form the set of addresses of records that can disagree with the pattern in the numberof positions smaller than the given threshold value. We use metric properties of the Hamming space and show that computational efforts needed to search for a pattern in databases can be essentially decreased by using the triangle inequality for the Hamming distances between binary vectors. Furthermore, an introduction of the Lee distance in the space containing the Hamming distances leads to a new metric space where the triangle inequality is effectively used.

We analyze data transmission over parallel binary symmetric channels with dependent noise. If a sender is active, then he transmits a codeword. If a sender is nonactive, then he transmits the all-zero vector. The dependence of noise in the channels gives a possibility of using the multiple access technique to encode and to decode transmitted messages. We show that under certain symmetric assumptions on the distribution of noise, one can asymptotically reach the same maximum transmission rate in the cases when the decoder knows the set of active users and when he does not have this information.

In this article, the computation of the entropy rate H(y) of a binary-valued stochastic process (Y/sub 1/, Y/sub 2/,...) which is a function of a stationary, time-invariant and irreducible Markov chain (X/sub 1/, X/sub 2/,..) is considered. The central idea of this article is to replace the summation over all words of length n by a summation over a complete set of prefixes (or prefixset for brevity). A prefixset W is a finite set of words (not necessarily of equal length) containing a unique prefix for each word of sufficient length. The method of prefixsets is of interest beyond computing the entropy rate. For the problem of estimating the next state of a Markov chain from observed output sequences, we can precompute a prefixset W of these sequences and associate a unique estimate of the state with each of the elements of W. The method also has a strong relation with variable-to-fixed length (Tunstall) codes. It replaces the set of all words of a given length by a prefixset of "more typical" words, effectively balancing the contributions of all words in the bounds.

A coset representation of the bit error probabilities for binary linear block codes and arbitrary symmetric memoryless channels is derived. Such a representation leads to simple upper bounds on the bit error probabilities for code components expressed via 2n code spectra, where n is the code length, and to a "bounded distance decoding" algorithm. The performance of the algorithm is illustrated for the (23,12) Golay code and a particular channel having non-binary output alphabet where it attains a sub-optimum performance.

We construct a one-to-one mapping between binary vectors of length $n$ and preorder codewords of regular, ordered, oriented, rooted, binary trees having $N \approx n + 2$ log $n$ nodes. The mappings in both directions can be organized in such a way that complexities of all transformations are measured by linear functions of $n$. The approach is then completely extended to non-regular binary trees and partially extended to $D$-ary trees with $D > 2$.

We describe a class of codes that can be effectively used when one of $q^n$ vectors of length $n$ has to be delivered to the receiver over a noiseless $q$-ary channel in asynchronous mode assuming that the latter one receives the transmitted vector with the delay $\\tau\\in\\{0,\\dotsc,n-1\\}$, unknown in advance, while all other received symbols are arbitrarily chosen. The codes are specified for any $n$ by a regular algorithm, which is based on properties of ordered, oriented, rooted, binary trees, and have length $N\\approx n + 2$ log$_q n$. We show that these codes can be used in such a way that encoding and decoding complexities are measured by linear functions of $n$.

Regular constructions for specific permutation codes used in a multiple-access OR channel where the inputs originate from a fast frequency hopping/multiple frequency shift keying modulation are presented for 3 situations : (1) each sender is either active or passive; (2) the jammer is allowed to corrupt a certain number of transmitted frequencies; and (3) the sender transmit one of a certain number of messages. We show that these constructions are optimum ones for the situations (1), (2) and that they are close to the optimum for the situation (3).

A construction of uniquely decodable codes for the two-user binary adder channel is presented. The rates of the codes obtained by this construction are greater than the rates guaranteed by the Coebergh van den Braak and van Tilborg construction and these codes can be used with simple encoding and decoding procedures.

Asymptotic lower bounds on the code rate when the encoder and decoder have some partial knowledge about the positions where errors may occur during transmission of a codeword are derived.

The computational distribution of sequential decoding for discrete memoryless multiple-access channels is examined. It is shown that all possible collections of incorrect paths in the code tree may be described by bipartite graphs. Using this fact and a new decoding metric it is proved that the number of computations in the first incorrect subtree is a Paretean random variable, and that the parameter of the Pareto distribution is estimated similarly to the parameter for systems of information transmission with one source.

We describe hashing of databases as a problem of information and coding theory. It is shown that the triangle inequality for the Hamming distances between binary vectors may essentially decrease the computational efforts of a search for a pattern in a database. Introduction of the Lee distance in the space, which consists of the Hamming distances, leads to a new metric space where the triangle inequality can be effectively used.

A computational method, which allows us to upper-bound the solution of a wide class of systems of linear recurrent equations, is proposed. This method is used to estimate the transfer functions of noncatastrophic convolutional encoders.

An upper bound on the maximal transmission rate over binary-input memoryless channels, provided that the decoding decision rule is given, is derived. If the decision rule is equivalent to the maximum-likelihood decoding (matched decoding), then the bound coincides with the channel capacity. Otherwise (mismatched decoding), it coincides with a known lower bound.