FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 | 3 |

«Abstract. One of the basic problems in cryptography is the generation of a common secret key between two parties, for instance in order to com- ...»

-- [ Page 1 ] --

Information-Theoretic Key Agreement:

From Weak to Strong Secrecy for Free

Ueli Maurer1 and Stefan Wolf1

Computer Science Department, Swiss Federal Institute of Technology (ETH Zurich),

CH-8092 Zurich, Switzerland


Abstract. One of the basic problems in cryptography is the generation

of a common secret key between two parties, for instance in order to com-

municate privately. In this paper we consider information-theoretically

secure key agreement. Wyner and subsequently Csisz´r and K¨rner de- a o scribed and analyzed settings for secret-key agreement based on noisy communication channels. Maurer as well as Ahlswede and Csisz´r gen-a eralized these models to a scenario based on correlated randomness and public discussion. In all these settings, the secrecy capacity and the secret-key rate, respectively, have been defined as the maximal achiev- able rates at which a highly-secret key can be generated by the legitimate partners. However, the privacy requirements were too weak in all these definitions, requiring only the ratio between the adversary’s information and the length of the key to be negligible, but hence tolerating her to ob- tain a possibly substantial amount of information about the resulting key in an absolute sense. We give natural stronger definitions of secrecy ca- pacity and secret-key rate, requiring that the adversary obtains virtually no information about the entire key. We show that not only secret-key agreement satisfying the strong secrecy condition is possible, but even that the achievable key-generation rates are equal to the previous weak notions of secrecy capacity and secret-key rate. Hence the unsatisfactory old definitions can be completely replaced by the new ones. We prove these results by a generic reduction of strong to weak key agreement.

The reduction makes use of extractors, which allow to keep the required amount of communication negligible as compared to the length of the resulting key.

1 Introduction and Preliminaries

1.1 Models of Information-Theoretic Secret-Key Agreement This paper is concerned with information-theoretic security in cryptography.

Unlike computationally-secure cryptosystems, the security of which is based on the assumed yet unproven hardness of a certain problem such as integer factoring, a proof without any computational assumption, based on information theory rather than complexity theory, can be given for the security of an information- theoretically (or unconditionally) secure system.

From Weak to Strong Information-Theoretic Key Agreement 357 A fundamental problem is the generation of a mutual key about which an adversary has virtually no information. Wyner [18] and later Csisz´r anda K¨rner [10] considered the natural message-transmission scenarios in which the o legitimate partners Alice and Bob, as well as the adversary Eve, are connected by noisy channels. In Csisz´r and K¨rner’s setting, Alice sends information (given by a o the random variable X) to Bob (receiving Y ) and to the opponent Eve (who obtains Z) over a noisy broadcast channel characterized by the conditional distribution PY Z|X. Wyner’s model corresponds to the special case where X → Y → Z is a Markov chain.

The secrecy capacity CS (PY Z|X ) of the channel PY Z|X has been defined as the maximal rate at which Alice can transmit a secret string to Bob by using only the given noisy (one-way) broadcast channel such that the rate at which the eavesdropper receives information about the string can be made arbitrarily small.

More precisely, the secrecy capacity is the maximal asymptotically-achievable ratio between the number of generated key bits and the number of applications of the noisy broadcast channel such that Eve’s per-letter information about the key is small.

As a natural generalization of these settings, Maurer [13] and subsequently Ahlswede and Csisz´r [1] have considered the model of secret-key agreement by a public discussion from correlated randomness. Here, two parties Alice and Bob, having access to specific dependent information, use authentic public communication to agree on a secret key about which an adversary, who also knows some related side information, obtains only a small fraction of the total information.

More precisely, it is assumed in this model that Alice and Bob and the adversary Eve have access to repeated independent realizations of random variables X, Y, and Z, respectively. A special example is the situation where all the parties receive noisy versions of the outcomes of some random source, e.g., random bits broadcast by a satellite at low signal power.

The secret-key rate S(X; Y ||Z) has, in analogy to the secrecy capacity, been defined in [13] as the maximal rate at which Alice and Bob can generate a secret key by communication over the noiseless and authentic but otherwise insecure channel in such a way that the opponent obtains information about this key only at an arbitrarily small rate.

Note that Maurer’s model is a generalization of the earlier settings in the sense that only the correlated information, but not the insecure communication is regarded as a resource. In particular, the communication can be interactive instead of only one-way, and the required amount of communication has no inuence on the resulting secret-key rate. These apparently innocent modifications have dramatic consequences for the possibility of secret-key agreement.

–  –  –

initial advantage in terms of PY Z|X, whereas interactive secret-key generation can be possible in settings that are initially much less favorable for the legitimate partners.

It was shown [10] that CS (PY Z|X ) ≥ maxPX (I(X; Y ) − I(X; Z)), where the maximum is taken over all possible distributions PX on the range X of X, and that equality holds whenever I(X; Y ) − I(X; Z) is non-negative for all distributions PX. On the other hand, it is clear from the above bound that if U → X → Y Z is a Markov chain, then CS (PY Z|X ) ≥ I(U ; Y ) − I(U ; Z) is also

true. If the maximization is extended in this way, then equality always holds:

CS (PY Z|X ) = max (I(U ; Y ) − I(U ; Z)) (1) PU X : U →X→Y Z is the main result of [10]. It is a consequence of equality (1) that Alice and Bob can generate a secret key by noisy one-way communication exactly in scenarios that provide an advantage of the legitimate partners over the opponent in terms of the broadcast channel’s conditional distribution PY Z|X.

The secret-key rate S(X; Y ||Z), as a function of PXY Z, has been studied intensively. Lower and upper bounds on this quantity were derived, as well as necessary and sufficient criteria for the possibility of secret-key agreement [13], [15]. The lower bound

S(X; Y ||Z) ≥ max [I(X; Y ) − I(X; Z), I(Y ; X) − I(Y ; Z) ] (2)

follows from equality (1) [13]. The important difference to the previous settings however is that secret-key agreement can even be possible when the right-hand side of inequality (2) is zero or negative. A special protocol phase, called advantage distillation, requiring feedback instead of only one-way communication, must be used in this case. On the other hand, it was shown in [15] that S(X; Y ||Z) ≤ I(X; Y ↓Z) := min [I(X; Y |Z)] PZ|Z holds, where I(X; Y ↓ Z) is called the intrinsic conditional information between X and Y, given Z. It has been conjectured in [15], based on some evidence, that S(X; Y ||Z) = I(X; Y ↓ Z) holds for all PXY Z, or at least that I(X; Y ↓ Z) 0 implies S(X; Y ||Z) 0. Most recent results suggest that the latter is true if |X | + |Y| ≤ 5, but false in general [11].

1.3 Contributions of this Paper and Related Work In all the mentioned scenarios, the conditions on the resulting secret key were too weak originally. As it is often done in information theory, all the involved quantities, including the information about the key the adversary is tolerated to obtain, were measured in terms of an information rate, which is defined as the ratio between the information quantity of interest and the number of independent repetitions of the underlying random experiment. Unfortunately, the total information the adversary gains about the resulting secret key is then, although From Weak to Strong Information-Theoretic Key Agreement 359 arbitrarily small in terms of the rate, not necessarily bounded, let alone negligibly small. The reason is that for a given (small) ratio 0, key agreement with respect to the security parameter is required to work only for strings of length N exceeding some bound N0 ( ) which can depend on. In particular, N0 ( ) · → ∞ for → 0 is possible. Clearly, this is typically unacceptable in a cryptographic scenario. For instance, the generated key cannot be used for a one-time-pad encryption if all parts of the message must be protected.

Motivated by these considerations, stronger definitions of the rates at which a secret key can be generated are given for the different scenarios. More specifically, it is required that the information the adversary obtains about the entire key be negligibly small in an absolute sense, not only in terms of a rate. In the setting of secret-key agreement by noiseless public discussion from common information it is additionally required that the resulting secret key, which must be equal for Alice and Bob with overwhelming probability, is perfectly-uniformly distributed.

The main result of this paper is a generic reduction from strong to weak key agreement with low communication complexity. As consequences of this, Theorems 1 and 2 state that both for the secrecy capacity and for the secretkey rate, strengthening the security requirements does not reduce the achievable key-generation rates. This is particularly interesting for the case of the secrecy capacity because in this model, all the communication must be carried out over the noisy channel. Recent advances in the theory of extractors allow for closing the gap between weak and strong security in this case.

An important consequence is that all previous results on CS (PY Z|X ) and on S(X; Y ||Z), briefly described in Section 1.2, immediately carry over to the strong notions although they were only proved for the weaker definitions. The previous definitions were hence unnecessarily weak and can be entirely replaced by the new notions.

A basic technique used for proving the mentioned reduction is privacy amplification, introduced in [3], where we use both universal hashing and, as a new method in this context, extractors. A particular problem to be dealt with is to switch between (conditional) Shannon-, R´nyi-, and min-entropy of random e variables or, more precisely, of blocks of independent repetitions of random variables, and the corresponding probability distributions. A powerful tool for doing this are typical-sequences techniques.

Similar definitions of strong secrecy in key agreement have been proposed already by Maurer [14] (for the secret-key rate) and by Csisz´r [9] (for the a secrecy capacity). The authors have learned about the existence of the paper [9] (in Russian) only a few days before submitting this final version. In [14], the lower bound (3) on a slightly weaker variant of the strong secret-key rate than the one studied in this paper was proven. We present a substantially simplified proof here. In [9], a result similar to Theorem 2 was shown, using methods different from ours. More precisely, it was proved that the technique of [10] actually leads to a stronger secrecy than stated. In contrast to this, we propose a generic procedure for amplifying the secrecy of any information-theoretic key 360 Ueli Maurer and Stefan Wolf agreement, requiring an amount of communication which is negligible compared to the length of the resulting key.

1.4 Entropy Measures and Variational Distance

–  –  –

2 Secret-Key Agreement from Correlated Randomness In this section we define a stronger variant of the secret-key rate of a distribution PXY Z and show that this new quantity is equal to the previous, weak secretkey rate as defined in [13]. The protocol for strong key agreement consists of the following steps. First, weak key agreement is repeated many times. Then, so-called information reconciliation (error correction) and privacy amplification are carried out. These steps are described in Section 2.2. Of central importance for all the arguments made are typical-sequences techniques (Section 2.3). The main result of this section, the equality of the secret-key rates, is then proven in Section 2.4.

2.1 Definition of Weak and Strong Secret-Key Rates

–  –  –

As pointed out in Section 1.3, the given definition of the secret-key rate is unsatisfactorily and, as shown later, unnecessarily weak. We give a strong definition which bounds the information leaked to the adversary in an absolute sense and additionally requires the resulting key to be perfectly-uniformly distributed.

1 All the logarithms in this paper are to the base 2, unless otherwise stated.

From Weak to Strong Information-Theoretic Key Agreement 361 Definition 2 The strong secret-key rate of X and Y with respect to Z, denoted by S(X; Y ||Z), is defined in the same way as S(X; Y ||Z) with the modifications that Alice and Bob compute strings SA and SB which are with probability at least 1 − both equal to a string S with the properties

–  –  –

Obviously, S(X; Y ||Z) ≤ S(X; Y ||Z) holds. It is the goal of this section to show equality of the rates for every distribution PXY Z. Thus the attention can be totally restricted to the strong notion of secret-key rate.

2.2 Information Reconciliation and Privacy Amplification In this section we analyze the two steps, called information reconciliation and privacy amplification, of a protocol allowing strong secret-key agreement whenever I(X; Y ) − I(X; Z) 0 or I(Y ; X) − I(Y ; Z) 0 holds. More precisely, we show

S(X; Y ||Z) ≥ max { I(X; Y ) − I(X; Z), I(Y ; X) − I(Y ; Z) }. (3)

Pages:   || 2 | 3 |

Similar works:

«From Semiotics to Computational Semiotics Ricardo R. Gudwin DCA-FEEC-UNICAMP Cidade Universitária Zeferino Vaz S/N 13083-970 Campinas SP Brasil e-mail: gudwin@dca.fee.unicamp.br ABSTRACT: Semiotics is a branch of human sciences, which studies the science of signification and representation, involving mainly the phenomena of cognition and communication on living systems. This interconnects somewhat with the study of intelligent systems, where some of the objectives are the study of the...»

«N PAGE 808 Form Approved A0 A8 •ADoMB No. 0704 0188 No hour per response. including the time for reviewinsg instructionis, searching existing data sources.s eI Public r aspect of this ollect on of Information. Send comments regarding this burden estimate or any other co g~thecti.hington Headquarters Services. Directorate tor Information Operations arid Reports, 1215 Jefferson 1 011111 11 gement and Budget. Paperwork Reduction Project (0704-0188). Washington, DC 20503. Davis H 3. REPORT TYPE...»

