Efficient One-Way Secret-Key Agreement and Private Channel Coding via Polarization
D. Sutter; J. M. Renes; R. Renner
2013
Efficient One-Way Secret-Key Agreement and Private Channel Coding via Polarization
Type
Online Database
Author
D. Sutter; J. M. Renes; R. Renner
Year
2013
Abstract
We introduce explicit schemes based on the polarization phenomenon for the tasks of one-way secret key agreement from common randomness and private channel coding. For the former task, we show how to use common randomness and insecure one-way communication to obtain a strongly secure key such that the key construction has a complexity essentially linear in the blocklength and the rate at which the key is produced is optimal, i.e., equal to the one-way secret-key rate. For the latter task, we present a private channel coding scheme that achieves the secrecy capacity using the condition of strong secrecy and whose encoding and decoding complexity are again essentially linear in the blocklength.
We address the question of whether there is a way of characterizing the quantum information transport properties of a medium or material. For this analysis, the special features of quantum information have to be taken into account. We find that quantum communication over an isotropic medium, as opposed to classical information transfer, requires the transmitter to direct the signal toward the receiver. Furthermore, for large classes of media there is a threshold, in the sense that'sufficiently much'of the signal has to be collected. Therefore, the medium's capacity for quantum communication can be characterized in terms of how the sizes of the transmitter and receiver have to scale with the transmission distance to maintain quantum information transmission. To demonstrate the applicability of this concept, an n-dimensional spin lattice is considered, yielding a sufficient scaling of δn/3 with the distance δ.
We argue that the concepts of"freedom of choice"and of"causal order"are intrinsically linked: a choice is considered"free"if it is correlated only to variables in its causal future. We discuss the implications of this to Bell-type scenarios, where two separate measurements are carried out, neither of which lies in the causal future of the other, and where one typically assumes that the measurement settings are chosen freely. Furthermore, we refute a recent criticism made by Ghirardi and Romano in [arXiv:1301.5040] and [arXiv:1302.1635] that we used an unphysical freedom of choice assumption in our previous works, [Nat. Commun. 2, 411 (2011)] and [Phys. Rev. Lett. 108, 150402 (2012)].
N. J. Beaudry; M. Lucamarini; S. Mancini; R. Renner
2013
Security of two-way quantum key distribution
Type
Online Database
Author
N. J. Beaudry; M. Lucamarini; S. Mancini; R. Renner
Year
2013
Abstract
Quantum key distribution protocols typically make use of a one-way quantum channel to distribute a shared secret string to two distant users. However, protocols exploiting a two-way quantum channel have been proposed as an alternative route to the same goal, with the potential advantage of outperforming one-way protocols. In this paper we provide a strategy to prove security for two-way quantum key distribution protocols against the most general quantum attack possible by an eavesdropper. We apply this method to prove the security of two important examples of such protocols. In our analysis we utilize an entropic uncertainty relation, which results in partially device-independent security, where only a few assumptions need to be made about the devices used in the protocol. We also show that a two-way protocol can outperform comparable one-way protocols in some scenarios.
We provide a framework for one-shot quantum rate distortion coding, in which the goal is to determine the minimum number of qubits required to compress quantum information as a function of the probability that the distortion incurred upon decompression exceeds some specified level. We first derive lower and upper bounds on the minimum qubit compression size of a one-shot entanglement-assisted quantum rate distortion code. These bounds then lead to a one-shot characterization of the minimum qubit compression size for an entanglement-assisted quantum rate-distortion code in terms of the smooth max-information, a quantity previously employed in the one-shot quantum reverse Shannon theorem. Next, we show how these bounds converge to the known expression for the entanglement-assisted quantum rate distortion function for asymptotically many copies of a memoryless quantum information source. Finally, we give a tight, finite blocklength characterization for the entanglement-assisted minimum qubit compression size of a memoryless isotropic qubit source subject to an average symbol-wise distortion constraint.
Security of continuous-variable quantum key distribution against general attacks
A. Leverrier; R. Garcia-Patron; R. Renner; N. J. Cerf
2013
Security of continuous-variable quantum key distribution against general attacks
Type
Journal Article
Author
A. Leverrier; R. Garcia-Patron; R. Renner; N. J. Cerf
Year
2013
Journal
Physical Review Letters
Abstract
We prove the security of Gaussian continuous-variable quantum key distribution with coherent states against arbitrary attacks in the finite-size regime. In contrast to previously known proofs of principle (based on the de Finetti theorem), our result is applicable in the practically relevant finite-size regime. This is achieved using a novel proof approach, which exploits phase-space symmetries of the protocols as well as the postselection technique introduced by Christandl, Koenig, and Renner [ Phys. Rev. Lett. 102 020504 (2009)].
Composable security of delegated quantum computation
V. Dunjko; J. F. Fitzsimons; C. Portmann; R. Renner
2013
Composable security of delegated quantum computation
Type
Online Database
Author
V. Dunjko; J. F. Fitzsimons; C. Portmann; R. Renner
Year
2013
Abstract
Delegating difficult computations to remote large computation facilities, with appropriate security guarantees, is a possible solution for the ever-growing needs of personal computing power. For delegated computation protocols to be usable in a larger context---or simply to securely run two protocols in parallel---the security definitions need to be composable. Here, we define composable security for delegated quantum computation, and prove that several known protocols are composable, including Broadbent, Fitzsimons and Kashefi's Universal Blind Quantum Computation protocol. We distinguish between protocols which provide only blindness---the computation is hidden from the server---and those that are also verifiable---the client can check that it has received the correct result. We show that the composable security definition capturing both these notions can be reduced to a combination of two distinct stand-alone security definitions.
One-Shot Classical-Quantum Capacity and Hypothesis Testing
L. Wang; R. Renner
2012
One-Shot Classical-Quantum Capacity and Hypothesis Testing
Type
Journal Article
Author
L. Wang; R. Renner
Year
2012
Journal
Physical Review Letters
Abstract
The one-shot classical capacity of a quantum channel quantifies the amount of classical information that can be transmitted through a single use of the channel such that the error probability is below a certain threshold. In this work, we show that this capacity is well approximated by a relative-entropy-type measure defined via hypothesis testing. Combined with a quantum version of Stein’s lemma, our results give a conceptually simple proof of the well-known Holevo-Schumacher-Westmoreland theorem for the capacity of memoryless channels. More generally, we obtain tight capacity formulas for arbitrary (not necessarily memoryless) channels.
Trevisan's extractor in the presence of quantum side information
A. De; C. Portmann; T. Vidick; R. Renner
2012
Trevisan's extractor in the presence of quantum side information
Type
Journal Article
Author
A. De; C. Portmann; T. Vidick; R. Renner
Year
2012
Journal
SIAM Journal on Computing
Abstract
Randomness extraction involves the processing of purely classical information and is therefore usually studied with in the framework of classical probability theory. However, such a classical treatment is generally too restrictive for applications where side information about the values taken by classical random variables may be represented by the state of a quantum system. This is particularly relevant in the context of cryptography, where an adversary may make use of quantum devices. Here, we show that the well-known construction paradigm for extractors proposed by Trevisan is sound in the presence of quantum side information. We exploit the modularity of this paradigm to give several concrete extractor constructions, which, e.g., extract all the conditional (smooth) min-entropy of the source using a seed of length polylogarithmic in the input, or only require the seed to be weakly random.
The impossibility of non-signaling privacy amplification
E. Haenggi; R. Renner; S. Wolf
2012
The impossibility of non-signaling privacy amplification
Type
Journal Article
Author
E. Haenggi; R. Renner; S. Wolf
Year
2012
Journal
Theoretical Computer Science, Elsevier
Abstract
Barrett, Hardy, and Kent have shown in 2005 that protocols for quantum key agreement exist the security of which can be proven under the assumption that quantum or relativity theory is correct. More precisely, this is based on the non-local behavior of certain quantum systems, combined with the non-signaling postulate from relativity. An advantage is that the resulting security is independent of what (quantum) systems the legitimate parties'devices operate on: they do not have to be trusted. Unfortunately, the protocol proposed by Barrett et al. cannot tolerate any errors caused by noise in the quantum channel. Furthermore, even in the error-free case it is inefficient: its communication complexity is Theta(1/epsilon) when forcing the attacker's information below epsilon, even if only a single key bit is generated. Potentially, the problem can be solved by privacy amplification of relativistic - or non-signaling - secrecy. We show, however, that such privacy amplification is impossible with respect to the most important form of non-local behavior, and application of arbitrary hash functions.
The chain rule for the Shannon and von Neumann entropy, which relates the total entropy of a system to the entropies of its parts, is of central importance to information theory. Here we consider the chain rule for the more general smooth min- and max-entropy, used in one-shot information theory. For these entropy measures, the chain rule no longer holds as an equality, but manifests itself as a set of inequalities that reduce to the chain rule for the von Neumann entropy in the i.i.d. case.
Is a system's wave function in one-to-one correspondence with its elements of reality?
R. Colbeck; R. Renner
2012
Is a system's wave function in one-to-one correspondence with its elements of reality?
Type
Journal Article
Author
R. Colbeck; R. Renner
Year
2012
Journal
Physical Review Letters
Abstract
Although quantum mechanics is one of our most successful physical theories, there has been a long-standing debate about the interpretation of the wave function—the central object of the theory. Two prominent views are that (i) it corresponds to an element of reality, i.e., an objective attribute that exists before measurement, and (ii) it is a subjective state of knowledge about some underlying reality. A recent result [M. F. Pusey, J. Barrett, and T. Rudolph, arXiv:1111.3328] has placed the subjective interpretation into doubt, showing that it would contradict certain physically plausible assumptions, in particular, that multiple systems can be prepared such that their elements of reality are uncorrelated. Here we show, based only on the assumption that measurement settings can be chosen freely, that a system’s wave function is in one-to-one correspondence with its elements of reality. This also eliminates the possibility that it can be interpreted subjectively.
The completeness of quantum theory for predicting measurement outcomes
R. Colbeck; R. Renner
2012
The completeness of quantum theory for predicting measurement outcomes
Type
Online Database
Author
R. Colbeck; R. Renner
Year
2012
Abstract
The predictions that quantum theory makes about the outcomes of measurements are generally probabilistic. This has raised the question whether quantum theory can be considered complete, or whether there could exist alternative theories that provide improved predictions. Here we review recent work that considers arbitrary alternative theories, constrained only by the requirement that they are compatible with a notion of"free choice"(defined with respect to a natural causal structure). It is shown that quantum theory is"maximally informative", i.e., there is no other compatible theory that gives improved predictions. Furthermore, any alternative maximally informative theory is necessarily equivalent to quantum theory. This means that the state a system has in such a theory is in one-to-one correspondence with its quantum-mechanical state (the wave function). In this sense, quantum theory is complete.
Polar coding, introduced 2008 by Arıkan, is the first (very) efficiently encodable and decodable coding scheme whose information transmission rate provably achieves the Shannon bound for classical discrete memoryless channels in the asymptotic limit of large block sizes. Here, we study the use of polar codes for the transmission of quantum information. Focusing on the case of qubit Pauli channels and qubit erasure channels, we use classical polar codes to construct a coding scheme that asymptotically achieves a net transmission rate equal to the coherent information using efficient encoding and decoding operations and code construction. Our codes generally require preshared entanglement between sender and receiver, but for channels with a sufficiently low noise level we demonstrate that the rate of preshared entanglement required is zero.
Tight Finite-Key Analysis for Quantum Cryptography
M. Tomamichel; C. W. Lim; N. Gisin; R. Renner
2012
Tight Finite-Key Analysis for Quantum Cryptography
Type
Journal Article
Author
M. Tomamichel; C. W. Lim; N. Gisin; R. Renner
Year
2012
Journal
Nature Communications
Abstract
Despite enormous theoretical and experimental progress in quantum cryptography, the security of most current implementations of quantum key distribution is still not rigorously established. One significant problem is that the security of the final key strongly depends on the number, M, of signals exchanged between the legitimate parties. Yet, existing security proofs are often only valid asymptotically, for unrealistically large values of M. Another challenge is that most security proofs are very sensitive to small differences between the physical devices used by the protocol and the theoretical model used to describe them. Here we show that these gaps between theory and experiment can be simultaneously overcome by using a recently developed proof technique based on the uncertainty relation for smooth entropies.
One-Shot Classical Data Compression with Quantum Side Information and the Distillation of Common Randomness or Secret Keys
J. M. Renes; R. Renner
2012
One-Shot Classical Data Compression with Quantum Side Information and the Distillation of Common Randomness or Secret Keys
Type
Journal Article
Author
J. M. Renes; R. Renner
Year
2012
Journal
IEEE Transactions on Information Theory
Abstract
The task of compressing classical information in the one-shot scenario is studied in the setting where the decompressor additionally has access to some given quantum side information. In this hybrid classical-quantum version of the famous Slepian-Wolf problem, the smooth max entropy is found to govern the number of bits into which classical information can be compressed so that it can be reliably recovered from the compressed version and quantum side information. Combining this result with known results on privacy amplification then yields tight bounds on the amount of common randomness and secret key that can be recovered in one shot from hybrid classical-quantum systems using one-way classical communication.
Mathematical and Engineering Methods in Computer Science
Abstract
It is well known that classical computationally-secure cryp- tosystems may be susceptible to quantum attacks, i.e., attacks by ad- versaries able to process quantum information. A prominent example is the RSA public key cryptosystem, whose security is based on the hard- ness of factoring; it can be broken using a quantum computer running Shor’s efficient factoring algorithm. In this extended abstract, we review an argument which shows that a similar problem can arise even if a cryptosystem provides information-theoretic security. As long as its se- curity analysis is carried out within classical information theory, attacks by quantum adversaries cannot in general be excluded.
Logic gates are the elementary building blocks of computers. The finding that a single logic gate may drive a refrigerator is a beautiful demonstration that information-processing devices can have useful thermodynamic properties.
Laws of thermodynamics beyond the von Neumann regime
D. Egloff; O. C. O. Dahlsten; R. Renner; V. Vedral
2012
Laws of thermodynamics beyond the von Neumann regime
Type
Online Database
Author
D. Egloff; O. C. O. Dahlsten; R. Renner; V. Vedral
Year
2012
Abstract
Standard thermodynamics is associated with the von Neumann entropy. There has recently been great interest in making thermodynamics more suitable for the quantum and nano-regime by taking inspiration from single-shot information theory, which replaces the von Neumann entropy with the more general smooth entropies. These reduce to the von Neumann entropy in the regime of asymptotically many identical and uncorrelated systems, the von Neumann regime. We propose generalisations of the laws of thermodynamics which analogously reduce to the standard laws in that same limit. We motivate these by analysing a very generic Szilard-engine model. We derive how much work one can extract in a single extraction as a function of the success-probability. Neither the initial nor final state is required to be thermal. In the appropriate limits we recover existing results.
Are there fundamentally random processes in nature? Theoretical predictions, confirmed experimentally, such as the violation of Bell inequalities, point to an affirmative answer. However, these results are based on the assumption that measurement settings can be chosen freely at random, so assume the existence of perfectly free random processes from the outset. Here we consider a scenario in which this assumption is weakened and show that partially free random bits can be amplified to make arbitrarily free ones. More precisely, given a source of random bits whose correlation with other variables is below a certain threshold, we propose a procedure for generating fresh random bits that are virtually uncorrelated with all other variables. We also conjecture that such procedures exist for any non-trivial threshold. Our result is based solely on the no-signalling principle, which is necessary for the existence of free randomness.
Experimental Bound on the Maximum Predictive Power of Physical Theories
T. E. Stuart; J. A. Slater; R. Colbeck; R. Renner; W. Tittel
2012
Experimental Bound on the Maximum Predictive Power of Physical Theories
Type
Journal Article
Author
T. E. Stuart; J. A. Slater; R. Colbeck; R. Renner; W. Tittel
Year
2012
Journal
Physical Review Letters
Abstract
The question of whether the probabilistic nature of quantum mechanical predictions can be alleviated by supplementing the wave function with additional information has received a lot of attention during the past century. A few specific models have been suggested and subsequently falsified. Here we give a more general answer to this question: We provide experimental data that, as well as falsifying these models, cannot be explained within any alternative theory that could predict the outcomes of measurements on maximally entangled particles with significantly higher probability than quantum theory. Our conclusion is based on the assumptions that all measurement settings have been chosen freely (within a causal structure compatible with relativity theory), and that the presence of the detection loophole did not affect the measurement outcomes.
Tsirelson's bound from a Generalised Data Processing Inequality
O. C. O. Dahlsten; D. Lercher; R. Renner
2012
Tsirelson's bound from a Generalised Data Processing Inequality
Type
Journal Article
Author
O. C. O. Dahlsten; D. Lercher; R. Renner
Year
2012
Journal
New Journal of Physics
Abstract
The strength of quantum correlations is bounded from above by Tsirelson's bound. We establish a connection between this bound and the fact that correlations between two systems cannot increase under local operations, a property known as the data processing inequality (DPI). More specifically, we consider arbitrary convex probabilistic theories. These can be equipped with an entropy measure that naturally generalizes the von Neumann entropy, as shown recently in Short and Wehner (2010 New J. Phys. 12 033023) and Barnum et al (2010 New J. Phys. 12 033024). We prove that if the DPI holds with respect to this generalized entropy measure then the underlying theory necessarily respects Tsirelson's bound. We, moreover, generalize this statement to any entropy measure satisfying certain minimal requirements. A consequence of our result is that not all the entropic relations used for deriving Tsirelson's bound via information causality in Pawlowski et al (2009 Nature 461 1101–4) are necessary.
An intuitive proof of the data processing inequality
N. J. Beaudry; R. Renner
2012
An intuitive proof of the data processing inequality
Type
Journal Article
Author
N. J. Beaudry; R. Renner
Year
2012
Journal
Quantum Information and Computation
Abstract
The data processing inequality (DPI) is a fundamental feature of information theory. Informally it states that you cannot increase the information content of a quantum system by acting on it with a local physical operation. When the smooth min-entropy is used as the relevant information measure, then the DPI follows immediately from the definition of the entropy. The DPI for the von Neumann entropy is then obtained by specializing the DPI for the smooth min-entropy by using the quantum asymptotic equipartition property (QAEP). We provide a short proof of the QAEP and therefore obtain a self-contained proof of the DPI for the von Neumann entropy
F. Dupuis; L. Kraemer; P. Faist; J. M. Renes; R. Renner
2012
Generalized Entropies
Type
Online Database
Author
F. Dupuis; L. Kraemer; P. Faist; J. M. Renes; R. Renner
Year
2012
Abstract
We study an entropy measure for quantum systems that generalizes the von Neumann entropy as well as its classical counterpart, the Gibbs or Shannon entropy. After establishing a few basic properties of this generalized entropy, we show that it is closely related to smooth entropies, a family of entropy measures that is used to characterize a wide range of operational quantities.
In 1960, Ernst Specker showed, in an article written in German and entitled “Die Logik nicht gleichzeitig entscheidbarer Aussagen” (The logic of not simultaneously decidable propositions) that it is impossible to predict the behavior of a quantum-mechanical system under all possible measurements in a consistent and context-independent way. Later, John Bell showed a similar result based on the joint behavior of entangled pairs of particles, and on the assumption of locality instead of non-contextuality. We discuss the relevance and applications of these results. Moreover, we prove a rigorous link between the two lines of reasoning or, equivalently, between the assumptions of non-contextuality – which appears hard to translate to an actual experiment –, versus locality – which can be quite easily guaranteed in practice by a spacelike separation of the measurement events.
Reply to recent scepticism about the foundations of quantum cryptography
R. Renner
2012
Reply to recent scepticism about the foundations of quantum cryptography
Type
Online Database
Author
R. Renner
Year
2012
Abstract
In a series of recent papers, Hirota and Yuen claim to have identified a fundamental flaw in the theory underlying quantum cryptography, which would invalidate existing security proofs. In this short note, we sketch their argument and show that their conclusion is unjustified --- it originates from a confusion between necessary and sufficient criteria for secrecy.
Quantum state tomography is the task of inferring the state of a quantum system by appropriate measurements. Since the frequency distributions of the outcomes of any finite number of measurements will generally deviate from their asymptotic limits, the estimates computed by standard methods do not in general coincide with the true state and, therefore, have no operational significance unless their accuracy is defined in terms of error bounds. Here we show that quantum state tomography, together with an appropriate data analysis procedure, yields reliable and tight error bounds, specified in terms of confidence regions—a concept originating from classical statistics. Confidence regions are subsets of the state space in which the true state lies with high probability, independently of any prior assumption on the distribution of the possible states. Our method for computing confidence regions can be applied to arbitrary measurements including fully coherent ones; it is practical and particularly well suited for tomography on systems consisting of a small number of qubits, which are currently in the focus of interest in experimental quantum information science.
Device-Independent Quantum Key Distribution with Local Bell Test
C. C. W. Lim; C. Portmann; M. Tomamichel; R. Renner; N. Gisin
2012
Device-Independent Quantum Key Distribution with Local Bell Test
Type
Online Database
Author
C. C. W. Lim; C. Portmann; M. Tomamichel; R. Renner; N. Gisin
Year
2012
Abstract
Device-independent quantum key distribution (DIQKD) in its current design requires a violation of Bell's inequality between two honest parties, Alice and Bob, who are connected by a quantum channel. However, in reality, quantum channels are lossy, and this can be exploited for attacks based on the detection loophole. Here, we propose a novel approach to DIQKD that overcomes this limitation. In particular, based on a combination between an entropic uncertainty relation and the Clauser-Horne-Shimony-Holt (CHSH) test, we design a DIQKD protocol where the CHSH test is carried out entirely in Alice's laboratory. Thus the loophole caused by channel losses is avoided.
Towards characterizing the nonlocality of entangled quantum states
R. Renner; S. Wolf
2012
Towards characterizing the nonlocality of entangled quantum states
Type
Journal Article
Author
R. Renner; S. Wolf
Year
2012
Journal
Theoretical Computer Science
Abstract
The behavior of entangled quantum systems can generally not be explained as being determined by shared classical randomness. In the first part of this paper, we propose a simple game for n players demonstrating this non-local property of quantum mechanics: While, on the one hand, it is immediately clear that classical players will lose the game with substantial probability, it can, on the other hand, always be won by players sharing an entangled quantum state. The simplicity of the classical analysis of our game contrasts the often quite involved analysis of previously proposed examples of this type.
In the second part, aiming at a quantitative characterization of the non-locality ofn-partite quantum states, we consider a general class of n-player games, where the amount of communication between certain (randomly chosen) groups of players is measured. Comparing the classical communication needed for both classical players and quantum players (initially sharing a given quantum state) to win such a game, a new type of separation results is obtained. In particular, we show that in order to simulate two separated qubits of an n-partite GHZ state at least Ω(loglogn) bits of information are required.
Achieving the Capacity of any DMC using only Polar Codes
D. Sutter; J. M. Renes; F. Dupuis; R. Renner
2012
Achieving the Capacity of any DMC using only Polar Codes
Type
Conference Proceedings
Author
D. Sutter; J. M. Renes; F. Dupuis; R. Renner
Year of Conference
2012
Conference Name
IEEE Information Theory Workshop
Abstract
We construct a channel coding scheme to achieve the capacity of any discrete memoryless channel based solely on the techniques of polar coding. In particular, we show how source polarization and randomness extraction via polarization can be employed to “shape” uniformly-distributed i.i.d. random variables into approximate i.i.d. random variables distributed according to the capacity-achieving distribution. We then combine this shaper with a variant of polar channel coding, constructed by the duality with source coding, to achieve the channel capacity. Our scheme inherits the low complexity encoder and decoder of polar coding. It differs conceptually from Gallager's method for achieving capacity, and we discuss the advantages and disadvantages of the two schemes. An application to the AWGN channel is discussed.
Landauer's Principle states that the work cost of erasure of one bit of information has a fundamental lower bound of kT ln(2). Here we prove a quantitative Landauer's principle for arbitrary processes, providing a general lower bound on their work cost. This bound is given by the minimum amount of (information theoretical) entropy that has to be dumped into the environment, as measured by the conditional max-entropy. The bound is tight up to a logarithmic term in the failure probability. Our result shows that the minimum amount of work required to carry out a given process depends on how much correlation we wish to retain between the input and the output systems, and that this dependence disappears only if we average the cost over many independent copies of the input state. Our proof is valid in a general framework that specifies the set of possible physical operations compatible with the second law of thermodynamics. We employ the technical toolbox of matrix majorization, which we extend and generalize to a new kind of majorization, called lambda-majorization. This allows us to formulate the problem as a semidefinite program and provide an optimal solution.
International Conference on Information Theoretic Security
Abstract
Randomness extraction is the art of distilling almost perfectly random bits from an entropy source. Since the source can generally be considered as one that emits classical data, randomness extraction is usually analyzed within the framework of classical probability theory. However, it has been realized recently that this classical treatment is limited: it does not cover situations where the source|while still emitting classical data|is correlated to quantum side information. Here, we review some recent work that overcomes this limitation.
Uncertainty relations give upper bounds on the accuracy by which the outcomes of two incompatible measurements can be predicted. While established uncertainty relations apply to cases where the predictions are based on purely classical data (e.g., a description of the system’s state before measurement), an extended relation which remains valid in the presence of quantum information has been proposed recently [Berta et al., Nature Phys. 6, 659 (2010)]. Here, we generalize this uncertainty relation to one formulated in terms of smooth entropies. Since these entropies measure operational quantities such as extractable secret key length, our uncertainty relation is of immediate practical use. To illustrate this, we show that it directly implies security of quantum key distribution protocols. Our security claim remains valid even if the implemented measurement devices deviate arbitrarily from the theoretical model.
In the spirit of algebraic abstraction, this paper advocates the definition and use of higher levels of abstraction in cryptography (and beyond). If contrasted with the standard bottom-up approach to defining models of computation, algorithms, complexity, efficiency, and then security of cryptographic schemes, our approach is top-down and axiomatic, where lower abstraction levels inherit the definitions and theorems (e.g. a composition theorem) from the higher level, but the definition or concretization of low levels is not required for proving theorems at the higher levels. The goal is to strive for simpler definitions, higher generality of results, simpler proofs, improved elegance, possibly better didactic suitability, and to derive new insights from the abstract viewpoint. In particular, we propose a general framework for defining and proving that a system satisfying an (abstract or ideal) specification is constructed from some systems satisfying certain (concrete or real) specifications. This puts the well-known “ideal-world real-world” paradigm on a new theoretical foundation, applicable in various cryptographic settings. Existing frameworks for proving composable security can be explained as special cases of our framework, thereby allowing to distinguish between relevant and less relevant aspects of the underlying technical definitions and to prove a single common composition theorem. Some properties of our framework are as follows. It is independent of particular models of computation, communication, and adversary behavior. It can be instantiated in many different ways, for example to arrive at different notions of security or of efficiency and infeasibility. It can precisely capture settings with no central adversary where entities have potentially conflicting goals (e.g. a coercion scenario). The relation between the ideal and the real setting is tight, via an isomorphism notion for settings. The (desired) asymmetry between real and ideal is captured in a formal abstraction notion (the ideal setting is an abstraction of the real setting). A main theorem states that such an abstraction statement can be proved by using local (as opposed to monolithic) simulators.
No extension of quantum theory can have improved predictive power
R. Colbeck; R. Renner
2011
No extension of quantum theory can have improved predictive power
Type
Journal Article
Author
R. Colbeck; R. Renner
Year
2011
Journal
Nature Communications
Abstract
According to quantum theory, measurements generate random outcomes, in stark contrast with classical mechanics. This raises the question of whether there could exist an extension of the theory which removes this indeterminism, as suspected by Einstein, Podolsky and Rosen (EPR). Although this has been shown to be impossible, existing results do not imply that the current theory is maximally informative. Here we ask the more general question of whether any improved predictions can be achieved by any extension of quantum theory. Under the assumption that measurements can be chosen freely, we answer this question in the negative: no extension of quantum theory can give more information about the outcomes of future measurements than quantum theory itself. Our result has significance for the foundations of quantum mechanics, as well as applications to tasks that exploit the inherent randomness in quantum theory, such as quantum cryptography.
We explore the possibility of passive error correction in the toric code model. We first show that even coherent dynamics, stemming from spin interactions or the coupling to an external magnetic field, lead to logical errors. We then argue that Anderson localization of the defects, arising from unavoidable fluctuations of the coupling constants, provides a remedy. This protection is demonstrated by using general analytical arguments that are complemented with numerical results which show that self-correcting memory can in principle be achieved in the limit of a nonzero density of identical defects.
Sampling of min-entropy relative to quantum knowledge
R. Koenig; R. Renner
2011
Sampling of min-entropy relative to quantum knowledge
Type
Journal Article
Author
R. Koenig; R. Renner
Year
2011
Journal
IEEE Transactions on Information Theory
Abstract
Let X_1, ..., X_n be a sequence of n classical random variables and consider a sample of r positions selected at random. Then, except with (exponentially in r) small probability, the min-entropy of the sample is not smaller than, roughly, a fraction r/n of the total min-entropy of all positions X_1, ..., X_n, which is optimal. Here, we show that this statement, originally proven by Vadhan [LNCS, vol. 2729, Springer, 2003] for the purely classical case, is still true if the min-entropy is measured relative to a quantum system. Because min-entropy quantifies the amount of randomness that can be extracted from a given random variable, our result can be used to prove the soundness of locally computable extractors in a context where side information might be quantum-mechanical. In particular, it implies that key agreement in the bounded-storage model (using a standard sample-and-hash protocol) is fully secure against quantum adversaries, thus solving a long-standing open problem.
Inadequacy of von Neumann entropy for characterizing extractable work
O. C. O. Dahlsten; R. Renner; E. Rieper; V. Vedral
2011
Inadequacy of von Neumann entropy for characterizing extractable work
Type
Journal Article
Author
O. C. O. Dahlsten; R. Renner; E. Rieper; V. Vedral
Year
2011
Journal
New Journal of Physics
Abstract
The lack of knowledge that an observer has about a system limits the amount of work it can extract. This lack of knowledge is normally quantified using the Gibbs/von Neumann entropy. We show that this standard approach is, surprisingly, only correct in very specific circumstances. In general, one should use the recently developed smooth entropy approach. For many common physical situations, including large but internally correlated systems, the resulting values for the extractable work can deviate arbitrarily from those suggested by the standard approach.
Quantum key distribution (QKD) is often, more correctly, called key growing. Given a short key as a seed, QKD enables two parties, connected by an insecure quantum channel, to generate a secret key of arbitrary length. Conversely, no key agreement is possible without access to an initial key. Here, we consider another fundamental cryptographic task, commitments. While, similar to key agreement, commitments cannot be realized from scratch, we ask whether they may be grown. That is, given the ability to commit to a fixed number of bits, is there a way to augment this to commitments to strings of arbitrary length? Using recently developed information-theoretic techniques, we answer this question in the negative.
The Quantum Reverse Shannon Theorem based on One-Shot Information Theory
M. Berta; M. Christandl; R. Renner
2011
The Quantum Reverse Shannon Theorem based on One-Shot Information Theory
Type
Journal Article
Author
M. Berta; M. Christandl; R. Renner
Year
2011
Journal
Communications in Mathematical Physics
Abstract
The Quantum Reverse Shannon Theorem states that any quantum channel can be simulated by an unlimited amount of shared entanglement and an amount of classical communication equal to the channel’s entanglement assisted classical capacity. In this paper, we provide a new proof of this theorem, which has previously been proved by Bennett, Devetak, Harrow, Shor, and Winter. Our proof has a clear structure being based on two recent information-theoretic results: one-shot Quantum State Merging and the Post-Selection Technique for quantum channels.
Consider a bipartite system, of which one subsystem, A, undergoes a physical evolution separated from the other subsystem, R. We are interested in conditions under which this evolution destroys all initial correlations between the subsystems A and R, i.e. decouples the subsystems. Quantitatively this is done in terms of decoupling theorems. Such theorems have proven useful in various applications in the area of quantum information theory. This paper builds on preceding work, which shows that decoupling can be achieved by applying a typical unitary on A chosen with respect to the Haar measure followed by a process that adds sufficient decoherence. Here, we prove a generalized decoupling theorem for the case where the unitary is chosen from an almost two-design. A main implication of this result is that decoupling is physical, in the sense that it can be achieved by short sequences of random two-body interactions, which can be modeled as efficient circuits. We discuss applications of this result.
The Leftover Hash Lemma states that the output of a two-universal hash function applied to an input with sufficiently high entropy is almost uniformly random. In its standard formulation, the lemma refers to a notion of randomness that is (usually implicitly) defined with respect to classical side information. Here, a strictly more general version of the Leftover Hash Lemma that is valid even if side information is represented by the state of a quantum system is shown. Our result applies to almost two-universal families of hash functions. The generalized Leftover Hash Lemma has applications in cryptography, e.g., for key agreement in the presence of an adversary who is not restricted to classical information processing.
Noisy channel coding via privacy amplification and information reconciliation
J. M. Renes; R. Renner
2011
Noisy channel coding via privacy amplification and information reconciliation
Type
Journal Article
Author
J. M. Renes; R. Renner
Year
2011
Journal
IEEE Transactions on Information Theory
Abstract
We show that optimal protocols for noisy channel coding of public or private information over either classical or quantum channels can be directly constructed from two more primitive information-theoretic protocols: privacy amplification and information reconciliation, also known as data compression with side information. We do this in the one-shot scenario of structureless resources, and formulate our results in terms of the smooth min- and max-entropy. In the context of classical information theory, this shows that essentially all two-terminal protocols can be reduced to these two primitives, which are in turn governed by the smooth min- and max-entropies, respectively. In the context of quantum information theory, the recently-established duality of these two protocols means essentially all two-terminal protocols can be constructed using just a single primitive. As an illustration, we show how optimal noisy channel coding protocols can be constructed solely from privacy amplification.
We consider an extension of the conditional min- and max-entropies to infinite-dimensional separable Hilbert spaces. We show that these satisfy characterizing properties known from the finite-dimensional case, and retain information-theoretic operational interpretations, e.g., the min-entropy as maximum achievable quantum correlation, and the max-entropy as decoupling accuracy. We furthermore generalize the smoothed versions of these entropies and prove an infinite-dimensional quantum asymptotic equipartition property. To facilitate these generalizations we show that the min- and max-entropy can be expressed in terms of convergent sequences of finite-dimensional min- and max-entropies, which provides a convenient technique to extend proofs from the finite to the infinite-dimensional setting.
L. del Rio; J. Åberg; R. Renner; O. Dahlsten; V. Vedral
2011
The thermodynamic meaning of negative entropy
Type
Journal Article
Author
L. del Rio; J. Åberg; R. Renner; O. Dahlsten; V. Vedral
Year
2011
Journal
Nature
Abstract
Landauer's erasure principle exposes an intrinsic relation between thermodynamics and information theory: the erasure of information stored in a system, S, requires an amount of work proportional to the entropy of that system. This entropy, H(S|O), depends on the information that a given observer, O, has about S, and the work necessary to erase a system may therefore vary for different observers. Here, we consider a general setting where the information held by the observer may be quantum-mechanical, and show that an amount of work proportional to H(S|O) is still sufficient to erase S. Since the entropy H(S|O) can now become negative, erasing a system can result in a net gain of work (and a corresponding cooling of the environment).
A Conceptually Simple Proof of the Quantum Reverse Shannon Theorem
M. Berta; M. Christandl; R. Renner
2010
A Conceptually Simple Proof of the Quantum Reverse Shannon Theorem
Type
Conference Proceedings
Author
M. Berta; M. Christandl; R. Renner
Year of Conference
2010
Publisher
Springer
Conference Name
Theory of Quantum Computation, Communication, and Cryptography - TQC 2010
Abstract
The Quantum Reverse Shannon Theorem states that any quantum channel can be simulated by an unlimited amount of shared entanglement and an amount of classical communication equal to the channel’s entanglement assisted classical capacity. In this extended ab- stract, we summarize a new and conceptually simple proof of this theorem [journal reference: arXiv.org:quant-ph/0912.3805], which has previously been proved in [Bennett et al., arXiv.org:quant-ph/0912.5537]. Our proof is based on optimal one-shot Quantum State Merging and the Post-Selection Technique for quantum channels.
The uncertainty principle in the presence of quantum memory
M. Berta; M. Christandl; R. Colbeck; J. M. Renes; R. Renner
2010
The uncertainty principle in the presence of quantum memory
Type
Journal Article
Author
M. Berta; M. Christandl; R. Colbeck; J. M. Renes; R. Renner
Year
2010
Journal
Nature Physics
Abstract
The uncertainty principle, originally formulated by Heisenberg, clearly illustrates the difference between classical and quantum mechanics. The principle bounds the uncertainties about the outcomes of two incompatible measurements, such as position and momentum, on a particle. It implies that one cannot predict the outcomes for both possible choices of measurement to arbitrary precision, even if information about the preparation of the particle is available in a classical memory. However, if the particle is prepared entangled with a quantum memory, a device that might be available in the not-too-distant future, it is possible to predict the outcomes for both measurement choices precisely. Here, we extend the uncertainty principle to incorporate this case, providing a lower bound on the uncertainties, which depends on the amount of entanglement between the particle and the quantum memory. We detail the application of our result to witnessing entanglement and to quantum key distribution.
Device-Independent Quantum Key Distribution with Commuting Measurements
E. Haenggi; R. Renner
2010
Device-Independent Quantum Key Distribution with Commuting Measurements
Type
Online Database
Author
E. Haenggi; R. Renner
Year
2010
Abstract
We consider quantum key distribution in the device-independent scenario, i.e., where the legitimate parties do not know (or trust) the exact specification of their apparatus. We show how secure key distribution can be realized against the most general attacks by a quantum adversary under the condition that measurements on different subsystems by the honest parties commute.
In classical and quantum information theory, operational quantities such as the amount of randomness that can be extracted from a given source or the amount of space needed to store given data are normally characterized by one of two entropy measures, called smooth min-entropy and smooth max-entropy, respectively. While both entropies are equal to the von Neumann entropy in certain special cases (e.g., asymptotically, for many independent repetitions of the given data), their values can differ arbitrarily in the general case. In this paper, a recently discovered duality relation between (nonsmooth) min- and max-entropies is extended to the smooth case. More precisely, it is shown that the smooth min-entropy of a system $A$ conditioned on a system $B$ equals the negative of the smooth max-entropy of $A$ conditioned on a purifying system $C$. This result immediately implies that certain operational quantities (such as the amount of compression and the amount of randomness that can be extracted from given data) are related. We explain how such relations have applications in cryptographic security proofs.
Efficient Device-Independent Quantum Key Distribution
E. Haenggi; R. Renner; S. Wolf
2010
Efficient Device-Independent Quantum Key Distribution
Type
Conference Proceedings
Author
E. Haenggi; R. Renner; S. Wolf
Year of Conference
2010
Publisher
Springer
Conference Name
Advances in Cryptology - EUROCRYPT 2010
Abstract
An efficient protocol for quantum key distribution is proposed the security of which is entirely device-independent and not even based on the accuracy of quantum physics. A scheme of that type relies on the quantum-physical phenomenon of non-local correlations and on the assumption that no illegitimate information flows within and between Alice’s and Bob’s laboratories. The latter can be enforced via the non-signaling postulate of relativity if all measurements are carried out simultaneously enough.
If a quantum system A, which is initially correlated to another system, E, undergoes an evolution separated from E, then the correlation to E generally decreases. Here, we study the conditions under which the correlation disappears completely, resulting in a decoupling of A from E. We give a criterion for decoupling in terms of two smooth entropies, one quantifying the amount of initial correlation between A and E, and the other characterizing the mapping that describes the evolution of A. The criterion applies to arbitrary such mappings and is tight if the mapping satisfies certain natural conditions. Decoupling has a number of applications both in physics and information theory, e.g., as a building block for quantum information processing protocols. As an example, we give a one-shot state merging protocol and show that it is essentially optimal in terms of its entanglement consumption/production.
Simplifying information-theoretic arguments by post-selection
R. Renner
2010
Simplifying information-theoretic arguments by post-selection
Type
Conference Proceedings
Author
R. Renner
Year of Conference
2010
Publisher
IOS Press
Conference Name
NATO Advanced Research Workshop Quantum Cryptography and Computing: Theory and Implementation
Abstract
Devices and protocols for information processing are often required to work for arbitrary inputs. For example, in channel coding theory, one demands that a coding scheme transmits any possible input state reliably over a given noisy channel. Similarly, in quantum cryptography, security of a protocol should hold independently of the inputs, even if they are chosen maliciously. In this short paper, we review the Post-Selection Technique introduced in (Phys. Rev. Lett. 102:020504, 2009). Its main purpose is to simplify the analysis of information processing schemes so that only one single input needs to be considered. If a scheme satisfies a desired criterion when acting on this particular input, then—under certain symmetry conditions—the same criterion is automatically met for arbitrary inputs. We illustrate the Post-Selection Technique at the example of quantum cryptography. Here, it can be used to show that security of a Quantum Key Distribution scheme against general attacks—somewhat surprisingly—follows from its security against one specific attack. This not only simplifies security proofs, but also has other remarkable implications, e.g., that no randomness is needed for privacy amplification.
Leftover Hashing against quantum side information (short version)
M. Tomamichel; R. Renner; C. Schaffner; A. Smith
2010
Leftover Hashing against quantum side information (short version)
Type
Conference Proceedings
Author
M. Tomamichel; R. Renner; C. Schaffner; A. Smith
Year of Conference
2010
Conference Name
IEEE International Symposium on Information Theory
Abstract
The Leftover Hash Lemma states that the output of a two-universal hash function applied to an input with sufficiently high entropy is almost uniformly random. In its standard formulation, the lemma refers to a notion of randomness that is (usually implicitly) defined with respect to classical side information. Here, we prove a (strictly) more general version of the Leftover Hash Lemma that is valid even if side information is represented by the state of a quantum system. Furthermore, our result applies to arbitrary δ-almost two-universal families of hash functions. The generalized Leftover Hash Lemma has applications in cryptography, e.g., for key agreement in the presence of an adversary who is not restricted to classical information processing.
Postselection Technique for Quantum Channels with Applications to Quantum Cryptography
M. Christandl; R. Koenig; R. Renner
2009
Postselection Technique for Quantum Channels with Applications to Quantum Cryptography
Type
Journal Article
Author
M. Christandl; R. Koenig; R. Renner
Year
2009
Journal
Physical Review Letters
Abstract
We propose a general method for studying properties of quantum channels acting on an n-partite system, whose action is invariant under permutations of the subsystems. Our main result is that, in order to prove that a certain property holds for any arbitrary input, it is sufficient to consider the special case where the input is a particular de Finetti-type state, i.e., a state which consists of n identical and independent copies of an (unknown) state on a single subsystem. A similar statement holds for more general channels which are covariant with respect to the action of an arbitrary finite or locally compact group. Our technique can be applied to the analysis of information-theoretic problems. For example, in quantum cryptography, we get a simple proof for the fact that security of a discrete-variable quantum key distribution protocol against collective attacks implies security of the protocol against the most general attacks. The resulting security bounds are tighter than previously known bounds obtained by proofs relying on the exponential de Finetti theorem [Renner, Nature Physics 3,645(2007)]
Defining the local part of a hidden variable model: a comment
R. Colbeck; R. Renner
2009
Defining the local part of a hidden variable model: a comment
Type
Online Database
Author
R. Colbeck; R. Renner
Year
2009
Abstract
In [Physical Review Letters 101, 050403 (2008)], we showed that quantum theory cannot be explained by a hidden variable model with a non-trivial local part. The purpose of this comment is to clarify our notion of local part, which seems to have caused some confusion in the recent literature. This notion is based on Bell's and demands that local hidden variables are physical, the idea being that, if discovered, they would not contradict basic physical principles. We explain why the recent supposed"counterexamples"that have appeared are not counterexamples to our theorem--in fact they are based on a definition of local hidden variables which would allow signaling and is therefore not physical.
XVI International Congress on Mathematical Physics
Abstract
Given a bipartite quantum system with parts A and R, we say that a mapping EE applied to A decouples A from R if the outcome EE of is uncorrelated to R. The notion of decoupling plays a crucial role in various information-theoretic arguments and is also used for foundational considerations in the context of statistical mechanics. Here, we consider decoupling operations EE which take the form of projective measurements. We review a recent result which shows that a randomly chosen projective measurement achieves decoupling if and only if a certain entropic quantity, called smooth entropy, is sufficiently large. Furthermore, the random choice is almost always optimal.
IEEE International Symposium on Information Theory
Abstract
New channel coding converse and achievability bounds are derived for a single use of an arbitrary channel. Both bounds are expressed using a quantity called the"smooth 0-divergence", which is a generalization of Renyi's divergence of order 0. The bounds are also studied in the limit of large block-lengths. In particular, they combine to give a general capacity formula which is equivalent to the one derived by Verdu and Han.
Smooth Entropies and the Quantum Information Spectrum
N. Datta; R. Renner
2009
Smooth Entropies and the Quantum Information Spectrum
Type
Journal Article
Author
N. Datta; R. Renner
Year
2009
Journal
IEEE Transactions on Information Theory
Abstract
Many of the traditional results in information theory, such as the channel coding theorem or the source coding theorem, are restricted to scenarios where the underlying resources are independent and identically distributed (i.i.d.) over a large number of uses. To overcome this limitation, two different techniques, the information spectrum method and the smooth entropy framework, have been developed independently. They are based on new entropy measures, called spectral entropy rates and smooth entropies, respectively, that generalize Shannon entropy (in the classical case) and von Neumann entropy (in the more general quantum case). Here, we show that the two techniques are closely related. More precisely, the spectral entropy rate can be seen as the asymptotic limit of the smooth entropy. Our results apply to the quantum setting and thus include the classical setting as a special case.
In this paper, we show that the conditional min-entropy H min(A |B) of a bipartite state rhoAB is directly related to the maximum achievable overlap with a maximally entangled state if only local actions on the B-part of rhoAB are allowed. In the special case where A is classical, this overlap corresponds to the probability of guessing A given B. In a similar vein, we connect the conditional max-entropy H max(A |B) to the maximum fidelity of rhoAB with a product state that is completely mixed on A. In the case where A is classical, this corresponds to the security of A when used as a secret key in the presence of an adversary holding B. Because min- and max-entropies are known to characterize information-processing tasks such as randomness extraction and state merging, our results establish a direct connection between these tasks and basic operational problems. For example, they imply that the (logarithm of the) probability of guessing A given B is a lower bound on the number of uniform secret bits that can be extracted from A relative to an adversary holding B.
In this article, we review several aspects of composability in the context of quantum cryptography. The first part is devoted to key distribution. We discuss the security criteria that a quantum key distribution protocol must fulfill to allow its safe use within a larger security application (e.g., for secure message transmission). To illustrate the practical use of composability, we show how to generate a continuous key stream by sequentially composing rounds of a quantum key distribution protocol. In a second part, we take a more general point of view, which is necessary for the study of cryptographic situations involving, for example, mutually distrustful parties. We explain the universal composability framework and state the composition theorem which guarantees that secure protocols can securely be composed to larger applications
de Finetti Representation Theorem for Infinite-Dimensional Quantum Systems and Applications to Quantum Cryptography
R. Renner; J. I. Cirac
2009
de Finetti Representation Theorem for Infinite-Dimensional Quantum Systems and Applications to Quantum Cryptography
Type
Journal Article
Author
R. Renner; J. I. Cirac
Year
2009
Journal
Physical Review Letters
Abstract
We show that the quantum de Finetti theorem holds for states on infinite-dimensional systems, provided they satisfy certain experimentally verifiable conditions. This result can be applied to prove the security of quantum key distribution based on weak coherent states or other continuous variable states against general attacks.
Space-quest, experiments with quantum entanglement in space
R. Ursin et al. (int. al. R. Renner)
2009
Space-quest, experiments with quantum entanglement in space
Type
Journal Article
Author
R. Ursin et al. (int. al. R. Renner)
Year
2009
Journal
Europhysics News
Abstract
The European Space Agency (ESA) has supported a range of studies in the field of quantum physics and quantum information science in space for several years, and consequently we have submitted the mission proposal Space-QUEST (Quantum Entanglement for Space Experiments) to the European Life and Physical Sciences in Space Program. We propose to perform space-to-ground quantum communication tests from the International Space Station (ISS). We present the proposed experiments in space as well as the design of a space based quantum communication payload.
The classical asymptotic equipartition property is the statement that, in the limit of a large number of identical repetitions of a random experiment, the output sequence is virtually certain to come from the typical set, each member of which is almost equally likely. In this paper, a fully quantum generalization of this property is shown, where both the output of the experiment and side information are quantum. An explicit bound on the convergence is given, which is independent of the dimensionality of the side information. This naturally leads to a family of REacutenyi-like quantum conditional entropies, for which the von Neumann entropy emerges as a special case.
The Encyclopedia of Algorithms provides a comprehensive set of solutions to important algorithmic problems for students and researchers, including high-impact solutions from the most recent decade. A must-have for computer scientists, this encyclopedic reference has been edited by Ming Yang Kao, Editor-in-Chief of the top journal in the field, Algorithmica. All of the entries have been written and peer-reviewed by experts in the field. Nearly 400 entries are organized alphabetically by problem, with subentries for distinct solutions. Extensive cross-references support efficient, user-friendly searches for immediate access to useful information. This defining reference is published both in print and online. The print publication includes an index of subjects and authors as well as a chronology for locating recent solutions. The online edition supplements this index with hyperlinks as well as including internal hyperlinks to related entries in the text, CrossRef citations, and links to additional significant research. Open problems, links to downloadable code, experimental results, data sets, and illustrations are included.
Extracting classical randomness in a quantum world
R. Renner
2008
Extracting classical randomness in a quantum world
Type
Conference Proceedings
Author
R. Renner
Year of Conference
2008
Conference Name
IEEE Information Theory Workshop
Abstract
Extractors are functions that transform a weakly random value X into an almost perfectly uniform value Z. Traditionally, extractors have been studied in a context where the side information, relative to which the distributions of X and Z are defined, is purely classical. Only recently, the notion of extractors has been generalized to scenarios where side information might be represented by the state of a quantum-mechanical system (while X and Z are still classical). This generalization is crucial for numerous applications, e.g., in cryptography, where an adversary might hold quantum-mechanical side information. In this article, we review this generalized notion of extractors as well as a construction of extractors based on two-universal hashing.
Hidden Variable Models for Quantum Theory Cannot Have Any Local Part
R. Colbeck; R. Renner
2008
Hidden Variable Models for Quantum Theory Cannot Have Any Local Part
Type
Journal Article
Author
R. Colbeck; R. Renner
Year
2008
Journal
Physical Review Letters
Abstract
It was shown by Bell that no local hidden variable model is compatible with quantum mechanics. If, instead, one permits the hidden variables to be entirely nonlocal, then any quantum mechanical predictions can be recovered. In this Letter, we consider general hidden variable models which can have both local and nonlocal parts. We show the existence of (experimentally verifiable) quantum correlations that are incompatible with any hidden variable model having a nontrivial local part, such as the model proposed by Leggett.
Quantum Cryptography with Finite Resources: Unconditional Security Bound for Discrete-Variable Protocols with One-Way Postprocessing
V. Scarani; R. Renner
2008
Quantum Cryptography with Finite Resources: Unconditional Security Bound for Discrete-Variable Protocols with One-Way Postprocessing
Type
Journal Article
Author
V. Scarani; R. Renner
Year
2008
Journal
Physical Review Letters
Abstract
We derive a bound for the security of quantum key distribution with finite resources under one-way postprocessing, based on a definition of security that is composable and has an operational meaning. While our proof relies on the assumption of collective attacks, unconditional security follows immediately for standard protocols such as Bennett-Brassard 1984 and six-states protocol. For single-qubit implementations of such protocols, we find that the secret key rate becomes positive when at least N∼105 signals are exchanged and processed. For any other discrete-variable protocol, unconditional security can be obtained using the exponential de Finetti theorem, but the additional overhead leads to very pessimistic estimates.
Security Bounds for Quantum Cryptography with Finite Resources
V. Scarani; R. Renner
2008
Security Bounds for Quantum Cryptography with Finite Resources
Type
Book Section
Author
V. Scarani; R. Renner
Year
2008
Publisher
Springer
Abstract
A practical quantum key distribution (QKD) protocol necessarily runs in finite time and, hence, only a finite amount of communication is exchanged. This is in contrast to most of the standard results on the security of QKD, which only hold in the limit where the number of transmitted signals approaches infinity. Here, we analyze the security of QKD under the realistic assumption that the amount of communication is finite. At the level of the general formalism, we present new results that help simplifying the actual implementation of QKD protocols: in particular, we show that symmetrization steps, which are required by certain security proofs (e.g., proofs based on de Finetti’s representation theorem), can be omitted in practical implementations. Also, we demonstrate how two-way reconciliation protocols can be taken into account in the security analysis. At the level of numerical estimates, we present the bounds with finite resources for “device-independent security” against collective attacks.
M. Christandl; A. Ekert; M. Horodecki; P. Horodecki; J. Oppenheim; R. Renner
2007
Unifying classical and quantum key distillation
Type
Conference Proceedings
Author
M. Christandl; A. Ekert; M. Horodecki; P. Horodecki; J. Oppenheim; R. Renner
Year of Conference
2007
Publisher
Springer
Conference Name
Theory of Cryptography
Abstract
Assume that two distant parties, Alice and Bob, as well as an adversary, Eve, have access to (quantum) systems prepared jointly according to a tripartite state. In addition, Alice and Bob can use local operations and authenticated public classical communication. Their goal is to establish a key which is unknown to Eve. We initiate the study of this scenario as a unification of two standard scenarios: (i) key distillation (agreement) from classical correlations and (ii) key distillation from pure tripartite quantum states. Firstly, we obtain generalisations of fundamental results related to scenarios (i) and (ii), including upper bounds on the key rate. Moreover, based on an embedding of classical distributions into quantum states, we are able to find new connections between protocols and quantities in the standard scenarios (i) and (ii). Secondly, we study specific properties of key distillation protocols. In particular, we show that every protocol that makes use of pre-shared key can be transformed into an equally efficient protocol which needs no pre-shared key. This result is of practical significance as it applies to quantum key distribution (QKD) protocols, but it also implies that the key rate cannot be locked with information on Eve's side. Finally, we exhibit an arbitrarily large separation between the key rate in the standard setting where Eve is equipped with quantum memory and the key rate in a setting where Eve is only given classical memory. This shows that assumptions on the nature of Eve's memory are important in order to determine the correct security threshold in QKD.
A Tight High-Order Entropic Quantum Uncertainty Relation with Applications
I. B. Damgaard; S. Fehr; R. Renner; L. Salvail; C. Schaffner
2007
A Tight High-Order Entropic Quantum Uncertainty Relation with Applications
Type
Conference Proceedings
Author
I. B. Damgaard; S. Fehr; R. Renner; L. Salvail; C. Schaffner
Year of Conference
2007
Publisher
Springer
Conference Name
Advances in Cryptology - CRYPTO 2007
Abstract
We derive a new entropic quantum uncertainty relation involving min-entropy. The relation is tight and can be applied in various quantum-cryptographic settings. Protocols for quantum 1-out-of-2 Oblivious Transfer and quantum Bit Commitment are presented and the uncertainty relation is used to prove the security of these protocols in the bounded quantum-storage model according to new strong security definitions. As another application, we consider the realistic setting of Quantum Key Distribution (QKD) against quantum-memory-bounded eavesdroppers. The uncertainty relation allows to prove the security of QKD protocols in this setting while tolerating considerably higher error rates compared to the standard model with unbounded adversaries. For instance, for the six-state protocol with one-way communication, a bit-flip error rate of up to 17% can be tolerated (compared to 13% in the standard model). Our uncertainty relation also yields a lower bound on the min-entropy key uncertainty against known-plaintext attacks when quantum ciphers are composed. Previously, the key uncertainty of these ciphers was only known with respect to Shannon entropy.
SECOQC White Paper on Quantum Key Distribution and Cryptography
R. Alleaume et al. (int. al. R. Renner)
2007
SECOQC White Paper on Quantum Key Distribution and Cryptography
Type
Online Database
Author
R. Alleaume et al. (int. al. R. Renner)
Year
2007
Abstract
The SECOQC White Paper on Quantum Key Distribution and Cryptography is the outcome on a thorough consultation and discussion among the participants of the European project SECOQC (www.secoqc.net). This paper is a review article that attempts to position Quantum Key Distribution (QKD) in terms of cryptographic applications. A detailed comparison of QKD with the solutions currently in use to solve the key distribution problem, based on classical cryptography, is provided. We also detail how the work on QKD networks lead within SECOQC will allow the deployment of long-distance secure communication infrastructures based on quantum cryptography. The purpose of the White Paper is finally to promote closer collaboration between classical and quantum cryptographers. We believe that very fruitful research, involving both communities, could emerge in the future years and try to sketch what may be the next challenges in this direction.
We prove a new kind of quantum de Finetti theorem for representations of the unitary group U(d). Consider a pure state that lies in the irreducible representation U_{mu+nu} for Young diagrams mu and nu. U_{mu+nu} is contained in the tensor product of U_mu and U_nu; let xi be the state obtained by tracing out U_nu. We show that xi is close to a convex combination of states Uv, where U is in U(d) and v is the highest weight vector in U_mu. When U_{mu+nu} is the symmetric representation, this yields the conventional quantum de Finetti theorem for symmetric states, and our method of proof gives near-optimal bounds for the approximation of xi by a convex combination of product states. For the class of symmetric Werner states, we give a second de Finetti-style theorem (our'half'theorem); the de Finetti-approximation in this case takes a particularly simple form, involving only product states with a fixed spectrum. Our proof uses purely group theoretic methods, and makes a link with the shifted Schur functions. It also provides some useful examples, and gives some insight into the structure of the set of convex combinations of product states.
Small Accessible Quantum Information Does Not Imply Security
R. Koenig; R. Renner; A. Bariska; U. Maurer
2007
Small Accessible Quantum Information Does Not Imply Security
Type
Journal Article
Author
R. Koenig; R. Renner; A. Bariska; U. Maurer
Year
2007
Journal
Physical Review Letters
Abstract
The security of quantum key distribution is typically defined in terms of the mutual information between the distributed key S and the outcome of an optimal measurement applied to the adversary’s system. We show that even if this so-called accessible information is small, the key S might not be secure enough to be used in applications such as one-time pad encryption. This flaw is due to a locking property of the accessible information: one additional (physical) bit of information can increase the accessible information by more than one bit.
Security of quantum-key-distribution protocols using two-way classical communication or weak coherent pulses
B. Kraus; C. Branciard; R. Renner
2007
Security of quantum-key-distribution protocols using two-way classical communication or weak coherent pulses
Type
Journal Article
Author
B. Kraus; C. Branciard; R. Renner
Year
2007
Journal
Physical Review A
Abstract
We apply the techniques introduced by Kraus et al. [Phys. Rev. Lett. 95, 080501 (2005)] to prove security of quantum-key-distribution (QKD) schemes using two-way classical post-processing as well as QKD schemes based on weak coherent pulses instead of single-photon pulses. As a result, we obtain improved bounds on the secret-key rate of these schemes. For instance, for the six-state protocol using two-way classical post-processing we recover the known threshold for the maximum tolerated bit error rate of the channel, 0.276, but demonstrate that the secret-key rate can be substantially higher than previously shown. Moreover, we provide a detailed analysis of the Bennett-Brassard 1984 (BB84) and the SARG protocol using weak coherent pulses (with and without decoy states) in the so-called untrusted-device scenario, where the adversary might influence the detector efficiencies. We evaluate lower bounds on the secret-key rate for realistic channel parameters and show that, for channels with low noise level, the bounds for the SARG protocol are superior to those for the BB84 protocol, whereas this advantage disappears with increasing noise level.
Symmetry of large physical systems implies independence of subsystems
R. Renner
2007
Symmetry of large physical systems implies independence of subsystems
Type
Journal Article
Author
R. Renner
Year
2007
Journal
Nature Physics
Abstract
Composite systems consisting of a large number of similar subsystems play an important role in many areas of physics as well as in information theory. Their analysis, however, often relies on the assumption that the subsystems are mutually independent (or only weakly correlated). Here, we show that this assumption is generally justified for quantum systems that are symmetric, that is, invariant under permutations of the subsystems. Because symmetry is often implied by natural properties, for example, the indistinguishability of identical particles, the result has a wide range of consequences. In particular, it implies that global properties of a large composite system can be estimated by measurements applied to a limited number of (randomly chosen) sample subsystems, a fact that is important for the interpretation of experimental data. Moreover, it generalizes statements in quantum information theory and cryptography, which previously have only been known to hold under certain independence assumptions.
Beweisbare Sicherheit durch Quantenkryptografie (Provable Security in Quantum Cryptography)
R. Renner
2007
Beweisbare Sicherheit durch Quantenkryptografie (Provable Security in Quantum Cryptography)
Type
Journal Article
Author
R. Renner
Year
2007
Journal
it - Information Technology
Abstract
Die Sicherheit heutiger kryptografischer Verfahren beruht meist auf der nicht beweisbaren Annahme, dass einem Gegner nur beschränkte Rechenleistung zur Verfügung steht. Im Gegensatz dazu bietet die Quantenkryptografie, die quantenmechanische Eigenschaften kleinster Teilchen wie zum Beispiel Photonen nutzt, beweisbare Sicherheit. Dieser Artikel erläutert die Funktionsweise dieser neuartigen Technik. The security of established cryptographic schemes mostly relies on the non-provable assumption that a potential adversary only has limited computational power. In contrast, quantum cryptography provides provable security, using properties of small particles such as photons. In this article we explain how this new technique works.
Trade-Offs in Information-Theoretic Multi-Party One-Way Key Agreement
R. Renner; S. Wolf; J. Wullschleger
2007
Trade-Offs in Information-Theoretic Multi-Party One-Way Key Agreement
Type
Conference Proceedings
Author
R. Renner; S. Wolf; J. Wullschleger
Year of Conference
2007
Publisher
Springer
Conference Name
International Conference on Information Theoretic Security
Abstract
We consider the following scenario involving three honest parties, Alice, Bob, and Carol, as well as an adversary, Eve. Each party has access to a single piece of information, jointly distributed according to some distribution P. Additionally, authentic public communication is possible from Alice to Carol and from Bob to Carol. Their goal is to establish two information-theoretically secret keys, one known to Alice and Carol, and one known to Bob and Carol. We derive joint bounds on the lengths of these keys. Our protocols combine distributed variants of Slepian-Wolf coding and the leftover hash lemma. The obtained bounds are expressed in terms of smooth Rényi entropies and show that these quantities are useful in this—single-serving—context as well.
Computational Indistinguishability Amplification: Tight Product Theorems for System Composition
U. Maurer; K. Pietrzak; R. Renner
2007
Computational Indistinguishability Amplification: Tight Product Theorems for System Composition
Type
Conference Proceedings
Author
U. Maurer; K. Pietrzak; R. Renner
Year of Conference
2007
Publisher
Springer
Conference Name
Advances in Cryptology - CRYPTO 2007
Abstract
Many aspects of cryptographic security proofs can be seen as the proof that a certain system (e.g. a block cipher) is indistinguishable from an ideal system (e.g. a random permutation), for different types of distinguishers. This paper presents a new generic approach to proving upper bounds on the information-theoretic distinguishing advantage (from an ideal system) for a combined system, assuming upper bounds of certain types for the component systems. For a general type of combination operation of systems, including the XOR of functions or the cascade of permutations, we prove two amplification theorems. The first is a product theorem, in the spirit of XOR-lemmas: The distinguishing advantage of the combination of two systems is at most twice the product of the individual distinguishing advantages. This bound is optimal. The second theorem states that the combination of systems is secure against some strong class of distinguishers, assuming only that the components are secure against some weaker class of distinguishers. A key technical tool of the paper is the proof of a tight two-way correspondence, previously only known to hold in one direction, between the distinguishing advantage of two systems and the probability of winning an appropriately defined game.
Virtually all presently used cryptosystems can theoretically be broken by an exhaustive key-search, and they might even be broken in practice due to novel algorithms or progress in computer engineering. In contrast, by exploiting the fact that certain communication channels are inherently noisy, one can achieve encryption provably secure against adversaries with unbounded computing power, in arguably practical settings. This chapter discusses secret key-agreement by public discussion from correlated information in a new definitional framework for information-theoretic reductions.
Unconditional security of key distribution from causality constraints
L. Masanes; R. Renner; M. Christandl; A. Winter; J. Barrett
2006
Unconditional security of key distribution from causality constraints
Type
Online Database
Author
L. Masanes; R. Renner; M. Christandl; A. Winter; J. Barrett
Year
2006
Abstract
We analyze a protocol which generates secret key from correlations that violate a Bell inequality by a sufficient amount, and prove its security against eavesdroppers which are only constrained by the fact that any information accessible to them must be compatible with the impossibility of arbitrarily fast signaling. We prove unconditional security according to the strongest notion, the so called universally-composable security. The no-signaling assumption is imposed at the level of the outcome probabilities given the choice of the observable, therefore, the protocol remains secure in situations where the honest parties do not have a complete control over their quantum apparatuses, or distrust them. The techniques developed are very general and can be applied to other Bell inequality-based protocols. In particular, we provide a scheme for estimating Bell-inequality violations when the samples are not independent and identically distributed.
On the Impossibility of Extracting Classical Randomness Using a Quantum Computer
Y. Dodis; R. Renner
2006
On the Impossibility of Extracting Classical Randomness Using a Quantum Computer
Type
Book Section
Author
Y. Dodis; R. Renner
Year
2006
Publisher
Springer
Abstract
In this work we initiate the question of whether quantum computers can provide us with an almost perfect source of classical randomness, and more generally, suffice for classical cryptographic tasks, such as encryption. Indeed, it was observed [SV86, MP91, DOPS04] that classical computers are insufficient for either one of these tasks when all they have access to is a realistic imperfect source of randomness, such as the Santha-Vazirani source.
IEEE International Symposium on Information Theory
Abstract
In this paper we provide the answer to the following question: given a noisy channel PY|X and epsilon>0, how many bits can be transmitted with an error of at most epsilon by a single use of the channel?
Smooth entropies characterize basic information-theoretic properties of random variables, such as the number of bits required to store them or the amount of uniform randomness that can be extracted from them (possibly with respect to side information). In this paper, explicit and almost tight bounds on the smooth entropies of n-fold product distributions, Pn, are derived. These bounds are expressed in terms of the Shannon entropy of a single distribution, P . The results can be seen as an extension of the asymptotic equipartition property (AEP).
On the variational distance of independently repeated experiments
R. Renner
2005
On the variational distance of independently repeated experiments
Type
Online Database
Author
R. Renner
Year
2005
Abstract
Let P and Q be two probability distributions which differ only for values with non-zero probability. We show that the variational distance between the n-fold product distributions P^n and Q^n cannot grow faster than the square root of n.
Universally Composable Privacy Amplification Against Quantum Adversaries
R. Renner; R. König
2005
Universally Composable Privacy Amplification Against Quantum Adversaries
Type
Book Section
Author
R. Renner; R. König
Year
2005
Publisher
Springer
Abstract
Privacy amplification is the art of shrinking a partially secret string Z to a highly secret key S. We show that, even if an adversary holds quantum information about the initial string Z, the key S obtained by two-universal hashing is secure, according to a universally composable security definition. Additionally, we give an asymptotically optimal lower bound on the length of the extractable key S in terms of the adversary’s (quantum) knowledge about Z. Our result has applications in quantum cryptography. In particular, it implies that many of the known quantum key distribution protocols are universally composable.
Simple and Tight Bounds for Information Reconciliation and Privacy Amplification
R. Renner; S. Wolf
2005
Simple and Tight Bounds for Information Reconciliation and Privacy Amplification
Type
Conference Proceedings
Author
R. Renner; S. Wolf
Year of Conference
2005
Publisher
Springer
Conference Name
Advances in Cryptology - ASIACRYPT 2005
Abstract
Shannon entropy is a useful and important measure in information processing, for instance, data compression or randomness extraction, under the assumption—which can typically safely be made in communication theory —that a certain random experiment is independently repeated many times. In cryptography , however, where a system’s working has to be proven with respect to a malicious adversary, this assumption usually translates to a restriction on the latter’s knowledge or behavior and is generally not satisfied. An example is quantum key agreement, where the adversary can attack each particle sent through the quantum channel differently or even carry out coherent attacks, combining a number of particles together. In information-theoretic key agreement, the central functionalities of information reconciliation and privacy amplification have, therefore, been extensively studied in the scenario of general distributions : Partial solutions have been given, but the obtained bounds are arbitrarily far from tight, and a full analysis appeared to be rather involved to do. We show that, actually, the general case is not more difficult than the scenario of independent repetitions—in fact, given our new point of view, even simpler. When one analyzes the possible efficiency of data compression and randomness extraction in the case of independent repetitions, then Shannon entropy H is the answer. We show that H can, in these two contexts, be generalized to two very simple quantities—H_0 epsilon and H_infty epsilon, called smooth Renyi entropies —which are tight bounds for data compression (hence, information reconciliation) and randomness extraction (privacy amplification), respectively. It is shown that the two new quantities, and related notions, do not only extend Shannon entropy in the described contexts, but they also share central properties of the latter such as the chain rule as well as sub-additivity and monotonicity.
A de Finetti representation for finite symmetric quantum states
R. Koenig; R. Renner
2005
A de Finetti representation for finite symmetric quantum states
Type
Journal Article
Author
R. Koenig; R. Renner
Year
2005
Journal
Journal of Mathematical Physics
Abstract
Consider a symmetric quantum state on an n-fold product space, that is, the state is invariant under permutations of the n subsystems. We show that, conditioned on the outcomes of an informationally complete measurement applied to a number of subsystems, the state in the remaining subsystems is close to having product form. This immediately generalizes the so-called de Finetti representation to the case of finite symmetric quantum states.
We address the question whether quantum memory is more powerful than classical memory. In particular, we consider a setting where information about a random n-bit string X is stored in s classical or quantum bits, for s<n, i.e., the stored information is bound to be only partial. Later, a randomly chosen predicate F about X has to be guessed using only the stored information. The maximum probability of correctly guessing F(X) is then compared for the cases where the storage device is classical or quantum mechanical, respectively. We show that, despite the fact that the measurement of quantum bits can depend arbitrarily on the predicate F, the quantum advantage is negligible already for small values of the difference n-s. Our setting generalizes the setting of Ambainis et al. who considered the problem of guessing an arbitrary bit (i.e., one of the n bits) of X. An implication for cryptography is that privacy amplification by universal hashing remains essentially equally secure when the adversary’s memory is allowed to be quantum rather than only classical. Since privacy amplification is a main ingredient of many quantum key distribution (QKD) protocols, our result can be used to prove the security of QKD in a generic way.
Lower and Upper Bounds on the Secret-Key Rate for Quantum Key Distribution Protocols Using One-Way Classical Communication
B. Kraus; N. Gisin; R. Renner
2005
Lower and Upper Bounds on the Secret-Key Rate for Quantum Key Distribution Protocols Using One-Way Classical Communication
Type
Journal Article
Author
B. Kraus; N. Gisin; R. Renner
Year
2005
Journal
Physical Review Letters
Abstract
We investigate a general class of quantum key distribution (QKD) protocols using one-way classical communication. We show that full security can be proven by considering only collective attacks. We derive computable lower and upper bounds on the secret-key rate of those QKD protocols involving only entropies of two-qubit density operators. As an illustration of our results, we determine new bounds for the Bennett-Brassard 1984, the 6-state, and the Bennett 1992 protocols. We show that in all these cases the first classical processing that the legitimate partners should apply consists in adding noise.
Information-theoretic security proof for quantum-key-distribution protocols
R. Renner; N. Gisin; B. Kraus
2005
Information-theoretic security proof for quantum-key-distribution protocols
Type
Journal Article
Author
R. Renner; N. Gisin; B. Kraus
Year
2005
Journal
Physical Review A
Abstract
We present a technique for proving the security of quantum-key-distribution (QKD) protocols. It is based on direct information-theoretic arguments and thus also applies if no equivalent entanglement purification scheme can be found. Using this technique, we investigate a general class of QKD protocols with one-way classical post-processing. We show that, in order to analyze the full security of these protocols, it suffices to consider collective attacks. Indeed, we give new lower and upper bounds on the secret-key rate which only involve entropies of two-qubit density operators and which are thus easy to compute. As an illustration of our results, we analyze the Bennett-Brassard 1984, the six-state, and the Bennett 1992 protocols with one-way error correction and privacy amplification. Surprisingly, the performance of these protocols is increased if one of the parties adds noise to the measurement data before the error correction. In particular, this additional noise makes the protocols more robust against noise in the quantum channel.
We propose various new techniques in quantum information theory, including a de Finetti style representation theorem for finite symmetric quantum states. As an application, we give a proof for the security of quantum key distribution which applies to arbitrary protocols.
One-Way Secret-Key Agreement and Applications to Circuit Polarization and Immunization of Public-Key Encryption
T. Holenstein; R. Renner
2005
One-Way Secret-Key Agreement and Applications to Circuit Polarization and Immunization of Public-Key Encryption
Type
Conference Proceedings
Author
T. Holenstein; R. Renner
Year of Conference
2005
Publisher
Springer
Conference Name
Advances in Cryptology - CRYPTO 2005
Abstract
Secret-key agreement between two parties Alice and Bob, connected by an insecure channel, can be realized in an information-theoretic sense if the parties share many independent pairs of correlated and partially secure bits. We study the special case where only one-way communication from Alice to Bob is allowed and where, for each of the bit pairs, with a certain probability, the adversary has no information on Alice’s bit. We give an expression which, for this situation, exactly characterizes the rate at which Alice and Bob can generate secret key bits. This result can be used to analyze a slightly restricted variant of the problem of polarizing circuits, introduced by Sahai and Vadhan in the context of statistical zero-knowledge, which we show to be equivalent to secret-key agreement as described above. This provides us both with new constructions to polarize circuits, but also proves that the known constructions work for parameters which are tight. As a further application of our results on secret-key agreement, we show how to immunize single-bit public-key encryption schemes from decryption errors and insecurities of the encryption, a question posed and partially answered by Dwork, Naor, and Reingold. Our construction works for stronger parameters than the known constructions.
A Generic Security Proof for Quantum Key Distribution
M. Christandl; R. Renner; A. Ekert
2004
A Generic Security Proof for Quantum Key Distribution
Type
Online Database
Author
M. Christandl; R. Renner; A. Ekert
Year
2004
Abstract
Quantum key distribution allows two parties, traditionally known as Alice and Bob, to establish a secure random cryptographic key if, firstly, they have access to a quantum communication channel, and secondly, they can exchange classical public messages which can be monitored but not altered by an eavesdropper, Eve. Quantum key distribution provides perfect security because, unlike its classical counterpart, it relies on the laws of physics rather than on ensuring that successful eavesdropping would require excessive computational effort. However, security proofs of quantum key distribution are not trivial and are usually restricted in their applicability to specific protocols. In contrast, we present a general and conceptually simple proof which can be applied to a number of different protocols. It relies on the fact that a cryptographic procedure called privacy amplification is equally secure when an adversary's memory for data storage is quantum rather than classical.
IEEE International Symposium on Information Theory
Abstract
This paper introduces the public Eve scenario and shows that the secret key rate in this scenario is bounded by the intrinsic information. This elucidates previous results and gives new insights in the gap between formation and extraction of secret information. Intrinsic information, in its function as an upper bound on the secret key rate, is generalized to secret key agreement from arbitrary tripartite quantum states.
IEEE International Symposium on Information Theory
Abstract
We introduce a new entropy measure, called smooth Renyi entropy. The measure characterizes fundamental properties of a random variable Z, such as the amount of uniform randomness that can be extracted from Z or the minimum length of an encoding of Z.
Privacy amplification secure against an adversary with selectable knowledge
R. Koenig; U. Maurer; R. Renner
2004
Privacy amplification secure against an adversary with selectable knowledge
Type
Conference Proceedings
Author
R. Koenig; U. Maurer; R. Renner
Year of Conference
2004
Conference Name
IEEE International Symposium on Information Theory
Abstract
We introduce the concept of selectable knowledge, which models the information stored in an arbitrary (e.g., quantum mechanical) device. We then analyze a situation where an entity A holds selectable knowledge about some random variable X and quantify the information A has about the output H(X) of a randomly chosen function H applied to X. This generalizes the setting of privacy amplification by universal hashing. In particular, our result can be used to prove that privacy amplification remains secure even if the enemy possesses quantum instead of classical information.
The Exact Price for Unconditionally Secure Asymmetric Cryptography
R. Renner; S. Wolf
2004
The Exact Price for Unconditionally Secure Asymmetric Cryptography
Type
Conference Proceedings
Author
R. Renner; S. Wolf
Year of Conference
2004
Publisher
Springer
Conference Name
Advances in Cryptology - EUROCRYPT 2004
Abstract
A completely insecure communication channel can only be transformed into an unconditionally secure channel if some information-theoretic primitive is given to start from. All previous approaches to realizing such authenticity and privacy from weak primitives were symmetric in the sense that security for both parties was achieved. We show that asymmetric information-theoretic security can, however, be obtained at a substantially lower price than two-way security|like in the computational-security setting, as the example of public-key cryptography demonstrates. In addition to this, we show that also an unconditionally secure bidirectional channel can be obtained under weaker conditions than previously known. One consequence of these results is that the assumption usually made in the context of quantum key distribution that the two parties share a short key initially is unnecessarily strong. Keywords. Information-theoretic security, authentication, information reconciliation, privacy amplification, quantum key agreement, reductions of information-theoretic primitives.
Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology
U. Maurer; R. Renner; C. Holenstein
2004
Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology
Type
Book Section
Author
U. Maurer; R. Renner; C. Holenstein
Year
2004
Publisher
Springer
Abstract
The goals of this paper are two-fold. First we introduce and motivate a generalization of the fundamental concept of the indistinguishability of two systems, called indifferentiability. This immediately leads to a generalization of the related notion of reducibility of one system to another. In contrast to the conventional notion of indistinguishability, indifferentiability is applicable in settings where a possible adversary is assumed to have access to additional information about the internal state of the involved systems, for instance the public parameter selecting a member from a family of hash functions. Second, we state an easily verifiable criterion for a system U not to be reducible (according to our generalized definition) to another system V and, as an application, prove that a random oracle is not reducible to a weaker primitive, called asynchronous beacon, and also that an asynchronous beacon is not reducible to a finite-length random string. Each of these irreducibility results alone implies the main theorem of Canetti, Goldreich, and Halevi stating that there exist cryptosystems that are secure in the random oracle model but for which replacing the random oracle by any implementation leads to an insecure cryptosystem.
Quantum pseudo-telepathy and the Kochen-Specker theorem
R. Renner; S. Wolf
2004
Quantum pseudo-telepathy and the Kochen-Specker theorem
Type
Conference Proceedings
Author
R. Renner; S. Wolf
Year of Conference
2004
Conference Name
IEEE International Symposium on Information Theory
Abstract
There are different approaches to proving the impossibility of classical hidden-variable explanations of quantum-mechanical behavior. Whereas Kochen and Specker proved that a three- or higherdimensional quantum-mechanical system cannot be “classically” prepared for all possible alternative measurements in a consistent way, Bell showed that the behavior of certain two-partite systems is nonlocal, i.e., inexplicable by shared classical information. We show a close connection between deterministic manifestations of such non-locality—called “pseudotelepathy” games—and Kochen and Specker’s theorem: Every such game leads to a Kochen-Specker contradiction, and vice versa.
Unconditional Authenticity and Privacy from an Arbitrarily Weak Secret
R. Renner; S. Wolf
2003
Unconditional Authenticity and Privacy from an Arbitrarily Weak Secret
Type
Conference Proceedings
Author
R. Renner; S. Wolf
Year of Conference
2003
Publisher
Springer
Conference Name
Advances in Cryptology - CRYPTO 2003
Abstract
Unconditional cryptographic security cannot be generated simply from scratch, but must be based on some given primitive to start with (such as, most typically, a private key). Whether or not this implies that such a high level of security is necessarily impractical depends on how weak these basic primitives can be, and how realistic it is therefore to realize or find them in|classical or quantum|reality. A natural way of minimizing the required resources for information-theoretic security is to reduce the length of the private key. In this paper, we focus on the level of its secrecy instead and show that even if the communication channel is completely insecure, a shared string of which an arbitrarily large fraction is known to the adversary can be used for achieving fundamental cryptographic goals such as message authentication and encryption. More precisely, we give protocols|using such a weakly secret key|allowing for both the exchange of authenticated messages and the extraction of the key’s entire amount of privacy into a shorter virtually secret key. Our schemes, which are highly interactive, show the power of two-way communication in this context: Under the given conditions, the same objectives cannot be achieved by one-way communication only.
New Bounds in Secret-Key Agreement: The Gap between Formation and Secrecy Extraction
R. Renner; S. Wolf
2003
New Bounds in Secret-Key Agreement: The Gap between Formation and Secrecy Extraction
Type
Conference Proceedings
Author
R. Renner; S. Wolf
Year of Conference
2003
Publisher
Springer
Conference Name
Advances in Cryptology - EUROCRYPT 2003
Abstract
Perfectly secret message transmission can be realized with only partially secret and weakly correlated information shared by the parties as soon as this information allows for the extraction of information-theoretically secret bits. The best known upper bound on the rate S at which such key bits can be generated has been the intrinsic information of the distribution modeling the parties’, including the adversary’s, knowledge. Based on a new property of the secret-key rate S, we introduce a conditional mutual information measure which is a stronger upper bound on S. Having thus seen that the intrinsic information of a distribution P is not always suitable for determining the number of secret bits extractable from P, we prove a different significance of it in the same context: It is a lower bound on the number of key bits required to generate P by public communication. Taken together, these two results imply that sometimes, (a possibly arbitrarily large fraction of) the correlation contained in distributed information cannot be extracted in the form of secret keys by any protocol.
A new measure for conditional mutual information and its properties
R. Renner; J. Skripsky; S. Wolf
2003
A new measure for conditional mutual information and its properties
Type
Conference Proceedings
Author
R. Renner; J. Skripsky; S. Wolf
Year of Conference
2003
Conference Name
IEEE International Symposium on Information Theory
Abstract
We propose a new conditional mutual information measure, called the reduced intrinsic information, and show its significance in the context of determining the number of secret-key bits that can be extracted from distributed information by public communication.
IEEE International Symposium on Information Theory
Abstract
The so-called intrinsic mutual information is an important measure in the context of information-theoretic secret-key agreement. We prove a property of this information measure which, in particular, strongly simplifies its computation. More generally, our result is useful for analyzing the correlation of two random variables conditioned on a third one.
Towards characterizing the nonlocality of entangled quantum states
R. Renner; S. Wolf
2003
Towards characterizing the nonlocality of entangled quantum states
Type
Conference Proceedings
Author
R. Renner; S. Wolf
Year of Conference
2003
Conference Name
IEEE International Symposium on Information Theory
Abstract
We propose a so-called pseudo-telepathy game for n players demonstrating the nonlocality of quantum information. The simplicity of its classical analysis contrasts the often quite involved analysis of previously proposed such games (G. Brassard, 1999). Moreover, our game allows for a quantitative characterization of entanglement in terms of communication complexity.
Linking Classical and Quantum Key Agreement: Is There a Classical Analog to Bound Entanglement?
N. Gisin; R. Renner; S. Wolf
2002
Linking Classical and Quantum Key Agreement: Is There a Classical Analog to Bound Entanglement?
Type
Journal Article
Author
N. Gisin; R. Renner; S. Wolf
Year
2002
Publisher
Springer
Journal
Algorithmica
Abstract
Abstract. After carrying out a protocol for quantum key agreement over a noisy quantum channel, the parties Alice and Bob must process the raw key in order to end up with identical keys about which the adversary has virtually no information. In principle, both classical and quantum protocols can be used for this processing. It is a natural question which type of protocol is more powerful. We show that the limits of tolerable noise are identical for classical and quantum protocols in many cases. More specifically, we prove that a quantum state between two parties is entangled if and only if the classical random variables resulting from optimal measurements provide some mutual classical information between the parties. In addition, we present evidence which strongly suggests that the potentials of classical and of quantum protocols are equal in every situation. An important consequence, in the purely classical regime, of such a correspondence would be the existence of a classical counterpart of so-called bound entanglement, namely ``bound information''that cannot be used for generating a secret key by any protocol. This stands in contrast to what was previously believed.
IEEE International Symposium on Information Theory
Abstract
Indistinguishability between systems is a basic concept in cryptography, allowing for a generic type of security proofs. Its scope of application is however restricted to systems whose behavior depends on some secret randomness. We propose a generalized definition of indistinguishability which overcomes this restriction, such that the same type of security proofs applies in a more general context where this randomness might be public.
IEEE International Symposium on Information Theory
Abstract
We give a necessary, sufficient, and easily verifiable criterion for the conditional probability distribution PZ|XY (where X, Y and Z are arbitrary random variables), such that I(X; Y)≥I(X; Y|Z) holds for any distribution PXY. Furthermore, the result is generalized to the case where Z is specified by a conditional probability distribution depending on more than two random variables.
Towards proving the existence of"bound"information
R. Renner; S. Wolf
2002
Towards proving the existence of"bound"information
Type
Conference Proceedings
Author
R. Renner; S. Wolf
Year of Conference
2002
Conference Name
IEEE International Symposium on Information Theory
Abstract
We show that information-theoretically secure key agreement and quantum distillation are strongly related. This leads to new evidence for the existence of bound information, i.e. correlated information not useful for the generation of a secret key.
Bound information: the classical analog to bound quantum entanglement
N. Gisin; R. Renner; S. Wolf
2000
Bound information: the classical analog to bound quantum entanglement
Type
Conference Proceedings
Author
N. Gisin; R. Renner; S. Wolf
Year of Conference
2000
Publisher
Birkhaeuser Verlag
Conference Name
European Congress of Mathematics
Abstract
It was recently pointed out that there is a close connection between information-theoretic key agreement and quantum entanglement purification. This suggests that the concept of bound entanglement (entanglement which cannot be purified) has a classical counterpart: bound information, which cannot be used to generate a secret key by any protocol. We analyze a probability distribution which results when a specific bound entangled quantum state is measured. We show strong evidence for the fact that the corresponding mutual information is indeed bound. The probable existence of such information contrasts previous beliefs in classical information theory.
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne
graphische Elemente dargestellt. Die Funktionalität der
Website ist aber trotzdem gewährleistet. Wenn Sie diese
Website regelmässig benutzen, empfehlen wir Ihnen, auf
Ihrem Computer einen aktuellen Browser zu installieren. Weitere
Informationen finden Sie auf folgender
Seite.
Important Note:
The content in this site is accessible to any browser or
Internet device, however, some graphics will display correctly
only in the newer versions of Netscape. To get the most out of
our site we suggest you upgrade to a newer browser. More
information
