On Abstract Models in Cryptography and Their Applications

Abstract

When talking about the security of a cryptographic scheme, researchers often model it as a game between a challenger and an adversary. Such a game gives a clear description of the ways we consider the adversary to interact with the scheme whose security we want to prove. A security reduction then only needs to implement these ways of interactions which we usually call ‘oracles’. However, the scheme may have some underlying building blocks, such as cryptographic groups or hash functions. For example, if the scheme uses a hash function, a security proof can be in the Random Oracle Model (ROM) where the hash function is replaced by an idealized function which returns uniformly random values from the output space of the hash function and can be accessed only through an oracle, thus giving the adversary no access to the code of the function. This gives a reduction some additional leverage over the adversary, for example it can observe what queries the adversary makes to the random oracle, or it can also program the random oracle, i.e. provide the adversary with a random oracle implementation that returns values that are useful for the reduction. Another case where the ROM is useful is when the reduction wants to rewind the adversary and replay it using a different hash function evaluation, for example in the context of Fiat-Shamir based signatures. When rewinding, we consider the adversary to be a computer program that the reduction can run multiple times and where it can determine the random coins given to the program. Other than that, the reduction gets only black-box access. In this thesis, we consider rewinding as a proof strategy in several contexts. First, we look into a novel strategy of so-called undirected rewinding. In this rewinding strategy, we rewind the adversary to every step of its execution, and then in some cases change some of its inputs at the step it has been rewound to (e.g. change responses to oracle queries it made). We apply this strategy to circumvent existing lower bounds (Kamath, Klein, Pietrzak and Walter, TCC 2021) for proving the adaptive security of the Goldreich-Goldwasser-Micali Pseudo-Random Function (GGM-PRF) as a Prefix-Constrained PRF (PC-PRF). A PC-PRF allows the holder of the secret PRF key to hand out prefix keys that allow others to evaluate the PRF on values that start with a specific prefix, while the function should still be pseudo-random on other inputs. In the adaptive setting, the adversary may query such prefix keys even depending on the keys it saw before, which makes it difficult for a reduction to predict its behaviour. We circumvent this issue by rewinding the adversary to learn some of its future choices and provide an analysis that shows that the reduction loss is polynomial in the input length rather than super-polynomial which would be the case for a straight-line reduction. We furthermore apply the undirected rewinding technique to prove the adaptive security of the Logical Key Hierarchy (LKH) protocol for server-assisted group key exchange. Also here it is tricky for straight-line reductions to figure out when to embed challenges, and we can help the reduction with a rewinding strategy. We then turn to the setting of blind and partially blind signatures. A blind signature scheme is a two-party protocol between a Signer and a User where the signer holds the secret signing key and the user has a message it wants to have signed. We require blindness, i.e. even a malicious Signer should not learn the User’s message, and one-more unforgeability, i.e. a malicious User should not be able to produce more message-signature pairs than it requested signatures from the Signer. In a partially blind scheme, signatures are issued with respect to a shared tag info and the two security properties need to hold with respect to each tag. We revisit the influential partially blind scheme by Abe and Okamoto (CRYPTO 2000) whose construction and proof have served as an inspiration for several other blind and partially blind signature schemes. We point out a subtle gap in their rewinding-based proof of one-more unforgeability. We then show how to mend the gap with a new analysis of the success probability of the forking strategy of the reduction. After this, we turn to the popular blind signature scheme by Abe (EUROCRYPT 2001) which is known to have a flaw in the rewinding based security proof (pointed out by Okuhbo and Abe, SCIS 2003). While the proof strategy for the Abe-Okamoto scheme can be applied, it incurs a rather large loss. We therefore turn to another abstract model in cryptography for proving one-more unforgeability: the Algebraic Group Model (AGM) (introduced by Fuchsbauer, Kiltz, Loss, CRYPTO 2018). In the AGM, adversaries are assumed to be algebraic. Intuitively speaking, this means the adversary computes new group elements only using the group operation. In the AGM, this intuition is modelled by requiring the adversary to always output an explanation how it computed the group elements in its output. We show how this algebraic explanation can be exploited by a reduction to show the concurrent security of Abe’s blind signature scheme and even of a new partially blind variant that we introduce. We furthermore investigate the sequential security of Blind Schnorr Signatures, and show that sequential One-More Unforgeability of Blind Schnorr Signatures can be shown assuming the hardness of the One-More Discrete Logarithm Problem in the AGM + ROM. We furthermore show that it is indeed necessary for an algebraic reduction (even against an algebraic adversary) to query the Discrete Logarithm Oracle as many times as the adversary closes a signing session. Whenever confronted with a new abstract model, one may ask how realistic it is and how it compares to other models and assumptions. We therefore provide some evidence towards the algebraic group model being realistic. Namely, we construct a group scheme that we call the algebraic wrapper from strong, but falsifiable assumptions. The algebraic wrapper allows the person who set up the group parameters to ‘extract’ an algebraic explanation in a limited manner. We show that several existing proofs from the AGM can be translated into the algebraic wrapper setting, lending some credibility to proofs in the AGM.