Search

In a conventional secret sharing scheme a dealer uses secure point-to-point channels to distribute the shares of a secret to a number of participants. At a later stage an authorised group of participants send their shares through secure point-to-point channels to a combiner who will reconstruct the secret. In this paper, we assume no point-to-point channel exists and communication is only through partial broadcast channels. A partial broadcast channel is a point-to-multipoint channel that enables a sender to send the same message simultaneously and privately to a fixed subset of receivers. We study secret sharing schemes with partial broadcast channels, called partial broadcast secret sharing schemes. We show that a necessary and sufficient condition for the partial broadcast channel allocation of a (t, n)-threshold partial secret sharing scheme is equivalent to a combinatorial object called a cover-free family. We use this property to construct a (t, n)-threshold partial broadcast secret sharing scheme with O(log n) partial broadcast channels. This is a significant reduction compared to npoint-to-point channels required in a conventional secret sharing scheme. Next, we consider communication rate of a partial broadcast secret sharing scheme defined as the ratio of the secret size to the total size of messages sent by the dealer. We show that the communication rate of a partial broadcast secret sharing scheme can approach 1/O(log n) which is a significant increase over the corresponding value, 1/n, in the conventional secret sharing schemes. We derive a lower bound on the communication rate and show that for a (t,n)-threshold partial broadcast secret sharing scheme the rate is at least 1/tand then we propose constructions with high communication rates. We also present the case of partial broadcast secret sharing schemes for general access structures, discuss possible extensions of this work and propose a number of open problems.In a conventional secret sharing scheme a dealer uses secure point-to-point channels to distribute the shares of a secret to a number of participants. At a later stage an authorised group of participants send their shares through secure point-to-point channels to a combiner who will reconstruct the secret. In this paper, we assume no point-to-point channel exists and communication is only through partial broadcast channels. A partial broadcast channel is a point-to-multipoint channel that enables a sender to send the same message simultaneously and privately to a fixed subset of receivers. We study secret sharing schemes with partial broadcast channels, called partial broadcast secret sharing schemes. We show that a necessary and sufficient condition for the partial broadcast channel allocation of a (t, n)-threshold partial secret sharing scheme is equivalent to a combinatorial object called a cover-free family. We use this property to construct a (t, n)-threshold partial broadcast secret sharing scheme with O(log n) partial broadcast channels. This is a significant reduction compared to npoint-to-point channels required in a conventional secret sharing scheme. Next, we consider communication rate of a partial broadcast secret sharing scheme defined as the ratio of the secret size to the total size of messages sent by the dealer. We show that the communication rate of a partial broadcast secret sharing scheme can approach 1/O(log n) which is a significant increase over the corresponding value, 1/n, in the conventional secret sharing schemes. We derive a lower bound on the communication rate and show that for a (t,n)-threshold partial broadcast secret sharing scheme the rate is at least 1/tand then we propose constructions with high communication rates. We also present the case of partial broadcast secret sharing schemes for general access structures, discuss possible extensions of this work and propose a number of open problems.

A code Dover Z2nis called a quasi-perfect Lee distance-(2t+ 1) code if dL(V,W) ≥ 2t+ 1 for every two code words V,Win D, and every word in Z2nis at distance  ≤  t+ 1 from at least one code word, where DL(V,W) is the Lee distance of Vand W. In this paper we present a fast decoding algorithm for quasi-perfect Lee codes. The basic idea of the algorithm comes from a geometric representation of Din the 2-dimensional plane. It turns out that to decode a word it suffices to calculate its distance to at most four code words.A code Dover Z2nis called a quasi-perfect Lee distance-(2t+ 1) code if dL(V,W) ≥ 2t+ 1 for every two code words V,Win D, and every word in Z2nis at distance  ≤  t+ 1 from at least one code word, where DL(V,W) is the Lee distance of Vand W. In this paper we present a fast decoding algorithm for quasi-perfect Lee codes. The basic idea of the algorithm comes from a geometric representation of Din the 2-dimensional plane. It turns out that to decode a word it suffices to calculate its distance to at most four code words.

