Key reconciliation for high performance Quantum Key Distribution

Quantum Key Distribution is carving its place among the tools used to secure communications. While a difficult technology, it enjoys benefits that set it apart from the rest, the most prominent is its provable security based on the laws of physics. QKD requires not only the mastering of signals at the quantum level, but also a classical processing to extract a secret-key from them. This postprocessing has been customarily studied in terms of the efficiency, a figure of merit that offers a biased view of the performance of real devices. Here we argue that it is the throughput the significant magnitude in practical QKD, specially in the case of high speed devices, where the differences are more marked, and give some examples contrasting the usual postprocessing schemes with new ones from modern coding theory. A good understanding of its implications is very important for the design of modern QKD devices.

Analysis of a rate-adaptive reconciliation protocol and the effect of leakage on the secret key rate

Quantum key distribution performs the trick of growing a secret key in two distant places connected by a quantum channel. The main reason is so that the legitimate users can bound the information gathered by the eavesdropper. In practical systems, whether because of finite resources or external conditions, the quantum channel is subject to fluctuations. A rate-adaptive information reconciliation protocol, which adapts to the changes in the communication channel, is then required to minimize the leakage of information in the classical postprocessing. We consider here the leakage of a rate-adaptive information reconciliation protocol. The length of the exchanged messages is larger than that of an optimal protocol; however, we prove that the min-entropy reduction is limited. The simulation results, both in the asymptotic and in the finite-length regime, show that this protocol allows to increase the amount of a distillable secret key.

Demystifying the information reconciliation protocol cascade

Cascade is an information reconciliation protocol proposed in the context of secret key agreement in quantum cryptography. This protocol allows removing discrepancies in two partially correlated sequences that belong to distant parties, connected through a public noiseless channel. It is highly interactive, thus requiring a large number of channel communications between the parties to proceed and, although its efficiency is not optimal, it has become the de-facto standard for practical implementations of information reconciliation in quantum key distribution. The aim of this work is to analyze the performance of Cascade, to discuss its strengths, weaknesses and optimization possibilities, comparing with some of the modified versions that have been proposed in the literature. When looking at all design trade-offs, a new view emerges that allows to put forward a number of guidelines and propose near optimal parameters for the practical implementation of Cascade improving performance significantly in comparison with all previous proposals.

Information reconciliation for Quantum Key Distribution

Secret-key agreement, a well-known problem in cryptography, allows two parties holding correlated sequences to agree on a secret key communicating over a public channel. It is usually divided into three different procedures: advantage distillation, information reconciliation and privacy amplification. The efficiency of each one of these procedures is needed if a positive key rate is to be attained from the legitimate parties? correlated sequences. Quantum key distribution (QKD) allows the two parties to obtain correlated sequences, provided that they have access to an authenticated channel. The new generation of QKD devices is able to work at higher speeds and in noisier or more absorbing environments. This exposes the weaknesses of current information reconciliation protocols, a key component to their performance. Here we present a new protocol based in low-density parity-check (LDPC) codes that presents the advantages of low interactivity, rate adaptability and high efficiency,characteristics that make it highly suitable for next generation QKD devices.

Fundamental finite key limits for information reconciliation in quantum key distribution

The security of quantum key distribution protocols is guaranteed by the laws of quantum mechanics. However, a precise analysis of the security properties requires tools from both classical cryptography and information theory. Here, we employ recent results in non-asymptotic classical information theory to show that information reconciliation imposes fundamental limitations on the amount of secret key that can be extracted in the finite key regime. In particular, we find that an often used approximation for the information leakage during one-way information reconciliation is flawed and we propose an improved estimate.

Information reconciliation methods in secret key distribution

