On the size of shares for secret sharing schemes

A secret sharing scheme permits a secret to be shared among participants in such a way that only qualified subsets of participants can recover the secret, but any nonqualified subset has absolutely no information on the secret. The set of all qualified subsets defines the access structure to the secret. Sharing schemes are useful in the management of cryptographic keys and in multiparty secure protocols.We analyze the relationships among the entropies of the sample spaces from which the shares and the secret are chosen. We show that there are access structures with four participants for which any secret sharing scheme must give to a participant a share at least 50% greater than the secret size. This is the first proof that there exist access structures for which the best achievable information rate (i.e., the ratio between the size of the secret and that of the largest share) is bounded away from 1. The bound is the best possible, as we construct a secret sharing scheme for the above access structures that meets the bound with equality.This work was partially supported by Algoritmi, Modelli di Calcolo e Sistemi Informativi of M.U.R.S.T. and by Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo of C.N.R. under Grant Number 91.00939.PF69.     

矢量空间秘密共享-多重签名方案

本文把矢量空间秘密共享方案与多重签名方案结合起来 ,提出了一种新的签名方案 ,即矢量空间秘密共享 -多重签名方案 ,并对该方案的安全性进行了分析 .在该方案中 ,任何参与者的授权子集能容易地产生群签名 ,而参与者的非授权子集不可能产生有效的群签名 ,验证者可通过验证方法验证个体签名和群签名的合法性 .该方案能保证一个参与者的授权子集的群签名不能被其他参与者子集所伪造 ,而且可以跟踪被怀疑的伪造者并将其曝光 .该方案能抵御各种可能的攻击 .     

矢量空间秘密共享-多重签名方案

本文把矢量空间秘密共享方案与多重签名方案结合起来,提出了一种新的签名方案,即矢量空间秘密共享-多重签名方案,并对该方案的安全性进行了分析.在该方案中,任何参与者的授权子集能容易地产生群签名,而参与者的非授权子集不可能产生有效的群签名,验证者可通过验证方法验证个体签名和群签名的合法性.该方案能保证一个参与者的授权子集的群签名不能被其他参与者子集所伪造,而且可以跟踪被怀疑的伪造者并将其曝光.该方案能抵御各种可能的攻击.     

AN EFFICIENT AND SECURE （t, n） THRESHOLD SECRET SHARING SCHEME

Based on Shamir＇s threshold secret sharing scheme and the discrete logarithm problem, a new （t, n） threshold secret sharing scheme is proposed in this paper. In this scheme, each participant＇s secret shadow is selected by the participant himself, and even the secret dealer cannot gain anything about his secret shadow. All the shadows are as short as the shared secret. Each participant can share many secrets with other participants by holding only one shadow. Without extra equations and information designed for verification, each participant is able to check whether another participant provides the true information or not in the recovery phase. Unlike most of the existing schemes, it is unnecessary to maintain a secure channel between each participant and the dealer. Therefore, this scheme is very attractive, especially under the circumstances that there is no secure channel between the dealer and each participant at all. The security of this scheme is based on that of Shamir＇s threshold scheme and the difficulty in solving the discrete logarithm problem. Analyses show that this scheme is a computationally secure and efficient scheme.     

双重门限秘密共享方案

基于RSA密码体制、Shamir门限方案和哈希函数的安全性,设计了一种双重门限秘密共享方案。方案中,参与者只需维护一个秘密份额,可实现对多个秘密的共享。秘密份额由参与者确定和保管,秘密分发者也不知晓,秘密共享过程中,只需出示伪秘密份额。方案不需要维护安全信道,算法能够保证信息安全传送,以及验证参与者是否进行了欺骗。     

一种无纠缠态的量子秘密共享协议

秘密共享是指将一个秘密按适当的方式进行隐藏或拆分,只有若干个参与者一同协作才能恢复该秘密,该技术在云计算领域中能够确保信息安全和数据保密.提出了一种不使用纠缠态的量子秘密共享协议,通过使用量子密码算法确保系统的安全性.相比其他的秘密共享协议,该协议具有以下优点:与传统的基于数论的秘密共享协议相比,本协议由于使用量子通信的技术,从而能够有效抵抗Shor算法攻击;相比其他的量子秘密共享协议,由于本协议没有使用量子纠缠态,在技术程度上更容易实现;如果存在攻击者或恶意的参与者,该协议能够在秘密恢复过程中迅速发现,避免恢复错误的秘密.     