Let G: = G(1,n,q) denote the Grassmannian of lines in PG(n,q), embedded as a point-set in PG(N, q) with $$N:=\binom{n+1}{2}-1.$$For n= 2 or 3 the characteristic function $$\chi (\overline{G})$$of the complement of Gis contained in the linear code generated by characteristic functions of complements of n-flats in PG(N, q). In this paper we prove this to be true for all cases (n, q) with q= 2 and we conjecture this to be true for all remaining cases (n, q). We show that the exact polynomial degree of $$ \chi (\overline{G})$$is $$(q-1)(\binom{n}{2}-1+\delta )$$for δ: = δ(n, q) = 0 or 1, and that the possibility δ = 1 is ruled out if the above conjecture is true. The result deg($$\chi (\overline{G}))= \binom{n}{2}-1$$for the binary cases (n,2) can be used to construct quantum codes by intersecting Gwith subspaces of dimension at least $$\binom{n}{2}.$$Let G: = G(1,n,q) denote the Grassmannian of lines in PG(n,q), embedded as a point-set in PG(N, q) with $$N:=\binom{n+1}{2}-1.$$For n= 2 or 3 the characteristic function $$\chi (\overline{G})$$of the complement of Gis contained in the linear code generated by characteristic functions of complements of n-flats in PG(N, q). In this paper we prove this to be true for all cases (n, q) with q= 2 and we conjecture this to be true for all remaining cases (n, q). We show that the exact polynomial degree of $$ \chi (\overline{G})$$is $$(q-1)(\binom{n}{2}-1+\delta )$$for δ: = δ(n, q) = 0 or 1, and that the possibility δ = 1 is ruled out if the above conjecture is true. The result deg($$\chi (\overline{G}))= \binom{n}{2}-1$$for the binary cases (n,2) can be used to construct quantum codes by intersecting Gwith subspaces of dimension at least $$\binom{n}{2}.$$

Combinatorial characterization of optimal authentication codes with arbitration was previously given by several groups of researchers in terms of affine α-resolvable  +  BIBDs and α-resolvable designs with some special properties, respectively. In this paper, we revisit this known characterization and restate it using a new idea of GOB designs. This newly introduced combinatorial structure simplifies the characterization, and enables us to extend Johansson’s well-known family of optimal authentication codes with arbitration to any finite projective spaces with dimension greater than or equal to 3.Combinatorial characterization of optimal authentication codes with arbitration was previously given by several groups of researchers in terms of affine α-resolvable  +  BIBDs and α-resolvable designs with some special properties, respectively. In this paper, we revisit this known characterization and restate it using a new idea of GOB designs. This newly introduced combinatorial structure simplifies the characterization, and enables us to extend Johansson’s well-known family of optimal authentication codes with arbitration to any finite projective spaces with dimension greater than or equal to 3.

The side class structure of a perfect 1-error correcting binary code (hereafter referred to as a perfect code) Cdescribes the linear relations between the coset representatives of the kernel of C. Two perfect codes Cand C′ are linearly equivalent if there exists a non-singular matrix Asuch that AC= C′ where Cand C′ are matrices with the code words of Cand C′ as columns. Hessler proved that the perfect codes Cand C′ are linearly equivalent if and only if they have isomorphic side class structures. The aim of this paper is to describe all side class structures. It is shown that the transpose of any side class structure is the dual of a subspace of the kernel of some perfect code and vice versa; any dual of a subspace of a kernel of some perfect code is the transpose of the side class structure of some perfect code. The conclusion is that for classification purposes of perfect codes it is sufficient to find the family of all kernels of perfect codes.The side class structure of a perfect 1-error correcting binary code (hereafter referred to as a perfect code) Cdescribes the linear relations between the coset representatives of the kernel of C. Two perfect codes Cand C′ are linearly equivalent if there exists a non-singular matrix Asuch that AC= C′ where Cand C′ are matrices with the code words of Cand C′ as columns. Hessler proved that the perfect codes Cand C′ are linearly equivalent if and only if they have isomorphic side class structures. The aim of this paper is to describe all side class structures. It is shown that the transpose of any side class structure is the dual of a subspace of the kernel of some perfect code and vice versa; any dual of a subspace of a kernel of some perfect code is the transpose of the side class structure of some perfect code. The conclusion is that for classification purposes of perfect codes it is sufficient to find the family of all kernels of perfect codes.

In (2,n) visual cryptographic schemes, a secret image(text or picture) is encrypted into nshares, which are distributed among nparticipants. The image cannot be decoded from any single share but any two participants can together decode it visually, without using any complex decoding mechanism. In this paper, we introduce three meaningful optimality criteria for evaluating different schemes and show that some classes of combinatorial designs, such as BIB designs, PBIB designs and regular graph designs, can yield a large number of black and white (2,n) schemes that are optimal with respect to all these criteria. For a practically useful range of n, we also obtain optimal schemes with the smallest possible pixel expansion.In (2,n) visual cryptographic schemes, a secret image(text or picture) is encrypted into nshares, which are distributed among nparticipants. The image cannot be decoded from any single share but any two participants can together decode it visually, without using any complex decoding mechanism. In this paper, we introduce three meaningful optimality criteria for evaluating different schemes and show that some classes of combinatorial designs, such as BIB designs, PBIB designs and regular graph designs, can yield a large number of black and white (2,n) schemes that are optimal with respect to all these criteria. For a practically useful range of n, we also obtain optimal schemes with the smallest possible pixel expansion.

