Sufficient Conditions for Monotonicity of the Undetected Error Probability for Large Channel Error Probabilities

The performance of a linear error-detecting code in a symmetric memoryless channel is characterized by its probability of undetected error, which is a function of the channel symbol error probability, involving basic parameters of a code and its weight distribution. However, the code weight distribution is known for relatively few codes since its computation is an NP-hard problem. It should therefore be useful to have criteria for properness and goodness in error detection that do not involve the code weight distribution. In this work we give two such criteria. We show that a binary linear code C of length n and its dual code C^⊥ of minimum code distance d^⊥ are proper for error detection whenever d^⊥ ≥ ?n/2? + 1, and that C is proper in the interval [(n + 1 ? 2d^⊥)/(n ? d^⊥); 1/2] whenever ?n/3? + 1 ≤ d^⊥ ≤ ?n/2?. We also provide examples, mostly of Griesmer codes and their duals, that satisfy the above conditions.     

Almost cover-free codes

We say that an s-subset of codewords of a code X is (s, l)-bad if X contains l other codewords such that the conjunction of these l words is covered by the disjunction of the words of the s-subset. Otherwise, an s-subset of codewords of X is said to be (s, l)-bad. A binary code X is called a disjunctive (s, l) cover-free (CF) code if X does not contain (s, l)-bad subsets. We consider a probabilistic generalization of (s, l) CF codes: we say that a binary code is an (s, l) almost cover-free (ACF) code if almost all s-subsets of its codewords are (s, l)-good. The most interesting result is the proof of a lower and an upper bound for the capacity of (s, l) ACF codes; the ratio of these bounds tends as s→∞ to the limit value log₂ e/(le).     

Conflict-avoiding codes and cyclic triple systems

The paper deals with the problem of constructing a code of the maximum possible cardinality consisting of binary vectors of length n and Hamming weight 3 and having the following property: any 3 × n matrix whose rows are cyclic shifts of three different code vectors contains a 3 × 3 permutation matrix as a submatrix. This property (in the special case w = 3) characterizes conflict-avoiding codes of length n for w active users, introduced in [1]. Using such codes in channels with asynchronous multiple access allows each of w active users to transmit a data packet successfully in one of w attempts during n time slots without collisions with other active users. An upper bound on the maximum cardinality of a conflict-avoiding code of length n with w = 3 is proved, and constructions of optimal codes achieving this bound are given. In particular, there are found conflict-avoiding codes for w = 3 which have much more vectors than codes of the same length obtained from cyclic Steiner triple systems by choosing a representative in each cyclic class.     

Mechanising a Type-Safe Model of Multithreaded Java with a Verified Compiler

This article presents JinjaThreads, a unified, type-safe model of multithreaded Java source code and bytecode formalised in the proof assistant Isabelle/HOL. The semantics strictly separates sequential aspects from multithreading features like locks, forks and joins, interrupts, and the wait-notify mechanism. This separation yields an interleaving framework and a notion of deadlocks that are independent of the language, and makes the type safety proofs modular. JinjaThreads’s non-optimising compiler translates source code into bytecode. Its correctness proof guarantees that the generated bytecode exhibits exactly the same observable behaviours as the source code, even for infinite executions and under the Java memory model. The semantics and the compiler are executable. JinjaThreads builds on and reuses the Java formalisations Jinja, Bali, \(\mu \)Java, and Java\(^{\ell ight}\) by Nipkow’s group. Being the result of more than fifteen years of studying Java in Isabelle/HOL, it constitutes a large and long-lasting case study. It shows that fairly standard formalisation techniques scale well and highlights the challenges, benefits, and drawbacks of formalisation reuse.     

On the symmetry group of the Mollard code

We study the symmetry group of a binary perfect Mollard code M(C,D) of length tm + t + m containing as its subcodes the codes C ¹ and D ² formed from perfect codes C and D of lengths t and m, respectively, by adding an appropriate number of zeros. For the Mollard codes, we generalize the result obtained in [1] for the symmetry group of Vasil’ev codes; namely, we describe the stabilizer

$$Sta{b_{{D^2}}}$$

Sym(M(C,D)) of the subcode D ² in the symmetry group of the code M(C,D) (with the trivial function). Thus we obtain a new lower bound on the order of the symmetry group of the Mollard code. A similar result is established for the automorphism group of Steiner triple systems obtained by the Mollard construction but not necessarily associated with perfect codes. To obtain this result, we essentially use the notions of “linearity” of coordinate positions (points) of a nonlinear perfect code and a nonprojective Steiner triple system.

     

MDS codes in Doob graphs

