printlogo
http://www.ethz.ch/index_EN
Welcome
 
print
  

Renner, Renato, Prof. Dr.

Renato Renner

ETH Z├╝rich
Prof. Dr. Renato Renner
Institut f. Theoretische Physik
HIT K 41.2
Wolfgang-Pauli-Str. 27
8093 Zuerich

Phone: +41 44 633 34 58
Fax: +41 44 633 11 15
E-Mail: 

Head of the Institute for Theoretical Physics

Quantum Information Theory (QIT) Group

Download CV (including publication list)

Publications

124 records found

Title Author(s) Year
Full Security of Quantum Key Distribution From No-Signaling Constraints Details
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.
Pages 4973--4986
Volume 60
Issue 8
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Quantum conditional mutual information and approximate Markov chains Details
Fawzi, Omar; Renner, Renato 2014
Quantum conditional mutual information and approximate Markov chains
Type Online Database
Author Fawzi, Omar; Renner, Renato
Year 2014
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

Non-signalling parallel repetition using de Finetti reductions Details
Arnon-Friedman, Rotem; Renner, Renato; Vidick, Thomas 2014
Non-signalling parallel repetition using de Finetti reductions
Type Online Database
Author Arnon-Friedman, Rotem; Renner, Renato; Vidick, Thomas
Year 2014
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

Approximate Degradable Quantum Channels Details
Sutter, David; Scholz, Volkher B.; Renner, Renato 2014
Approximate Degradable Quantum Channels
Type Online Database
Author Sutter, David; Scholz, Volkher B.; Renner, Renato
Year 2014
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

Using quantum key distribution for cryptographic purposes: A survey Details
Alléaume, Romain; Branciard, Cyril; Bouda, Jan; Debuisschert, Thierry; Dianati, Mehrdad; Gisin, Nicolas; Godfrey, Mark; Grangier, Philippe; Länger, T.; Lütkenhaus, N.; Monyk, Christian; Painchault, Philippe; Peev, Momtchil; Poppe, Andreas; Pornin, Thomas; Rarity, John; Renner, Renato; Ribordy, Gregoire; Riguidel, Michel; Salvail, Louis; Shields, Andrew; Weinfurter, Harald; Zeilinger, Anton 2014
Using quantum key distribution for cryptographic purposes: A survey
Type Journal Article
Author Alléaume, Romain; Branciard, Cyril; Bouda, Jan; Debuisschert, Thierry; Dianati, Mehrdad; Gisin, Nicolas; Godfrey, Mark; Grangier, Philippe; Länger, T.; Lütkenhaus, N.; Monyk, Christian; Painchault, Philippe; Peev, Momtchil; Poppe, Andreas; Pornin, Thomas; Rarity, John; Renner, Renato; Ribordy, Gregoire; Riguidel, Michel; Salvail, Louis; Shields, Andrew; Weinfurter, Harald; Zeilinger, Anton
Year 2014
Journal Theoretical Computer Science
Abstract The SECOQC White Paper on Quantum Key Distribution and Cryptography is the outcome on a thorough consultation and discussion among the participants of the European project SECOQC (www.secoqc.net). This paper is a review article that attempts to position Quantum Key Distribution (QKD) in terms of cryptographic applications. A detailed comparison of QKD with the solutions currently in use to solve the key distribution problem, based on classical cryptography, is provided. We also detail how the work on QKD networks lead within SECOQC will allow the deployment of long-distance secure communication infrastructures based on quantum cryptography. The purpose of the White Paper is finally to promote closer collaboration between classical and quantum cryptographers. We believe that very fruitful research, involving both communities, could emerge in the future years and try to sketch what may be the next challenges in this direction.
Pages 62--81
Volume 560
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Efficient Approximation of Quantum Channel Capacities Details
Sutter, David; Sutter, Tobias; Esfahani, Peyman Mohajerin; Renner, Renato 2014
Efficient Approximation of Quantum Channel Capacities
Type Online Database
Author Sutter, David; Sutter, Tobias; Esfahani, Peyman Mohajerin; Renner, Renato
Year 2014
Abstract 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.
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

Relative Thermalization Details
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.
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

