Tight Bounds for Unconditional Authentication Protocols in the Manual Channel and Shared Key Models

We address the message authentication problem in two seemingly different communication models. In the first model, the sender and receiver are connected by an insecure channel and by a low-bandwidth auxiliary channel, that enables the sender to ldquomanuallyrdquo authenticate one short message to the receiver (for example, by typing a short string or comparing two short strings). We consider this model in a setting where no computational assumptions are made, and prove that for any there exists a -round protocol for authenticating -bit messages, in which only bits are manually authenticated, and any adversary (even computationally unbounded) has probability of at most to cheat the receiver into accepting a fraudulent message. Moreover, we develop a proof technique showing that our protocol is essentially optimal by providing a lower bound of on the required length of the manually authenticated string. The second model we consider is the traditional message authentication model. In this model, the sender and the receiver share a short secret key; however, they are connected only by an insecure channel. We apply the proof technique above to obtain a lower bound of on the required Shannon entropy of the shared key. This settles an open question posed by Gemmell and Naor (Advances in Cryptology-CRYPTO '93, pp. 355-367, 1993). Finally, we prove that one-way functions are necessary (and sufficient) for the existence of protocols breaking the above lower bounds in the computational setting.     

Optimal Randomizer Efficiency in the Bounded-Storage Model

In the bounded-storage model for information-theoretically secure encryption and key-agreement one can prove the security of a cipher based on the sole assumption that the adversarys storage capacity is bounded, say by $s$ bits, even if her computational power is unlimited. Assume that a random $t$-bit string $R$ is either publicly available (e.g., the signal of a deep-space radio source) or broadcast by one of the legitimate parties. If $s < t$, the adversary can store only partial information about $R$. The legitimate sender Alice and receiver Bob, sharing a short secret key $K$ initially, can therefore potentially generate a very long $n$-bit one-time pad $X$ with $n\gg|K|$ about which the adversary has essentially no information. All \looseness = –1 previous results in the bounded-storage model were partial or far from optimal, for one of the following reasons: either the secret key $K$ had to be longer than the derived one-time pad ($n < |K|$), or $t$ had to be extremely large ($t > ns$), or the adversary was assumed to be able to store only $s$ actual bits of $R$ rather than arbitrary $s$ bits of information about $R$, or the adversary received a non-negligible amount of information about $X$. In this paper we prove the first non-restricted security result in the bounded-storage model: $K$ is short, $X$ is very long, and $t$ needs to be only moderately larger than $s + n$. In fact, $s/t$ can be arbitrarily close to $1$ and hence the storage bound is essentially optimal. The security can be proved also if $R$ is not uniformly random, provided that the min-entropy of $R$ is sufficiently greater than $s$.     

基于W态与Bell态纠缠的QDKD方案

为了提高密钥分发效率,利用量子密集编码的原理设计了一种基于W态和Bell态纠缠的量子确定性密钥分发方案(Quantum Deterministic Key Distribution, QDKD)。方案中,消息发送者Alice通过对持有粒子实施幺正操作实现确定性密钥的编码,接收方Bob利用粒子间联合测量获得确定性密钥。除去用于窃听检测的粒子,制备的粒子全部用于消息传输,每发送5个粒子可以实现5bits确定性密钥的分发。最后,利用信息论方法对方案进行安全性分析,结果表明,方案是安全可靠的,任何窃听行为能够被及时发现。     

An efficient t‐out‐of‐n oblivious transfer for information security and privacy protection

In t‐out‐of‐n oblivious transfer (OT), the receiver can only receive t messages out of n messages sent by the sender, and the sender has no idea about which ones have been received. Majority of the existence of previous efficient OT schemes require t calls of 1‐out‐of‐n OT to construct the t‐out‐of‐n OT. Its computational requirements and bandwidth consumption are quite demanding. On the basis of the elliptic curves cryptography, we propose a new t‐out‐of‐n OT protocol for private information retrieval in this article. It is more suitable for the smart cards or mobile units. Copyright © 2013 John Wiley & Sons, Ltd.     

One-way communication and error-correcting codes

We establish a further connection between one-way communication where a sender conveys information to a receiver who has related information, and error-correction coding where a sender attempts to communicate reliably over a noisy channel. Using this connection we obtain three results on the two problems. We derive an often-tight lower bound on the number of bits required for one-way communication based on the largest code for the corresponding error-correction problem. We construct an error-correcting code whose minimum distance properties are similar to those of Bose-Chaudhuri-Hocquenghem (BCH) codes based on a one-way communication protocol for set reconciliation. Finally, we prove that one-way communication is suboptimal for a large class of Hamming-distance problems.     

Source coding and graph entropies

A sender wants to accurately convey information to a receiver who has some, possibly related, data. We study the expected number of bits the sender must transmit for one and for multiple instances in two communication scenarios and relate this number to the chromatic and Korner (1973) entropies of a naturally defined graph     

Coding for computing

A sender communicates with a receiver who wishes to reliably evaluate a function of their combined data. We show that if only the sender can transmit, the number of bits required is a conditional entropy of a naturally defined graph. We also determine the number of bits needed when the communicators exchange two messages     

隐藏认证的不经意传输

该文在不经意传输和隐藏证书的基础上提出了隐藏认证的不经意传输, 利用双线性对构造了一个具体方案。解决了对于不经意传输的基于标准属性证书的访问控制可能暴露接收者的某些敏感信息问题。该方案有如下特点: 只有持有特定属性证书的接收者才能打开其所选择的消息,而接收者不需要向发送者提供任何证书。发送者不能确定接收者是否能够打开消息也不能确定接收者打开的是哪些消息。利用随机问答器模型, 在BDH假设及CT-CDH假设下证明了该方案的安全性。     

Bit commitment using pseudo-random synthesizer

This paper presents two practical message commitment schemes: one is suitable for committing many bits, and another is useful for committing any bit-long message. They are provably secure based on pseudo-random synthesizers. In these schemes, the sender may be unbounded to polynomial time and the receiver is bounded. The advantage of these schemes is that the secure parameter may be small.     

基于门限思想1-out-n不经意传输协议

在一个1—out—n的不经意传输模型中。发送者提供n条消息给另一方接收者。但是接收者只能选择获取其中的1条消患，并且发送者不知道接收者获取的是哪一条消息。文章提出了一个基于门限思想并且可复用的1—out-n不经意传输协议。它在效率方面优于以往的Naor-Pinkas协议和Tzeng协议。     

基于伪随机合成器的比特承诺

本文给出了两种可行的比特承诺方案:一种适应于承诺若干个比特,一种适应于承诺任意长度的消息。该方案的安全性是基于伪随机合成器的存在性,承诺者可以拥有无限的计算资源。其优点是对安全参数的要求较小。     

Reliable Multicast in Multi-Access Wireless LANs

Multicast is an efficient paradigm for transmitting data from a sender to a group of receivers. In this paper, we focus on multicast in single channel multi-access wireless local area networks (LANs) comprising several small cells. In such a system, a receiver cannot correctly receive a packet if two or more packets are sent to it at the same time, because the packets collide. Therefore, one has to ensure that only one node sends at a time. We look at two important issues. First, we consider the problem of the sender acquiring the multi-access channel for multicast transmission. Second, for reliable multicast in each cell of the wireless LAN, we examine ARQ-based approaches. The second issue is important because the wireless link error rates can be very high.We present a new approach to overcome the problem of feedback collision in single channel multi-access wireless LANs, both for the purpose of acquiring the channel and for reliability. Our approach involves the election of one of the multicast group members (receivers) as a leader or representative for the purpose of sending feedback to the sender. For reliable multicast, on erroneous reception of a packet, the leader does not send an acknowledgment, prompting a retransmission. On erroneous reception of the packet at receivers other than the leader, our protocol allows negative acknowledgments from these receivers to collide with the acknowledgment from the leader, thus destroying the acknowledgment and prompting the sender to retransmit the packet.Using analytical models, we demonstrate that the leader-based protocol exhibits higher throughput in comparison to two other protocols which use traditional delayed feedback-based probabilistic methods. Last, we present a simple scheme for leader election.     

Adaptive power permutation modulation: A novel transmission technique for increased spectral efficiency over fading channels

In this study, we propose a novel transmission technique for multiple-input multiple-output (MIMO) systems as a partial response to ever-growing demand for the increased spectral efficiency. The introduced scheme, called adaptive power permutation modulation (APPM), relies on the distinct power allocations on the conventionally modulated symbols to convey a certain number of additional information bits. Unlike the traditional power allocation strategies which generally aim to combat the channel fading and entail some form of channel state information (CSI) at the transmit side, APPM utilizes different power levels to convey additional information and does not necessitate any kind of CSI at the transmitter. The proposed approach is applied to two well-known MIMO configurations, Alamouti space-time block coding and zero-forcing beamforming, by embracing a general frequency-selective fading scenario under digital phase modulation. Both the modulation order and the power allocation levels on the modulated symbols are adaptively determined based on a set of additional information bits. It is shown that in addition to the conventionally modulated symbols, an extra sequence of $$ bits can be conveyed without any significant additional complexity where $$ equals the number of subcarriers. Also, it is demonstrated that considerable transmit power savings can be attained when compared with the standard schemes under a certain target spectral efficiency.     

Conditionally-perfect secrecy and a provably-secure randomized cipher

Shannon's pessimistic theorem, which states that a cipher can be perfect only when the entropy of the secret key is at least as great as that of the plaintext, is relativized by the demonstration of a randomized cipher in which the secret key is short but the plaintext can be very long. This cipher is shown to be perfect with high probability. More precisely, the eavesdropper is unable to obtain any information about the plaintext when a certain security event occurs, and the probability of this event is shown to be arbitrarily close to one unless the eavesdropper performs an infeasible computation. This cipher exploits the assumed existence of a publicly-accessible string of random bits whose length is much greater than that of all the plaintext to be encrypted; this is a feature that our cipher has in common with the previously considered book ciphers. Two modifications of this cipher are discussed that may lead to practical provably-secure ciphers based on either of two assumptions that appear to be novel in cryptography, viz., the (sole) assumption that the enemy's memory capacity (but not his computing power) is restricted and the assumption that an explicit function is, in a specified sense, controllably-difficult to compute, but not necessarily one-way.A preliminary version of this paper was presented at Eurocrypt '90, May 21–24, Århus, Denmark, and has appeared in the proceedings, pp.361–373.     

Selected Mapping Technique for PAPR Reduction Without Side Information Based on m-Sequence

Selected mapping (SLM) is a technique for reducing the high peak-to-average power ratio (PAPR) in which a suitable signal is selected among a set of alternative signals which all indicate alike information. The chief drawback existing in this method is that transmitter is compelled to send several additional bits called side information (SI) for each data block in order that recovering at the receiver side can be possible. In this paper, we present a novel SLM scheme by using the linear feedback shift register circuit and m-sequence named MSLM technique by which any side information bit is not explicitly sent. In MSLM, The basic idea is to fit the side information into transmitted symbols based upon which some special locations in the transmitted data block are expanded, i.e. some transmitted symbols are extended. In the receiver side, by using some properties of m-sequence the SI bits can be detected. We present the example of our method for an OFDM system through the use of 16-QAM modulation and different m-sequences and finally, concerned results are illustrated from the view point of bit error rate, probability of detection failure and PAPR reduction.     

Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage Model

We consider the problem of constructing randomness extractors that are locally computable; that is, read only a small number of bits from their input. As recently shown by locally computable extractors directly yield secure private-key cryptosystems in Maurers bounded-storage model. We suggest a general sample-then-extract approach to constructing locally computable extractors: use essentially any randomness-efficient sampler to select bits from the input and then apply any extractor to the selected bits. Plugging in known sampler and extractor constructions, we obtain locally computable extractors, and hence cryptosystems in the bounded-storage model, whose parameters improve upon previous constructions. We also provide lower bounds showing that the parameters we achieve are nearly optimal. The correctness of the sample-then-extract approach follows from a fundamental lemma of Nisan and Zuckerman, which states that sampling bits from a weak random source roughly preserves the min-entropy rate. We also present a refinement of this lemma, showing that the min-entropy rate is preserved up to an arbitrarily small additive loss, whereas the original lemma loses a logarithmic factor.     

Slepian-Wolf coding over broadcast channels

We discuss reliable transmission of a discrete memoryless source over a discrete memoryless broadcast channel, where each receiver has side information (of arbitrary quality) about the source unknown to the sender. When there are K=2 receivers, the optimum coding strategy using separate and stand-alone source and channel codes is to build two independent binning structures and send bin indices using degraded message sets through the channel, yielding a full characterization of achievable rates. However, as we show with an example, generalization of this technique to multiple binning schemes does not fully resolve the K>2 case. Joint source-channel coding, on the other hand, allows for a much simpler strategy (i.e., with no explicit binning) yielding a successful single-letter characterization of achievable rates for any Kges2. This characterization, which utilizes a trivial outer bound to the capacity region of general broadcast channels, is in terms of marginal source and channel distributions rather than a joint source-channel distribution. This contrasts with existing results for other multiterminal scenarios and implies that optimal schemes achieve "operational separation." On the other hand, it is shown with an example that an optimal joint source-channel coding strategy is strictly advantageous over the combination of stand-alone source and channel codes, and thus "informational separation" does not hold     

Practical and provably secure release of a secret and exchange of signatures

We present a protocol that allows a sender to release gradually and verifiably a secret to a receiver. We argue that the protocol can be efficiently applied to the exchange of secrets in many cases, such as when the secret is a digital signature. This includes Rabin, low-public-exponent RSA, and El Gamal signatures. In these cases, the protocol requires an interactive three-pass initial phase, after which each bit (or block of bits) of the signature can be released noninteractively (i.e., by sending one message). The necessary computations can be done in a couple of minutes on an up-to-date PC. The protocol is statistical zero-knowledge, and therefore releases a negligible amount of side information in the Shannon sense to the receiver. The sender is unable to cheat, if he cannot factor a large composite number before the protocol is completed.     

概率译码转发中继系统中的安全极化编码方法

该文针对中继节点依概率辅助译码转发的通信场景,提出一种中继辅助的安全极化编码方法,保证私密信息可靠传输的同时,达到提高安全传输速率的目的。首先,发送端分别进行两层极化编码——中继概率转发行为构成的虚拟二进制删除信道下的极化编码和实际传输信道下的极化编码,并将私密信息分别隐藏在两层码字中,分时隙广播出去。然后,中继依概率译码后提取出合法用户无法直接接收的固定信息再次进行安全极化编码并转发。最后,接收端利用收到的中继转发码字和发端码字依次分层进行译码。理论和仿真分析证明,所提方法下合法用户能够可靠接收私密信息,而窃听者无法获取任何私密信息信息量;安全传输速率随着码长和中继转发概率的增加而增大,且高于一般的安全极化编码方法。