«Brief Comments about Qualitative Data Analysis There are three vital aspects of qualitative data analysis. (1) What are the data “telling” you? What patterns, themes, and concepts emerge from the data? (2) Do the themes, patterns and concepts that emerge from the data conform to what my theoretical framework indicates should emerge? Am I seeing what I “expected” to see – based on theory – or are there unanticipated results? If so, what do those results mean? (3) How can I validate...»

«California Gambling Control Commission 2399 GATEWAY OAKS DRIVE, SUITE 220 SACRAMENTO, CA 95833 (916) 263-0700 FAX (916) 263-0499 www.cgcc.ca.gov MINUTES OF OCTOBER 7, 2010 COMMISSION MEETING OPEN SESSION 1. Call to Order and Pledge of Allegiance. Chairman Dean Shelton called the meeting to order at 10:01 a.m., and asked everyone to stand for the Pledge of Allegiance. 2. Roll Call of Commissioners. Roll Call of Commissioners was taken, with Chairman Dean Shelton and Commissioners James Shelby...»

«ADRENAL CORTICAL CANCER What is cancer? Cancer develops when cells in a part of the body begin to grow out of control. Although there are many kinds of cancer, they all start because of out-of-control growth of abnormal cells. Normal body cells grow, divide, and die in an orderly fashion. During the early years of a person's life, normal cells divide more rapidly until the person becomes an adult. After that, cells in most parts of the body divide only to replace worn-out or dying cells and to...»

«SECOND DRAFT 9/17/03 Notes for a Critical Interactionist Theory for Educators: Signification by Richard A. Quantz Educators have a dizzying array of social theories from which to choose. There are the classic theories of Durkheim, Weber, and Marx, as well as modernist theories such as Parson's functionalism, Blumer's symbolic interactionism, Luhman's (and a host of others) systems theory, the interpretive theories of phenomenologists such as Garfinkel and Burger and Luckman, as well as the...»

«Sector Standardization Needs Review #9-2 Sustainable Mining in Africa: Standards as Essential Catalysts Reuben Gisore Zvidzai Matina ARSO Central Secretariat Nairobi, Kenya June 2015 Contents Introduction 1. Significance if the Mining Sector in Africa 2. Mining in Africa: Managing the Impacts 2.1 The Environmental Impacts 2.1.1 Impacts on Water Resources 2.1.2 Impacts of Mining Projects on Air Quality 2.1.3 Climate Change Considerations 2.1.4 Impacts of Mining Projects on Soil Quality 2.1.5...»

«Financial Frictions, Investment and Tobin’s  ∗ Dan Cao† Guido Lorenzoni‡ Georgetown University Northwestern University and NBER Karl Walentin§ Sveriges Riksbank February 12, 2013 Abstract We develop a model of investment with financial constraints and use it to investigate the relation between investment and Tobin’s . A firm is financed partly by insiders, who control its assets, and partly by outside investors. When their wealth is scarce, insiders earn a rate of return...»

«Mothers of the Plaza de Mayo: First Responders for Human Rights Rachel Koepsel Case-Specific Briefing Paper Humanitarian Assistance in Complex Emergencies University of Denver 2011 Abstract The time from 1976 to 1983 in Argentina is known as the “Dirty War” period. It represents the lives lost, families destroyed, and human rights violations committed by the military government. The Mothers of the Plaza de Mayo were the first responders to the human rights violations and were able to defy...»


«Preliminary Report on the 22 December 2003 M6.5 San Simeon, California, Earthquake Jeanne L. Hardebeck1, John Boatwright1, Douglas Dreger2, Rakesh Goel3, Vladimir Graizer4, Kenneth Hudnut5, Chen Ji6, Lucile Jones5, John Langbein1, Jian Lin7, Evelyn Roeloffs8, Robert Simpson1, Keith Stark5, Ross Stein1, John C. Tinsley1.1. US Geological Survey, Menlo Park, California 2. University of California, Berkeley 3. California Polytechnic State University, San Luis Obispo 4. California Geological Survey,...»

«Languages at Risk: A Case Study from Sierra Leone Sullay M. Kanu University of Alberta 1. Introduction This paper seeks to address two issues. First, it seeks to provide evidence against the claim that “West African languages are generally holding their own in the face of globalization and the homogenizing forces of the twenty-first century” (Blench 2007:156). Secondly, it contributes to the current debate on the issue of whether indigenous languages (Brenzinger, Heine & Sommer 1991,...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.