Classical leakage resilience from fault-tolerant quantum computation Details
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.
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

Gibbs-Preserving Maps outperform Thermal Operations in the quantum regime Details
Faist, Philippe; Oppenheim, Jonathan; Renner, Renato 2014
Gibbs-Preserving Maps outperform Thermal Operations in the quantum regime
Type Online Database
Author Faist, Philippe; Oppenheim, Jonathan; Renner, Renato
Year 2014
Abstract 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.
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

The ultimate physical limits of privacy. Details
Ekert, Artur; Renner, Renato 2014
The ultimate physical limits of privacy.
Type Journal Article
Author Ekert, Artur; Renner, Renato
Year 2014
Journal Nature
Abstract 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.
Pages 443--7
Volume 507
Issue 7493
URL Link to Website / File

      Export: EndNote XML · BibTex

One-Shot Decoupling Details
Dupuis, Frédéric; Berta, Mario; Wullschleger, Jürg; Renner, Renato 2014
One-Shot Decoupling
Type Journal Article
Author Dupuis, Frédéric; Berta, Mario; Wullschleger, Jürg; Renner, Renato
Year 2014
Journal Communications in Mathematical Physics
Abstract 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.
Pages 251--284
Volume 328
Issue 1
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

True randomness from realistic quantum devices Details
Frauchiger, D.; Renner, R.; Troyer, M. 2013
True randomness from realistic quantum devices
Type Online Database
Author Frauchiger, D.; Renner, R.; Troyer, M.
Year 2013
Abstract 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.
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

Efficient One-Way Secret-Key Agreement and Private Channel Coding via Polarization Details
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.
Pages 194--213
Volume 8269
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Truly Random Number Generation Details
Frauchiger, D.; Renner, R. 2013
Truly Random Number Generation
Type Conference Proceedings
Author Frauchiger, D.; Renner, R.
Year of Conference 2013
Conference Name SPIE Security+Defense
Abstract 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.
Volume 8899
URL Link to Website / File

      Export: EndNote XML · BibTex

Directed quantum communication Details
Åberg, J.; Hengl, S.; Renner, R. 2013
Directed quantum communication
Type Journal Article
Author Åberg, J.; Hengl, S.; Renner, R.
Year 2013
Journal New Journal of Physics
Abstract 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δ.
Pages 33025
Volume 15
Issue 3
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Security of two-way quantum key distribution Details
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.
Pages 62302
Volume 88
Issue 6
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Smooth Max-Information as One-Shot Generalization for Mutual Information Details
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.
Pages 1573--1581
Volume 60
Issue 3
URL Link to Website / File

      Export: EndNote XML · BibTex

One-Shot Lossy Quantum Data Compression Details
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.
Pages 8057--8076
Volume 59
Issue 12
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Generalized Entropies Details
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.
Pages 134--153
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Quantum information: From bits to solids Details
Renner, Renato 2013
Quantum information: From bits to solids
Type Journal Article
Author Renner, Renato
Year 2013
Journal Nature Physics
Abstract 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.
Pages 697--698
Volume 9
Issue 11
URL Link to Website / File

      Export: EndNote XML · BibTex

A system's wave function is uniquely determined by its underlying physical state Details
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Λ.
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

de Finetti reductions beyond quantum theory Details
Arnon-Friedman, Rotem; Renner, Renato 2013
de Finetti reductions beyond quantum theory
Type Online Database
Author Arnon-Friedman, Rotem; Renner, Renato
Year 2013
Abstract 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.
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

Device-Independent Quantum Key Distribution with Local Bell Test Details
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.
Pages 031006
Volume 3
Issue 3
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Efficient quantum channel coding scheme requiring no preshared entanglement Details
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.
Pages 354--358
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Security of Continuous-Variable Quantum Key Distribution Against General Attacks Details
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)].
Pages 030502
Volume 110
Issue 3
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

A short note on the concept of free choice Details
Colbeck, R.; Renner, R. 2013
A short note on the concept of free choice
Type Online Database
Author Colbeck, R.; Renner, R.
Year 2013
Abstract 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)].
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

