UC-AGM

The algebraic-group model (AGM), which lies between the generic group model and the standard model of computation, provides a means by which to analyze the security of cryptosystems against so-called algebraic adversaries.

We formalize the AGM within the framework of universal composability, providing formal definitions for this setting and proving an appropriate composition theorem. This extends the applicability of the AGM to more-complex protocols, and lays the foundations for analyzing algebraic adversaries in a composable fashion.

Our results also clarify the meaning of composing proofs in the AGM with other proofs and they highlight a natural form of independence between idealized groups that seems inherent to the AGM and has not been made formal before—these insights also apply to the composition of game-based proofs in the AGM.

• https://eprint.iacr.org/2021/1218.pdf

1Introduction

Security proofs are often carried out in idealized models that seek to capture certain classes of adversarial behavior. Examples include the random-oracle model, in which the attacker is assumed to treat a hash function as an ideal random function; the ideal-cipher model, in which the attacker is assumed to treat a block cipher as an ideal keyed permutation; and the generic-group model (GGM) , where the attacker is assumed to treat group elements as abstract identifiers and group operations as black-box operations on those identifiers.

• V. I. Nechaev. Complexity of a determinate algorithm for the discrete logarithm.
• V. Shoup. Lower bounds for discrete logarithms and related problems

Cryptographers continually seek to refine these models, making them more expressive so they capture larger classes of algorithms and thus come closer to modeling adversaries performing arbitrary computation. With this motivation in mind, Fuchsbauer et al.  (based on ideas of Abdalla et al. ) proposed the algebraic-group model (AGM) as a more expressive version of the GGM. Roughly, the AGM considers algebraic adversaries that compute group elements via a sequence of "generic" group operations, but which - in contrast to the GGM - are allowed to utilize the actual bitstrings representing group elements in the course of their computation. This model is strictly stronger than the GGM; for example, index-calculus algorithms that apply to certain classes of groups are algebraic and hence allowed in the AGM, even though they are ruled out in the GGM by known lower bounds on the hardness of the discrete-logarithm problem in that model.

• G. Fuchsbauer, E. Kiltz, and J. Loss. The algebraic group model and its applications
• M. Abdalla, F. Benhamouda, and P. MacKenzie. Security of the J-PAKE password-authenticated key exchange protocol

The AGM has been used to show equivalence of various number-theoretic assumptions  and to prove security of SNARKs  and blind signatures.

• B. Auerbach, F. Giacon, and E. Kiltz. Everybody’s a target: Scalability in public-key encryption
• B. Bauer, G. Fuchsbauer, and J. Loss. A classification of computational assumptions in the algebraic group model
• A. Chiesa, Y. Hu, M. Maller, P. Mishra, N. Vesely, and N. P. Ward. Marlin: Preprocessing zkSNARKs with universal and updatable SRS
• M. Maller, S. Bowe, M. Kohlweiss, and S. Meiklejohn. Sonic: Zero-knowledge SNARKs from linear-size universal and updatable structured reference strings.
• G. Fuchsbauer, A. Plouviez, and Y. Seurin. Blind schnorr signatures and signed ElGamal encryption in the algebraic group model

An extension called the strong AGM has recently been used to prove hardness of the repeated squaring assumption underlying timed commitments and related primitives.

• J. Katz, J. Loss, and J. Xu. On the security of time-lock puzzles and timed commitments

Notably, none of the aforementioned results provide any guarantees of security under composition with other protocols (whether proven secure in the AGM or not). Here, we lay the foundations for a composable treatment of algebraic adversaries by formalizing the AGM within the framework of universal composability (UC) and proving a corresponding composition theorem. This involves not only formalizing a number of subtle issues related to the AGM itself (which may be of independent interest for subsequent work in the AGM), but also making a number of careful design decisions in defining what algebraic adversaries mean in the UC framework, in part to ensure that a suitable composition theorem holds.

• R. Canetti. Universally composable security: A new paradigm for cryptographic protocols

2Defining the AGM Within the UC Framework

Fix a group An algebraic representation of with respect to a list of elements is a tuple with . Roughly speaking, the AGM considers adversaries that are algebraic (with respect to ), meaning that if an adversary outputs a group element , then must also output an algebraic representation of with respect to the set of group elements (which we call a base) that has been given as input thus far.

We generalize the AGM to the standard UC framework by restricting our attention to algebraic attackers. While this is a natural idea, it involves dealing with a number of subtle technical issues.

First of all, to make this notion meaningful it is not sufficient to restrict the adversary to be algebraic; rather, we require the environment to be algebraic as well.

Moreover, in order for composition to possibly hold, we must also require the simulator used in proving security to be algebraic.

That is, in the UC-AGM a protocol securely realizes a functionality if, for any efficient algebraic adversary , there is an efficient algebraic simulator such that no efficient algebraic environment can distinguish the execution of with from the execution of with . Under this definition, we can indeed prove that a UC-style composition theorem holds in the UC-AGM.

Our definition of an algebraic algorithm makes a distinction between adversarial entities (real and ideal world adversaries and environments) and non-adversarial entities (uncorrupted protocol participants and ideal functionalities).

In the real world, we require the adversary to behave algebraically when it delivers group elements to uncorrupted participants and to ideal functionalities (when the proof is carried out in a hybrid real-world); moreover, we also require the environment to behave algebraically when it delivers group elements to the adversary, but not the converse.

Algebraic behavior is defined within the context of a UC AGM proof by specifying what set of group elements occurring during the protocol execution in the real-world must be used by the environment and by the adversary as a base for the provided group element representations. When this is the empty set, we recover the standard UC framework. The natural definition for this set is to include in it all the group elements that are produced by non-adversarial entities.

We show this pictorially in Figure 1, where the blue arrows denote that all group elements that are delivered must be accompanied by an algebraic decomposition with respect to base , which are the group elements produced by the machines within the boundary of . Note that, in the figure, is specified in a hybrid world that includes a functionality , which is within that boundary. The ideal world restrictions are equivalent, replacing with and with the ideal-world protocol that is realized by .

Formally, the quantification of the UC-emulation notion is subtle. As in UC, we require for all adversaries , the existence of a simulator , such that for all enviroments the real and ideal worlds are indistinguishable. However, the simulator is only required to work if the pair satisfies the algebraic restrictions specified in the real world. Intuitively, the extra power of the simulator comes from the fact that is bound to behave algebraically when interacting with and, furthermore, that will also behave algebraically if the simulator runs it internally. A caveat is that the simulator must also ensure that satisfy the algebraic restrictions in the ideal world. However, in the most common case when the simulator is interacting with an ideal functionality, if this interaction does not involve group elements, then the algebraic requirement is not a restriction on the simulation strategy (this is the case in all our proofs for concrete protocols).

The UC AGM composition theorem then states, as expected, that if . We show this scenario in Figure 2. Again the quantification is subtle. The composition theorem guarantees only hold if we restrict our quantification to match the emulation guarantee provided by i.e., we have that with respect to pairs that adhere to the base when interacting with machines in . Note that this means, in particular, that the attacker cannot use group elements produced in when attacking , unless it is able to provide a representation according to .

The companion UC AGM transitivity theory further highlights a natural notion of independence between UC AGM proofs. Suppose that is known to UC AGM emulate some functionality . Transitivity intuitively implies that if . We show that this is the case also in the UC AGM setting, if we restrict the quantification over to those attackers that independently meet the AGM restrictions imposed by the proofs of both and . This means providing algebraic representations to parties executing with respect to a base defined in the proof of and, similarly, respecting the algebraic base when interacting with parties executing . This restriction means that AGM UC composition works as expected for protocols that operate on groups that can be assumed to be independent.

We also show that the standard approach of writing UC proofs w.r.t. a dummy adversary still applies in the UC AGM setting.

3Discussion

Our theorems show that one should be very careful when composing proofs in the AGM, and not only in the UC setting.

For example, when composing game-based reductions carried out in the AGM, the same issues arise. Intuitively, composition can only be guaranteed when the AGM assumptions do not interact badly with each-other, i.e., interacting with one protocol does not allow an attacker to override the extractability assumption that is being captured by the AGM in the proof of another protocol. In practice this seems to imply excluding attackers that take group elements from one protocol and use them to attack another protocol (unless of course the algebraic construction of those elements can be explained with respect to the set of bases defined by the target protocol alone).

Interestingly, in recent independent work Kerber, Kiayias and Kohlweiss encouter a manifestation of the same problem in the constructive cryptography framework. In this work, the authors propose a general notion of proofs w.r.t. knowledge assumptions, which generalizes the AGM: adversaries provide the relevant extractable information when interacting with the protocol. Their goal is to study the composition of protocols that rely on different knowledge assumptions. It is beyond the scope of this paper to make a detailed comparison, since the approaches rely on different compositional frameworks and have different goals, but it is clear that the same restrictions must be imposed in the composition theorem to enable a proof; quoting from the paper: "Care must be taken that knowledge stemming from one knowledge assumption does not give an advantage in another... we conjecture that multiple instances with the AGM with independently sampled groups are sufficiently independent."

• T. Kerber, A. Kiayias, and M. Kohlweiss. Composition with knowledge assumptions

To conclude, we do not see the restrictions in the UC AGM composition theorems as a limitation of our work, but rather as a limitation inherent to proofs in idealized models-for example, it is easy to establish a parallel with the random oracle model in the UC setting, where the need for independent RO instances is well known.

On the contrary, we believe that an important contribution of our work is to clarify what this limitation means for proofs in the AGM. To overcome these limitations, and similarly to proofs in the random oracle model, one can prove multiple protocol executions secure simultaneously. At the very least, it is important to ensure that AGM UC proofs are carried out with respect to multi-session ideal functionalities, so that multiple executions of the same protocol can be guaranteed to compose securely. We adopt this approach in our proofs. Another option is to strengthen the proofs of each protocol to consider a global/shared source of bases along with a more powerful composition theorem, similarly to UC with global setup. We leave exploring this option as an interesting and important direction for future work.

• R. Canetti, A. Jain, and A. Scafuro. Practical UC security with a global random oracle
• R. Canetti, Y. Dodis, R. Pass, and S. Walfish. Universally composable security with global setup.