Personal and Password-Based Cryptography

This thesis addresses the question what cryptography can do for one personally, i.e., it looks at security and privacy challenges of individuals in today's world. In particular, this thesis solves a number of real-world problems, including secure handling of passwords used for authentication and how to extend digital signature schemes to allow for additional features. The presented protocols are provably secure under realistic assumptions, while providing state-of-the-art security and privacy guarantees. All proposed protocols are highly efficient, useful, yet deployable on a large scale, i.e., they are truly practical, thus bridging the gap between theory and practice. This is demonstrated by providing performance evaluations and estimates of selected protocols. In more detail, this thesis is split up into two main parts. The first part of this thesis deals with protocols which allow a user to authenticate securely with a, potentially low-entropy, password which must be considered a valuable asset not to be made public. The second part applies several of the ideas given in the first part of this thesis to digital signatures. In particular, the ideas introduced add new possibilities and privacy features to this already very versatile primitive. The first part of this thesis on protocols is split up into three sub-parts. The first sub-part addresses single sign-on (SSO) protocols. In existing work, ticket-granting server(s) can, e.g., impersonate users towards service providers or offline attack their passwords. To tackle this situation, two distributed password-based single sign-on (SSO) functionalities and their realizing protocols are presented, where the password check and token generation is distributed among multiple entities. Both functionalities are formulated in the universal-composition (UC) framework. This guarantees security in arbitrary contexts, while also absorbing unavoidable practical limitations such as typos, correlated password attempts by users and the case of guessed passwords into the definition. The first protocol offers the basic functionality one expects from such a distributed password-based SSO protocol, while the second protocol provides even more privacy guarantees. For example, the service providers no longer learn which other access rights an entity has, how long a token is valid and allows to establish different identities, i.e., pseudonyms, with each service provider. The second sub-part introduces password-authenticated signatures, realizing virtual smart-cards, as real smart-cards have a number of serious drawbacks. For example, special smart-card readers are needed for usage and are not always available, while assuming that users always carry such readers with them is unrealistic. Virtual smart-cards circumvent these limitations by letting a user enter a password on a personal device, such as a smart-phone, to generate signatures on arbitrary messages with the help of an additional server. This approach prevents an adversary from using the signing key, if a user loses a device without also entering the correct password. The server only contributes to signature generation, if the password entered was correct. Neither the server nor the device alone can mount attacks on the password or on the password attempts, while the server does not learn the messages signed. As for SSO, security is defined by providing an ideal functionality in the UC-framework, implying the same advantages. The realizing protocol is secure against adaptive adversaries, i.e., an adversary can adaptively corrupt any protocol participants. To account for the main use-case of lost devices, a new corruption model is introduced. Namely, the simulator does not receive all prior input and output upon corruption, which is necessary to model the case of lost devices such that the adversary does not receive the prior password attempts. This is accompanied by a new non-committing encryption scheme for the receiver which requires secure erasures. The implementation of the given protocol shows that it even outperforms state-of-the-art smart-cards. In the third sub-part, a fully simulatable non-committing encryption scheme is introduced. In particular, the encryption scheme introduced for the virtual smart-cards requires secure erasures. However, this is not always a reasonable assumption. To tackle this situation, this part presents an extended definition and protocol which allows simulating non-interactive ciphertexts even without secure erasures in a fully adaptive way. Hence, the simulator can give away the randomness for secret key generation and the randomness used for ciphertext generation to an adaptive adversary simultaneously. Such a non-interactive definition is in particular useful, if ciphertexts are further processed. This is demonstrated by providing the first definition of UC-secure signcryption in a setting with adaptive corruptions without secure erasures, which was not possible before. However, this part also comes with an impossibility result: it is proven that neither such an encryption scheme nor signcryption can be realized in non-idealized models. The second part of this thesis deals with digital signature schemes with additional features. Here, two main contributions are presented. The first contribution of this part is about sanitizable signature schemes. In already existing definitions of sanitizable signature schemes, a semi-trusted third party, named the sanitizer, can alter signer-chosen blocks of signed messages, but a third party can derive which parts are actually admissible. The newly introduced notion of invisible sanitizable signature schemes improves on this situation by also hiding which parts of a given message are sanitizable, adding an additional layer of privacy. To build this new primitive, the new notion of chameleon-hashes with ephemeral trapdoors is introduced. These chameleon-hashes allow one to find arbitrary collisions of a hash, if two trapdoors at the same time are known. One trapdoor is a long-term secret, while the second one is generated at hash generation. Finally, this thesis address the case of signing-right revocation. Nowadays, a certificate needs to be checked whether it is revoked at every signature verification. As verification naturally occurs more often, this negatively impacts on practicality, as thus network connectivity at verification is required. The protocols presented solve this by letting the signature itself vouch for the fact that the certificate was not revoked at signature generation time. This is achieved by letting a revocation authority contribute to signature generation. To account for privacy concerns, the authority does not learn the messages signed, while an extension also prohibits that the authority can link a signing protocol to the final signature. Summarized, this thesis presents provably secure protocols which are geared to be highly efficient and are of direct practical relevance for personal usage, meaning that the primitives can directly be deployed and used, even in today's infrastructure