Decoupling with unitary approximate two-designs Details
Szehr, Oleg; Dupuis, Frédéric; Tomamichel, Marco; Renner, Renato 2013
Decoupling with unitary approximate two-designs
Type Journal Article
Author Szehr, Oleg; Dupuis, Frédéric; Tomamichel, Marco; Renner, Renato
Year 2013
Journal New Journal of Physics
Abstract 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.
Pages 053022
Volume 15
Issue 5
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Chain Rules for Smooth Min- and Max-Entropies Details
Vitanov, Alexander; Dupuis, Frederic; Tomamichel, Marco; Renner, Renato 2013
Chain Rules for Smooth Min- and Max-Entropies
Type Journal Article
Author Vitanov, Alexander; Dupuis, Frederic; Tomamichel, Marco; Renner, Renato
Year 2013
Journal IEEE Transactions on Information Theory
Abstract 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.
Pages 2603--2612
Volume 59
Issue 5
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Composable security of delegated quantum computation Details
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.
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

An intuitive proof of the data processing inequality Details
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 definition of the entropy. The DPI for the von Neumann entropy is then obtained by specializing the DPI for the smooth min-entropy by using the quantum asymptotic equipartition property (QAEP). We provide a short proof of the QAEP and therefore obtain a self-contained proof of the DPI for the von Neumann entropy
Pages 432--441
Volume 12
Issue 5&6
URL Link to Website / File

      Export: EndNote XML · BibTex

Reliable Quantum State Tomography Details
Christandl, M.; Renner, R. 2012
Reliable Quantum State Tomography
Type Journal Article
Author Christandl, M.; Renner, R.
Year 2012
Journal Physical Review Letters
Abstract 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.
Pages 120403
Volume 109
Issue 12
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Is a system's wave function in one-to-one correspondence with its elements of reality? Details
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.
Pages 150402
Volume 108
Issue 15
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Tsirelson's bound from a Generalised Data Processing Inequality Details
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.
Pages 63024
Volume 14
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Trevisan's extractor in the presence of quantum side information Details
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.
Pages 915--940
Volume 41
Issue 4
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

The impossibility of non-signaling privacy amplification Details
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.
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Efficient Polar Coding of Quantum Information Details
Renes, J. M.; Dupuis, F.; Renner, R. 2012
Efficient Polar Coding of Quantum Information
Type Journal Article
Author Renes, J. M.; Dupuis, F.; Renner, R.
Year 2012
Journal Physical Review Letters
Abstract 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.
Pages 50504
Volume 109
Issue 5
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

One-Shot Classical Data Compression with Quantum Side Information and the Distillation of Common Randomness or Secret Keys Details
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.
Pages 1985--1991
Volume 58
Issue 3
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Ernst Specker and the Hidden Variables Details
Renner, R.; Wolf, S. 2012
Ernst Specker and the Hidden Variables
Type Journal Article
Author Renner, R.; Wolf, S.
Year 2012
Journal Elemente der Mathematik
Abstract 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.
Pages 122--133
Volume 67
Issue 3
URL Link to Website / File
 Link to Website / File

      Export: EndNote XML · BibTex

Towards characterizing the nonlocality of entangled quantum states Details
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.
URL Link to Website / File

      Export: EndNote XML · BibTex

The fridge gate Details
Renner, R. 2012
The fridge gate
Type Journal Article
Author Renner, R.
Year 2012
Journal Nature (News&Views)
Abstract 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.
Pages 164--165
Volume 482
URL Link to Website / File

      Export: EndNote XML · BibTex

Information Security in a Quantum World Details
Renner, R. 2012
Information Security in a Quantum World
Type Conference Proceedings
Author Renner, R.
Year of Conference 2012
Publisher Springer
Conference Name 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.
Pages 57--62
Volume 7119
URL Link to Website / File
 Link to Website / File

      Export: EndNote XML · BibTex

Experimental Bound on the Maximum Predictive Power of Physical Theories Details
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.
Pages 20402
Volume 109
Issue 2
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Achieving the Capacity of any DMC using only Polar Codes Details
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.
Pages 114--118
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Tight Finite-Key Analysis for Quantum Cryptography Details
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.
Pages 634
Volume 3
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Free randomness can be amplified Details
Colbeck, Roger; Renner, Renato 2012
Free randomness can be amplified
Type Journal Article
Author Colbeck, Roger; Renner, Renato
Year 2012
Journal Nature Physics
Abstract 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.
Pages 450--454
Volume 8
Issue 6
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

One-Shot Classical-Quantum Capacity and Hypothesis Testing Details
Wang, Ligong; Renner, Renato 2012
One-Shot Classical-Quantum Capacity and Hypothesis Testing
Type Journal Article
Author Wang, Ligong; Renner, Renato
Year 2012
Journal Physical Review Letters
Volume 108
Issue 20
URL Link to Website / File

      Export: EndNote XML · BibTex

Laws of thermodynamics beyond the von Neumann regime Details
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.
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

The completeness of quantum theory for predicting measurement outcomes Details
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.
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

Reply to recent scepticism about the foundations of quantum cryptography Details
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.
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

A Quantitative Landauer's Principle Details
Faist, Philippe; Dupuis, Frédéric; Oppenheim, Jonathan; Renner, Renato 2012
A Quantitative Landauer's Principle
Type Online Database
Author Faist, Philippe; Dupuis, Frédéric; Oppenheim, Jonathan; Renner, Renato
Year 2012
Abstract 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.
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

Sampling of min-entropy relative to quantum knowledge Details
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.
Pages 4760--4787
Volume 57
Issue 7
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Abstract cryptography Details
Maurer, U.; Renner, R. 2011
Abstract cryptography
Type Conference Proceedings
Author Maurer, U.; Renner, R.
Year of Conference 2011
Publisher Tsinghua University Press
Conference Name Innovations in Computers Science
Abstract 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.
Pages 1--21
Conference Location Beijing, China
URL Link to Website / File

      Export: EndNote XML · BibTex

Noisy channel coding via privacy amplification and information reconciliation Details
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.
Pages 7377--7385
Volume 57
Issue 11
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Quantum-Resilient Randomness Extraction Details
Renner, R. 2011
Quantum-Resilient Randomness Extraction
Type Conference Proceedings
Author Renner, R.
Year of Conference 2011
Publisher Springer
Conference Name 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.
Pages 52--57
Volume 6673
URL Link to Website / File

      Export: EndNote XML · BibTex

The thermodynamic meaning of negative entropy Details
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).
Pages 61--63
Volume 474
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Localization of Toric Code Defects Details
Stark, C.; Pollet, L.; Imamoglu, A.; Renner, R. 2011
Localization of Toric Code Defects
Type Journal Article
Author Stark, C.; Pollet, L.; Imamoglu, A.; Renner, R.
Year 2011
Journal Physical Review Letters
Abstract 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.
Pages 30504
Volume 107
Issue 3
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Uncertainty Relation for Smooth Entropies Details
Tomamichel, Marco; Renner, Renato 2011
Uncertainty Relation for Smooth Entropies
Type Journal Article
Author Tomamichel, Marco; Renner, Renato
Year 2011
Journal Physical Review Letters
Pages 110506
Volume 106

      Export: EndNote XML · BibTex

Impossibility of Growing Commitments Details
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.
Pages 90502
Volume 107
Issue 9
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

No extension of quantum theory can have improved predictive power Details
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.
Pages 411
Volume 2
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Min- and Max-Entropy in Infinite Dimensions Details
Furrer, Fabian; Åberg, Johan; Renner, Renato 2011
Min- and Max-Entropy in Infinite Dimensions
Type Journal Article
Author Furrer, Fabian; Åberg, Johan; Renner, Renato
Year 2011
Journal Communications in Mathematical Physics
Pages 165--186
Volume 306
Issue 1
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

The Quantum Reverse Shannon Theorem based on One-Shot Information Theory Details
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.
Pages 579--615
Volume 306
Issue 3
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Leftover Hashing Against Quantum Side Information Details
Tomamichel, Marco; Schaffner, Christian; Smith, Adam; Renner, Renato 2011
Leftover Hashing Against Quantum Side Information
Type Journal Article
Author Tomamichel, Marco; Schaffner, Christian; Smith, Adam; Renner, Renato
Year 2011
Journal IEEE Transactions 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 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.
Pages 5524--5535
Volume 57
Issue 8
URL Link to Website / File

      Export: EndNote XML · BibTex