We consider in this thesis the problem of information reconciliation in the context of secret key distillation between two legitimate parties. In some scenarios of interest this problem can be advantageously solved with low density parity check (LDPC) codes optimized for the binary symmetric channel. In particular, we demonstrate that our method leads to a significant efficiency improvement, with respect to earlier interactive reconciliation methods. We propose a protocol based on LDPC codes that can be adapted to changes in the communication channel extending the original source. The efficiency of our protocol is only limited by the quality of the code and, while transmitting more information than needed to reconcile Alice’s and Bob’s sequences, it does not reveal any more information on the original source than an ad-hoc code would have revealed.---ABSTRACT---En esta tesis estudiamos el problema de la reconciliación de información en el contexto de la destilación de secreto entre dos partes. En algunos escenarios de interés, códigos de baja densidad de ecuaciones de paridad (LDPC) adaptados al canal binario simétrico ofrecen una buena solución al problema estudiado. Demostramos que nuestro método mejora significativamente la eficiencia de la reconciliación. Proponemos un protocolo basado en códigos LDPC que puede ser adaptado a cambios en el canal de comunicaciones mediante una extensión de la fuente original. La eficiencia de nuestro protocolo está limitada exclusivamente por el código utilizado y no revela información adicional sobre la fuente original que la que un código con la tasa de información adaptada habría revelado.

An information reconciliation protocol for secret-key agreement with small leakage

We report on a variant of the so-called Cascade protocol that is well-known for its usage as information reconciliation protocol in quantum cryptography. A theoretical analysis of the optimal size of the parity check blocks is provided. We obtain a very small leakage which is for block sizes of 2^16 typically only 2.5% above the Shannon limit, and notably, this holds for a QBER between 1% and 50%. For a QBER between 1% and 6% the leakage is only 2% above the Shannon limit. As comparison, the leakage of the original Cascade algorithm is 20% (40%) above the Shannon limit for a QBER of 10% (35%).

Rate-Adaptive LDPC-based key reconciliation for high performance quantum key distribution

The postprocessing or secret-key distillation process in quantum key distribution (QKD) mainly involves two well-known procedures: information reconciliation and privacy amplification. Information or key reconciliation has been customarily studied in terms of efficiency. During this, some information needs to be disclosed for reconciling discrepancies in the exchanged keys. The leakage of information is lower bounded by a theoretical limit, and is usually parameterized by the reconciliation efficiency (or inefficiency), i.e. the ratio of additional information disclosed over the Shannon limit. Most techniques for reconciling errors in QKD try to optimize this parameter. For instance, the well-known Cascade (probably the most widely used procedure for reconciling errors in QKD) was recently shown to have an average efficiency of 1.05 at the cost of a high interactivity (number of exchanged messages). Modern coding techniques, such as rate-adaptive low-density parity-check (LDPC) codes were also shown to achieve similar efficiency values exchanging only one message, or even better values with few interactivity and shorter block-length codes.

Efficient information reconciliation for Continuous-Variable QKD using Non-Binary Low-Density Parity-Check Codes

We present here an information reconciliation method and demonstrate for the first time that it can achieve efficiencies close to 0.98. This method is based on the belief propagation decoding of non-binary LDPC codes over finite (Galois) fields. In particular, for convenience and faster decoding we only consider power-of-two Galois fields.

Blind reconiliation

Information reconciliation is a crucial procedure in the classical post-processing of quantum key distribution (QKD). Poor reconciliation e?ciency, revealing more information than strictly needed, may compromise the maximum attainable distance, while poor performance of the algorithm limits the practical throughput in a QKD device. Historically, reconciliation has been mainly done using close to minimal information disclosure but heavily interactive procedures, like Cascade, or using less e?cient but also less interactive ?just one message is exchanged? procedures, like the ones based in low-density parity-check (LDPC) codes. The price to pay in the LDPC case is that good e?ciency is only attained for very long codes and in a very narrow range centered around the quantum bit error rate (QBER) that the code was designed to reconcile, thus forcing to have several codes if a broad range of QBER needs to be catered for. Real world implementations of these methods are thus very demanding, either on computational or communication resources or both, to the extent that the last generation of GHz clocked QKD systems are ?nding a bottleneck in the classical part. In order to produce compact, high performance and reliable QKD systems it would be highly desirable to remove these problems. Here we analyse the use of short-length LDPC codes in the information reconciliation context using a low interactivity, blind, protocol that avoids an a priori error rate estimation. We demonstrate that 2×103 bits length LDPC codes are suitable for blind reconciliation. Such codes are of high interest in practice, since they can be used for hardware implementations with very high throughput.