The Doob graph D(m, n), where m > 0, is a Cartesian product of m copies of the Shrikhande graph and n copies of the complete graph K ₄ on four vertices. The Doob graph D(m, n) is a distance-regular graph with the same parameters as the Hamming graph H(2m + n, 4). We give a characterization of MDS codes in Doob graphs D(m, n) with code distance at least 3. Up to equivalence, there are m ³/36+7m ²/24+11m/12+1?(m mod 2)/8?(m mod 3)/9 MDS codes with code distance 2m + n in D(m, n), two codes with distance 3 in each of D(2, 0) and D(2, 1) and with distance 4 in D(2, 1), and one code with distance 3 in each of D(1, 2) and D(1, 3) and with distance 4 in each of D(1, 3) and D(2, 2).     

Property-Preserving Data Reconstruction

We initiate a new line of investigation into online property-preserving data reconstruction. Consider a dataset which is assumed to satisfy various (known) structural properties; e.g., it may consist of sorted numbers, or points on a manifold, or vectors in a polyhedral cone, or codewords from an error-correcting code. Because of noise and errors, however, an (unknown) fraction of the data is deemed unsound, i.e., in violation with the expected structural properties. Can one still query into the dataset in an online fashion and be provided data that is always sound? In other words, can one design a filter which, when given a query to any item I in the dataset, returns a sound item J that, although not necessarily in the dataset, differs from I as infrequently as possible. No preprocessing should be allowed and queries should be answered online.We consider the case of a monotone function. Specifically, the dataset encodes a function f:{1,…,n}?? R that is at (unknown) distance ε from monotone, meaning that f can—and must—be modified at ε n places to become monotone.Our main result is a randomized filter that can answer any query in O(log?² nlog? log?n) time while modifying the function f at only O(ε n) places. The amortized time over n function evaluations is O(log?n). The filter works as stated with probability arbitrarily close to 1. We provide an alternative filter with O(log?n) worst case query time and O(ε nlog?n) function modifications. For reconstructing d-dimensional monotone functions of the form f:{1,…,n} ^d ? ? R, we present a filter that takes (2 ^O(d)(log?n)^4d?2log?log?n) time per query and modifies at most O(ε n ^d ) function values (for constant d).     

Propelinear codes related to some classes of optimal codes

A code is said to be propelinear if its automorphism group contains a subgroup that acts regularly on codewords. We show propelinearity of complements of cyclic codes C _1,i , (i, 2 ^m ? 1) = 1, of length n = 2 ^m ? 1, including the primitive two-error-correcting BCH code, to the Hamming code; the Preparata code to the Hamming code; the Goethals code to the Preparata code; and the Z₄-linear Preparata code to the Z₄-linear perfect code.     

A Note on the Uniqueness of (<Emphasis Type="Italic">w,r</Emphasis>) Cover-Free Codes

A binary code is called a (w, r) cover-free code if it is the incidence matrix of a family of sets where the intersection of any w sets is not covered by the union of any other r sets. For certain (w, r) cover-free codes with a simple structure, we obtain a new condition of optimality and uniqueness up to row and/or column permutations.     

Chronicle of a Java Card death

Various attacks are designed to gain access to the assets of Java Card Platforms. These attacks use software, hardware or a combination of both. Manufacturers have improved their countermeasures to protect card assets from these attacks. In this paper, we attempt to gain access to assets of a recent Java Card Platform by combining various logical attacks. As we did not have any information about the internal structure of the targeted platform, we had to execute various attacks and analyze the results. Our investigation on the targeted Java Card Platform lead us to introduce two generic methods to gain access to the assets of Java Card Platforms. One of the new methods we present in this paper is based on the misuse of the Java Card API to build a type confusion and get access to the objects (including cryptographic keys) of a Java Card applet. The other method is a new approach to get access to the return address of the methods in Java Cards with Separate Stack countermeasure. We also propose a pattern that the targeted platform uses to store data and code of applets on the card plus the ability to read and write in the data and code area of the applets in different security contexts. These new attacks occur even in the presence of countermeasures such as Separate Stack for kernel and user data, indirect mapping for objects addressing and firewall mechanisms.     

Maximum Remaining Service Time in Infinite-Server Queues

We study the maximum remaining service time in infinite-server queues of type M|G|∞ (at a given time and in a stationary regime). The following cases for the arrival flow rate are considered: (1) time-independent, (2) given by a function of time, (3) given by a random process. As examples of service time distributions, we consider exponential, hyperexponential, Pareto, and uniform distributions. In the case of a constant rate, we study effects that arise when the average service time is infinite (for power-law distribution tails). We find the extremal index of the sequence of maximum remaining service times. The results are extended to queues of type M^X|G|∞, including those with dependent service times within a batch.     

