Верхняя оценка $O(1)$ для односторонней вероятностной сложности предиката GT для протоколов с общими случайными битами. Оценка $O(\log^2 n)$ вероятностной двусторонней сложности предиката GT. Оценка $O(\log n)$ для односторонней сложности предиката GT для протоколов с общими случайными битами.

Амплификация.

Теорема Ньюмана об уменьшении количества случайных битов и замене общих битов на приватные.