Year 2000 — a Sytems Integration challenge

BT, along with virtually every other IT-dependent business worldwide, is tackling a problem which is quite unique and if not corrected could be disastrous. The problem, sometimes known as the Year 2000 bug or millennium time bomb, has been caused by the use of two digits to represent the year in the majority of our systems and applications. The problem is technically not difficult to fix but the volume of changes occurring, and the need to potentially test every system to ensure that it is year 2000 proof, presents unique and challenging difficulties for integration and testing. Why this is the case, what problems need to be addressed, and an overview of some of the proposed integration and test strategies to tackle these problems, is the subject of this paper.     

Virtual conferencing

Current multi-party video- and audioconferencing systems limit natural communications between participants. People communicate by speech, facial expressions and body gestures. In interactions between three or more people, these communications channels are directed towards particular participants. Spatial proximity and gaze direction are therefore important elements for effective conversational interactions, and yet are largely unsupported in existing conferencing tools. Advanced audioconferencing systems do simulate presence in a shared environment by using virtual humans to represent the people taking part in a meeting, but the keyboard and mouse are used to direct conversations to specific people or to change the visual representation to simulate emotion.This paper describes an experimental implementation of virtual conferencing, which uses machine vision to control a realistic virtual human, with the objective of making virtual meetings more like physical ones. The computer vision system provides a more natural interface to the environment, while the realistic representation of users, with appropriate facial gestures and upper body movement, gives more natural visual feedback.     

Pervasive Home Environments

For decades, technologists have been promising the intelligent house. The vision is usually portrayed as a house filled with technology which will do the dweller's bidding and take all domestic drudgery out of their lives. The truly intelligent house is still some way off, but the emergence of broadband, availability of faster, smaller and ever cheaper computing equipment and a variety of wired and wireless network technologies are enabling technologies that bring this vision closer to reality. These technology trends lead to the concept that computing and other smart devices will become pervasive, fully networked and disappear into the infrastructure of the home. People will carry out their tasks unaware of the complexity of the infrastructure that supports their activities in much the same way as people today use mains electricity.This paper introduces these concepts and discusses the technological challenges to be overcome. We present our vision of the pervasive home environment where inhabitants can focus on tasks rather than the technology: I need to create X and send it to Y rather than I need to use this computer and this application which needs access to service A and resource B. Although this sounds simple, the environment needs to understand who I is, and who or what Y is. Appropriate permissions must be in place and resources allocated, if available. The most appropriate interface for the task and user must be determined.The pervasive, intelligent home will make available new ways to access and share information. It will herald new services, such as care and support of people in the home, entertainment, educational and security services. The final part of the paper discusses the commercial opportunities and challenges which must be met, not least the need for industry to agree on open standards and interfaces.     

Performance Monitoring for In-life Capacity Management

The key to providing a meaningful management view of the performance of complex systems lies in having a co-ordinated process for data collection, analysis and presentation. TeleMarketing Services, such as the Freefone service, provide a good example. Managers of diverse, remote subsystems receive summarised performance and customer service information, mostly in the form of simple graphs, in exchange for providing reliable data. The aim is to bring together a structured view of all the components, including a red-amber-green status table, for use by senior customer-facing staff. Generally, the analyses focus on capacity, forecast and measurement, covering a flexible range of parameters. Managers then have an early view of service degradation, potential capacity exhaustion, workload imbalance and resource wastage, enabling timely remedial action, fault clearance and system enhancements.     

基于ECC的可公开验证的非交互式密钥共享方案

提出一种基于椭圆曲线加密的非交互式零知识证明协议,并基于该证明协议提出一个可公开验证的密钥共享方案.在该方案中,密钥和密钥份额被嵌入椭圆曲线的点上,任何人均可对密钥和密钥份额进行验证,只有合法参与者集合可恢复出密钥,但无法知道密钥的具体内容;这样有效阻止了攻击者窃取密钥,也防止了数据的误发和成员之间的欺诈,更有利于密钥的复制与更新.     

On the distribution of characteristics in bijective mappings

