Архив задач олимпиады по математике и криптографии
Ключи в виде уравнений для четверых, 11 кл.
Каждому из четырех абонентов A1,A2,A3,A4 надо выдать по два уравнения вида aw+bx+cy++dz=t, где a,b,c,d,t,w,x,y,z∈{0,1}. Значения секретных битов w,x,y,z одинаковы для всех абонентов и им заранее неизвестны. Приведите хотя бы один пример уравнений, которые надо выдать этим четырем абонентам, чтобы каждая пара {A1,A3},{A1,A4},{A2,A3} могла достоверно вычислить w,x,y,z, но чтобы при этом: 1) ни одна другая пара абонентов не могла бы достоверно вычислить более одного секретного бита; 2) ни один абонент в одиночку не был в состоянии достоверно вычислить даже один секретный бит. Например, если абонент A1 получит уравнения {w+x+y+z=1; w+x+0∙y+0∙z=1}, а A2 – {w+0∙x+y+0∙z=0; w+x+0∙y++z=0}. Тогда, объединившись, из имеющихся в их распоряжении четырех уравнений они однозначно найдут, что w=1,x=0,y=1,z=1. При этом будем говорить, что пара абонентов {A1,A2} может достоверно вычислить секретные биты w,x,y,z. Здесь традиционно полагается, что 1+1=0.
Пусть w0,x0,y0,z0 – значения секретных битов w,x,y,z. Решим прежде задачу, предполагая, что все секретные биты равны нулю: w0=x0=y0=z0=0. Затем в уравнениях можно будет сделать замену w→w+w0,…,z→z+z0 и тем самым получить решение задачи в общем случае. Запишем теперь какую-нибудь систему из четырех уравнений, которой удовлетворяют только нулевые значения. Например,
w+x=0 (1)
x+y=0 (2)
y+z=0 (3)
w+x+y=0 (4)
Запишем еще одно уравнение, сложив эти четыре:
x+y+z=0 (5)
Система из любых четырех уравнений из набора (1) – (5) имеет только нулевое решение. Далее идея в следующем. Если пара абонентов должна уметь находить все биты, то этой паре выдадим четыре различные уравнения из набора (1) – (5), если же нет, то хоть одно уравнение у этой пары должно быть общим.
Замечание. Здесь нет четких алгоритмов и успех заранее не гарантирован. Возможно, следовало выбрать какие-то другие уравнения (1) – (4). Заметим, например, что абонентам, которые не должны уметь находить секрет, нельзя выдать уравнения (1), (2) и (4), так как значение бита z они не найдут, но определят, что w=x=y=0, а это по условию недопустимо. Никакому абоненту нельзя выдать уравнения (2) и (5), так как из них следует, что z=0. Абонентам раздать уравнения можно так: