Kerberos is a widely-deployed network authentication protocol that is being considered for standardization. Like other standard protocols, Kerberos is no exception to security flaws and weaknesses, as has been demonstrated in several prior works. Provable security guarantees go a long way in restoring users' faith, thus making a protocol an even stronger candidate for standards. In this thesis, our goal was thus to provide provable security support for Kerberos and other practical protocols. Our contributions are three-fold: We first look at the symmetric encryption schemes employed in the current version 5 of Kerberos. Several recent results have analyzed a significant part of Kerberos v.5 using formal-methods-based approaches, which are meaningful only if the underlying encryption schemes satisfy strong cryptographic notions of privacy and authenticity. However, to our knowledge these schemes were never analyzed and proven to satisfy such notions. This thesis aims to bridge this gap. Our provable security analyses confirm that some of the encryption scheme options in Kerberos v.5 already provide privacy and authenticity, and for the remaining we suggest slight modifications for the same. We next turn our attention to the ways in which the keys and other random strings needed in cryptographic schemes employed by practical protocols are generated. Randomness needs to be carefully generated for the provable security guarantees to hold. We propose an efficient pseudorandom generator (PRG) based on hash functions. The security of our PRG relies on exponential collision-resistance and regularity of the underlying hash function. Our PRG can be used to generate various strings, like session keys, sequence numbers, confounders, etc., which are all suggested to be generated randomly in the Kerberos v.5 specification, but no algorithms are mentioned. Each of the above strings are required to satisfy different properties, all of which are trivially satisfied by the pseudorandom strings output by a PRG. Finally, we look at the problem of revocation associated with two relatively new types of encryption schemes: identity-based encryption (IBE) and attribute-based encryption (ABE). While these encryption schemes are relatively less efficient compared to public-key encryption schemes, they have already been used (and are very likely to be used in future, as well) in many practical protocols due to their attractive features. Any setting, public-key, identity-based, or attribute-based, must provide a means to revoke users from the system. However, unlike public-key encryption, there has been little prior work on studying the revocation mechanisms in an IBE or ABE. We propose new primitives and their efficient and provably secure instantiations, focusing on the revocation problem. We would like to note that even though all the results presented in this thesis are motivated mainly by provable security in practice, only the first bullet above has a direct impact on a practical and widely deployed protocol Kerberos. Our PRG is the most efficient construction among theoretical PRGs, but it may still not be efficient enough to be directly usable in practical protocols. And our results and techniques for revocation in IBE and ABE have found much wider applications in information security, such as mobile social networks, cloud-based secure health records, data outsourcing systems, vehicular ad-hoc networks, etc.

Šiame darbe yra tiriami dešimt skirtingų pseudoatsitiktinių generatorių ir jų statistinės savybės. Pseudoatsitiktiniai skaičiai yra naudojami daugelyje sričių, todėl yra labai svarbu, kad jie pasižymėtų kokybišku atsitiktinumu. Atliekant kiekvieną testą yra tikrinama hipotezė, ar sekos nariai yra iš tikrųjų atsitiktiniai. Viso darbe yra naudojami 15 šiame darbe išanalizuotų testų. Yra rekomenduojama, kad testavimo metu kievienoje sekoje būtų bent 1,000,000 bitų. Kad gauti reikšmingus rezultatus, kiekvienam generatoriui ištirti yra naudojami 50,000,000 bitų suskirstyti į dešimt sekų. Seka išlaiko testą, tada, kai testavimo metu gauta p-reikšmė yra 0.01 arba didesnė, kitu atveju – testas neišlaikytas. Jeigu bent aštuonios iš dešimties sekų išlaikė testus, tai yra laikoma, kad generatoriaus generuojama seka šio testo atžvilgiu yra atsitiktinė. Tyrimo metu buvo pastebėta, kad penki iš dešimties generatorių pastoviai išlaiko visus testus. Šiame darbe generatoriai yra suskirstyti pagal kokybiškumą atsižvelgiant į testų rezultatus. Pasiūlytas originalus pseudoatsitiktinis generatorius visada išlaiko 14 iš 15 testų ir yra laikoma, kad jo generuojama skaičių seka yra atsitiktinė, tačiau už jį yra pranašesnių generatorių. / Ten different pseudorandom number generator‘s statistical features were analyzed in this work. Pseudorandom numbers are applied in many fields, that‘s why it‘s important for them to have high quality of randomness. Hypothesis that random numbers are indeed random are checked by 15 different tests that are analyzed in this work. It is recommended that at least 1,000,000 bits of data would be used during the test. To archive meaningful results 50,000,000 of random bits divided into ten sequences are used for each pseudorandom number generator. For generator to pass any of the tests it is required that 8 out of 10 sequence’s p-value would be higher or equal to 0.01. During investigation it was noticed, that only five out of ten generators constantly pass all of the tests. In this work we classify each of the generators and separate those of higher and lower quality and determine which one is the best or the worst. Proposed unique pseudorandom number generator is constantly passing 14 out of 15 tests and is considered to have a high quality of randomness, but, according to results it is not the best of in this work’s analyzed generators.

To the field of cryptography, quantum mechanics is a game changer. The exploitation of quantum mechanical properties through the manipulation of quantum information, the information encoded in the state of quantum systems, would allow many protocols in use today to be broken as well as lead to the expansion of cryptography to new protocols. In this thesis, quantum encryption, i.e. encryption schemes for quantum data, is defined, along with several definitions of security, broadly divisible into semantic security and ciphertext indistinguishability, which are proven equivalent, in analogy to the foundational result by Goldwasser and Micali. Private- and public-key quantum encryption schemes are also constructed from quantum-secure cryptographic primitives, and their security is proven. Most of the results are in the joint paper Computational Security of Quantum Encryption, to appear in the 9th International Conference on Information Theoretic Security (ICITS2016).