Differential cryptanalysis is a method of attacking iterated mappings based on differences known as characteristics. The probability of a given characteristic is derived from the XOR tables associated with the iterated mapping. If is a mapping : Z ₂ ^m , then for each , X, Y Z ₂ ^m the XOR table for gives the number of input pairs of difference X=X+X for which gp(X)+(X)=Y.The complexity of a differential attack depends upon two properties of the XOR tables: the density of zero entries in the table, and the size of the largest entry in the table. In this paper we present the first results on the expected values of these properties for a general class of mappings . We prove that if : Z ₂ ^m Z ₂ ^m is a bijective mapping, then the expected size of the largest entry in the XOR table for is bounded by 2m, while the fraction of the XOR table that is zero approaches e ^–1/2=0.60653. We are then able to demonstrate that there are easily constructed classes of iterated mappings for which the probability of a differential-like attack succeeding is very small.The author is presently employed by the Distributed System Technology Center, Brisbane, Australia.     

Residential Gateways

The residential gateway (RG) is set to become a key infrastructure component in the future home network. Ideally home networks should be easy to set up and operate and it should also be possible to securely deliver and manage services. For service providers, the RG appears to offer a huge opportunity to extend their presence into the home and in so doing own the territory. However, a new generation of customers are used to retaining control and many people will be unwilling to let external agents intrude too far into their environment. This paper examines the residential gateway, the forms it might take, the roles it could play and looks at aspects of management.     

Some improved bounds on the information rate of perfect secret sharing schemes

In this paper we study secret sharing schemes for access structures based on graphs. A secret sharing scheme enables a secret key to be shared among a set of participants by distributing partial information called shares. Suppose we desire that some specified pairs of participants be able to compute the key. This gives rise in a natural way to a graphG which contains these specified pairs as its edges. The secret sharing scheme is calledperfect if a pair of participants corresponding to a nonedge ofG can obtain no information regarding the key. Such a perfect secret sharing scheme can be constructed for any graph. In this paper we study the information rate of these schemes, which measures how much information is being distributed as shares compared with the size of the secret key. We give several constructions for secret sharing schemes that have a higher information rate than previously known schemes. We prove the general result that, for any graphG having maximum degreed, there is a perfect secret sharing scheme realizingG in which the information rate is at least 2/(d+3). This improves the best previous general bound by a factor of almost two. The work of E. F. Brickell was performed at the Sandia National Laboratories and was supported by the U.S. Department of Energy under Contract Number DE-AC04-76DP00789. The research of D. R. Stinson was supported by NSERC Operating Grant A9287 and by the Center for Communication and Information Science, University of Nebraska.     

Hierarchical Threshold Secret Sharing

We consider the problem of threshold secret sharing in groups with hierarchical structure. In such settings, the secret is shared among a group of participants that is partitioned into levels. The access structure is then determined by a sequence of threshold requirements: a subset of participants is authorized if it has at least k₀ 0 members from the highest level, as well as at least k₁ > k₀ members from the two highest levels and so forth. Such problems may occur in settings where the participants differ in their authority or level of confidence and the presence of higher level participants is imperative to allow the recovery of the common secret. Even though secret sharing in hierarchical groups has been studied extensively in the past, none of the existing solutions addresses the simple setting where, say, a bank transfer should be signed by three employees, at least one of whom must be a department manager. We present a perfect secret sharing scheme for this problem that, unlike most secret sharing schemes that are suitable for hierarchical structures, is ideal. As in Shamir's scheme, the secret is represented as the free coefficient of some polynomial. The novelty of our scheme is the usage of polynomial derivatives in order to generate lesser shares for participants of lower levels. Consequently, our scheme uses Birkhoff interpolation, i.e., the construction of a polynomial according to an unstructured set of point and derivative values. A substantial part of our discussion is dedicated to the question of how to assign identities to the participants from the underlying finite field so that the resulting Birkhoff interpolation problem will be well posed. In addition, we devise an ideal and efficient secret sharing scheme for the closely related hierarchical threshold access structures that were studied by Simmons and Brickell.     

Symmetry relations in multidimensional Fourier transform pairs

