A construction for t-fold perfect authentication codes with arbitration

Authentication codes with arbitration protect against deceptions from the transmitter and the receiver as well as that from the opponent. An authentication code with arbitration is t-fold perfect if the numbers of decoding rules and encoding rules meet the information-theoretic lower bounds. Pei (Message authentication codes (in Chinese). USCT, Hefei, 2009) pointed out that there has not yet been able to construct t-fold perfect authentication codes with arbitration for \(t > 2\) . In this paper, we define a new design, perfect strong strict restricted partially balanced t-design, and prove that the existence of perfect strong strict restricted partially balanced t-designs implies the existence of t-fold perfect authentication codes with arbitration. Further, we obtain some new infinite classes of t-fold perfect authentication codes with arbitration.     

A construction for optimal <Emphasis Type="Italic">c</Emphasis>-splitting authentication and secrecy codes

Authentication and secrecy codes which provide both secrecy and authentication have been intensively studied in the case where there is no splitting; however the results concerning the case where there is splitting are far fewer. In this paper, we focus on the case with c-splitting, and obtain a bound on the number of encoding rules required in order to obtain maximum levels of security. A c-splitting authentication and secrecy code is called optimal if it obtains maximum levels of security and has the minimum number of encoding rules. We define a new design, called an authentication perpendicular multi-array, and prove that the existence of authentication perpendicular multi-arrays implies the existence of optimal c-splitting authentication and secrecy codes. Further, we study the constructions and existence of authentication perpendicular multi-arrays, and then obtain two new infinite classes of optimal c-splitting authentication and secrecy codes.     

Construction of Cartesian authentication codes from unitary geometry

In the present paper several constructions of Cartesian authentication codes from unitary geometry over finite fields are presented and their size parameters are computed. Assuming that the encoding rules are chosen according to a uniform probability distribution, the probabilities P _I and P _S of a successful impersonation attack and a successful substitution attack, respectively, of these codes are also computed. Moreover, those codes so constructed, for which P _I and P _S are nearly optimal, are also determined.     

On construction of vertex-transitive partitions of the <Emphasis Type="Italic">n</Emphasis>-cube into perfect codes

Two methods are presented to construct some vertex-transitive and 2-transitive partitions of the n-cube into perfect codes. Some lower bounds are given on the number of transitive, vertex-transitive, and 2-transitive partitions of the n-cube into perfect codes.     

构作正交空间中的一类Cartesian认证码

利用正交几何构作出一类Cartesian认证码,并且计算了它们的参数.假定信源和编码规则都按等概率分布选取,求出了认证码的成功的模仿攻击概率PI和成功的替换攻击概率PS.本文构作的Cartesian认证码的成功的模仿攻击概率PI均达到了其下界.     

New Constructions for IPP Codes

Identifiable parent property (IPP) codes are introduced to provide protection against illegal producing of copyrighted digital material. In this paper we consider explicit construction methods for IPP codes by means of recursion techniques. The first method directly constructs IPP codes, whereas the second constructs perfect hash families that are then used to derive IPP codes. In fact, the first construction provides an infinite class of IPP codes having the best known asymptotic behavior. We also prove that this class has a traitor tracing algorithm with a runtime of O(M) in general, where M is the number of codewords.     

On maximal Spherical codes II

We consider spherical codes attaining the Levenshtein upper bounds on the cardinality of codes with prescribed maximal inner product. We prove that the even Levenshtein bounds can be attained only by codes which are tight spherical designs. For every fixed n ≥ 5, there exist only a finite number of codes attaining the odd bounds. We derive different expressions for the distance distribution of a maximal code. As a by-product, we obtain a result about its inner products. We describe the parameters of those codes meeting the third Levenshtein bound, which have a regular simplex as a derived code. Finally, we discuss a connection between the maximal codes attaining the third bound and strongly regular graphs. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 316–326, 1999     

A new class of 3-fold perfect splitting authentication codes

Restricted strong partially balanced t-designs were first formulated by Pei, Li, Wang and Safavi-Naini in investigation of authentication codes with arbitration. In this article, we will prove that splitting authentication codes that are multi-fold perfect against spoofing can be characterized in terms of restricted strong partially balanced t-designs. We will also investigate the existence of restricted strong partially balanced 3-designs RSPBD 3-(v, b, 3 × 2; λ₁, λ₂, 1, 0)s, and show that there exists an RSPBD 3-(v, b, 3 × 2; λ₁, λ₂, 1, 0) for any v o 9 (mod 16){v\equiv 9\ (\mbox{{\rm mod}}\ 16)} . As its application, we obtain a new infinite class of 3-fold perfect splitting authentication codes.     