Inadequacy of von Neumann entropy for characterizing extractable work Details
Dahlsten, Oscar C. O.; Renner, Renato; Rieper, Elisabeth; Vedral, Vlatko 2011
Inadequacy of von Neumann entropy for characterizing extractable work
Type Journal Article
Author Dahlsten, Oscar C. O.; Renner, Renato; Rieper, Elisabeth; Vedral, Vlatko
Year 2011
Journal New Journal of Physics
Pages 53015
Volume 13
Issue 5
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

The uncertainty principle in the presence of quantum memory Details
Berta, Mario; Christandl, Matthias; Colbeck, Roger; Renes, Joseph M.; Renner, Renato 2010
The uncertainty principle in the presence of quantum memory
Type Journal Article
Author Berta, Mario; Christandl, Matthias; Colbeck, Roger; Renes, Joseph M.; Renner, Renato
Year 2010
Publisher Nature Publishing Group
Journal Nature Physics
Pages 659--662
Volume 6
Issue 9
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Device-Independent Quantum Key Distribution with Commuting Measurements Details
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.
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

A Conceptually Simple Proof of the Quantum Reverse Shannon Theorem Details
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.
Pages 131--140
Volume 6519
Conference Location Leeds
URL Link to Website / File

      Export: EndNote XML · BibTex

Duality between smooth min- and max-entropies Details
Tomamichel, M.; Colbeck, R.; Renner, R. 2010
Duality between smooth min- and max-entropies
Type Journal Article
Author Tomamichel, M.; Colbeck, R.; Renner, R.
Year 2010
Journal IEEE Transactions on information theory
Pages 4674--4681
Volume 56
Issue 9

      Export: EndNote XML · BibTex

Leftover Hashing against quantum side information (short version) Details
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.
Pages 2703--2707
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Simplifying information-theoretic arguments by post-selection Details
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.
Pages 66--75
Volume 26
Notes Submimtted version: http://www.qit.ethz.ch/paperPDFs/Post_Selection/
URL Link to Website / File

      Export: EndNote XML · BibTex

Efficient Device-Independent Quantum Key Distribution Details
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.
Pages 216--234
Volume 6110
Editor Gilbert, Henri
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

The Operational Meaning of Min- and Max-Entropy Details
Koenig, R.; Renner, R.; Schaffner, C. 2009
The Operational Meaning of Min- and Max-Entropy
Type Journal Article
Author Koenig, R.; Renner, R.; Schaffner, C.
Year 2009
Journal IEEE Transactions on Information Theory
Abstract 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.
Pages 4337--4347
Volume 55
Issue 9
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Composability in quantum cryptography Details
Mueller-Quade, J.; Renner, R. 2009
Composability in quantum cryptography
Type Journal Article
Author Mueller-Quade, J.; Renner, R.
Year 2009
Journal New Journal of Physics
Abstract 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
Pages 85006
Volume 11
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Space-quest, experiments with quantum entanglement in space Details
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.
Pages 26--29
Volume 40
Issue 3
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

de Finetti Representation Theorem for Infinite-Dimensional Quantum Systems and Applications to Quantum Cryptography Details
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.
Pages 110504
Volume 102
Issue 11
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Optimal decoupling Details
Renner, R. 2009
Optimal decoupling
Type Conference Proceedings
Author Renner, R.
Year of Conference 2009
Publisher World Scientific
Conference Name 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.
Pages 541--545
URL Link to Website / File

      Export: EndNote XML · BibTex

