Cryptographical properties of Ising spin systems

Rate distortion theorem and the multicritical point of a spin glass

A spin system can be thought of as an information coding system that transfers information of the interaction configuration into information of the equilibrium state of the spin variables. Hence it can be expected that the relations between the interaction configuration and equilibrium states are consistent with the known laws of information theory. We show that Shannon's rate distortion theorem can be used to obtain a universal constraint on neighboring spin correlations for a broad range of Ising spin systems with two-body spin interactions. Remarkably, this constraint gives a bound for the multicritical point in the phase diagram, when a mean-field behavior for the neighboring spin pairs can be expected in the paramagnetic phase.

Cavity approach for real variables on diluted graphs and application to synchronization in small-world lattices

We study XY spin systems on small-world lattices for a variety of graph structures, e.g., Poisson and scale-free, superimposed upon a one-dimensional chain. In order to solve this model we extend the cavity method in the one pure-state approximation to deal with real-valued dynamical variables. We find that small-world architectures significantly enlarge the region in parameter space where synchronization occurs. We contrast the results of population dynamics performed on a truncated set of cavity fields with Monte Carlo simulations and find fair agreement. Further, we investigate the appearance of replica symmetry breaking in the spin-glass phase by numerically analyzing the proliferation of pure states in the message passing equations.

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

We analyze the security and reliability of a recently proposed class of public-key cryptosystems against attacks by unauthorized parties who have acquired partial knowledge of one or more of the private key components and/or of the plaintext. Phase diagrams are presented, showing critical partial knowledge levels required for unauthorized decryption.

Phase transitions in quantum pattern recognition

With the help of quantum mechanics one can formulate a model of associative memory with optimal storage capacity. This model is generalized by introducing a parameter playing the role of an effective temperature. The corresponding thermodynamics provides criteria to tune the efficiency of quantum pattern recognition. It is shown that the associative memory undergoes a phase transition from a disordered, high-temperature phase with no correlation between input and output to an ordered, low-temperature phase with minimal input-output Hamming distance.

Random graph coloring: statistical physics approach

The problem of vertex coloring in random graphs is studied using methods of statistical physics and probability. Our analytical results are compared to those obtained by exact enumeration and Monte Carlo simulations. We critically discuss the merits and shortcomings of the various methods, and interpret the results obtained. We present an exact analytical expression for the two-coloring problem as well as general replica symmetric approximated solutions for the thermodynamics of the graph coloring problem with p colors and K-body edges.

Exact solutions for diluted spin glasses and optimization problems

We study the low temperature properties of p-spin glass models with finite connectivity and of some optimization problems. Using a one-step functional replica symmetry breaking ansatz we can solve exactly the saddle-point equations for graphs with uniform connectivity. The resulting ground state energy is in perfect agreement with numerical simulations. For fluctuating connectivity graphs, the same ansatz can be used in a variational way: For p-spin models (known as p-XOR-SAT in computer science) it provides the exact configurational entropy together with the dynamical and static critical connectivities (for p = 3, gamma(d) = 0.818, and gamma(s) = 0.918), whereas for hard optimization problems like 3-SAT or Bicoloring it provides new upper bounds for their critical thresholds ( gamma(var)(c) = 4.396 and gamma(var)(c) = 2.149).