Signatures on Equivalence Classes: A New Tool for Privacy-Enhancing Cryptography

During the past decades the world has seen a rapid and historically unprecedented evolvement of technology. Computer and Internet technology, in particular, have penetrated practically all spheres of life. Meanwhile privacy has become a rare good, since privacy and data security concerns have often been put aside. The reasons are to seek in cost efficiency or the business model, in plain indifference or lack of awareness of users and sometimes in the complexity and practical inefficiency of cryptographic solutions. We deliberately outsource large amounts of personal data to places we do not know and cannot control through communication channels of sometimes questionable security. At the same time, our actions leave digital footprints, whose extents we can barely conceive. A fortiori, it is a necessity to counter these developments through strong privacy-enhancing cryptography, which allows us to secure our personal data and reduce our communication traces that are analyzable by third parties while still upholding functionality. This thesis introduces structure-preserving signatures on equivalence classes (SPS-EQs) and presents several applications to privacy-enhancing cryptography. Loosely speaking, an SPS-EQ allows us to sign projective equivalence classes (defined in the bilinear-group setting) and to adapt signatures to arbitrary representatives of the respective class later on. At the same time, it should be infeasible to link message-signature pairs belonging to the same class. Surprisingly, SPS-EQs enable new construction paradigms for very efficient and intelligible schemes. We will describe two SPS-EQ constructions and a security model, which we will also discuss in more detail. Using SPS-EQs, we will then show a new and efficient way to build blind and partially blind signatures—two basic building blocks for privacy-enhancing protocols—, introduce new design paradigms for one-show attribute-based credentials (ABCs) and multi-show ABCs—methods that allow us to authenticate ourselves without disclosing our identity. More precisely, we will give the first practically efficient round-optimal blind signature scheme having security proofs in the standard model. We will then show the first one-show ABC based on a standard-model blind signature scheme. Further, we will present an efficient multi-show ABC along with a game-based security model and a new perfectly-hiding set commitment scheme as its second building block—both latter contributions are of independent interest. Our multi-show ABC is the first to simultaneously have constant-size credentials and constant communication effort—two distinguishing features for efficiency and thus practicality. Furthermore, it is the first ABC whose anonymity holds against malicious organization keys in the standard model. Last but not least, we will also take a look at verifiably-encrypted signatures (VESs). These are signature schemes for fair exchange in digital business processes. We will point out flaws in their security model, show how to fix them and give a black-box VES construction from SPS-EQ, which allows us to relate SPS-EQs to public-key encryption and separate certain classes of SPS-EQ from one-way functions (OWFs). This relation is somewhat surprising, since digital signature schemes can usually be built from OWFs.