==
Да, ещё одно — как можно реализовать конверты: хэшем. Если есть (объявлена публично) односторонняя функция F (которую трудно обратить, но которая тем не менее взаимно-однозначна), то пусть X на каждом шаге для каждой вершины j вычисляет
f_j=F(c_j R_j),
где с_j — пара бит, кодирущих цвет в этой вершине, а R_j — ещё куча-куча "мусорных бит", и объявляет результат вычисления f_j публично. (Мусор нужен, чтобы Y не мог просто перебрать три варианта цвета и вычислить от них F; если я правильно понимаю, такой мусор в криптографии называется "солью").

И протокол дополняется тем, как происходит "вскрытие конвертов": Y говорит, какие именно конверты вскрывает, X для них объявляет c_j и R_j, после чего Y проверяет, что F от заявленных c_j R_j это действительно ранее объявленные f_j.

А стратегия X — тем, что мусорные биты нужно выбирать совершенно случайными, чтобы объявление f_j и впрямь не приводило ни к какой (значимой) утечке информации.
==