A Fully Quantum Asymptotic Equipartition Property Details
Tomamichel, Marco; Colbeck, Roger; Renner, Renato 2009
A Fully Quantum Asymptotic Equipartition Property
Type Journal Article
Author Tomamichel, Marco; Colbeck, Roger; Renner, Renato
Year 2009
Journal IEEE Transactions on Information Theory
Pages 5840--5847
Volume 55
Issue 12
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Simple channel coding bounds Details
Wang, L.; Renner, R.; Colbeck, R. 2009
Simple channel coding bounds
Type Conference Proceedings
Author Wang, L.; Renner, R.; Colbeck, R.
Year of Conference 2009
Conference Name 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.
Pages 1804--1808
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Postselection Technique for Quantum Channels with Applications to Quantum Cryptography Details
Christandl, Matthias; König, Robert; Renner, Renato 2009
Postselection Technique for Quantum Channels with Applications to Quantum Cryptography
Type Journal Article
Author Christandl, Matthias; König, Robert; Renner, Renato
Year 2009
Publisher American Physical Society
Journal Physical Review Letters
Pages 20504
Volume 102
Issue 2
URL Link to Website / File

      Export: EndNote XML · BibTex

Smooth Entropies and the Quantum Information Spectrum Details
Datta, Nilanjana; Renner, Renato 2009
Smooth Entropies and the Quantum Information Spectrum
Type Journal Article
Author Datta, Nilanjana; Renner, Renato
Year 2009
Journal IEEE Transactions on Information Theory
Pages 2807----2815
Volume 55
Issue 6
URL Link to Website / File

      Export: EndNote XML · BibTex

Defining the local part of a hidden variable model: a comment Details
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.
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

Hidden Variable Models for Quantum Theory Cannot Have Any Local Part Details
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.
Pages 50403
Volume 101
Issue 5
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Quantum Key Distribution Details
Renner, R. 2008
Quantum Key Distribution
Type Generic
Author Renner, R.
Year 2008
Publisher Springer
Secondary Title Encyclopedia of Algorithms
Abstract 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.
Pages 708--711
URL Link to Website / File

      Export: EndNote XML · BibTex

Extracting classical randomness in a quantum world Details
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.
Pages 360--363
URL Link to Website / File

      Export: EndNote XML · BibTex

Quantum Cryptography with Finite Resources: Unconditional Security Bound for Discrete-Variable Protocols with One-Way Postprocessing Details
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.
Pages 200501
Volume 100
Issue 20
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Security Bounds for Quantum Cryptography with Finite Resources Details
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.
Volume 5106
Editor Kawano, Y.; Mosca, M.
City Berlin Heidelberg
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Small Accessible Quantum Information Does Not Imply Security Details
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.
Pages 140502
Volume 98
Issue 14
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Symmetry of large physical systems implies independence of subsystems Details
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.
Pages 645--649
Volume 3
Issue 9

      Export: EndNote XML · BibTex

Computational Indistinguishability Amplification: Tight Product Theorems for System Composition Details
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.
Volume 4622
Editor Menezes, A.
Notes Submitted version: https://edit.ethz.ch/qit/paperPDFs/MaPiRe07.pdf/
URL Link to Website / File

      Export: EndNote XML · BibTex

Unbreakable Keys from Random Noise Details
Maurer, U.; Renner, R.; Wolf, S. 2007
Unbreakable Keys from Random Noise
Type Book Section
Author Maurer, U.; Renner, R.; Wolf, S.
Year 2007
Publisher Springer
Abstract 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.
Editor Tuyls, P.; Skoric, B.; Kevenaar, T.
City London
Notes Submitted version: https://edit.ethz.ch/qit/paperPDFs/RennerWolf.pdf/
URL Link to Website / File

      Export: EndNote XML · BibTex

Beweisbare Sicherheit durch Quantenkryptografie (Provable Security in Quantum Cryptography) Details
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.
Pages 127--130
Volume 49
Issue 2
URL Link to Website / File

      Export: EndNote XML · BibTex

Trade-Offs in Information-Theoretic Multi-Party One-Way Key Agreement Details
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.
Pages 65--75
Notes Submitted version: https://edit.ethz.ch/qit/paperPDFs/ReWoWu07.pdf/
URL Link to Website / File

      Export: EndNote XML · BibTex

Security of quantum-key-distribution protocols using two-way classical communication or weak coherent pulses Details
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.
Pages 12316
Volume 75
Issue 1
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

One-and-a-Half Quantum de Finetti Theorems Details
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.
Pages 473--498
Volume 273
Issue 2
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