External difference families (EDFs) are a type of new combinatorial designs originated from cryptography. In this paper, some earlier ideas of recursive and cyclotomic constructions of combinatorial designs are extended, and a number of classes of EDFs and disjoint difference families are presented. A link between a subclass of EDFs and a special type of (almost) difference sets is set up.External difference families (EDFs) are a type of new combinatorial designs originated from cryptography. In this paper, some earlier ideas of recursive and cyclotomic constructions of combinatorial designs are extended, and a number of classes of EDFs and disjoint difference families are presented. A link between a subclass of EDFs and a special type of (almost) difference sets is set up.

The basic necessary conditions for the existence of a (v, k, λ)-perfect Mendelsohn design (briefly (v, k, λ)-PMD) are v≥ kand λ v(v− 1) ≡ 0 (mod k). These conditions are known to be sufficient in most cases, but certainly not in all. For k= 3, 4, 5, 7, very extensive investigations of (v, k, λ)-PMDs have resulted in some fairly conclusive results. However, for k= 6 the results have been far from conclusive, especially for the case of λ = 1, which was given some attention in papers by Miao and Zhu [34], and subsequently by Abel et al. [1]. Here we investigate the situation for k= 6 and λ > 1. We find that the necessary conditions, namely v≥ 6 and λ v(v− 1)≡0 (mod 6) are sufficient except for the known impossible cases v= 6 and either λ = 2 or λ odd.The basic necessary conditions for the existence of a (v, k, λ)-perfect Mendelsohn design (briefly (v, k, λ)-PMD) are v≥ kand λ v(v− 1) ≡ 0 (mod k). These conditions are known to be sufficient in most cases, but certainly not in all. For k= 3, 4, 5, 7, very extensive investigations of (v, k, λ)-PMDs have resulted in some fairly conclusive results. However, for k= 6 the results have been far from conclusive, especially for the case of λ = 1, which was given some attention in papers by Miao and Zhu [34], and subsequently by Abel et al. [1]. Here we investigate the situation for k= 6 and λ > 1. We find that the necessary conditions, namely v≥ 6 and λ v(v− 1)≡0 (mod 6) are sufficient except for the known impossible cases v= 6 and either λ = 2 or λ odd.

An (n, d, k)-mapping fis a mapping from binary vectors of length nto permutations of length n+ ksuch that for all x, y$$\in$${0,1}n, dH(f(x), f(y)) ≥  dH(x, y) + d, if dH(x, y) ≤  (n+ k) − dand dH(f(x), f(y))  =  n+ k, if dH(x, y) > (n+ k) − d. In this paper, we construct an (n,3,2)-mapping for any positive integer n≥  6. An (n, r)-permutation array is a permutation array of length nand any two permutations of which have Hamming distance at least r. Let P(n, r) denote the maximum size of an (n, r)-permutation array and A(n, r) denote the same setting for binary codes. Applying (n,3,2)-mappings to the design of permutation array, we can construct an efficient permutation array (easy to encode and decode) with better code rate than previous results [Chang (2005). IEEE Trans inf theory 51:359–365, Chang et al. (2003). IEEE Trans Inf Theory 49:1054–1059; Huang et al. (submitted)]. More precisely, we obtain that, for n≥  8, P(n, r) ≥  A(n− 2, r− 3) > A(n− 1,r− 2) = A(n, r− 1) when nis even and P(n, r) ≥  A(n− 2, r− 3) = A(n− 1, r− 2) > A(n, r− 1) when nis odd. This improves the best bound A(n− 1,r− 2) so far [Huang et al. (submitted)] for n≥  8.An (n, d, k)-mapping fis a mapping from binary vectors of length nto permutations of length n+ ksuch that for all x, y$$\in$${0,1}n, dH(f(x), f(y)) ≥  dH(x, y) + d, if dH(x, y) ≤  (n+ k) − dand dH(f(x), f(y))  =  n+ k, if dH(x, y) > (n+ k) − d. In this paper, we construct an (n,3,2)-mapping for any positive integer n≥  6. An (n, r)-permutation array is a permutation array of length nand any two permutations of which have Hamming distance at least r. Let P(n, r) denote the maximum size of an (n, r)-permutation array and A(n, r) denote the same setting for binary codes. Applying (n,3,2)-mappings to the design of permutation array, we can construct an efficient permutation array (easy to encode and decode) with better code rate than previous results [Chang (2005). IEEE Trans inf theory 51:359–365, Chang et al. (2003). IEEE Trans Inf Theory 49:1054–1059; Huang et al. (submitted)]. More precisely, we obtain that, for n≥  8, P(n, r) ≥  A(n− 2, r− 3) > A(n− 1,r− 2) = A(n, r− 1) when nis even and P(n, r) ≥  A(n− 2, r− 3) = A(n− 1, r− 2) > A(n, r− 1) when nis odd. This improves the best bound A(n− 1,r− 2) so far [Huang et al. (submitted)] for n≥  8.

In this paper, a construction of optimal constant composition codes is developed, and used to derive some series of new optimal constant composition codes meeting the upper bound given by [13].In this paper, a construction of optimal constant composition codes is developed, and used to derive some series of new optimal constant composition codes meeting the upper bound given by [13].

