Последовательности, функции и их кодирование на Верченко
Ошибка.
Попробуйте повторить позже
Каждому из четырех абонентов 
надо выдать по два уравнения вида 
где 
Значения секретных битов 
одинаковы для всех абонентов и им заранее неизвестны. Приведите хотя бы один пример уравнений,
которые надо выдать этим четырем абонентам, чтобы каждая пара 
могла достоверно вычислить 
но
чтобы при этом: 
ни одна другая пара абонентов не могла бы достоверно вычислить более одного секретного бита; 
ни один абонент в
одиночку не был в состоянии достоверно вычислить даже один секретный бит. Например, если абонент 
получит уравнения
а 
— 
Тогда, объединившись, из имеющихся
в их распоряжении четырех уравнений они однозначно найдут, что 
При этом будем говорить, что
пара абонентов 
может достоверно вычислить секретные биты 
Здесь традиционно полагается, что
Источники:
Подсказка 1
Для начала подумайте, как спрятать один конкретных бит z от всех абонентов, кроме конкретной пары.
Подсказка 2
Можно выбрать один конкретный бит и выдать его первому абоненту (уравнением a = p). А второму выдать уравнение a + z = q. Тогда они смогут угадать секретный бит z. Но как спрятать его от остальных? Каким выбрать a?
Подсказка 3
Попробуйте сделать так, чтобы a зависел от других секретных битов.
"Спрятать"один бит, например, 
от всех абонентов, но сделать его доступным для пары 
можно следующим общим способом:
выбрать некоторый бит 
пусть 
выдать это уравнение 
а уравнение 
— уравнение 
— произвольные,
но зафиксированные значения). Ни 
ни 
не могут достоверно получить значение бита 
из имеющихся у них уравнений, но вместе
они смогут его вычислить: 
Применительно к задаче, в качестве бита 
можно использовать сумму других двух секретных бит. Выдадим абоненту 
уравнение
а 
— уравнение 
тогда, сложив эти уравнения вместе, пара абонентов 
найдет 
Выдадим абоненту 
также уравнение 
тогда они найдут бит 
Очевидно, что при таком способе, если пара
абонентов находит 
бита, то она найдет и третий, так как он будет присутствовать хотя бы у одного абонента в линейной комбинации:
Этот способ можно распространить и на пары абонентов 
проверяя при этом, что пары абонентов
не смогут найти ни одного бита.
Например,
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