A Tight High-Order Entropic Quantum Uncertainty Relation with Applications Details
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.
Volume 4622
Editor Menezes, A.
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Unifying classical and quantum key distillation Details
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.
Pages 456--478
Volume 4392
Conference Location Amsterdam
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

On the Impossibility of Extracting Classical Randomness Using a Quantum Computer Details
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.
City Berlin Heidelberg
URL Link to Website / File

      Export: EndNote XML · BibTex

On the randomness of independent experiments Details
Holenstein, T.; Renner, R. 2006
On the randomness of independent experiments
Type Journal Article
Author Holenstein, T.; Renner, R.
Year 2006
Journal IEEE Transactions on Information Theory
Abstract 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).
Pages 1865--1871
Volume 57
Issue 4
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

The Single-Serving Channel Capacity Details
Renner, R.; Wolf, S.; Wullschleger, J. 2006
The Single-Serving Channel Capacity
Type Conference Proceedings
Author Renner, R.; Wolf, S.; Wullschleger, J.
Year of Conference 2006
Conference Name 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?
Pages 1424--1427
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Security of Quantum Key Distribution Details
Renner, Renato 2005
Security of Quantum Key Distribution
Type Thesis
Author Renner, Renato
Year 2005
University ETH Zürich
Thesis Type PhD Thesis
URL Link to Website / File

      Export: EndNote XML · BibTex

Information-theoretic security proof for quantum-key-distribution protocols Details
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.
Pages 12332
Volume 72
Issue 1
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

On the variational distance of independently repeated experiments Details
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.
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

Simple and Tight Bounds for Information Reconciliation and Privacy Amplification Details
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 satisfied. An example is quantum key agreement, where the adversary can attack each particle sent through the quantum channel differently or even carry out coherent attacks, combining a number of particles together. In information-theoretic key agreement, the central functionalities of information reconciliation and privacy amplification have, therefore, been extensively studied in the scenario of general distributions : Partial solutions have been given, but the obtained bounds are arbitrarily far from tight, and a full analysis appeared to be rather involved to do. We show that, actually, the general case is not more difficult than the scenario of independent repetitions—in fact, given our new point of view, even simpler. When one analyzes the possible efficiency of data compression and randomness extraction in the case of independent repetitions, then Shannon entropy H is the answer. We show that H can, in these two contexts, be generalized to two very simple quantities—H_0 epsilon and H_infty epsilon, called smooth Renyi entropies—which are tight bounds for data compression (hence, information reconciliation) and randomness extraction (privacy amplification), respectively. It is shown that the two new quantities, and related notions, do not only extend Shannon entropy in the described contexts, but they also share central properties of the latter such as the chain rule as well as sub-additivity and monotonicity.
Pages 199--216
Volume 3788
Editor Roy, B.
Notes Submitted version: https://edit.ethz.ch/qit/paperPDFs/RenWol05.pdf/
URL Link to Website / File

      Export: EndNote XML · BibTex

Universally Composable Privacy Amplification Against Quantum Adversaries Details
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.
Pages 407--425
Volume 3378
Editor Kilian, J.
City Berlin Heidelberg
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

Lower and Upper Bounds on the Secret-Key Rate for Quantum Key Distribution Protocols Using One-Way Classical Communication Details
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.
Pages 80501
Volume 95
Issue 8
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

A de Finetti representation for finite symmetric quantum states Details
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.
Pages 122108
Volume 46
Issue 12
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

On the power of quantum memory Details
Koenig, R.; Maurer, U.; Renner, R. 2005
On the power of quantum memory
Type Journal Article
Author Koenig, R.; Maurer, U.; Renner, R.
Year 2005
Journal IEEE Transactions on Information Theory
Abstract 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.
Pages 2391--2401
Volume 51
Issue 7
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

One-Way Secret-Key Agreement and Applications to Circuit Polarization and Immunization of Public-Key Encryption Details
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.
Pages 478--493
Volume 3621
Editor Shoup, V.
Notes Submitted version: https://edit.ethz.ch/qit/paperPDFs/HolRen05.pdf/
URL Link to Website / File

      Export: EndNote XML · BibTex