A relation between the types of symmetries that exist in signal and Fourier transform domain representations is derived for continuous as well as discrete domain signals. The symmetry is expressed by a set of parameters, and the relations derived in this paper will help to find the parameters of a symmetry in the signal or transform domain resulting from a given symmetry in the transform or signal domain respectively. A duality among the relations governing the conversion of the parameters of symmetry in the two domains is also brought to light. The application of the relations is illustrated by a number of two-dimensional examples.Notation R the set of real numbers - R ^m R × R × ... × R m-dimensional real vector space - continuous domain real vector - L {¦ – _i , i = 1,2,..., m} - m-dimensional frequency vector - W { – _i ,i=1,2,..., m} - m-dimensional normalized frequency vector - _P {¦ – _i , i=1,2,...,m} - g(ol) g (₁,₂,..., _m ) continuous domain signal - () ( _{1 2},..., _m )=G (j ₁,j ₂,..., j _m ) Fourier transform ofg (ol) - (A,b,,,) parameters ofT- symmetry - N the set of integers - N ^m N × N × ... × N m-dimensional integer vector spacem-dimensional lattice - h(n) h (n ₁,.,n _m ) discrete domain signal - H() Fourier transform ofh (n) - v ₁,v ₂,..., v_m m sample-direction and interval vectors - V (v ₁ v ₂ ...v _m ) sampling basis matrix - [x]^* complex conjugate ofx - detA determinant ofA - X {x¦ – x _i , i=1,2,..., m} - A ^–t [A ^–1] ^t ,t stands for transpose This work was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant A-7739 to M. N. S. Swamy and in part by Tennessee Technological University under its Faculty Research support program to P. K. Rajan.     

Unified IP Networks

Corporations are looking to harness the flexibility and ubiquity of IP as a means of automating key business transactions and increasing efficiency. As part of this eRevolution corporate businesses are looking at migrating new applications on to their existing IP infrastructures.Computer/telephony integration and unified messaging are applications that will drive forward the integration of voice and data networks for BT's corporate customers, enabling the use of a flexible, shared IP infrastructure for voice and data.While voice over IP is widely seen as the obvious way forward there are many issues to be resolved before this can deliver the anticipated benefits. This paper provides an insight into the building blocks required to enable the development/deployment of shared infrastructure, for quality of service (QoS) capable, unified, IP network solutions. It highlights the detailed understanding and careful design approach required (particularly in the complex area of network QoS) to engineer custom voice solutions as part of a unified IP network design based on today's technology. Emerging protocols and technology, which may turn the unified network dream into reaility, are identified.     

A VLSI decoder for a new type of constellations adapted to the Rayleigh Fading Channel

Diversity is the key solution to obtain efficient channel coding in wireless communications, where the signal is subject to fading (Rayleigh Fading Channel). For high spectral efficiency, the best solutions used nowadays are based on QAM constellations of 1-order diversity, associated with a binary code or a trellis coded modulation to increase the overall diversity. It has been shown that a new class of d-dimensional non-QAM constellations, named -constellations, can bring a d-order diversity without the addition of redundancy. Combined with classical coding techniques, -constellations are very efficient. However, the decoding algorithm is far more complicated for -constellations than for QAM-constellations. A sub-optimal algorithm that allows the decoding of -constellations is proposed. An example of an application for a 4 bits/Hz/s spectral efficiency with a 4-D -constellation is given. The VLSI architecture of the decoder is described. The implementation leads to 72 K gates, a binary rate of 32 Mbits/s and a BER of 10^-3 for a SNR of 14 dB.     

Higher-order terms in asymptotic expansion for information loss in quantized random processes

Uniform quantization of random vectors onto -grids ⁿ is considered. Higherorder terms in asymptotic expansions for the entropy of the -quantized random vector and for the loss of the mutual information between two random vectors under such quantization as 0+are obtained. The coefficients in these asymptotics are explicitly calculated for Gaussian distributed vectors. Taken for initial segments of stationary Gaussian sequences, these factors have limit average values per unit of time. For such sequences governed by state-space equations, computation of these average values is reduced to solutions of algebraic matrix Riccati and Lyapunov equations.Work supported by the Australian Research Council grant A 4970 2246.     

On the design of feedback controllers to achieve prescribed initial value constraints

The problem of designing a stabilizing compensator for a control system to achieve prescribed initial value constraints ⁽ⁱ⁾(0⁺)=y_i is considered. Indeed, modulo certain technical conditions, such a compensator exists if and only if y_i=0;i= 0,1,...,rp +rt –2; whererp is the relative degree of the plant andrt is the relative degree of the system input. This theorem is derived and a complete parameterization of the set of compensators that achieve the prescribed design constraints is formulated.This research was supported in part by NSF Grant No. 921106.