A coding problem in steganography

To study how to design a steganographic algorithm more efficiently, a new coding problem—steganographic codes (abbreviated stego-codes)—is presented in this paper. The stego-codes are defined over the field with q(q ≥ 2) elements. A method of constructing linear stego-codes is proposed by using the direct sum of vector subspaces. And the problem of linear stego-codes is converted to an algebraic problem by introducing the concept of the tth dimension of a vector space. Some bounds on the length of stego-codes are obtained, from which the maximum length embeddable (MLE) code arises. It is shown that there is a corresponding relation between MLE codes and perfect error-correcting codes. Furthermore the classification of all MLE codes and a lower bound on the number of binary MLE codes are obtained based on the corresponding results on perfect codes. Finally hiding redundancy is defined to value the performance of stego-codes.      

Universal hashing and authentication codes

In this paper, we study the application of universal hashing to the construction of unconditionally secure authentication codes without secrecy. This idea is most useful when the number of authenticators is exponentially small compared to the number of possible source states (plaintext messages). We formally define some new classes of hash functions and then prove some new bounds and give some general constructions for these classes of hash functions. Then we discuss the implications to authentication codes.A preliminary version of this paper was presented at CRYPTO '91 and appeared in Lecture Notes in Computer Science, vol. 576, pp. 74–85, Springer-Verlag, 1992.     

The value of the stochastic solution in multistage problems

We generalize the definition of the bounds for the optimal value of the objective function for various deterministic equivalent models in multistage stochastic programs. The parameters EVPI and VSS were introduced for two-stage models. The parameter EVPI, the expected value of perfect information, measures how much it is reasonable to pay to obtain perfect information about the future. The parameter VSS, the value of the stochastic solution, allows us to obtain the goodness of the expected solution value when the expected values are replaced by the random values for the input variables. We extend the definition of these parameters to the multistage stochastic model and prove a similar chain of inequalities with the lower and upper bounds depending substantially on the structure of the problem. This research has been partially supported by the grants, 1/BBVA 00038.16421/2004 from Fundación BBVA, SEJ2005-05549/ECON from Ministerio de Educación y Ciencia and the grant GRUPOS79/04 from the Generalitat Valenciana, Spain.     

Some explicit upper bounds for residues of zeta functions of number fields taking into account the behavior of the prime 2

We recall the known explicit upper bounds for the residue at s = 1 of the Dedekind zeta function of a number field K. Then, we improve upon these previously known upper bounds by taking into account the behavior of the prime 2 in K. We finally give several examples showing how such improvements yield better bounds on the absolute values of the discriminants of CM-fields of a given relative class number. In particular, we will obtain a 4,000-fold improvement on our previous bound for the absolute values of the discriminants of the non-normal sextic CM-fields with relative class number one.     

Analysing and exploiting the Mantin biases in RC4

We explore the use of the Mantin biases (Mantin, Eurocrypt 2005) to recover plaintexts from RC4-encrypted traffic. We provide a more fine-grained analysis of these biases than in Mantin’s original work. We show that, in fact, the original analysis was incorrect in certain cases: the Mantin biases are sometimes non-existent, and sometimes stronger than originally predicted. We then show how to use these biases in a plaintext recovery attack. Our attack targets two unknown bytes of plaintext that are located close to sequences of known plaintext bytes, a situation that arises in practice when RC4 is used in, for example, TLS. We provide a statistical framework that enables us to make predictions about the performance of this attack and its variants. We then extend the attack using standard dynamic programming techniques to tackle the problem of recovering longer plaintexts, a setting of practical interest in recovering HTTP session cookies and user passwords that are protected by RC4 in TLS. We perform experiments showing that we can successfully recover 16-byte plaintexts with 80% success rate using \(2^{31}\) ciphertexts, an improvement over previous attacks.     

New Combinatorial Bounds for Authentication Codes and Key Predistribution Schemes