A Generic Security Proof for Quantum Key Distribution Details
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.
Name of Database arXiv.org
URL Link to Website / File

      Export: EndNote XML · BibTex

The Exact Price for Unconditionally Secure Asymmetric Cryptography Details
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.
Pages 109--125
Volume 3027
Editor Cachin, C.; Camenisch, J.
Notes Submitted version: https://edit.ethz.ch/qit/paperPDFs/RenWol04.pdf/
URL Link to Website / File

      Export: EndNote XML · BibTex

Quantum pseudo-telepathy and the Kochen-Specker theorem Details
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.
Pages 322
URL Link to Website / File

      Export: EndNote XML · BibTex

Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology Details
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.
Pages 21--39
Volume 2951
Editor Naor, M.
City Berlin Heidelberg
Notes Submitted version: https://edit.ethz.ch/qit/paperPDFs/MaReHo04.pdf/
URL Link to Website / File

      Export: EndNote XML · BibTex

Privacy amplification secure against an adversary with selectable knowledge Details
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.
Pages 231
URL Link to Website / File

      Export: EndNote XML · BibTex

On intrinsic information Details
Christandl, M.; Renner, R. 2004
On intrinsic information
Type Conference Proceedings
Author Christandl, M.; Renner, R.
Year of Conference 2004
Publisher IEEE
Conference Name 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.
Conference Location Chicago
URL Link to Website / File

      Export: EndNote XML · BibTex

Smooth Renyi entropy and applications Details
Renner, Renato; Wolf, Stephan 2004
Smooth Renyi entropy and applications
Type Conference Proceedings
Author Renner, Renato; Wolf, Stephan
Year of Conference 2004
Conference Name Information Theory, 2004. ISIT 2004. Proceedings. International Symposium on
Pages 233
URL Link to Website / File

      Export: EndNote XML · BibTex

New Bounds in Secret-Key Agreement: The Gap between Formation and Secrecy Extraction Details
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.
Volume 2656
Editor Biham, E.
URL Link to Website / File

      Export: EndNote XML · BibTex

A new measure for conditional mutual information and its properties Details
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.
Pages 259
URL Link to Website / File

      Export: EndNote XML · BibTex

Unconditional Authenticity and Privacy from an Arbitrarily Weak Secret Details
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.
Pages 78--95
Volume 2729
URL Link to Website / File

      Export: EndNote XML · BibTex

Towards characterizing the nonlocality of entangled quantum states Details
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.
Pages 428
URL Link to Website / File
Link to Website / File

      Export: EndNote XML · BibTex

A property of the intrinsic mutual information Details
Christandl, M.; Renner, R.; Wolf, S. 2003
A property of the intrinsic mutual information
Type Conference Proceedings
Author Christandl, M.; Renner, R.; Wolf, S.
Year of Conference 2003
Conference Name 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.
Pages 258
URL Link to Website / File

      Export: EndNote XML · BibTex

Generalized indistinguishability Details
Maurer, U.; Renner, R. 2002
Generalized indistinguishability
Type Conference Proceedings
Author Maurer, U.; Renner, R.
Year of Conference 2002
Conference Name 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.
Pages 295
URL Link to Website / File

      Export: EndNote XML · BibTex

About the mutual (conditional) information Details
Renner, R.; Maurer, U. 2002
About the mutual (conditional) information
Type Conference Proceedings
Author Renner, R.; Maurer, U.
Year of Conference 2002
Conference Name 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.
Pages 364
URL Link to Website / File

      Export: EndNote XML · BibTex

Towards proving the existence of"bound"information Details
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.
Pages 103
URL Link to Website / File

      Export: EndNote XML · BibTex

Linking Classical and Quantum Key Agreement: Is There a Classical Analog to Bound Entanglement? Details
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.
Pages 389--412
Volume 34
Issue 4
URL Link to Website / File

      Export: EndNote XML · BibTex

Bound information: the classical analog to bound quantum entanglement Details
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.
Pages 439--447
Volume 202
URL Link to Website / File

      Export: EndNote XML · BibTex

 

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

© 2014 ETH Zurich | Imprint | Disclaimer | 11 October 2014
top