Decoding errors can be seen from the point of view of the receiver or the transmitter. This naturally leads to different functions for the decoding error probability. We study their behaviour and the relation between these two functions. Though both functions are equally good when used to compare two codes with respect to decoding errors only one of them reflects in general the properties such a function should have. This is not the function one usually considers in the literature when studying decoding errors. Both functions coincide only if the underlying code is perfect. The investigations in this paper can be seen as a continuation of earlier work of MacWilliams (see chap. 16.1 in [2]).Decoding errors can be seen from the point of view of the receiver or the transmitter. This naturally leads to different functions for the decoding error probability. We study their behaviour and the relation between these two functions. Though both functions are equally good when used to compare two codes with respect to decoding errors only one of them reflects in general the properties such a function should have. This is not the function one usually considers in the literature when studying decoding errors. Both functions coincide only if the underlying code is perfect. The investigations in this paper can be seen as a continuation of earlier work of MacWilliams (see chap. 16.1 in [2]).

Cumulative arrays have played an important role in the early development of the secret sharing theory. They have not been subject to extensive study so far, as the secret sharing schemes built on them generally result in much larger sizes of shares, when compared with other conventional approaches. Recent works in threshold cryptography show that cumulative arrays may be the appropriate building blocks in non-homomorphic threshold cryptosystems where the conventional secret sharing methods are generally of no use. In this paper we study several extensions of cumulative arrays and show that some of these extensions significantly improve the performance of conventional cumulative arrays. In particular, we derive bounds on generalised cumulative arrays and show that the constructions based on perfect hash families are asymptotically optimal. We also introduce the concept of ramp perfect hash families as a generalisation of perfect hash families for the study of ramp secret sharing schemes and ramp cumulative arrays.Cumulative arrays have played an important role in the early development of the secret sharing theory. They have not been subject to extensive study so far, as the secret sharing schemes built on them generally result in much larger sizes of shares, when compared with other conventional approaches. Recent works in threshold cryptography show that cumulative arrays may be the appropriate building blocks in non-homomorphic threshold cryptosystems where the conventional secret sharing methods are generally of no use. In this paper we study several extensions of cumulative arrays and show that some of these extensions significantly improve the performance of conventional cumulative arrays. In particular, we derive bounds on generalised cumulative arrays and show that the constructions based on perfect hash families are asymptotically optimal. We also introduce the concept of ramp perfect hash families as a generalisation of perfect hash families for the study of ramp secret sharing schemes and ramp cumulative arrays.

This is a continuation of the previous papers [3, 4, 5]. We finish determining the minimum distance of two-point codes on a Hermitian curve.This is a continuation of the previous papers [3, 4, 5]. We finish determining the minimum distance of two-point codes on a Hermitian curve.

So far there is no systematic attempt to construct Boolean functions with maximum annihilator immunity. In this paper we present a construction keeping in mind the basic theory of annihilator immunity. This construction provides functions with the maximum possible annihilator immunity and the weight, nonlinearity and algebraic degree of the functions can be properly calculated under certain cases. The basic construction is that of symmetric Boolean functions and applying linear transformation on the input variables of these functions, one can get a large class of non-symmetric functions too. Moreover, we also study several other modifications on the basic symmetric functions to identify interesting non-symmetric functions with maximum annihilator immunity. In the process we also present an algorithm to compute the Walsh spectra of a symmetric Boolean function with O(n2) time and O(n) space complexity.So far there is no systematic attempt to construct Boolean functions with maximum annihilator immunity. In this paper we present a construction keeping in mind the basic theory of annihilator immunity. This construction provides functions with the maximum possible annihilator immunity and the weight, nonlinearity and algebraic degree of the functions can be properly calculated under certain cases. The basic construction is that of symmetric Boolean functions and applying linear transformation on the input variables of these functions, one can get a large class of non-symmetric functions too. Moreover, we also study several other modifications on the basic symmetric functions to identify interesting non-symmetric functions with maximum annihilator immunity. In the process we also present an algorithm to compute the Walsh spectra of a symmetric Boolean function with O(n2) time and O(n) space complexity.

In 1779 Euler proved that for every even nthere exists a latin square of order nthat has no orthogonal mate, and in 1944 Mann proved that for every nof the form 4k+ 1, k≥ 1, there exists a latin square of order nthat has no orthogonal mate. Except for the two smallest cases, n= 3 and n= 7, it is not known whether a latin square of order n= 4k+ 3 with no orthogonal mate exists or not. We complete the determination of all nfor which there exists a mate-less latin square of order nby proving that, with the exception of n= 3, for all n= 4k+ 3 there exists a latin square of order nwith no orthogonal mate. We will also show how the methods used in this paper can be applied more generally by deriving several earlier non-orthogonality results.In 1779 Euler proved that for every even nthere exists a latin square of order nthat has no orthogonal mate, and in 1944 Mann proved that for every nof the form 4k+ 1, k≥ 1, there exists a latin square of order nthat has no orthogonal mate. Except for the two smallest cases, n= 3 and n= 7, it is not known whether a latin square of order n= 4k+ 3 with no orthogonal mate exists or not. We complete the determination of all nfor which there exists a mate-less latin square of order nby proving that, with the exception of n= 3, for all n= 4k+ 3 there exists a latin square of order nwith no orthogonal mate. We will also show how the methods used in this paper can be applied more generally by deriving several earlier non-orthogonality results.