This paper provides new combinatorial bounds and characterizations of authentication codes (A-codes) and key predistribution schemes (KPS). We first prove a new lower bound on the number of keys in an A-code without secrecy, which can be thought of as a generalization of the classical Rao bound for orthogonal arrays. We also prove a new lower bound on the number of keys in a general A-code, which is based on the Petrenjuk, Ray-Chaudhuri and Wilson bound for t-designs. We also present new lower bounds on the size of keys and the amount of users' secret information in KPS, the latter of which is accomplished by showing that a certain A-code is hiding inside any KPS.     

A shift register construction of unconditionally secure authentication codes

We consider the authentication problem, using the model described by Simmons. Several codes have been constructed using combinatorial designs and finite geometries. We introduce a new way of constructing authentication codes using LFSR-sequences. A central part of the construction is an encoding matrix derived from these LFSR-sequences. Necessary criteria for this matrix in order to give authentication codes that provides protection aginst impersonation and substitution attacks will be given. These codes also provide perfect secrecy if the source states have a uniform distribution. Moreover, the codes give a natural splitting of the key into two parts, one part used aginst impersonation attacks and a second part used against substitution attacks and for secrecy simultaneously. Since the construction is based on the theory of LFSR-sequences it is very suitable for implementation and a simple implementation of the construction is given.     

On Linear Programming Bounds for Spherical Codes and Designs

We investigate universal bounds on spherical codes and spherical designs that could be obtained using Delsartes linear programming methods. We give a lower estimate for the LP upper bound on codes, and an upper estimate for the LP lower bound on designs. Specifically, when the distance of the code is fixed and the dimension goes to infinity, the LP upper bound on codes is at least as large as the average of the best known upper and lower bounds. When the dimension n of the design is fixed, and the strength k goes to infinity, the LP bound on designs turns out, in conjunction with known lower bounds, to be proportional to k^n-1.     

Artin–Schreier curves and weights of two-dimensional cyclic codes

Let be the finite field with q elements of characteristic p, be the extension of degree m>1 and f(x) be a polynomial over . The maximum number of affine -rational points that a curve of the form y^q−y=f(x) can have is q^m+1. We determine a necessary and sufficient condition for such a curve to achieve this maximum number. Then we study the weights of two-dimensional (2-D) cyclic codes. For this, we give a trace representation of the codes starting with the zeros of the dual 2-D cyclic code. This leads to a relation between the weights of codewords and a family of Artin–Schreier curves. We give a lower bound on the minimum distance for a large class of 2-D cyclic codes. Then we look at some special classes that are not covered by our main result and obtain similar minimum distance bounds.     

Configuration distribution and designs of codes in the Johnson scheme

The main goal of this article is to present several connections between perfect codes in the Johnson scheme and designs, and provide new tools for proving Delsarte conjecture that there are no nontrivial perfect Codes in the Johnson scheme. Three topics will be considered. The first is the configuration distribution which is akin to the weight distribution in the Hamming scheme. We prove that if there exists an e‐perfect code in the Johnson scheme then there is a formula which connects the number of vectors at distance i from any codeword in various codes isomorphic to . The second topic is the Steiner systems embedded in a perfect code. We prove a lower bound on the number of Steiner systems embedded in a perfect code. The last topic is the strength of a perfect code. We show two new methods for computing the strength of a perfect code and demonstrate them on 1‐perfect codes. We further discuss how to settle Delsarte conjecture. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 15–34, 2007     

Constructions and bounds on linear error-block codes

We obtain new bounds on the parameters and we give new constructions of linear error-block codes. We obtain a Gilbert–Varshamov type construction. Using our bounds and constructions we obtain some infinite families of optimal linear error-block codes over . We also study the asymptotic of linear error-block codes. We define the real valued function α _q,m,a (δ), which is an analog of the important real valued function α _q (δ) in the asymptotic theory of classical linear error-correcting codes. We obtain both Gilbert–Varshamov and algebraic geometry type lower bounds on α _q,m,a (δ). We compare these lower bounds in graphs.      

Hasse–Weil bound for additive cyclic codes

We obtain a bound on the minimum distance of additive cyclic codes via the number of rational points on certain algebraic curves over finite fields. This is an extension of the analogous bound in the case of classical cyclic codes. Our result is the only general bound on such codes aside from Bierbrauer’s BCH bound. We compare our bounds’ performance against the BCH bound for additive cyclic codes in a special case and provide examples where it yields better results.