Архив задач олимпиады по математике и криптографии
Ключи в виде уравнений для четверых, 8-9 кл.
6. 8-9 Каждому из четырех абонентов A1,A2,A3,A4 надо выдать по два уравнения вида ax+by+cz=d, где a,b,c,d,x,y,z∈{0,1}. Значения секретных битов w,x,y,z одинаковы для всех абонентов и им заранее неизвестны. Пусть, например, A1 получит уравнения {x+y+z=1,x+y+0∙z=1}, а A2 – {0∙x+y+0∙z=1,0∙x+0∙y+0∙z=0}. Здесь традиционно полагается, что 1+1=0. Тогда, объединившись, из имеющихся в их распоряжении четырех уравнений они однозначно найдут, что x=0,y=1,z=0. При этом будем говорить, что пара абонентов {A1,A2} может достоверно вычислить секретные биты x,y,z. Приведите хотя бы один пример уравнений, которые надо выдать этим четырем абонентам, чтобы каждая пара {A1,A2},{A1,A3},{A1,A4} могла достоверно вычислить x,y,z, но чтобы при этом ни одна другая пара абонентов это сделать не смогла и ни один абонент в одиночку не смог бы найти даже один секретный бит.
“Спрятать” один бит, пусть z, от всех абонентов, но сделать его доступным для пары {Ai,Aj} можно следующим общим способом: выбрать некоторый бит a, пусть a=p, выдать это уравнение Ai, а абоненту Aj – уравнение a+z=q (p,q∈{0,1} – произвольные, но зафиксированные значения). Ни Ai, ни Aj не могут достоверно получить значение бита z из имеющихся у них уравнений, но вместе они смогут его вычислить: a+a+z=z=p+q. Применительно к задаче, в качестве бита a можно использовать сумму других двух секретных бит. Выдадим абоненту A2 уравнение x+y=p1, а A1 – уравнение x+y+z=q1, тогда сложив эти уравнения вместе, пара абонентов {A1,A2} найдет z=p1+q1. Выдадим абоненту A2 также уравнение x+z=p2, тогда они найдут бит y=p2+q1. Очевидно, что при таком способе, если пара абонентов находит 2 бита, то она найдет и третий, так как он будет присутствовать хотя бы у одного абонента в линейной комбинации: x=p1+p2+q1. Этот способ можно распространить и на пары абонентов {A1,A3}, {A1,A4}, проверяя при этом, что пары абонентов {A2,A3},{A2,A4},{A3,A4} не смогут найти ни одного бита.