ВОССТАНОВЛЕНИЕ КОМПОНЕНТОВ В СХЕМЕ РАСПРЕДЕЛЕНИЯ СЕКРЕТА НА ОСНОВЕ КОДОВ, ИСПРАВЛЯЮЩИХ ОШИБКИ

COMPONENT RECOVERY IN THE SECRET SHARING SCHEME BASED ON ERROR-CORRECTING CODES

Artak Khemchyan Ararat

Candidate of Science, Associate Professor in Information Security and Software Development Department, National Polytechnic University of Armenia,

• , Yerevan

АННОТАЦИЯ

В последнее время предметом исследований являются схемы распределения секрета на основе кодов, исправляющих ошибки. Основным преимуществом этих схем является их скорость. В дополнение к возможностям распределения и восстановления, для процесса необходимы также проверка подлинности компонента, восстановление испорченного или утерянного компонента, а также обновление существующих. В данной статье рассматривается метод восстановления утерянного или испорченного компонента для схемы распределения секрета на основе кодов, исправляющих ошибки. С помощью этого метода выполняется промежуточное раскрытие секрета но данный метод быстрее, чем процесс восстановления и повторного распределения секрета. Метод восстановления испорченного или отсутствующего компонента позволяют периодически проверять компоненты и при обнаружении испорченного или недостающего компонента немедленно восстановить его и привести схему в рабочее состояние. В целом предложенный метод в совокупности с методом проверки подлинности компонента позволяют создать полноценную схему распределения секрета на основе кодов, исправляющих ошибки.

ABSTRACT

Recently, the subject of studies has been secret sharing schemes based on error-correcting codes. The main advantage of these schemes is their performance. In addition to the possibilities of sharing and recovery, the sharing process requires recovery of the damaged or lost component, as well as the ability to upgrade the existing components. This article describes the recovery method of the lost or damaged components for the secret sharing scheme based on error-correcting codes. By this method intermediate disclosure of secrets is carried out, but the described method is faster than the process of restoring and re-sharing of the secret. The method of component authentication for secret sharing schemes based on error-correcting codes. Verification and recovery methods allow to periodically check the components, detect the damaged or missing component, immediately restore it and bring the scheme to a working state.

Ключевые слова: распределение секрета; пороговая схема; коды, исправляющие ошибки; восстановление компонента; обновление компонента.

Keywords: secret sharing, threshold scheme, error-correcting codes, component recovery, component update.

1. В последнее время предметом исследований являются схемы распределения секрета на основе кодов, исправляющих ошибки [1]. О связи схем распределения секрета и кодов, исправляющих ошибки, говорили еще в 1981 году [2]. Преимуществом этих схем является их скорость.

Как и в других схемах, в схемах распределения секрета, могут возникнуть непредвиденные обстоятельства. Однако возможности восстановления и распределения секрета недостаточно. В таких системах планируются проверка компонентов [3], восстановление утраченного или поврежденного компонента, получение новых компонентов, обновление компонентов и другие возможности. Например, в известной схеме Шамира [4] все эти возможности есть. В данной статье представлен метод восстановления утерянного или испорченного компонента для схемы распределения секрета на основе кодов, исправляющих ошибки.

Восстановление испорченного или утерянного компонента. При распределенной системе хранения информации, возможны потеря или повреждение компонента. В этой ситуации необходимо метод восстановления этого компонента. После распределения секрет уничтожают, и вполне естественно, что для восстановления поврежденного или отсутствующего компонента требуется наличие некоторых других компонентов. Есть два варианта восстановления недостающих компонентов:

• без раскрытия секрета,
• путем раскрытия секрета.

Второй вариант, в свою очередь, имеет два подварианта. В первом случае в полностью восстанавливают секрет, после чего его снова распределяют. Очевидно, что этот вариант более медленный, и время восстановления равно сумме времен восстановления и распределения. Во втором случае возможно быстрое восстановление компонента с промежуточным раскрытием секрета. Очевидно, что наиболее предпочтительным является вариант без раскрытия секрета, но не все схемы обеспечивают такую ​​возможность. В таких схемах желательно иметь вариант с промежуточным раскрытием секрета, но с возможностью быстрого восстановления компонента.