Optimisation of a non linear fuzzy function

 We present a first study concerning the optimization of a non linear fuzzy function f depending both on a crisp variable and a fuzzy number: therefore the function value is a fuzzy number. More specifically, given a real fuzzy number ?∈F and the function f(a,x):R ²→R, we consider the fuzzy extension induced by f, f˜ : F × R → F, f˜(?,x) = Y˜. If K is a convex subset of R, the problem we consider is “maximizing”f˜(?,x), xˉ∈ K. The first problem is the meaning of the word “maximizing”: in fact it is well-known that ranking fuzzy numbers is a complex matter. Following a general method, we introduce a real function (evaluation function) on real fuzzy numbers, in order to get a crisp rating, induced by the order of the real line. In such a way, the optimization problem on fuzzy numbers can be written in terms of an optimization problem for the real-valued function obtained by composition of f with a suitable evaluation function. This approach allows us to state a necessary and sufficient condition in order that ∈K is the maximum for f˜ in K, when f(a,x) is convex-concave (Theorem 4.1).     

On the Smallest Size of an Almost Complete Subset of a Conic in PG(2, <Emphasis Type="Italic">q</Emphasis>) and Extendability of Reed–Solomon Codes

Abstract—In the projective plane PG(2, q), a subset S of a conic C is said to be almost complete if it can be extended to a larger arc in PG(2, q) only by the points of C \ S and by the nucleus of C when q is even. We obtain new upper bounds on the smallest size t(q) of an almost complete subset of a conic, in particular,

$$t(q) < \sqrt {q(3lnq + lnlnq + ln3)} + \sqrt {\frac{q}{{3\ln q}}} + 4 \sim \sqrt {3q\ln q} ,t(q) < 1.835\sqrt {q\ln q.} $$

The new bounds are used to extend the set of pairs (N, q) for which it is proved that every normal rational curve in the projective space PG(N, q) is a complete (q+1)-arc, or equivalently, that no [q+1,N+1, q?N+1]_q generalized doubly-extended Reed–Solomon code can be extended to a [q + 2,N + 1, q ? N + 2]_q maximum distance separable code.

     

Polar Codes with Higher-Order Memory

We introduce a construction of a set of code sequences {C_n^(m) : n ≥ 1, m ≥ 1} with memory order m and code length N(n). {C_n^(m)} is a generalization of polar codes presented by Ar?kan in [1], where the encoder mapping with length N(n) is obtained recursively from the encoder mappings with lengths N(n ? 1) and N(n ? m), and {C_n^(m)} coincides with the original polar codes when m = 1. We show that {C_n^(m)} achieves the symmetric capacity I(W) of an arbitrary binary-input, discrete-output memoryless channel W for any fixed m. We also obtain an upper bound on the probability of block-decoding error P_e of {C_n^(m)} and show that \({P_e} = O({2^{ - {N^\beta }}})\) is achievable for β < 1/[1+m(? ? 1)], where ? ∈ (1, 2] is the largest real root of the polynomial F(m, ρ) = ρ^m ? ρ^{m ? 1} ? 1. The encoding and decoding complexities of {C_n^(m)} decrease with increasing m, which proves the existence of new polar coding schemes that have lower complexity than Ar?kan’s construction.     

A unified integration and component testing approach from deterministic stream X-machine specifications

One of the great benefits of using a stream X-machine to specify a system is its associated testing method. Under certain design for test conditions, this method produces a test suite that can determine the correctness of the implementation under test (IUT), provided that the basic components of the stream X-machine model have been correctly implemented. However, such an approach implies that each component can be tested in isolation from the rest of the system. This is a limitation that, in practice, can be resolved by developing stubs and drivers. However, this adds complexity to the testing process and, furthermore, these new pieces of software can introduce faults that can invalidate the theoretical results of the aforementioned testing method. This paper extends the approach by allowing component testing to be performed in parallel with integration testing, while still guaranteeing the IUT correctness under the given design for test conditions. It also shows how the integration test suite, produced in previous publications, can be reduced.     

Bounds on the rate of separating codes

A code with words in a finite alphabet is said to be an (s, l) separating code if for any two disjoint collections of its words of size at most s and l, respectively, there exists a coordinate in which the set of symbols of the first collection do not intersect the set of symbols of the second. The main goal of the paper is obtaining new bounds on the rate of (s, l) separating codes. Bounds on the rate of binary (s, l) separating codes, the most important for applications, are studied in more detail. We give tables of numerical values of the best presently known bounds on the rate.     

Shadow Prices in Territory Division

