A Second Note on the Feasibility of Generalized Universal Composability

Author: Alonso González, and A.H..


Yao et al. [1,2] claimed a potential limitation on the class of protocols that could be securely implemented in the generalized universal composability (GUC) framework proposed by Canetti et al. [3]. Specifically, Yao et al. presented a concrete attack on a GUC Zero Knowledge (GUCZK) protocol, a natural adaptation Blum's ZK proof for Directed Hamiltonicity using the general GUC feasibility of Canetti et al. [3]. Interestingly, the attack was not analysed in the GUC model in Yao et al. [2] but in the FUC model, a new UC-like framework proposed in the same work. Nonetheless, Yao et al. [2] argued that, in light of this attack, GUC would lose its concurrent general composability and proof of knowledge properties. Concretely, they argue that GUC composability would now be with respect to some adversaries with limited access to external arbitrary protocols.In this work, we show that the claimed attack from Yao et al. is indeed harmless and does not contradict the security of the mentioned GUCZK protocol, thus restoring the general feasibility for GUC.

[1] A.C.C.Yao , F.F.Yao and Y.Zhao (2007). A note on the feasibility of generalized universal composability. In: J.-Y. S.Cai , B.Cooper and H.Zhu (eds.) Theory and Applications of Models of Computation, Lecture Notes in Computer Science, volume 4484, Springer, Berlin, Heidelberg, 474-485.
[2] A.C.-C.Yao , F.F.Yao and Y.Zhao (2009b). A note on universal composable zero-knowledge in the common reference string model. Theoretical Computer Science 410 (11) 1099-1108.
[3] R.Canetti , Y.Dodis , R.Pass and S.Walfish (2007). Universally composable security with global setup. In: S. P.Vadhan (ed.) TCC. Springer Lecture Notes in Computer Science, 4392, 61-85.

Ref: In Mathematical Structures in Computer Science, 8 June 2016 (First View), pp. 1--14, Cambridge University Press. Link.
Preliminary full version available as PDF.