Symmetric Tardos fingerprinting codes for arbitrary alphabet sizes

Fingerprinting provides a means of tracing unauthorized redistribution of digital data by individually marking each authorized copy with a personalized serial number. In order to prevent a group of users from collectively escaping identification, collusion-secure fingerprinting codes have been proposed. In this paper, we introduce a new construction of a collusion-secure fingerprinting code which is similar to a recent construction by Tardos but achieves shorter code lengths and allows for codes over arbitrary alphabets. We present results for ‘symmetric’ coalition strategies. For binary alphabets and a false accusation probability , a code length of symbols is provably sufficient, for large c ₀, to withstand collusion attacks of up to c ₀ colluders. This improves Tardos’ construction by a factor of 10. Furthermore, invoking the Central Limit Theorem in the case of sufficiently large c ₀, we show that even a code length of is adequate. Assuming the restricted digit model, the code length can be further reduced by moving from a binary alphabet to a q-ary alphabet. Numerical results show that a reduction of 35% is achievable for q = 3 and 80% for q = 10.      

Improved versions of Tardos’ fingerprinting scheme

We study the Tardos’ probabilistic fingerprinting scheme and show that its codeword length may be shortened by a factor of approximately 4. We achieve this by retracing Tardos’ analysis of the scheme and extracting from it all constants that were arbitrarily selected. We replace those constants with parameters and derive a set of inequalities that those parameters must satisfy so that the desired security properties of the scheme still hold. Then we look for a solution of those inequalities in which the parameter that governs the codeword length is minimal. A further reduction in the codeword length is achieved by decoupling the error probability of falsely accusing innocent users from the error probability of missing all colluding pirates. Finally, we simulate the Tardos scheme and show that, in practice, one may use codewords that are shorter than those in the original Tardos scheme by a factor of at least 16.      

Moment inequalities and central limit properties of isotropic convex bodies

The object of our investigations are isotropic convex bodies , centred at the origin and normed to volume one, in arbitrary dimensions. We show that a certain subset of these bodies – specified by bounds on the second and fourth moments – is invariant under forming ‘expanded joinsrsquo;. Considering a body K as above as a probability space and taking , we define random variables on K. It is known that for subclasses of isotropic convex bodies satisfying a ‘concentration of mass property’, the distributions of these random variables are close to Gaussian distributions, for high dimensions n and ‘most’ directions . We show that this ‘central limit property’, which is known to hold with respect to convergence in law, is also true with respect to -convergence and -convergence of the corresponding densities. Received: 21 March 2001 / in final form: 17 October 2001 / Published online: 4 April 2002     

A semidefinite optimization approach to the steady-state analysis of queueing systems

Obtaining (tail) probabilities from a transform function is an important topic in queueing theory. To obtain these probabilities in discrete-time queueing systems, we have to invert probability generating functions, since most important distributions in discrete-time queueing systems can be determined in the form of probability generating functions. In this paper, we calculate the tail probabilities of two particular random variables in discrete-time priority queueing systems, by means of the dominant singularity approximation. We show that obtaining these tail probabilities can be a complex task, and that the obtained tail probabilities are not necessarily exponential (as in most ‘traditional’ queueing systems). Further, we show the impact and significance of the various system parameters on the type of tail behavior. Finally, we compare our approximation results with simulations.     

Simultaneous Approximation in Positive Characteristic

 Let be the approximation exponent of a power series α (so that when α is algebraic of degree d, then by Dirichlet’s and Liouville’s Theorems). If the characteristic is positive, q is a power of the characteristic, and are related by a fractional linear transformation with polynomial coefficients, then by respective work of Voloch and of de Mathan, there are constants such that has no solution if , and infinitely many solutions if . We will formulate and prove generalizations to simultaneous approximation.     

On The Span Of A Random Channel Assignment Problem

In the radio channel assignment problems considered here, we must assign a ‘channel’ from the set 1,2,... of positive integers to each of n transmitters, and we wish to minimise the span of channels used, subject to the assignment leading to an acceptable level of interference. A standard form of this problem is the ‘constraint matrix’ model. The simplest case of this model (the 0, 1 case) is essentially graph colouring. We consider here a random model for the next simplest case (with lengths 0, 1 or 2), and determine the asymptotic behaviour of the span of channels needed as n→∞. We find that there is a ‘phase change’ in this behaviour, depending on the probabilities for the different lengths.     

Simultaneous Approximation in Positive Characteristic

 Let be the approximation exponent of a power series α (so that when α is algebraic of degree d, then by Dirichlet’s and Liouville’s Theorems). If the characteristic is positive, q is a power of the characteristic, and are related by a fractional linear transformation with polynomial coefficients, then by respective work of Voloch and of de Mathan, there are constants such that has no solution if , and infinitely many solutions if . We will formulate and prove generalizations to simultaneous approximation. (Received 7 December 1999; in revised form 31 March 2000)     

