Abstract We study the fully automated amortised analysis of purely functional data structures like skew heaps , as well as weight - and rank-biased leftist heaps. For that we generalise earlier works on automated amortised resource analysis by developing a type inference based approach with a generic type system. This allows for modular reasoning and the inference of precise and optimal cost bounds. More specifically, we extend the work on the ATLAS system by Leutgeb et al. which was developed to cover the analysis of splay trees and some closely related data structures. To enable the analysis of skew heaps, however, and the even more challenging (amortised) analysis of leftist heaps, we have developed a range of new techniques for type-based automated analysis. By introducing a generic type system we allow for arbitrary (classes of) potential functions, compared to the use of hard-coded potential functions in ATLAS, which we have implemented in Haskell in an entirely modular way. We have also greatly enhanced the existing type inference algorithm by extensions in multiple directions, including path-sensitive reasoning, data structure invariants, and template parameters for piecewise defined potential functions. We show how our newly developed system supports the use of all known potential functions for analysing skew heaps and leftist heaps, confirming the known bounds.

We address the problem of designing optimal schemes for the generation of secure cryptographic keys from continuous noisy data. We argue that, contrary to the discrete case, a universal fuzzy extractor does not exist. This implies that in the continuous case, key extraction schemes have to be designed for particular probability distributions. We extend the known definitions of the correctness and security properties of fuzzy extractors. Our definitions apply to continuous as well as discrete variables. We propose a generic construction for fuzzy extractors from noisy continuous sources, using independent partitions. The extra freedom in the choice of discretization, which does not exist in the discrete case, is advantageously used to give the extracted key a uniform distribution. We analyze the privacy properties of the scheme and the error probabilities in a one-dimensional toy model with simplified noise. Finally, we study the security implications of incomplete knowledge of the source's probability distribution${\BBP }$. We derive a bound on the min-entropy of the extracted key under the worst-case assumption, where the attacker knows${\BBP }$exactly.

We investigate the recently introduced notion of smooth Renyi entropy for the case of ergodic information sources, thereby generalizing previous work which concentrated mainly on i.i.d. information sources. We will actually consider ergodic quantum information sources, of which ergodic classical information sources are a special case. We prove that the average smooth Renyi entropy rate will approach the entropy rate of a stationary, ergodic source, which is equal to the Shannon entropy rate for a classical source and the von Neumann entropy rate for a quantum source.

Recently, a quantum key exchange protocol that uses squeezed states was presented by Gottesman and Preskill. In this paper we give a generic security proof for this protocol. The method used for this generic security proof is based on recent work by Christiandl, Renner and Ekert

Recently, an information theoretical model for quantum secret sharing (QSS) schemes was introduced. By using this model, we prove that pure state quantum threshold schemes (QTS) can be constructed from quantum MDS codes and vice versa. In particular, we consider stabilizer codes and give a constructive proof of their relation with QTS. Furthermore, we reformulate the monotone span program (MSP) construction according to the information theoretical model and check the recoverability and secrecy requirement. Finally, we consider QSS schemes which are based on quantum teleportation