The work presented in this thesis discusses various formalisms for representing the addition of order-controlling and order-relaxing mechanisms to existing formal language models. An immediate example is shuffle expressions, which can represent not only all regular languages (a regular expression is a shuffle expression), but also features additional operations that generate arbitrary interleavings of its argument strings. This defines a language class which, on the one hand, does not contain all context-free languages, but, on the other hand contains an infinite number of languages that are not context-free. Shuffle expressions are, however, not themselves the main interest of this thesis. Instead we consider several formalisms that share many of their properties, where some are direct generalisations of shuffle expressions, while others feature very different methods of controlling order. Notably all formalisms that are studied here have a semi-linear Parikh image, are structured so that each derivation step generates at most a constant number of symbols (as opposed to the parallel derivations in for example Lindenmayer systems), feature interesting ordering characteristics, created either by derivation steps that may generate symbols in multiple places at once, or by multiple generating processes that produce output independently in an interleaved fashion, and are all limited enough to make the question of efficient parsing an interesting and reasonable goal. This vague description already hints towards the formalisms considered; the different classes of mildly context-sensitive devices and concurrent finite-state automata. This thesis will first explain and discuss these formalisms, and will then primarily focus on the associated membership problem (or parsing problem). Several parsing results are discussed here, and the papers in the appendix give a more complete picture of these problems and some related ones.

Public key encryption plays a vital role in securing sensitive data in practical applications. The security of many encryption schemes relies on mathematical problems related to the difficulty of factoring large integers. In particular, subgroup problems in composite order groups are a general class of problems widely used in the construction of secure public-key encryption schemes. This thesis studies public-key encryption schemes that are provably secure based on the difficulty of subgroup or other integer factorisation related problems in the standard model. Firstly, a number of new public-key encryption schemes are presented which are secure in the sense of indistinguishability against chosen-ciphertext attack in the standard model. These schemes are obtained by instantiating the two previous paradigms for chosen-ciphertext security by Cramer and Shoup, and Kurosawa and Desmedt, with three previously studied subgroup membership problems. The resulting schemes are very efficient, and are comparable if not superior in terms of efficiency when compared to previously presented instantiations. Secondly, a new approach is presented for constructing RSA-related public key encryption schemes secure in the sense of indistinguishability against chosenciphertext attack without random oracles. This new approach requires a new set of assumptions, called the Oracle RSA-type assumptions. The motivating observation is that RSA-based encryption schemes can be viewed as tag-based encryption schemes, and as a result can be used as a building block in a previous technique for obtaining chosen-ciphertext security. Two example encryption schemes are additionally presented, each of which is of comparable efficiency to other public key schemes of similar security. Finally, the notion of self-escrowed public-key infrastructures is revisited, and a security model is defined for self-escrowed encryption schemes. The security definitions proposed consider adversarial models which reflect an attacker's ability to recover private keys corresponding to public keys of the attacker's choice. General constructions for secure self-escrowed versions of ElGamal, RSA, Cramer-Shoup and Kurosawa-Desmedt encryption schemes are also presented, and efficient instantiations are provided. In particular, one instantiation solves the 'key doubling problem' observed in all previous self-escrowed encryption schemes. Also, for another instantiation a mechanism is described for distributing key recovery amongst a number of authorities.