Isotonic tests for spread and tail

Summary One-sample test problem for ‘stochastically more (or less) spread’ is defined and a family of tests with isotonic power is given. The problem is closely related to that for ‘longer (or shorter) tail’ in the reliability theory and the correspondence between them is shown. To characterize the tests three spread preorders inR ⁿ and corre-sponding tail preorders inR ₊ ⁿ are introduced. Functions which are ‘monotone’ in these orders, and subsets which are ‘centrifugal’ or ‘centripetal’ with respect to these orders are studied. These notions generalize the Schur convexity. The Institute of Statistical Mathematics     

Estimating tail probabilities of heavy tailed distributions with asymptotically zero relative error

Efficient estimation of tail probabilities involving heavy tailed random variables is amongst the most challenging problems in Monte-Carlo simulation. In the last few years, applied probabilists have achieved considerable success in developing efficient algorithms for some such simple but fundamental tail probabilities. Usually, unbiased importance sampling estimators of such tail probabilities are developed and it is proved that these estimators are asymptotically efficient or even possess the desirable bounded relative error property. In this paper, as an illustration, we consider a simple tail probability involving geometric sums of heavy tailed random variables. This is useful in estimating the probability of large delays in M/G/1 queues. In this setting we develop an unbiased estimator whose relative error decreases to zero asymptotically. The key idea is to decompose the probability of interest into a known dominant component and an unknown small component. Simulation then focuses on estimating the latter ‘residual’ probability. Here we show that the existing conditioning methods or importance sampling methods are not effective in estimating the residual probability while an appropriate combination of the two estimates it with bounded relative error. As a further illustration of the proposed ideas, we apply them to develop an estimator for the probability of large delays in stochastic activity networks that has an asymptotically zero relative error.      

On the Number of i.i.d. Samples Required to Observe All of the Balls in an Urn

Suppose an urn contains m distinct balls, numbered 1,...,m, and let τ denote the number of i.i.d. samples required to observe all of the balls in the urn. We generalize the partial fraction expansion type arguments used by Pólya (Z Angew Math Mech 10:96–97, 1930) for approximating \mathbbE(t)\mathbb{E}(\tau) in the case of fixed sample sizes to obtain an approximation of \mathbbE(t)\mathbb{E}(\tau) when the sample sizes are i.i.d. random variables. The approximation agrees with that of Sellke (Ann Appl Probab 5(1):294–309, 1995), who made use of Wald’s equation and a Markov chain coupling argument. We also derive a new approximation of \mathbbV(t)\mathbb{V}(\tau), provide an (improved) bound on the error in these approximations, derive a recurrence for \mathbbE(t)\mathbb{E}(\tau), give a new large deviation type result for tail probabilities, and look at some special cases.     

Gambler’s ruin and winning a series by <Emphasis Type="Italic">m</Emphasis> games

Two teams play a series of games until one team accumulates m more wins than the other. These series are fairly common in some sports provided that the competition has already extended beyond some number of games. We generalize these schemes to allow ties in the single games. Different approaches offer different advantages in calculating the winning probabilities and the distribution of the duration N, including difference equations, conditioning, explicit and implicit path counting, generating functions and a martingale-based derivation of the probability and moment generating functions of N. The main result of the paper is the determination of the exact distribution of N for a series of fair games without ties as a sum of independent geometrically distributed random variables and its approximation.     

Discontinuous Galerkin methods for the linear Schrödinger equation in non-cylindrical domains

The convergence of a discontinuous Galerkin method for the linear Schrödinger equation in non-cylindrical domains of ${\mathbb{R}^m}The convergence of a discontinuous Galerkin method for the linear Schr?dinger equation in non-cylindrical domains of \mathbbR^m{\mathbb{R}^m}, m ≥ 1, is analyzed in this paper. We show the existence of the resulting approximations and prove stability and error estimates in finite element spaces of general type. When m = 1 the resulting problem is related to the standard narrow angle ‘parabolic’ approximation of the Helmholtz equation, as it appears in underwater acoustics. In this case we investigate theoretically and numerically the order of convergence using finite element spaces of piecewise polynomial functions.     

Réseaux quaternioniens et invariant de Venkov

We define an infinite family of even unimodular latticesU _n with minimal norm 4, endowed with a quaternionic structure. We compute their ‘Venkov invariant’, which allows us to identifyU ₃₂ with a previous known lattice, constructed from the Reed-Muller code of length 32.      

Parameter redundancy in neural networks: an application of Chebyshev polynomials

