IEEE International Symposium on Information Theory (ISIT)

Common randomness and secret key generation with a helper

I.A CSISZAR, P. Narayan

Published Nov 22, 2002• 12 citations

Abstract

Ahlswede-Csiszar (1993) and Csiszar (see Problemy Peredacii Informatsii, 1996) have addressed problems of determining the common randomness (CR) capacity and the secret key (SK) capacity for a variety of models as they arise in information theory and cryptography. We study problems of common randomness and secret key generation by a pair of terminals called the "users" with help from a third terminal, called the "helper". Noiseless one-way communication from the helper to the users as also from one user to the other, subject to rate constraints, is permitted over public channels. A situation involving a wiretapper is also considered.

DOI: 10.1109/isit.1997.613072

Related papers

Common randomness and secret key generation with a helper

Imre Csiszár, Prakash Narayan

We consider the generation of common randomness (CR), secret or not secret, by two user terminals with aid from a "helper" terminal. Each terminal observes a different component of a discrete memoryless multiple source. The helper aids the users by transmitting information to them over a noiseless public channel subject to a rate constraint. Furthermore, one of the users is allowed to transmit to the other user over a public channel under a similar rate constraint. We study the maximum rate of CR which can be thus generated, including under additional secrecy conditions when it must be concealed from a wiretapper. Lower bounds for the corresponding capacities are provided, and single-letter capacity formulas are obtained for several special cases of interest.

IEEE Transactions on Information TheoryMar 1, 2000302 citations

Secrecy capacities for multiterminal channel models

Imre Csiszár, Prakash Narayan

We derive single-letter characterizations of (strong) secrecy capacities for models in which a "helper" terminal is connected to an arbitrary number of "user" terminals by a discrete memoryless channel (DMC). The helper terminal governs the input of the DMC, over which it transmits to the user terminals that observe the corresponding outputs; transmissions over the DMC are secure. Additionally, following each transmission over the DMC, unrestricted and interactive public communication is permitted between all the terminals. A subset of the user terminals, and possibly the helper terminal, generate secrecy with the remaining user terminals acting as abettors. We distinguish between the cases in which the helper terminal may, or may not, randomize. Two kinds of secrecy capacity are considered, depending on the extent of an eavesdropper's knowledge: secret key (SK) and private key (PK) capacity. These secrecy capacities are shown to be achievable with noninteractive communication between the terminals and with no public transmission from the helper terminal. When the helper terminal is forbidden to randomize, the needed transmission over the DMC entails only that of a constant sequence. It is also shown that additional randomization at the user terminals does not serve to enhance the secrecy capacities

IEEE International Symposium on Information Theory (ISIT)Jan 1, 20057 citations

Common randomness in information theory and cryptography. I. Secret sharing

Rudolf Ahlswede, Imre Csiszár

As the first part of a study of problems involving common randomness at distance locations, information-theoretic models of secret sharing (generating a common random key at two terminals, without letting an eavesdropper obtain information about this key) are considered. The concept of key-capacity is defined. Single-letter formulas of key-capacity are obtained for several models, and bounds to key-capacity are derived for other models.>

IEEE Transactions on Information TheoryJul 1, 19931,325 citations

The secret key capacity for multiple terminals

Imre Csiszár, Prakash Narayan

We consider the problem of characterizing the secret key (SK)-capacity for an arbitrary number of terminals, each of which observes a distinct component of a discrete memoryless multiple source, with unconstrained public communication allowed between these terminals. Our main contribution is the determination of SK-capacity for an arbitrary subset of terminals with the remaining terminals serving as "helpers," when an eavesdropper observes the communication between the terminals but does not have access to any other information. We also determine the private key (PK)-capacity when the eavesdropper additionally wiretaps some of the helper terminals from which too the key must then be concealed.

IEEE Information Theory Workshop (ITW)Aug 27, 20039 citations

Common Randomness and Secret Key Capacities of Two-way Channels.

Hadi Ahmadi, Reihaneh Safavi–Naini

Abstract. Common Randomness Generation (CRG) and Secret Key Establishment (SKE) are fundamental primitives that are used in information-theoretic coding and cryptography. We study these two problems over the two-way channel model of communication, introduced by Shannon. In this model, the common randomness (CK) capacity is defined as the maximum number of random bits per channel use that the two parties can generate. The secret key (SK) capacity is defined similarly when the random bits are also required to be secure against a passive adversary. We provide lower bounds on the two capacities. These lower bounds are tighter than those one might derive based on the previously known results. We prove our lower bounds by proposing a two-round, two-level coding construction over the two-way channel. We show that the lower bound on the common randomness capacity can also be achieved using a simple interactive channel coding (ICC) method. We furthermore provide upper bounds on these capacities and show that the lower and the upper bounds coincide when the two-way channel consists of two independent (physically degraded) one-way channels. We apply the results to the case where the channels are binary symmetric.

Jan 1, 20110 citations

Rate regions of secret key sharing in a new source model

Somayeh Salimi, Mahmoud Salmasizadeh, Mohammad Reza Aref

A source model for secret key generation between terminals is considered. Two users, namely users 1 and 2, at one side communicate with another user, namely user 3, while at the other side via a public channel where three users can observe i.i.d. outputs of correlated sources. Each of users 1 and 2 intends to share a secret key with user 3 where user 1 acts as a wiretapper for user 2 and vice versa. In this model, two situations are considered: communication from users 1 and 2 to user 3 (the forward key strategy) and from user 3 to users 1 and 2 (the backward key strategy). In both situations, the goal is sharing a secret key between user 1 and user 3 while leaking no effective information about that key to user 2, and simultaneously, sharing another secret key between user 2 and user 3 while leaking no effective information about the latter key to user 1. This model is motivated by wireless communications when considering user 3 as a base station and users 1 and 2 as network users. For both the forward and backward key strategies, inner and outer bounds of secret key capacity regions are derived. In special situations where one of users 1 and 2 is only interested in wiretapping and not key sharing, the results agree with that of Ahlswede and Csiszar. Also, the authors investigate some special cases in which the inner bound coincides with the outer bound and secret key capacity region is deduced.

IET CommunicationsMar 4, 201114 citations