We consider a geographic optimization problem in which we are given a region R, a probability density function f(?) defined on R, and a collection of n utility density functions u _i (?) defined on R. Our objective is to divide R into n sub-regions R _i so as to “balance” the overall utilities on the regions, which are given by the integrals \(\iint _{R_{i}}f(x)u_{i}(x)\, dA\). Using a simple complementary slackness argument, we show that (depending on what we mean precisely by “balancing” the utility functions) the boundary curves between optimal sub-regions are level curves of either the difference function u _i (x) ? u _j (x) or the ratio u _i (x)/u _j (x). This allows us to solve the problem of optimally partitioning the region efficiently by reducing it to a low-dimensional convex optimization problem. This result generalizes, and gives very short and constructive proofs of, several existing results in the literature on equitable partitioning for particular forms of f(?) and u _i (?). We next give two economic applications of our results in which we show how to compute a market-clearing price vector in an aggregate demand system or a variation of the classical Fisher exchange market. Finally, we consider a dynamic problem in which the density function f(?) varies over time (simulating population migration or transport of a resource, for example) and derive a set of partial differential equations that describe the evolution of the optimal sub-regions over time. Numerical simulations for both static and dynamic problems confirm that such partitioning problems become tractable when using our methods.     

On ℤ<Subscript>4</Subscript>-linear codes with the parameters of Reed-Muller codes

For any pair of integers r and m, 0 ≤ r ≤ m, we construct a class of quaternary linear codes whose binary images under the Gray map are codes with the parameters of the classical rth-order Reed-Muller code RM(r, m).     

Meaningful (2, infinity) secret image sharing scheme based on flipping operations

In this paper, a new method to construct a secret image sharing (SIS) scheme is proposed, where a secret image is shared into several shares by a perfect secure way without any knowledge of cryptography. A basic algorithm implemented by flipping operations with probability for constructing a meaningful (2, 2) SIS scheme is first proposed. Neither codebook tailor-made requirement nor pixel expansion is required in the proposed scheme. Additionally, the meaningful shares by the proposed scheme can be directly generated without any extra data hiding process. During the decrypting procedure, the secret image is visually revealed by performing XOR operations on two meaningful shares. In the following stage, a meaningful (2, infinity) SIS scheme is extended underlying the basic algorithm, where the number of shares can be extended anytime. Further, no matter how large the number of the extended shares is, the visual qualities of both the meaningful share and revealed secret image remain unchanged. Finally, sufficient number of formal proofs are provided to validate the correctness of the proposed schemes, whose superiority is also demonstrated by the experimental results.     

Incompressible Functions,Relative-Error Extractors,and the Power of Nondeterministic Reductions

A circuit C compresses a function \({f : \{0,1\}^n\rightarrow \{0,1\}^m}\) if given an input \({x\in \{0,1\}^n}\), the circuit C can shrink x to a shorter ?-bit string x′ such that later, a computationally unbounded solver D will be able to compute f(x) based on x′. In this paper we study the existence of functions which are incompressible by circuits of some fixed polynomial size \({s=n^c}\). Motivated by cryptographic applications, we focus on average-case \({(\ell,\epsilon)}\) incompressibility, which guarantees that on a random input \({x\in \{0,1\}^n}\), for every size s circuit \({C:\{0,1\}^n\rightarrow \{0,1\}^{\ell}}\) and any unbounded solver D, the success probability \({\Pr_x[D(C(x))=f(x)]}\) is upper-bounded by \({2^{-m}+\epsilon}\). While this notion of incompressibility appeared in several works (e.g., Dubrov and Ishai, STOC 06), so far no explicit constructions of efficiently computable incompressible functions were known. In this work, we present the following results:

1. (1)
   Assuming that E is hard for exponential size nondeterministic circuits, we construct a polynomial time computable boolean function \({f:\{0,1\}^n\rightarrow \{0,1\}}\) which is incompressible by size n ^c circuits with communication \({\ell=(1-o(1)) \cdot n}\) and error \({\epsilon=n^{-c}}\). Our technique generalizes to the case of PRGs against nonboolean circuits, improving and simplifying the previous construction of Shaltiel and Artemenko (STOC 14).
    
2. (2)
   We show that it is possible to achieve negligible error parameter \({\epsilon=n^{-\omega(1)}}\) for nonboolean functions. Specifically, assuming that E is hard for exponential size \({\Sigma_3}\)-circuits, we construct a nonboolean function \({f:\{0,1\}^n\rightarrow \{0,1\}^m}\) which is incompressible by size n ^c circuits with \({\ell=\Omega(n)}\) and extremely small \({\epsilon=n^{-c} \cdot 2^{-m}}\). Our construction combines the techniques of Trevisan and Vadhan (FOCS 00) with a new notion of relative error deterministic extractor which may be of independent interest.
    
3. (3)
   We show that the task of constructing an incompressible boolean function \({f:\{0,1\}^n\rightarrow \{0,1\}}\) with negligible error parameter \({\epsilon}\) cannot be achieved by “existing proof techniques”. Namely, nondeterministic reductions (or even \({\Sigma_i}\) reductions) cannot get \({\epsilon=n^{-\omega(1)}}\) for boolean incompressible functions. Our results also apply to constructions of standard Nisan-Wigderson type PRGs and (standard) boolean functions that are hard on average, explaining, in retrospect, the limitations of existing constructions. Our impossibility result builds on an approach of Shaltiel and Viola (STOC 08).