Towards an Optimal Implementation of Cascade

Cascade is an information reconciliation protocol proposed in the context of secret key agreement in quantum cryptography. This protocol allows removing discrepancies in two partially correlated sequences that belong to distant parties, connected through a public noiseless channel. It is highly interactive, thus requiring a large number of channel communications between the parties to proceed and, although its efficiency is not optimal, it has become the de-facto standard for practical implementations of information reconciliation in quantum key distribution. The aim of this work is to analyze the performance of Cascade, to discuss its strengths, weaknesses and optimization possibilities, comparing with some of the modified versions that have been proposed in the literature. When looking at all design trade-offs, a new view emerges that allows to put forward a number of guidelines and propose near optimal parameters for the practical implementation of Cascade improving performance significantly in comparison with all previous proposals.

Las casualidades controladas : la primera visibilidad del cambio del paradigma moderno

Como no pocos proyectos, el origen de esta tesis es fruto de una casualidad. Hace unos años me topé en Londres, en la librería Walden Books del 38 de Harmood St., con una primera edición de la conocida monografía de Mies a cargo de Philip Johnson. El librito, en realidad catálogo de la exposición que en 1947 el MoMA de Nueva York dedicara a la obra de Mies Van der Rohe a los diez años del desembarco del arquitecto en Estados Unidos, tiene un tamaño de 10 x 7,5 pulgadas, es decir, la mitad del formato americano Crown (20x15 pulgadas), equivalente a 508 x 381 mm. Se imprimieron, en su primera tirada, editada por The Plantin Press, 12.000 ejemplares. Ese mismo año, con edición al cuidado de Reynal y Hitchcock, se publicaría la primera traducción al inglés de Cuando las catedrales eran blancas de Le Corbusier y una selección de poemas de Lorca, siete años después de su Poeta en Nueva York. En la monografía, en la página 109, aparece el conocido croquis de Mies Sketch for a glass house on a hillside. c. 1934, escasamente unas líneas, aunque precisas y llenas de matices, de la casa en una ladera que rápidamente nos remite a aquella primera propuesta de Saarinen para una casa en el aire, primero en 1941 en Pensilvania y después, en 1945, con Charles Eames, en Los Angeles, que nunca llegarían a construirse, sino en su aliteraciones posteriores realizadas por Harry Seidler (Julian Rose House, Wahroonga, Sydney, 1949), Philip Johnson (Leonhardt house, Long Island, Nueva York, 1956) o Craig Ellwood (Smith House, Crestwood Hills, 1958; Frank & Polly Pierson House, Malibú, 1962; Chamorro House, Hollywood Hills, 1963, o la serie Weekend House, con Gerald Horn, entre 1964 y 1970, hasta el magnífico Art Center College of Design de Pasadera, su puente habitado de 1977). El relato que da origen al texto discurre en un estricto período de tiempo, desde los primeros dibujos de la Case Study House nº8, dentro del programa promovido por John Entenza y su revista Arts & Architecture en California, realizados en el estudio de Saarinen en Bloomfield Hills, Michigan, hasta que el proyecto de la casa Eames finaliza cinco años después de acabar la obra en 1955, en la versión conocida, radicalmente distinta al proyecto original, cuando la pareja Charles y Ray Eames edita el corto House After Five Years of Living. La discusión original en torno a esta casita, o mejor, a las circunstancias, casualidades controladas, que rodean su construcción, se produce estrictamente cuando rastreamos aquellos invariantes que se mantienen en las dos versiones y las reconcilian. En este corto período de tiempo se producen en el proyecto una serie de decisiones que permiten descubrir, tanto en la forma como en el mismo proceso transformador del proyecto, en su obsesivo registro, en los nuevos referentes asumidos y propuestos, la primera visibilidad del cambio del paradigma moderno. Pero este momento germinal que cristaliza el paso a la postmodernidad no es inédito en la historia de la arquitectura americana. Así, el relato abre su ámbito temporal hasta un nuevo período de cincuenta años que arranca en 1893, año de la celebración en Chicago de la Exposición Internacional Colombina. En la White City de Hunt & McKim y del traidor Burham, Louis Sullivan construye su Golden Doorway en el pabellón de los Transportes. Aquella que visitará Adolf Loos antes de volver, renovado, a Viena; la misma que admirará André Bouillet, representante de la Union Centrale des Arts Decoratifs de Paris, y que deslumbrará en los museos de toda Europa, de París a Moscú en grandes fotografías y maquetas. Hasta que en Finlandia alguien muestra una de esas fotografías a un joven estudiante de diecinueve años en el Instituto Politécnico. Eliel Saarinen queda fascinado por la poderosa novedad de la imagen. Cuelga la fotografía frente a su tablero de dibujo, consciente de que la Golden Doorway, esa puerta de la aventura y la catarsis que Sullivan acuñaría como distintivo y que resolvería como único elemento complejo sus proyectos más maduros, desprovistos de todo ornamento; la misma que repetirían más tarde, con profundo reconocimiento, Ladovsky, Wright, Scarpa o Moneo, puerta dentro de puerta, fuelle y umbral, contenía, en sus propias palabras emocionadas, todo el futuro de la arquitectura. Desde ahí, pasando por el año 1910, momento de la huida de Wright a La Toscana y el descubrimiento de su arquitectura en Europa, entre otros por un joven Mies van der Rohe, meritorio en el estudio de Peter Behrens, a través del Wasmuth Portfolio; y así como algo después, en 1914, Schindler y en 1923 Neutra, harán el camino inverso, hasta que Mies les siga en 1937, animado por un Philip Johnson que había viajado a Europa en 1930, volviendo a 1945 y el inicio del programa Case Study House en California, hasta 1949, momento de la construcción de la CSH#8, y, por fin, al año 1955, after 5 years of living, en el que Julius Shulman fotografía la casa de Ray y Charles Eames en el prado de Chautauqua sobre las Pacific Palisades de Los Angeles, lanzando sus finas líneas amarillas hasta Alison y Peter Smithson y su tardomoderno heroico, hasta el primer Foster y su poético hightech y hasta el O-riginal Ghery, deconstruyendo el espacio esencial de su casa desde el espacio mismo, abiertas ya las puertas al nuevo siglo. Y en estos cambios de paradigma, desde el rígido eclecticismo de los estilos al lirismo moderno en el gozne secular y de ahí a la frivolidad, ligereza, exhibicionismo y oportunismo cultos del hecho postmoderno, hay algo que se mantiene invariante en los bandazos de la relación del hombre contemporáneo con su entorno. Como la escultura, que según Barnett Newman no es sino aquello contra lo que uno choca cuando retrocede para mirar un cuadro, en estos prístinos lugares, comunes y corrientes, recorrido, puerta, umbral, recinto y vacío, te topas con la arquitectura antes de darte cuenta de que es arquitectura. ABSTRACT As with many other projects, the origin of this doctoral thesis is the result of a chance. A few years ago I found in a bookstore in London, 38 Harmood st., Walden Books, a first edition of the well-known monograph about Mies by Philip Johnson. The tiny book, in fact a catalog of the exhibition that the MoMA of New York devoted to the work of Mies van der Rohe in 1947, ten years after his landing in the United States, has a size of 10 x 7.5 inches, that is, half of Crown American format (20 x 15 inches), equivalent to 508 x 381 mm. In the first printing, published by The Plantin Press, 12,000 copies were released. That same year, produced by Reynal and Hitchcock, both the first English translation of When the cathedrals were white by Le Corbusier and a selection of poems by Lorca were published, seven years after his Poet in New York. Inside the book, the famous drawing from Mies Sketch for a glass house on a hillside c. 1934 appears on page 109, barely a few lines, precise and nuanced though, the house on a hillside that quickly reminds us of the proposals of Eero Saarinen for a house in the air, first in 1941, in Pennsylvania, and later, in 1945, with Charles Eames, in Los Angeles, that would never be built, but in their later alliterations made by Harry Seidler (Julian Rose House, Wahroonga, Sydney, 1949), Philip Johnson (Leonhardt house, Long Island, New York, 1956) or Craig Ellwood (Smith House, Crestwood Hills, 1958; Frank Pierson & Polly House, Malibu, 1962, Chamorro House, Hollywood Hills, 1963, or the Weekend House series, with Gerald Horn, between 1964 and 1970, to the magnificent Art Center College of Design Pasadena, the inhabited bridge, in 1977). The story that gives rise to the text flows in a short amount of time, from the first drawings of the Case Study House No. 8, within the program promoted by John Entenza and his magazine Arts & Architecture in California, made in the study of Saarinen in Bloomfield Hills, Michigan, until the project of the Eames house is completed five years after finishing the construction in 1955, in the final version we know, radically different from the initial state, when the couple, Charles and Ray, published the film House after Five Years of Living. The original discussion around this house, or better, about the circumstances, controlled coincidences, regarding its construction, appears when one takes account of those that remain, the invariants, in the two versions, drawn and built, which precisely allow the reconciliation between both projects. In this short period of time a series of decisions made in the transformation process of the project reveal, in the obsessive record made by Charles Eames and in the new proposed references, the first visibility of the changing of the modern paradigm. But this germinal moment that crystallizes the transition to postmodernism is not unprecedented in the history of American architecture. So, the story opens its temporal scope to a fifty-year period that started in 1893, date of the celebration of the Chicago World´s Columbian Exposition. In the White City by Hunt & McKim and Burnham, the traitor, Louis Sullivan builds his Golden Doorway in the Transportation Building. That visited by a renovated Adolf Loos before his coming back to Vienna; the same that André Bouillet, Head of the Union Centrale des Arts Decoratifs in Paris, admired and dazzled in museums all over Europe, from Paris to Moscow, in large photographs and models. Until someone in Finland showed one of those photos to a young nineteen-years-old student at the Polytechnic Institute. Eliel Saarinen became fascinated by the powerful new image: he hanged the picture in front of his drawing board, aware that the Golden Doorway, that door of adventure and catharsis Sullivan coined as distinctive and as a single complex element which would solve their most mature projects, devoid of all ornament; the same that would repeat later, with deep appreciation, Ladovsky, Wright, Scarpa, or Moneo, a door inside a door, a threshold, a gap that contained, in its own moving words, the whole future of architecture. From there, through 1910, when Wright's flight to Tuscany allows Europe to discover his architecture, including a young Mies van der Rohe, meritorious in the studio of Peter Behrens, via the Wasmuth Portfolio; and as a little bit later, in 1914, Schindler and Neutra in 1923, made the travel in opposite direction, until Mies follows them in 1937, led by a Philip Johnson who had traveled to Europe in 1930, we return to 1945 and the beginning of the program Case Study House in California, and from 1949, when construction of the CSH # 8 begins, and finally, to 1955, after five years of living, when Julius Shulman photographs the inside of the house with Ray and Charles Eames, and all their belongins, at the Chautauqua meadows on Pacific Palisades in Los Angeles, launching its fine yellow lines to Alison and Peter Smithson and his heroic late modern, up to the first Foster and his poetic hightech and even the O-riginal Gehry, deconstructing the essential space of his home from the space itself, opening the doors to the new century. And these paradigm shifts, from the hard eclectic styles to modern secular lyricism in the hinge and then overcoming the cultured frivolity, lightness, exhibitionism, and opportunism of the postmodern skeptical focus, something remains intense, invariant in the lurching relationship of contemporary man and his environment. As the sculpture, which according to Barnett Newman is what you bump into when you back up to see a painting, in these pristine, ordinary places, promenade, door, threshold, enclosure and emptiness, you stumble upon the architecture even before realizing that it is architecture.