Рассмотрим схему распределения секрета, представленную в [1]. На рисунке 1 показана схема распределения секрета для этого метода. Как видно из рисунка, на вход дается секретный файл, затем он кодируется выбранным кодом, исправляющим ошибки, после чего имеют место группировка, перестановка и распределение головной части компонентов файла.

Теперь представим, что какой-то компонент потерялся. Процесс восстановления основан на промежуточном раскрытии секрета, но в этом процессе отсутствует процесс декодирования. Процесс восстановления изображен на рисунке 2. Как мы видно из рисунка, в качестве входной информации предоставляем t компонентов и номер компонента k, который должен быть восстановлен. Необходимо восстановить Shamir sharing сектор и получить пароль перестановки, номер таблицы и код, исправляющий ошибки. С помощью этих данных можно выполнить обратные операции группирования и перестановки. После этого для восстановления секрета необходимо провести операцию декодирования, но это не является обезательно для восстановления компонента. Для восстановления компонента необходимо только разделить данные тех столбцов, которые используются для получения компонента под номером k.

Рисунок 1. Работа схемы распределения секрета

Рисунок 2. Восстановление потерянного компонента

Рассмотрим пример. Предположим, что для распределения используется таблица 1, который обеспечивает (4,5) пороговую схему. В качестве недостающей рассмотрим первый компонент. В этом случае для восстановления следует предстовлять входные данные компонентов 2-5 и число 1. После операций Shamir restoring, Permutation-1 и Ungrouping получим данные тех столбцов, которые указаны перед компонентой 2-5. Нетрудно видеть, что там имеются необходимые столбцы для первого компонента. Необходимо взять эти столбцы, образовать первый компонент и вывести его на выход. Как видно, в этом процессе не используется трудоемкая операция декодирования данных для восстановления недостающих столбцов.

Таблица 1.

Пороговая схема (4,5)

Таким образом, получен метод быстрого восстановления поврежденных или отсутствующих компонентов, который основан на промежуточном раскрытии секрета. Описанная схема не может восстановить недостающий компонент, когда  . В этом случае не может быть восстановлен сектор Shamir sharing, следовательно, невозможно выполнить дальнейшие действия. Следовательно, можем констатировать, что такая схема распределения очень рискованная, и даже повреждение или потеря одного компонента приведут к потере секрета.

Для безотказной работы схемы распределения секрета, предпочтительно периодически выполнять проверку всех компонентов и при обнаружении поврежденных или отсутствующих компонентов произвести их восстановление. В противном случае, после долгого хранения может оказаться, что было повреждено или утеряно столько компонентов, что больше невозможно восстановить секрет, что приведет к потере секрета.

Заключение. Исследована пороговая схема распределения секрета на основе кодов, исправляющих ошибки, и предложен метод восстановления утраченного или поврежденного компонента. Метод восстановления компонента основан на промежуточном раскрытия секрета, но работает более быстро по сравнению с процессом восстановления и заново распределения секрета. С помощью этого метода можно при необходимости восстанавливать поврежденные или недостающие компоненты.

Список литературы:

1. Khemchyan A.A., Margarov G.I. Secret sharing based on error-correcting codes // Procedings of information technologies, electronics, radio engineering // NPUA Armenia, 2015. - Vol.1 - P.62-67.
2. McEliece R, J., Sarwate D.V. On sharing secrets and Reed-Solomon codes // Comm. ACM 1981. – 24 – P.583-584.
3. Хемчян А.А. Проверка компонентов в схеме распределения секрета на основе кодов, исправляющих ошибки // Вопросы технических и физико-математических наук в свете современных исследований: сб. ст. по матер. LX междунар. науч.-практ. конф. № 2(51). – Новосибирск: СибАК, 2023. – С. 5-10.
4. Shamir A. How to share a secret // Commun. ACM 1979. - Vol. 22, no. 11 - P.612-613.