We propose an iterative method for approximating the capacity of classical-quantum channels with a discrete input alphabet and a finite dimensional output, possibly under additional constraints on the input distribution. Based on duality of convex programming, we derive explicit upper and lower bounds for the capacity. To provide an varepsilon-close estimate to the capacity, the presented algorithm requires O( tfrac{(N vee M) M3 log(N){1/2}}{ varepsilon}), where N denotes the input alphabet size and M the output dimension. We then generalize the method for the task of approximating the capacity of classical-quantum channels with a bounded continuous input alphabet and a finite dimensional output. For channels with a finite dimensional quantum mechanical input and output, the idea of a universal encoder allows us to approximate the Holevo capacity using the same method. In particular, we show that the problem of approximating the Holevo capacity can be reduced to a multidimensional integration problem. For families of quantum channels fulfilling a certain assumption we show that the complexity to derive an varepsilon-close solution to the Holevo capacity is subexponential or even polynomial in the problem size. We provide several examples to illustrate the performance of the approximation scheme in practice.
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.
Full Security of Quantum Key Distribution From No-Signaling Constraints
Masanes, Lluis; Renner, Renato; Christandl, Matthias; Winter, Andreas; Barrett, Jonathan
2014
Full Security of Quantum Key Distribution From No-Signaling Constraints
Type
Journal Article
Author
Masanes, Lluis; Renner, Renato; Christandl, Matthias; Winter, Andreas; Barrett, Jonathan
Year
2014
Journal
IEEE Transactions on Information Theory
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.
In this brief note, we compare two frameworks for characterizing possible operations in quantum thermodynamics. One framework considers Thermal Operations---unitaries which conserve energy. The other framework considers all maps which preserve the Gibbs state at a given temperature. Thermal Operations preserve the Gibbs state; hence a natural question which arises is whether the two frameworks are equivalent. Classically, this is true---Gibbs-Preserving Maps are no more powerful than Thermal Operations. Here, we show that this no longer holds in the quantum regime: a Gibbs-Preserving Map can generate coherent superpositions of energy levels while Thermal Operations cannot. This gap has an impact on clarifying a mathematical framework for quantum thermodynamics.
Classical leakage resilience from fault-tolerant quantum computation
Lacerda, Felipe G.; Renes, Joseph M.; Renner, Renato
2014
Classical leakage resilience from fault-tolerant quantum computation
Type
Online Database
Author
Lacerda, Felipe G.; Renes, Joseph M.; Renner, Renato
Year
2014
Abstract
Physical implementations of cryptographic algorithms leak information, which makes them vulnerable to so-called side-channel attacks. The problem of secure computation in the presence of leakage is generally known as leakage resilience. In this work, we establish a connection between leakage resilience and fault-tolerant quantum computation. We first prove that for a general leakage model, there exists a corresponding noise model in which fault tolerance implies leakage resilience. Then we show how to use constructions for fault-tolerant quantum computation to implement classical circuits that are secure in specific leakage models.
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.
Among those who make a living from the science of secrecy, worry and paranoia are just signs of professionalism. Can we protect our secrets against those who wield superior technological powers? Can we trust those who provide us with tools for protection? Can we even trust ourselves, our own freedom of choice? Recent developments in quantum cryptography show that some of these questions can be addressed and discussed in precise and operational terms, suggesting that privacy is indeed possible under surprisingly weak assumptions.
del Rio, Lidia; Hutter, Adrian; Renner, Renato; Wehner, Stephanie
2014
Relative Thermalization
Type
Online Database
Author
del Rio, Lidia; Hutter, Adrian; Renner, Renato; Wehner, Stephanie
Year
2014
Abstract
When studying thermalization of quantum systems, it is typical to ask whether a system interacting with an environment will evolve towards a local thermal state. Here, we show that a more general and relevant question is"when does a system thermalize relative to a particular reference?"By relative thermalization we mean that, as well as being in a local thermal state, the system is uncorrelated with the reference. We argue that this is necessary in order to apply standard statistical mechanics to the study of the interaction between a thermalized system and a reference. We then derive a condition for relative thermalization of quantum systems interacting with an arbitrary environment. This condition has two components: the first is state-independent, reflecting the structure of invariant subspaces, like energy shells, and the relative sizes of system and environment; the second depends on the initial correlations between reference, system and environment, measured in terms of conditional entropies. Intuitively, a small system interacting with a large environment is likely to thermalize relative to a reference, but only if, initially, the reference was not highly correlated with the system and environment. Our statement makes this intuition precise, and we show that in many natural settings this thermalization condition is approximately tight. Established results on thermalization, which usually ignore the reference, follow as special cases of our statements.
Efficient One-Way Secret-Key Agreement and Private Channel Coding via Polarization
Sutter, D.; Renes, J. M.; Renner, R.
2013
Efficient One-Way Secret-Key Agreement and Private Channel Coding via Polarization
Type
Journal Article
Author
Sutter, D.; Renes, J. M.; Renner, R.
Year
2013
Journal
Advances in Cryptology - ASIACRYPT 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.
Randomness is crucial for a variety of applications, ranging from gambling to computer simulations, and from cryptography to statistics. However, many of the currently used methods for generating randomness do not meet the criteria that are necessary for these applications to work properly and safely. A common problem is that a sequence of numbers may look random but nevertheless not be truly random. In fact, the sequence may pass all standard statistical tests and yet be perfectly predictable. This renders it useless for many applications. For example, in cryptography, the predictability of a randomly"chosen password is obviously undesirable. Here, we review a recently developed approach to generating true | and hence unpredictable | randomness.
Even if the output of a Random Number Generator (RNG) is perfectly uniformly distributed, it may be correlated to pre-existing information and therefore be predictable. Statistical tests are thus not sufficient to guarantee that an RNG is usable for applications, e.g., in cryptography or gambling, where unpredictability is important. To enable such applications a stronger notion of randomness, termed"true randomness", is required, which includes independence from prior information. Quantum systems are particularly suitable for true randomness generation, as their unpredictability can be proved based on physical principles. Practical implementations of Quantum RNGs (QRNGs) are however always subject to noise, I.e., influences which are not fully controlled. This reduces the quality of the raw randomness generated by the device, making it necessary to post-process it. Here we provide a framework to analyse realistic QRNGs and to determine the post-processing that is necessary to turn their raw output into true randomness.
Smooth Max-Information as One-Shot Generalization for Mutual Information
Ciganović, N.; Beaudry, N. J.; Renner, R.
2013
Smooth Max-Information as One-Shot Generalization for Mutual Information
Type
Journal Article
Author
Ciganović, N.; Beaudry, N. J.; Renner, R.
Year
2013
Journal
IEEE Transactions on Information Theory
Abstract
We study formal properties of smooth max-information, a generalization of von Neumann mutual information derived from the max-relative entropy. Recent work suggests that it is a useful quantity in one-shot channel coding, quantum rate distortion theory and the physics of quantum many-body systems. Max-information can be defined in multiple ways. We demonstrate that different smoothed definitions are essentially equivalent (up to logarithmic terms in the smoothing parameters). These equivalence relations allow us to derive new chain rules for the max-information in terms of min- and max-entropies, thus extending the smooth entropy formalism to mutual information.
Datta, Nilanjana; Renes, Joseph M.; Renner, Renato; Wilde, Mark M.
2013
One-Shot Lossy Quantum Data Compression
Type
Journal Article
Author
Datta, Nilanjana; Renes, Joseph M.; Renner, Renato; Wilde, Mark M.
Year
2013
Journal
IEEE Transactions on Information Theory
Abstract
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.
Information theory was originally developed to study the fundamental limits of telecommunication. But thanks to recent extensions it can now also be applied to solid-state physics.
A system's wave function is uniquely determined by its underlying physical state
Colbeck, R.; Renner, R.
2013
A system's wave function is uniquely determined by its underlying physical state
Type
Online Database
Author
Colbeck, R.; Renner, R.
Year
2013
Abstract
We address the question of whether the quantum-mechanical wave functionΨof a system is uniquely determined by any complete descriptionΛof the system's physical state. We show that this is the case if the latter satisfies a notion of"free choice". This notion requires that certain experimental parameters, which according to quantum theory can be chosen independently of other variables, retain this property in the presence ofΛ. An implication of this result is that, among all possible descriptionsΛof a system's state compatible with free choice, the wave functionΨis as objective asΛ.
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δ.
Beaudry, N. J.; Lucamarini, M.; Mancini, S.; Renner, R.
2013
Security of two-way quantum key distribution
Type
Journal Article
Author
Beaudry, N. J.; Lucamarini, M.; Mancini, S.; Renner, R.
Year
2013
Journal
Physical Review A
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.
Dupuis, F.; Kraemer, L.; Faist, Ph.; Renes, J. M.; Renner, R.
2013
Generalized Entropies
Type
Conference Proceedings
Author
Dupuis, F.; Kraemer, L.; Faist, Ph.; Renes, J. M.; Renner, R.
Year of Conference
2013
Conference Name
XVIIth International Congress on Mathematical Physics
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.
Efficient quantum channel coding scheme requiring no preshared entanglement
Sutter, David; Renes, Joseph M.; Dupuis, Frederic; Renner, Renato
2013
Efficient quantum channel coding scheme requiring no preshared entanglement
Type
Conference Proceedings
Author
Sutter, David; Renes, Joseph M.; Dupuis, Frederic; Renner, Renato
Year of Conference
2013
Publisher
IEEE
Conference Name
2013 IEEE International Symposium on Information Theory
Abstract
We construct an explicit entanglement distillation scheme which achieves a communication rate not less than the coherent information when used to transmit quantum information over a noisy quantum channel. For Pauli and erasure channels we also present efficient encoding and decoding algorithms for this communication scheme based on polar codes, but which do not require the sender and receiver to share any entanglement before the protocol begins. Due to the existence of degeneracies in the involved error-correcting codes it is indeed possible that the rate of the scheme exceeds the coherent information. We provide a simple criterion which indicates such performance. Finally we discuss how the scheme can be used for secret key distillation as well as private channel coding.
de Finetti-type theorems enable a substantially simplified analysis of information-processing tasks in various areas, such as quantum cryptography and quantum tomography. The idea is that instead of carrying out the analysis for any possible state it is sufficient to consider one particular de Finetti state, that is, a convex combination of I.I.d. states. It is thus interesting to see whether such de Finetti-type theorems are unique for quantum theory or whether they hold for more general theories. Here we prove a de Finetti-type theorem in the framework of conditional probability distributions. In this framework, a system is described by a conditional probability distribution P_A|X where X denotes the measurement and A the outcome. We show that any permutation invariant system P_A|X can be reduced to a de Finetti system. We then demonstrate how the theorem can be applied to security proofs of device independent cryptographic protocols.
Device-Independent Quantum Key Distribution with Local Bell Test
Lim, Charles Ci Wen; Portmann, Christopher; Tomamichel, Marco; Renner, Renato; Gisin, Nicolas
2013
Device-Independent Quantum Key Distribution with Local Bell Test
Type
Journal Article
Author
Lim, Charles Ci Wen; Portmann, Christopher; Tomamichel, Marco; Renner, Renato; Gisin, Nicolas
Year
2013
Journal
Physical Review X
Abstract
Device-independent quantum key distribution (DIQKD) in its current design requires a violation of a Bell's inequality between two parties, Alice and Bob, who are connected by a quantum channel. However, in reality, quantum channels are lossy and current DIQKD protocols are thus vulnerable to attacks exploiting the detection loophole of the Bell test. Here, we propose a novel approach to DIQKD that overcomes this limitation. In particular, we propose a protocol where the Bell test is performed entirely on two casually independent devices situated in Alice's laboratory. As a result, the detection loophole caused by the losses in the channel is avoided.
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.
Consider a bipartite system, of which one subsystem, A, undergoes a physical evolution separated from the other subsystem, R. One may ask under which conditions this evolution destroys all initial correlations between the subsystems A and R, I.e. decouples the subsystems. A quantitative answer to this question is provided by decoupling theorems, which have been developed recently in the area of quantum information theory. This paper builds on preceding work, which shows that decoupling is achieved if the evolution on A consists of a typical unitary, 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 approximate two-design. A main implication of this result is that decoupling is physical, in the sense that it occurs already for short sequences of random two-body interactions, which can be modeled as efficient circuits. Our decoupling result is independent of the dimension of the R system, which shows that approximate two-designs are appropriate for decoupling even if the dimension of this system is large.
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)].
Security of Continuous-Variable Quantum Key Distribution Against General Attacks
Leverrier, Anthony; García-Patrón, Raúl; Renner, Renato; Cerf, Nicolas
2013
Security of Continuous-Variable Quantum Key Distribution Against General Attacks
Type
Journal Article
Author
Leverrier, Anthony; García-Patrón, Raúl; Renner, Renato; Cerf, Nicolas
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
Dunjko, V.; Fitzsimons, J. F.; Portmann, C.; Renner, R.
2013
Composable security of delegated quantum computation
Type
Online Database
Author
Dunjko, V.; Fitzsimons, J. F.; Portmann, C.; Renner, R.
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.
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.
Laws of thermodynamics beyond the von Neumann regime
Egloff, Dario; Dahlsten, Oscar C. O.; Renner, Renato; Vedral, Vlatko
2012
Laws of thermodynamics beyond the von Neumann regime
Type
Online Database
Author
Egloff, Dario; Dahlsten, Oscar C. O.; Renner, Renato; Vedral, Vlatko
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.
The completeness of quantum theory for predicting measurement outcomes
Colbeck, R.; Renner, R.
2012
The completeness of quantum theory for predicting measurement outcomes
Type
Online Database
Author
Colbeck, R.; Renner, R.
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.
Reply to recent scepticism about the foundations of quantum cryptography
Renner, R.
2012
Reply to recent scepticism about the foundations of quantum cryptography
Type
Online Database
Author
Renner, R.
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.
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.
An intuitive proof of the data processing inequality
Beaudry, N. J.; Renner, R.
2012
An intuitive proof of the data processing inequality
Type
Journal Article
Author
Beaudry, N. J.; Renner, R.
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 deﬁnition 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
The impossibility of non-signaling privacy amplification
Haenggi, E.; Renner, R.; Wolf, S.
2012
The impossibility of non-signaling privacy amplification
Type
Journal Article
Author
Haenggi, E.; Renner, R.; Wolf, S.
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.
Polar coding, introduced 2008 by Ar{Ikan, 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
Tomamichel, M.; Lim, C. W.; Gisin, N.; Renner, R.
2012
Tight Finite-Key Analysis for Quantum Cryptography
Type
Journal Article
Author
Tomamichel, M.; Lim, C. W.; Gisin, N.; Renner, R.
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.
Achieving the Capacity of any DMC using only Polar Codes
Sutter, D.; Renes, J. M.; Dupuis, F.; Renner, R.
2012
Achieving the Capacity of any DMC using only Polar Codes
Type
Conference Proceedings
Author
Sutter, D.; Renes, J. M.; Dupuis, F.; Renner, R.
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.
Experimental Bound on the Maximum Predictive Power of Physical Theories
Stuart, T. E.; Slater, J. A.; Colbeck, R.; Renner, R.; Tittel, W.
2012
Experimental Bound on the Maximum Predictive Power of Physical Theories
Type
Journal Article
Author
Stuart, T. E.; Slater, J. A.; Colbeck, R.; Renner, R.; Tittel, W.
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.
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.
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.
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.
Towards characterizing the nonlocality of entangled quantum states
Renner, R.; Wolf, S.
2012
Towards characterizing the nonlocality of entangled quantum states
Type
Journal Article
Author
Renner, R.; Wolf, S.
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.
One-Shot Classical Data Compression with Quantum Side Information and the Distillation of Common Randomness or Secret Keys
Renes, J. M.; Renner, R.
2012
One-Shot Classical Data Compression with Quantum Side Information and the Distillation of Common Randomness or Secret Keys
Type
Journal Article
Author
Renes, J. M.; Renner, R.
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.
Trevisan's extractor in the presence of quantum side information
De, A.; Portmann, C.; Vidick, T.; Renner, R.
2012
Trevisan's extractor in the presence of quantum side information
Type
Journal Article
Author
De, A.; Portmann, C.; Vidick, T.; Renner, R.
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.
Tsirelson's bound from a Generalised Data Processing Inequality
Dahlsten, O. C. O.; Lercher, D.; Renner, R.
2012
Tsirelson's bound from a Generalised Data Processing Inequality
Type
Journal Article
Author
Dahlsten, O. C. O.; Lercher, D.; Renner, R.
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.
Is a system's wave function in one-to-one correspondence with its elements of reality?
Colbeck, R.; Renner, R.
2012
Is a system's wave function in one-to-one correspondence with its elements of reality?
Type
Journal Article
Author
Colbeck, R.; Renner, R.
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.
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.
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 delta-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.
The Quantum Reverse Shannon Theorem based on One-Shot Information Theory
Berta, M.; Christandl, M.; Renner, R.
2011
The Quantum Reverse Shannon Theorem based on One-Shot Information Theory
Type
Journal Article
Author
Berta, M.; Christandl, M.; Renner, R.
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.
No extension of quantum theory can have improved predictive power
Colbeck, R.; Renner, R.
2011
No extension of quantum theory can have improved predictive power
Type
Journal Article
Author
Colbeck, R.; Renner, R.
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.
Sampling of min-entropy relative to quantum knowledge
Koenig, R.; Renner, R.
2011
Sampling of min-entropy relative to quantum knowledge
Type
Journal Article
Author
Koenig, R.; Renner, R.
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.
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.
Noisy channel coding via privacy amplification and information reconciliation
Renes, J. M.; Renner, R.
2011
Noisy channel coding via privacy amplification and information reconciliation
Type
Journal Article
Author
Renes, J. M.; Renner, R.
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.
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.
del Rio, L.; Åberg, J.; Renner, R.; Dahlsten, O.; Vedral, V.
2011
The thermodynamic meaning of negative entropy
Type
Journal Article
Author
del Rio, L.; Åberg, J.; Renner, R.; Dahlsten, O.; Vedral, V.
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).
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.
Winkler, S.; Tomamichel, M.; Hengl, S.; Renner, R.
2011
Impossibility of Growing Commitments
Type
Journal Article
Author
Winkler, S.; Tomamichel, M.; Hengl, S.; Renner, R.
Year
2011
Journal
Physical Review Letters
Abstract
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.
Device-Independent Quantum Key Distribution with Commuting Measurements
Haenggi, E.; Renner, R.
2010
Device-Independent Quantum Key Distribution with Commuting Measurements
Type
Online Database
Author
Haenggi, E.; Renner, R.
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.
A Conceptually Simple Proof of the Quantum Reverse Shannon Theorem
Berta, M.; Christandl, M.; Renner, R.
2010
A Conceptually Simple Proof of the Quantum Reverse Shannon Theorem
Type
Conference Proceedings
Author
Berta, M.; Christandl, M.; Renner, R.
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.
Efficient Device-Independent Quantum Key Distribution
Haenggi, E.; Renner, R.; Wolf, S.
2010
Efficient Device-Independent Quantum Key Distribution
Type
Conference Proceedings
Author
Haenggi, E.; Renner, R.; Wolf, S.
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.
Simplifying information-theoretic arguments by post-selection
Renner, R.
2010
Simplifying information-theoretic arguments by post-selection
Type
Conference Proceedings
Author
Renner, R.
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)
Tomamichel, M.; Renner, R.; Schaffner, C.; Smith, A.
2010
Leftover Hashing against quantum side information (short version)
Type
Conference Proceedings
Author
Tomamichel, M.; Renner, R.; Schaffner, C.; Smith, A.
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.
Defining the local part of a hidden variable model: a comment
Colbeck, R.; Renner, R.
2009
Defining the local part of a hidden variable model: a comment
Type
Online Database
Author
Colbeck, R.; Renner, R.
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.
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
Space-quest, experiments with quantum entanglement in space
Renner), R. Ursin et al. (int. al. R.
2009
Space-quest, experiments with quantum entanglement in space
Type
Journal Article
Author
Renner), R. Ursin et al. (int. al. R.
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.
de Finetti Representation Theorem for Infinite-Dimensional Quantum Systems and Applications to Quantum Cryptography
Renner, R.; Cirac, J. I.
2009
de Finetti Representation Theorem for Infinite-Dimensional Quantum Systems and Applications to Quantum Cryptography
Type
Journal Article
Author
Renner, R.; Cirac, J. I.
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.
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.
Hidden Variable Models for Quantum Theory Cannot Have Any Local Part
Colbeck, R.; Renner, R.
2008
Hidden Variable Models for Quantum Theory Cannot Have Any Local Part
Type
Journal Article
Author
Colbeck, R.; Renner, R.
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.
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
Renner, R.
2008
Extracting classical randomness in a quantum world
Type
Conference Proceedings
Author
Renner, R.
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.
Quantum Cryptography with Finite Resources: Unconditional Security Bound for Discrete-Variable Protocols with One-Way Postprocessing
Scarani, V.; Renner, R.
2008
Quantum Cryptography with Finite Resources: Unconditional Security Bound for Discrete-Variable Protocols with One-Way Postprocessing
Type
Journal Article
Author
Scarani, V.; Renner, R.
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
Scarani, V.; Renner, R.
2008
Security Bounds for Quantum Cryptography with Finite Resources
Type
Book Section
Author
Scarani, V.; Renner, R.
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.
Symmetry of large physical systems implies independence of subsystems
Renner, Renato
2007
Symmetry of large physical systems implies independence of subsystems
Type
Journal Article
Author
Renner, Renato
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.
Christandl, M.; König, R.; Mitchison, G.; Renner, R.
2007
One-and-a-Half Quantum de Finetti Theorems
Type
Journal Article
Author
Christandl, M.; König, R.; Mitchison, G.; Renner, R.
Year
2007
Journal
Communications in Mathematical Physics
Abstract
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.
Christandl, M.; Ekert, A.; Horodecki, M.; Horodecki, P.; Oppenheim, J.; Renner, R.
2007
Unifying classical and quantum key distillation
Type
Conference Proceedings
Author
Christandl, M.; Ekert, A.; Horodecki, M.; Horodecki, P.; Oppenheim, J.; Renner, R.
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
Damgaard, I. B.; Fehr, S.; Renner, R.; Salvail, L.; Schaffner, C.
2007
A Tight High-Order Entropic Quantum Uncertainty Relation with Applications
Type
Conference Proceedings
Author
Damgaard, I. B.; Fehr, S.; Renner, R.; Salvail, L.; Schaffner, C.
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.
Small Accessible Quantum Information Does Not Imply Security
Koenig, R.; Renner, R.; Bariska, A.; Maurer, U.
2007
Small Accessible Quantum Information Does Not Imply Security
Type
Journal Article
Author
Koenig, R.; Renner, R.; Bariska, A.; Maurer, U.
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
Kraus, B.; Branciard, C.; Renner, R.
2007
Security of quantum-key-distribution protocols using two-way classical communication or weak coherent pulses
Type
Journal Article
Author
Kraus, B.; Branciard, C.; Renner, R.
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.
Computational Indistinguishability Amplification: Tight Product Theorems for System Composition
Maurer, U.; Pietrzak, K.; Renner, R.
2007
Computational Indistinguishability Amplification: Tight Product Theorems for System Composition
Type
Conference Proceedings
Author
Maurer, U.; Pietrzak, K.; Renner, R.
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.
Beweisbare Sicherheit durch Quantenkryptografie (Provable Security in Quantum Cryptography)
Renner, R.
2007
Beweisbare Sicherheit durch Quantenkryptografie (Provable Security in Quantum Cryptography)
Type
Journal Article
Author
Renner, R.
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
Renner, R.; Wolf, S.; Wullschleger, J.
2007
Trade-Offs in Information-Theoretic Multi-Party One-Way Key Agreement
Type
Conference Proceedings
Author
Renner, R.; Wolf, S.; Wullschleger, J.
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.
On the Impossibility of Extracting Classical Randomness Using a Quantum Computer
Dodis, Y.; Renner, R.
2006
On the Impossibility of Extracting Classical Randomness Using a Quantum Computer
Type
Book Section
Author
Dodis, Y.; Renner, R.
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.
Pages
204--215
Volume
4052
Editor
Bugliesi, M.; Preneel, B.; Sassone, V.; Wegener, I.
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).
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?
One-Way Secret-Key Agreement and Applications to Circuit Polarization and Immunization of Public-Key Encryption
Holenstein, T.; Renner, R.
2005
One-Way Secret-Key Agreement and Applications to Circuit Polarization and Immunization of Public-Key Encryption
Type
Conference Proceedings
Author
Holenstein, T.; Renner, R.
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 de Finetti representation for finite symmetric quantum states
Koenig, R.; Renner, R.
2005
A de Finetti representation for finite symmetric quantum states
Type
Journal Article
Author
Koenig, R.; Renner, R.
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
Kraus, B.; Gisin, N.; Renner, R.
2005
Lower and Upper Bounds on the Secret-Key Rate for Quantum Key Distribution Protocols Using One-Way Classical Communication
Type
Journal Article
Author
Kraus, B.; Gisin, N.; Renner, R.
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.
Universally Composable Privacy Amplification Against Quantum Adversaries
Renner, R.; König, R.
2005
Universally Composable Privacy Amplification Against Quantum Adversaries
Type
Book Section
Author
Renner, R.; König, R.
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.
On the variational distance of independently repeated experiments
Renner, R.
2005
On the variational distance of independently repeated experiments
Type
Online Database
Author
Renner, R.
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 Pn and Qn cannot grow faster than the square root of n.
Simple and Tight Bounds for Information Reconciliation and Privacy Amplification
Renner, R.; Wolf, S.
2005
Simple and Tight Bounds for Information Reconciliation and Privacy Amplification
Type
Conference Proceedings
Author
Renner, R.; Wolf, S.
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 satisﬁed. An example is quantum key agreement, where the adversary can attack each particle sent through the quantum channel diﬀerently 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 ampliﬁcation 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 diﬃcult than the scenario of independent repetitions—in fact, given our new point of view, even simpler. When one analyzes the possible eﬃciency 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 ampliﬁcation), 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.
Information-theoretic security proof for quantum-key-distribution protocols
Renner, R.; Gisin, N.; Kraus, B.
2005
Information-theoretic security proof for quantum-key-distribution protocols
Type
Journal Article
Author
Renner, R.; Gisin, N.; Kraus, B.
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.
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.
A Generic Security Proof for Quantum Key Distribution
Christandl, M.; Renner, R.; Ekert, A.
2004
A Generic Security Proof for Quantum Key Distribution
Type
Online Database
Author
Christandl, M.; Renner, R.; Ekert, A.
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.
Privacy amplification secure against an adversary with selectable knowledge
Koenig, R.; Maurer, U.; Renner, R.
2004
Privacy amplification secure against an adversary with selectable knowledge
Type
Conference Proceedings
Author
Koenig, R.; Maurer, U.; Renner, R.
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.
Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology
Maurer, U.; Renner, R.; Holenstein, C.
2004
Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology
Type
Book Section
Author
Maurer, U.; Renner, R.; Holenstein, C.
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.
The Exact Price for Unconditionally Secure Asymmetric Cryptography
Renner, R.; Wolf, S.
2004
The Exact Price for Unconditionally Secure Asymmetric Cryptography
Type
Conference Proceedings
Author
Renner, R.; Wolf, S.
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.
Quantum pseudo-telepathy and the Kochen-Specker theorem
Renner, R.; Wolf, S.
2004
Quantum pseudo-telepathy and the Kochen-Specker theorem
Type
Conference Proceedings
Author
Renner, R.; Wolf, S.
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.
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
Renner, R.; Wolf, S.
2003
Towards characterizing the nonlocality of entangled quantum states
Type
Conference Proceedings
Author
Renner, R.; Wolf, S.
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.
Unconditional Authenticity and Privacy from an Arbitrarily Weak Secret
Renner, R.; Wolf, S.
2003
Unconditional Authenticity and Privacy from an Arbitrarily Weak Secret
Type
Conference Proceedings
Author
Renner, R.; Wolf, S.
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.
A new measure for conditional mutual information and its properties
Renner, R.; Skripsky, J.; Wolf, S.
2003
A new measure for conditional mutual information and its properties
Type
Conference Proceedings
Author
Renner, R.; Skripsky, J.; Wolf, S.
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.
New Bounds in Secret-Key Agreement: The Gap between Formation and Secrecy Extraction
Renner, R.; Wolf, S.
2003
New Bounds in Secret-Key Agreement: The Gap between Formation and Secrecy Extraction
Type
Conference Proceedings
Author
Renner, R.; Wolf, S.
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.
Linking Classical and Quantum Key Agreement: Is There a Classical Analog to Bound Entanglement?
Gisin, N.; Renner, R.; Wolf, S.
2002
Linking Classical and Quantum Key Agreement: Is There a Classical Analog to Bound Entanglement?
Type
Journal Article
Author
Gisin, N.; Renner, R.; Wolf, S.
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
Renner, R.; Wolf, S.
2002
Towards proving the existence of"bound"information
Type
Conference Proceedings
Author
Renner, R.; Wolf, S.
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
Gisin, N.; Renner, R.; Wolf, S.
2000
Bound information: the classical analog to bound quantum entanglement
Type
Conference Proceedings
Author
Gisin, N.; Renner, R.; Wolf, S.
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