In this paper we consider the (t, n)-threshold visual secret sharing scheme (VSSS) in which black pixels in a secret black-white images is reproduced perfectly as black pixels when we stack arbitrary tshares. This paper provides a new characterization of the (t, n)-threshold visual secret sharing scheme with such a property (hereafter, we call such a VSSS the (t, n)-PBVSSS for short). We use an algebraic method to characterize basis matrices of the (t, n)-PBVSSS in a certain class of matrices. We show that the set of all homogeneous polynomials each element of which yields basis matrices of the (t, n)-PBVSSS becomes a set of lattice points in an (n−t+1)-dimensional linear space. In addition, we prove that the optimal basis matrices in the sense of maximizing the relative difference among all the basis matrices in the class coincides with the basis matrices given by Blundo, Bonis and De Santis [3] for all n≥ t≥ 2.In this paper we consider the (t, n)-threshold visual secret sharing scheme (VSSS) in which black pixels in a secret black-white images is reproduced perfectly as black pixels when we stack arbitrary tshares. This paper provides a new characterization of the (t, n)-threshold visual secret sharing scheme with such a property (hereafter, we call such a VSSS the (t, n)-PBVSSS for short). We use an algebraic method to characterize basis matrices of the (t, n)-PBVSSS in a certain class of matrices. We show that the set of all homogeneous polynomials each element of which yields basis matrices of the (t, n)-PBVSSS becomes a set of lattice points in an (n−t+1)-dimensional linear space. In addition, we prove that the optimal basis matrices in the sense of maximizing the relative difference among all the basis matrices in the class coincides with the basis matrices given by Blundo, Bonis and De Santis [3] for all n≥ t≥ 2.

Boolean functions on the space $$\mathbb{F}_{2}^{m}$$are not only important in the theory of error-correcting codes, but also in cryptography. In these two cases, the nonlinearity of these functions is a main concept. Carlet, Olejár and Stanek gave an asymptotic lower bound for the nonlinearity of most of them, and I gave an asymptotic upper bound which was strictly larger. In this article, I improve the bounds and get an exact limit for the nonlinearity of most of Boolean functions. This article is inspired by a paper of G. Halász about the related problem of real polynomials with random coefficients.Boolean functions on the space $$\mathbb{F}_{2}^{m}$$are not only important in the theory of error-correcting codes, but also in cryptography. In these two cases, the nonlinearity of these functions is a main concept. Carlet, Olejár and Stanek gave an asymptotic lower bound for the nonlinearity of most of them, and I gave an asymptotic upper bound which was strictly larger. In this article, I improve the bounds and get an exact limit for the nonlinearity of most of Boolean functions. This article is inspired by a paper of G. Halász about the related problem of real polynomials with random coefficients.

In Homma M and Kim SJ [2], the authors considered two-point codes on a Hermitian curve defined over fields of odd characteristic. In this paper, we study the geometry of a Hermitian curve over fields of even characteristic and classify the two-point codes whose minimum distances agree with the designed ones.In Homma M and Kim SJ [2], the authors considered two-point codes on a Hermitian curve defined over fields of odd characteristic. In this paper, we study the geometry of a Hermitian curve over fields of even characteristic and classify the two-point codes whose minimum distances agree with the designed ones.

Mappings from the set of binary vectors of a fixed length to the set of permutations of the same length that strictly increase Hamming distances are useful for the construction of permutation codes (permutation arrays). In this paper, we propose new simpler algorithms of distance-increasing mappings. These algorithms do not need any table lookup operations, and they are built up with fewer swap perations. In the comparison of our new algorithms with other DIMs, we also give some numerical results to illustrate that the distance expansion distributions of our new mappings are not bad.Mappings from the set of binary vectors of a fixed length to the set of permutations of the same length that strictly increase Hamming distances are useful for the construction of permutation codes (permutation arrays). In this paper, we propose new simpler algorithms of distance-increasing mappings. These algorithms do not need any table lookup operations, and they are built up with fewer swap perations. In the comparison of our new algorithms with other DIMs, we also give some numerical results to illustrate that the distance expansion distributions of our new mappings are not bad.

