In this thesis, we explore cryptographic protocols in three seemingly counter-intuitive settings or properties and attempt to achieve secure protocols under these settings.

First, we consider the problem of future proofing of classical signatures against quantum computers, particularly in blockchain systems. We attempt to solve this problem by simply hiding the public keys until necessary. While post-quantum cryptography standardization efforts are ongoing, we propose an immediate, practical solution for securing public ledger transactions during the transition process. We formalize the notion of digital signatures with hidden public keys. This seems counter-intuitive at first because the actual signature protocol being used is still classical but the public key is hidden. We present a generic transformation that converts these classical signatures into post-quantum ones suitable for single use.

Second, we approach the problem of letting someone else you don't trust manage your cryptographic actions through a formal framework for digital consent. Drawing parallels from real-world action of giving a consent, we develop a protocol that enables users to delegate cryptographic operations while maintaining security and accountability. Our framework uses simple cryptographic primitives, supports various authentication methods, and enables practical applications such as PDF signing and e-banking, while reducing the burden of managing high entropy key material for end users.

Finally, we investigate the seemingly contradictory requirements of anonymity and non-transferability in credential systems. We introduce and formalize non-transferable one-time anonymous tokens (NTAT), providing a construction with efficient implementation. Our solution achieves accountability, unlinkability, and non-transferability.

We observe that all the solutions to the above problems seem simple yet counter-intuitive at first but achievable by using the correct cryptographic primitives under suitable infrastructures.