Analysis of common attacks in public-key cryptosystems based on low-density parity-check codes

The security and reliability of a class of public-key cryptosystems against attacks by unauthorized parties, who had acquired partial knowledge of one or more of the private key components and/or of the message, were discussed. The standard statistical mechanical methods of dealing with diluted spin systems with replica symmetric considerations were analyzed. The dynamical transition which defined decryption success in practical situation was studied. The phase diagrams which showed the dynamical threshold as a function of the partial acquired knowledge of the private key were also presented.

Finite-size effects in low-density parity-check codes applied to cryptography

DUE TO COPYRIGHT RESTRICTIONS ONLY AVAILABLE FOR CONSULTATION AT ASTON UNIVERSITY LIBRARY AND INFORMATION SERVICES WITH PRIOR ARRANGEMENT

Critical noise levels for low-density parity check decoding

We determine the critical noise level for decoding low-density parity check error-correcting codes based on the magnetization enumerator (M), rather than on the weight enumerator (W) employed in the information theory literature. The interpretation of our method is appealingly simple, and the relation between the different decoding schemes such as typical pairs decoding, MAP, and finite temperature decoding (MPM) becomes clear. In addition, our analysis provides an explanation for the difference in performance between MN and Gallager codes. Our results are more optimistic than those derived using the methods of information theory and are in excellent agreement with recent results from another statistical physics approach.

A statistical-mechanical analysis of coded CDMA with regular LDPC codes

We analyze, using the replica method of statistical mechanics, the theoretical performance of coded code-division multiple-access (CDMA) systems in which regular low-density parity-check (LDPC) codes are used for channel coding.

Augmented LDPC Graph for Distributed Video Coding with Multiple Side Information

The advances made in channel-capacity codes, such as turbo codes and low-density parity-check (LDPC) codes, have played a major role in the emerging distributed source coding paradigm. LDPC codes can be easily adapted to new source coding strategies due to their natural representation as bipartite graphs and the use of quasi-optimal decoding algorithms, such as belief propagation. This paper tackles a relevant scenario in distributedvideo coding: lossy source coding when multiple side information (SI) hypotheses are available at the decoder, each one correlated with the source according to different correlation noise channels. Thus, it is proposed to exploit multiple SI hypotheses through an efficient joint decoding technique withmultiple LDPC syndrome decoders that exchange information to obtain coding efficiency improvements. At the decoder side, the multiple SI hypotheses are created with motion compensated frame interpolation and fused together in a novel iterative LDPC based Slepian-Wolf decoding algorithm. With the creation of multiple SI hypotheses and the proposed decoding algorithm, bitrate savings up to 8.0% are obtained for similar decoded quality.

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.

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.

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.

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.

Magnetization enumerator for LDPC codes - a statistical physics approach

We propose a method based on the magnetization enumerator to determine the critical noise level for Gallager type low density parity check error correcting codes (LDPC). Our method provides an appealingly simple interpretation to the relation between different decoding schemes, and provides more optimistic critical noise levels than those reported in the information theory literature.

Advanced decoding technics for law density parity check codes decoding

DUE TO COPYRIGHT RESTRICTIONS ONLY AVAILABLE FOR CONSULTATION AT ASTON UNIVERSITY LIBRARY AND INFORMATION SERVICES WITH PRIOR ARRANGEMENT

Implementação de códigos LDPC em OFDM e SC-FDE

Os desenvolvimentos dos sistemas de comunicação sem fios apontam para transmissões de alta velocidade e alta qualidade de serviço com um uso eficiente de energia. Eficiência espectral pode ser obtida por modulações multinível, enquanto que melhorias na eficiência de potência podem ser proporcionadas pelo uso de códigos corretores de erros. Os códigos Low-Density Parity-Check (LDPC), devido ao seu desempenho próximo do limite de Shannon e baixa complexidade na implementação e descodificação são apropriados para futuros sistemas de comunicações sem fios. Por outro lado, o uso de modulações multinível acarreta limitações na amplificação. Contudo, uma amplificação eficiente pode ser assegurada por estruturas de transmissão onde as modulações multinível são decompostas em submodulações com envolvente constante que podem ser amplificadas por amplificadores não lineares a operar na zona de saturação. Neste tipo de estruturas surgem desvios de fase e ganho, produzindo distorções na constelação resultante da soma de todos os sinais amplificados. O trabalho foca-se no uso dos códigos LDPC em esquemas multiportadora e monoportadora, com especial ênfase na performance de uma equalização iterativa implementada no domínio da frequência por um Iterative Block-Decision Feedback Equalizer (IB-DFE). São analisados aspectos como o impacto do número de iterações no processo de descodificação dentro das iterações do processo de equalização. Os códigos LDPC também serão utilizados para compensar os desvios de fase em recetores iterativos para sistemas baseados em transmissores com vários ramos de amplificação. É feito um estudo sobre o modo como estes códigos podem aumentar a tolerância a erros de fase que incluí uma análise da complexidade e um algoritmo para estimação dos desequilíbrios de fase.

Statistical mechanics analysis of LDPC coding in MIMO Gaussian channels

Using analytical methods of statistical mechanics, we analyse the typical behaviour of a multiple-input multiple-output (MIMO) Gaussian channel with binary inputs under low-density parity-check (LDPC) network coding and joint decoding. The saddle point equations for the replica symmetric solution are found in particular realizations of this channel, including a small and large number of transmitters and receivers. In particular, we examine the cases of a single transmitter, a single receiver and symmetric and asymmetric interference. Both dynamical and thermodynamical transitions from the ferromagnetic solution of perfect decoding to a non-ferromagnetic solution are identified for the cases considered, marking the practical and theoretical limits of the system under the current coding scheme. Numerical results are provided, showing the typical level of improvement/deterioration achieved with respect to the single transmitter/receiver result, for the various cases. © 2007 IOP Publishing Ltd.

Reconciliación de errores mínimamente interactiva en distribución cuántica de claves

Algunos trabajos recientes han desarrollado varias alternativas a Cascade, entre las cuales destacan aquellas basadas en el uso de técnicas de codificación modernas. Por ejemplo, a través del uso de códigos Low-Density Parity-Check (LDPC) hoy día encontramos varias propuestas que permiten mejorar la eficiencia de la reconciliación de clave para ratios de error elevados. Al utilizar códigos LDPC tan sólo se requiere un único uso del canal de comunicación. Estas propuestas se basan en una técnica conocida como “codificación de síndrome” que permite aplicar métodos de corrección de errores para reconciliar cadenas aleatorias correlacionadas. En una de estas propuestas aplicamos dos técnicas conocidas en codificación, cómo son la perforación y el acortado de símbolos, para adaptar en tiempo real el ratio de información proporcionado por el síndrome intercambiado.

A mean field theory of coded CDMA systems

We present a mean field theory of code-division multiple access (CDMA) systems with error-control coding. On the basis of the relation between the free energy and mutual information, we obtain an analytical expression of the maximum spectral efficiency of the coded CDMA system, from which a mean field description of the coded CDMA system is provided in terms of a bank of scalar Gaussian channels whose variances in general vary at different code symbol positions. Regular low-density parity-check (LDPC)-coded CDMA systems are also discussed as an example of the coded CDMA systems.