In this paper we classify point sets of minimum size of two types (1) point sets meeting all secants to an irreducible conic $${\cal C}$$of the desarguesian projective plane PG(2,q), qodd; (2) point sets meeting all external lines and tangents to a given irreducible conic $${\cal C}$$of the desarguesian projective plane PG(2,q), qeven.In this paper we classify point sets of minimum size of two types (1) point sets meeting all secants to an irreducible conic $${\cal C}$$of the desarguesian projective plane PG(2,q), qodd; (2) point sets meeting all external lines and tangents to a given irreducible conic $${\cal C}$$of the desarguesian projective plane PG(2,q), qeven.

Recently, Eisenträger et al. proposed a very elegant method for speeding up scalar multiplication on elliptic curves. Their method relies on improved formulas for evaluating S=(2P+ Q) from given points Pand Qon an elliptic curve. Compared to the naive approach, the improved formulas save a field multiplication each time the operation is performed. This paper proposes a variant which is faster whenever a field inversion is more expensive than six field multiplications. We also give an improvement when tripling a point, and present a ternary/binary method to perform efficient scalar multiplication.Recently, Eisenträger et al. proposed a very elegant method for speeding up scalar multiplication on elliptic curves. Their method relies on improved formulas for evaluating S=(2P+ Q) from given points Pand Qon an elliptic curve. Compared to the naive approach, the improved formulas save a field multiplication each time the operation is performed. This paper proposes a variant which is faster whenever a field inversion is more expensive than six field multiplications. We also give an improvement when tripling a point, and present a ternary/binary method to perform efficient scalar multiplication.

In this paper, we describe authentication codes via (generalized) Gray images of suitable codes over Galois rings. Exponential sums over these rings help determine—or bound—the parameters of such codes.In this paper, we describe authentication codes via (generalized) Gray images of suitable codes over Galois rings. Exponential sums over these rings help determine—or bound—the parameters of such codes.

Baker et al. [2] show, via algebraic methods, that a regular hyperbolic fibration of PG(3, q) with constant back half gives rise to a flock of a quadratic cone in PG(3, q), and conversely. In this paper a geometric construction for qeven of the flock from the hyperbolic fibration, and conversely, will be described. A proof will be given that this geometric construction indeed corresponds to the known algebraic one.Baker et al. [2] show, via algebraic methods, that a regular hyperbolic fibration of PG(3, q) with constant back half gives rise to a flock of a quadratic cone in PG(3, q), and conversely. In this paper a geometric construction for qeven of the flock from the hyperbolic fibration, and conversely, will be described. A proof will be given that this geometric construction indeed corresponds to the known algebraic one.

In this paper we are dealing with the security of the Feistel structure in the Luby–Rackoff model when the round functions are replaced by permutations. There is a priorino reason to think that the security bounds remain the same in this case, as illustrated by Knudsen’s attack [5]. It is why we revisit Luby–Rackoff’s proofs [6] in this specific case. The conclusion is that when the inner functions are random permutations, a 3-round (resp. 4-round) Feistel scheme remains secure against pseudorandom (resp. superpseudorandom) distinguishers as long as m2n/2(with mthe number of queries and 2nthe block size).In this paper we are dealing with the security of the Feistel structure in the Luby–Rackoff model when the round functions are replaced by permutations. There is a priorino reason to think that the security bounds remain the same in this case, as illustrated by Knudsen’s attack [5]. It is why we revisit Luby–Rackoff’s proofs [6] in this specific case. The conclusion is that when the inner functions are random permutations, a 3-round (resp. 4-round) Feistel scheme remains secure against pseudorandom (resp. superpseudorandom) distinguishers as long as m2n/2(with mthe number of queries and 2nthe block size).

Abstract: A multi-secret sharing scheme is a protocol to share more than one secret among a set of participants, where each secret may have a distinct family of subsets of participants (also called ‘access structure’) that are qualified to recover it. In this paper we use an information-theoretic approach to analyze two different models for multi-secret sharing schemes. The proposed models generalize specific models which have already been considered in the literature. We first analyze the relationships between the security properties of the two models. Afterwards, we show that the security property of a multi-secret sharing scheme does not depend on the particular probability distribution on the sets of secrets. This extends the analogous result for the case of single-secret sharing schemes and implies that the bounds on the size of the information distributed to participants in multi-secret sharing schemes can all be strengthened. For each of the two models considered in this paper, we show lower bounds on the size of the shares distributed to participants. Specifically, for the general case in which the secrets are shared according to a tuple of arbitrary (and possibly different) access structures, we show a combinatorial condition on these structures that is sufficient to require a participant to hold information of size larger than a certain subset of secrets. For specific access structures of particular interest, namely, when all access structures are threshold structures, we show tight bounds on the size of the information distributed to participants.

