Some New Results on Key Distribution Patterns and Broadcast Encryption

This paper concerns methods by which a trusted authority can distribute keys and/or broadcast a message over a network, so that each member of a privileged subset of users can compute a specified key or decrypt the broadcast message. Moreover, this is done in such a way that no coalition is able to recover any information on a key or broadcast message they are not supposed to know. The problems are studied using the tools of information theory, so the security provided is unconditional (i.e., not based on any computational assumption).In a recent paper st95a, Stinson described a method of constructing key predistribution schemes by combining Mitchell-Piper key distribution patterns with resilient functions; and also presented a construction method for broadcast encryption schemes that combines Fiat-Naor key predistribution schemes with ideal secret sharing schemes. In this paper, we further pursue these two themes, providing several nice applications of these techniques by using combinatorial structures such as orthogonal arrays, perpendicular arrays, Steiner systems and universal hash families.     

Combinatorial Characterizations of Authentication Codes II

For any authentication code for k source states and v messages having minimum possible deception probabilities (namely, % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9qq-f0-yqaqVeLsFr0-vr% 0-vr0db8meaabaqaciGacaGaaeqabaWaaeaaeaaakeaacaWGqbWaaS% baaSqaaiaadsgaaeqaaOWaaSbaaSqaaiaaicdaaeqaaOGaeyypa0Za% aSGbaeaacaWGRbaabaGaamODaaaaaaa!3F28!\[P_d _0 = {k \mathord{\left/ {\vphantom {k v}} \right. \kern-\nulldelimiterspace} v}\] and % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9qq-f0-yqaqVeLsFr0-vr% 0-vr0db8meaabaqaciGacaGaaeqabaWaaeaaeaaakeaacaWGqbWaaS% baaSqaaiaadsgaaeqaaOWaaSbaaSqaaiaaigdaaeqaaOGaeyypa0Ze% xLMBb50ujbqeguuDJXwAKbacfaGae8hkaGIaam4AaiabgkHiTiaaig% dacqWFPaqkcqWFVaWlcqWFOaakcqWF2bGDcqGHsislcaaIXaGae8xk% aKIae8xkaKcaaa!4CD1!\[P_d _1 = (k - 1)/(v - 1))\], we show that there must be at least v encoding rules. (This can be thought of as an authentication-code analogue of Fisher's Inequality.) We derive several properties that an extremal code must satisfy, and we characterize the extremal codes for equiprobable source states as arising from symmetric balanced incomplete block designs. We also present an infinite class of extremal codes, in which the source states are not equiprobable, derived from affine planes.Dedicated to Gus Simmons     

On the existence of MOLS with equal-sized holes

We consider a pair of MOLS (mutually orthogonal Latin squares) having holes, corresponding to missing sub-MOLS, which are disjoint and spanning It is shown that a pair of MOLS withn holes of sizeh exist forh 2 if and only ifn 4 For SOLS (self-orthogonal Latin squares) with holes, we have the same result, with two possible exceptions SOLS with 7 or 13 holes of size 6     

On resolvable Golomb rulers,symmetric configurations and progressive dinner parties

Journal of Algebraic Combinatorics - We define a new type of Golomb ruler, which we term a resolvable Golomb ruler. These are Golomb rulers that satisfy an additional “resolvability”...     

Combinatorial characterizations of authentication codes

In this paper, we prove two new combinatorial characterizations of authentication codes. Authentication codes without secrecy are characterized in terms of orthogonal arrays; and general authentication codes are characterized in terms of balanced incomplete block designs. In both of these characterizations, it turns out that encoding rules must be equiprobable; in the second characteriztion, the source states must also be equiprobable.A preliminary version of this paper appeared in Advances in Cryptology—CRYPTO '91 Proceedings Lecture Notes in Computer Science 576 (1992) 62–73, Springer-Verlag.Research supported by NSERC grant A9287.     

Threshold Visual Cryptography Schemes with Specified Whiteness Levels of Reconstructed Pixels

In 1994, Naor and Shamir introduced an unconditionally secure method for encoding black and white images. This method, known as a threshold visual cryptography scheme (VCS), has the benefit of requiring no cryptographic computation on the part of the decoders. In a -VCS, a share, in the form of a transparency, is given to ">n users. Any ">k users can recover the secret simply by stacking transparencies, but ">k-1 users can gain no information about the secret whatsoever.In this paper, we first explore the issue of contrast, by demonstrating that the current definitions are inadequate, and by providing an alternative definition. This new definition motivates an examination of minimizing pixel expansion subject to fixing the VCS parameters ">h and ">l. New bounds on pixel expansion are introduced, and connections between these bounds are examined. The best bound presented is tighter than any previous bound. An analysis of connections between (2, ">n) schemes and designs such as BIBD's, PBD's, and (">r, )-designs is performed. Also, an integer linear program is provided whose solution exactly determines the minimum pixel expansion of a (2, ">n)-VCS with specified ">h and >l.     

Comparison of an analytic horn equation approach and a boundary element method for the calculation of sound fields in the human ear canal

The sound field inside a model human ear canal has been computed, to show both longitudinal variations along the canal length and transverse variations through cross-sectional slices. Two methods of computation were used. A modified horn equation approach parametrizes the sound field with a single coordinate, the position along a curved center axis-this approach can accommodate the curvature and varying cross-sectional area of the ear canal but cannot compute transverse variations of the sound field. A boundary element method (BEM) was also implemented to compute the full three-dimensional sound field. Over 2000 triangular mesh elements were used to represent the ear canal geometry. For a plane piston source at the entrance plane, the pressure along the curved center axis predicted by the two methods is in good agreement, for frequencies up to 15 kHz, for four different ear canals. The BEM approach, though, reveals spatial variations of sound pressure within each canal cross section. These variations are small below 4 kHz, but increase with frequency, reaching 1.5 dB at 8 kHz and 4.5 dB at 15 kHz. For source configurations that are more realistic than a simple piston, large transverse variations in sound pressure are anticipated in the vicinity of the source.     

Effect of handset proximity on hearing aid feedback

The increased sensitivity of hearing aids to feedback as a telephone handset is brought near has been studied experimentally and numerically. For the measurements, three different hearing aids were modified so that the open-loop transfer function could be measured. They were mounted in the pinna of a mannikin and the change in open-loop transfer function determined as a function of handset proximity. Increases of over 20 dB were observed, most of this change occurring within the first 10 mm of separation between pinna and handset. Numerical calculations performed using a boundary element technique were in good agreement with the measurements.     

Specification of the geometry of the human ear canal for the prediction of sound-pressure level distribution

The geometry of 15 human ear canals has been studied. Silicone rubber molds were made of the ear canals of human cadavers, and a mechanical probe system was used to obtain approximately 1000 coordinate points over the surface of each mold. The data points were accurate to about 0.03 mm in each of the three space directions, allowing ample resolution of surface detail. The measurements have been summarized as individual ear canal area functions, the area of cross-sectional slices normal to a curved central axis following the bends of the canal. Large intersubject differences were found, but several overall trends were evident in the area functions. Accurate specification of the canal geometry has lead to improved predictions of the sound-pressure distribution along the human ear canal at frequencies greater than 8 kHz. Such predictions are relevant to the development of high-frequency audiometric methods, high-fidelity hearing aids, and to the interpretation of experiments in physiological and psychological acoustics.