Paulo S. L. M. Barreto (#242)
Paulo S. L. M. Barreto
Topic of his/her doctorate.
Criptografia robusta e marcas d'água frágeis: construção e análise de algoritmos para localizar alterações em imagens digitais
pairing-based cryptosystems, watermarking
Year of completion
Digital watermarks are the method of choice for ensuring the integrity, authenticity, and non-repudiation of images and other digital signals derived from originally analog information. In particular, topological watermarks are capable of not only detecting, but also localizing alterations in marked images with a previously established resolution. The nature of the goals of such watermarks suggests a close association with asymmetric cryptographic algorithms; more precisely, with suitably organized digital signatures. This very observation indicates that it will be usually necessary to resort to cryptanalysis techniques to assess to what extent a watermark scheme achieves its design goals -- but unfortunately, this approach does not seem to be adopted in the majority of proposed schemes. Additionally, the intrusive character of any watermark requires minimizing the amount of data embedded in the host image (to avoid deteriorating the quality of the resulting image) and maximizing the processing speed (due to the naturally high number, typically several thousands, of signatures one must generate and verify in realistic images). In cryptographic terms, the signatures inserted in a host image must be as compact as possible, and its processing must be as efficient as feasible. There currently exist very few secure algorithms to obtain compact signatures; the most promising method, the so called BLS scheme, is based upon the concept of bilinear pairing on certain elliptic groups. However, until recently this technology was considered too inefficient to be used in practice.
The focus of our research is the cryptanalysis and the secure design of topological watermarking schemes, as well as the elaboration of efficient asymmetric algorithms as a cryptographic framework for such schemes. We point out several security breaches in proposed topological schemes; we especially define the concepts of transplantation attack and advanced birthday attack, to which nearly all watermarks in that category succumb. As a counterpart, we suggest a new watermarking scheme (called hash block chaining, or HBC) that resists not only these, but actually all attacks of which we are aware. On the cryptographic side, we present a deterministic, efficient variant (orders of magnitude faster than previously known variants) of Miller's algorithm to compute the Tate pairing, as well as a general algorithm to construct pairing-friendly elliptic curves and group generators. This part of our research has a character of its own, and its interest is quite independent from the context in which we apply it, since for the first time it makes practical a whole family of recent and extremely useful cryptographic algorithms -- the pairing based cryptosystems, which can elegantly solve several problems that remained open for decades. Finally, we show how our original results by themselves suggest other research problems, both in the area of image security and in the realm of cryptography per se.
pbarreto (at) larc.usp.br