Abstract: Emerging standards specify a communication rate between a contactless smartcard and a terminal that is of the same order of magnitude as the internal clock rate in the card. This gives a natural ground for the known card-terminal communication-computation trade-off, where non-secure operations should rather be performed by the terminal and not in the card. In this paper we treat an implementation of Elliptic Curve Digital Signature Algorithm (ECDSA), the most cost effective digital signature algorithm, which has a potential of being executed under the heavy constraints imposed by a contactless smartcard environment. This algorithm heavily relies on numerous calculations of modular multiplicative inverses. It is shown in this paper that, based on communicating with the terminal, each modular inverse operation needed to be executed in the card during ECDSA signature generation requires only two modular multiplications in the card. Each modular inverse operation performed during signature verification requires only one modular multiplication in the card. A complete ECDSA implementation over integers or over GF(2n) is then treated in detail

Abstract In this paper we initiate the study of hybrid slim near hexagons. These are near hexagons which are not dense and not a generalized hexagon in which each line is incident with exactly three points. In the present paper, we will emphasize slim near hexagons with at least one W(2)-quad or Q(5, 2)-quad. Such near hexagons are finite if there are no special points, i.e. points which lie at distance at most 2 from any other point. We will determine upper bounds for the number of lines through a fixed point. We will also look at the special case where the near hexagon has an order. We will determine all slim near hexagons with an order which contain at least one (necessarily big) Q(5,2)-quad, or at least one big W(2)-quad.

Abstract In this paper, we continue our investigation on “Extremal problems under dimension constraints” introduced [1]. The general problem we deal with in this paper can be formulated as follows. Let be an affine plane of dimension k in . Given determine or estimate .

Abstract Let V be a list of all vectors of GF(q)n, lexicographically ordered with respect to some basis. Algorithms which search list V from top to bottom, any time selecting a codeword which satisfies some criterion, are called greedy algorithms and the resulting set of codewords is called a lexicode. In many cases such a lexicode turns out to be linear. In this paper we present a greedy algorithm for the construction of a large class of linear q-ary lexicodes which generalizes the algorithms of several other papers and puts these into a wider framework. By applying this new method, one can produce linear lexicodes which cannot be constructed by previous algorithms, because the characteristics or the underlying field of the codes do not meet the conditions of those algorithms.

Let Vbe a finite set of velements. A packing of the pairs of Vby k-subsets is a family Fof k-subsets of V, called blocks, such that each pair in Voccurs in at most one member of F. For fixed vand k, the packing problem is to determine the number of blocks in any maximum packing. A maximum packing is resolvable if we can partition the blocks into classes (called parallel classes) such that every element is contained in precisely one block of each class. A resolvable maximum packing of the pairs of Vby k-subsets is denoted by RP(v,k). It is well known that an RP(v,4) is equivalent to a resolvable group divisible design (RGDD) with block 4 and group size h, where h=1,2 or 3. The existence of 4-RGDDs with group-type hnfor h=1 or 3 has been solved except for (h,n)=(3,4) (for which no such design exists) and possibly for (h,n)∈{(3,88),(3,124)}. In this paper, we first complete the case for h=3 by direct constructions. Then, we start the investigation for the existence of 4-RGDDs of type 2n. We shall show that the necessary conditions for the existence of a 4-RGDD of type 2n, namely, n≥ 4 and n≡ 4 (mod 6) are also sufficient with 2 definite exceptions (n=4,10) and 18 possible exceptions with n=346 being the largest. As a consequence, we have proved that there exists an RP(v,4) for v≡ 0 (mod 4) with 3 exceptions (v=8,12 or 20) and 18 possible exceptions.Let Vbe a finite set of velements. A packing of the pairs of Vby k-subsets is a family Fof k-subsets of V, called blocks, such that each pair in Voccurs in at most one member of F. For fixed vand k, the packing problem is to determine the number of blocks in any maximum packing. A maximum packing is resolvable if we can partition the blocks into classes (called parallel classes) such that every element is contained in precisely one block of each class. A resolvable maximum packing of the pairs of Vby k-subsets is denoted by RP(v,k). It is well known that an RP(v,4) is equivalent to a resolvable group divisible design (RGDD) with block 4 and group size h, where h=1,2 or 3. The existence of 4-RGDDs with group-type hnfor h=1 or 3 has been solved except for (h,n)=(3,4) (for which no such design exists) and possibly for (h,n)∈{(3,88),(3,124)}. In this paper, we first complete the case for h=3 by direct constructions. Then, we start the investigation for the existence of 4-RGDDs of type 2n. We shall show that the necessary conditions for the existence of a 4-RGDD of type 2n, namely, n≥ 4 and n≡ 4 (mod 6) are also sufficient with 2 definite exceptions (n=4,10) and 18 possible exceptions with n=346 being the largest. As a consequence, we have proved that there exists an RP(v,4) for v≡ 0 (mod 4) with 3 exceptions (v=8,12 or 20) and 18 possible exceptions.