This paper deals with feedforward neural networks containing a single hidden layer and with sigmoid/logistic activation function. Training such a network is equivalent to implementing nonlinear regression using a flexible functional form, but the functional form in question is not easy to deal with. The Chebyshev polynomials are suggested as a way forward, providing an approximation to the network which is superior to Taylor series expansions. Application of these approximations suggests that the network is liable to a ‘naturally occurring’ parameter redundancy, which has implications for the training process as well as certain statistical implications. On the other hand, parameter redundancy does not appear to damage the fundamental property of universal approximation.      

Approximation of classes of periodic multivariable functions by linear positive operators

In an N-dimensional space, we consider the approximation of classes of translation-invariant periodic functions by a linear operator whose kernel is the product of two kernels one of which is positive. We establish that the least upper bound of this approximation does not exceed the sum of properly chosen least upper bounds in m-and ((N − m))-dimensional spaces. We also consider the cases where the inequality obtained turns into the equality. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 58, No. 1, pp. 12–19, January, 2006.     

Smoothing algorithms for state–space models

Two-filter smoothing is a principled approach for performing optimal smoothing in non-linear non-Gaussian state–space models where the smoothing distributions are computed through the combination of ‘forward’ and ‘backward’ time filters. The ‘forward’ filter is the standard Bayesian filter but the ‘backward’ filter, generally referred to as the backward information filter, is not a probability measure on the space of the hidden Markov process. In cases where the backward information filter can be computed in closed form, this technical point is not important. However, for general state–space models where there is no closed form expression, this prohibits the use of flexible numerical techniques such as Sequential Monte Carlo (SMC) to approximate the two-filter smoothing formula. We propose here a generalised two-filter smoothing formula which only requires approximating probability distributions and applies to any state–space model, removing the need to make restrictive assumptions used in previous approaches to this problem. SMC algorithms are developed to implement this generalised recursion and we illustrate their performance on various problems.     

An improvement of discrete Tardos fingerprinting codes

It has been proven that the code lengths of Tardos’s collusion-secure fingerprinting codes are of theoretically minimal order with respect to the number of adversarial users (pirates). However, the code lengths can be further reduced as some preceding studies have revealed. In this article we improve a recent discrete variant of Tardos’s codes, and give a security proof of our codes under an assumption weaker than the original Marking Assumption. Our analysis shows that our codes have significantly shorter lengths than Tardos’s codes. For example, when c = 8, our code length is about 4.94% of Tardos’s code in a practical setting and about 4.62% in a certain limit case. Our code lengths for large c are asymptotically about 5.35% of Tardos’s codes. A part of this work was presented at 17th Applied Algebra, Algebraic Algorithms, and Error Correcting Codes (AAECC-17), Bangalore, India, December 16–20, 2007.     

Éclatement des coefficients des séries entières et deux théorèmes de Gabrielov

Given a non trivial power series in ℝ ^m × ℝ ^k , it is in general not possible to choose a good direction in ℝ ^k in order to apply Weierstrass Preparation Theorem. Now, one can make it possible by blowing-up coefficients in ℝ ^m . This enables e. g. to prove in some natural way Gabrielov’s complement theorem, as well as Gabrielov’s fiber components theorem in subanalytic geometry.      

The infinite server queue and heuristic approximations to the multi-server queue with and without retrials

In this paper, properties of the time-dependent state probabilities of theM _t /G/∞ queue, when the queue is assumed to start empty are studied. Those results are compared with corresponding time-dependent results for theM/M/1 queue. Approximation to the time-dependent state probabilities of theM/G/m/m queue by means of the corresponding time-dependent state probabilities of theM/G/∞ queue are discussed. Through a decomposition formula it is shown that the main performance characteristics of the ergodicM/M/m/m+d queue are sums of the corresponding random variables for the ergodicM/M/m/m andM/M/1/1+(d−1) queues, respectively, weighted by the 3-rd Erlang formula (stationary probability of waiting or being lost for theM/M/m/m+d queue). Successful exact and approximation extensions of this kind of decomposition formula to theM/M/m/m+d queue with retrials are presented.     

The <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/∞ system revisited: finiteness,summability, long range dependence,and reverse engineering

We explore M/G/∞ systems ‘fed’ by Poissonian inflows with infinite arrival rates. Three processes – corresponding to the system's state, workload, and queue-size – are studied and analyzed. Closed form formulae characterizing the system's stationary structure and correlation structure are derived. And, the issues of queue finiteness, workload summability, and Long Range Dependence are investigated. We then turn to devise a ‘reverse engineering’ scheme for the design of the system's correlation structure. Namely: how to construct an M/G/∞ system with a pre-desired ‘target’ workload/queue auto-covariance function. The ‘reverse engineering’ scheme is applied to various examples, including ones with infinite queues and non-summable workloads. AMS Subject Classifications Primary: 60K25; Secondary: 60G55, 60G10