A ν-player whist tournament is a schedule of games, where in each round the ν players are partitioned into games of four players each with at most one player left over. In each game two of the players play as partners against the other two. All pairs of players must play in the same game exactly three times during the tournament; of those three times, they are to play as partners exactly once. Whist tournaments for ν players are known to exist for all ν ≡ 0,1 (mod 4). The special cases of directed whist tournaments and triplewhist tournaments are known to exist for all sufficiently large ν, but for small ν several open cases remain. In this paper we introduce a correspondence between near resolvable 2-(ν, k, λ designs and a particular class of codes. The near resolvable 2-(13, 4, 3) designs are classified by classifying the corresponding codes with an orderly algorithm. Finally, the thirteen-player whist tournaments are enumerated starting from the near resolvable 2-(13, 4, 3) designs.A ν-player whist tournament is a schedule of games, where in each round the ν players are partitioned into games of four players each with at most one player left over. In each game two of the players play as partners against the other two. All pairs of players must play in the same game exactly three times during the tournament; of those three times, they are to play as partners exactly once. Whist tournaments for ν players are known to exist for all ν ≡ 0,1 (mod 4). The special cases of directed whist tournaments and triplewhist tournaments are known to exist for all sufficiently large ν, but for small ν several open cases remain. In this paper we introduce a correspondence between near resolvable 2-(ν, k, λ designs and a particular class of codes. The near resolvable 2-(13, 4, 3) designs are classified by classifying the corresponding codes with an orderly algorithm. Finally, the thirteen-player whist tournaments are enumerated starting from the near resolvable 2-(13, 4, 3) designs.

In this paper, we describe a solution to the register synthesis problem for a class of sequence generators known as algebraic feedback shift registers (AFSRs). These registers are based on the algebra of π-adic numbers, where π is an element in a ring R, and produce sequences of elements in R/(π). We give several cases where the register synthesis problem can be solved by an efficient algorithm. Consequently, any keystreams over R/(π) used in stream ciphers must be unable to be generated by a small register in these classes. This paper extends the analyses of feedback with carry shift registers and algebraic feedback shift registers by Goresky, Klapper, and Xu.

The Assmus–Mattson theorem is known as a method to find designs in linear codes over a finite field. It is an interesting problem to find an analog of the theorem for Z4-codes. In a previous paper, the author gave a candidate of the theorem. The purpose of this paper is to give an improvement of the theorem. It is known that the lifted Golay code over Z4contains 5-designs on Lee compositions. The improved method can find some of those without computational difficulty and without the help of a computer.

In this paper we continue our investigation on “Extremal problems under dimension constraint” introduced in [2]. Let E(n, k) be the set of (0,1)-vectors in ℝnwith kone's. Given 1 ≤ m, w≤ nlet X⊂ E(n, m) satisfy span (X) ∩ E(n, w) = ⊘. How big can |X| be? This is the main problem studied in this paper. We solve this problem for all parameters 1 ≤ m, w≤ nand n> n0(m, w).

There have been several recent constructions of partial difference sets (PDSs) using the Galois rings $GR(p^2,\; t)$ for $p$ a prime and $t$ any positive integer. This paper presents constructions of partial difference sets in $(Z\_\{p^r\})^\{2t\}$ where $p$ is any prime, and $r$ and $t$ are any positive integers. For the case where $r\; >\; 2$ many of the partial difference sets are constructed in groups with parameters distinct from other known constructions, and the PDSs are nested. Another construction of Paley partial difference sets is given for the case when $p$ is odd. The constructions make use of character theory and of the structure of the Galois ring $GR(p^r,\; t)$, and in particular, the ring $GR(p^r,\; t)\; \backslash times\; GR(p^r,\; t)$. The paper concludes with some open related problems.

Recently, and contrary to the common belief, Rivest and Silverman argued that the use of strong primes is unnecessary in the RSA cryptosystem. This paper analyzes how valid this assertion is for RSA-type cryptosystems over elliptic curves. The analysis is more difficult because the underlying groups are not always cyclic. Previous papers suggested the use of strong primes in order to prevent factoring attacks and cycling attacks. In this paper, we only focus on cycling attacks because for both RSA and its elliptic curve-based analogues, the length of the RSA-modulus nis typically the same. Therefore, a factoring attack will succeed with equal probability against all RSA-type cryptosystems. We also prove that cycling attacks reduce to find fixed points, and derive a factorization algorithm which (most probably) completely breaks RSA-type systems over elliptic curves if a fixed point is found.

The 1976 seminal paper of Diffie and Hellman is a landmark in the history of cryptography. They introduced the fundamental concepts of a trapdoor one-way function, a public-key cryptosystem, and a digital signature scheme. Moreover, they presented a protocol, the so-called Diffie–Hellman protocol, allowing two parties who share no secret information initially, to generate a mutual secret key. This paper summarizes the present knowledge on the security of this protocol.

In an earlier paper 7, some properties of the eigenspaces of the Bose-Mesner-algebras of association schemes are figured out, leaving open the problem of determining the eigenspaces. In the present paper, these eigenspaces and the eigenvalues are determined for projective spaces and for polar spaces. This allows characterizations of certain sets of subspaces of these geometries.