Прикладная дискретная математика
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Прикладная дискретная математика, 2019, номер 44, страницы 34–42
DOI: https://doi.org/10.17223/20710410/44/3
(Mi pdm659)
 

Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)

Математические методы криптографии

Cryptanalytic concept of finite automaton invertibility with finite delay

G. P. Agibalov

National Research Tomsk State University, Tomsk, Russia
Список литературы:
Аннотация: The automaton invertibility with a finite delay plays a very important role in the analysis and synthesis of finite automata cryptographic systems. The automaton cryptanalitic invertibility with a finite delay $\tau$ is studied in the paper. From the cryptanalyst's point of view, this notion means the theoretical possibility for recovering, under some conditions, a prefix $\alpha$ of a length $n$ in an unknown input sequence $\alpha\delta$ of an automaton from its output sequence $\gamma$ of the length $n+\tau$ and perhaps an additional information such as parameters $\tau$ and $n$, initial ($q$), intermediate ($\theta$) or final ($t$) state of the automaton or the suffix $\delta$ of the length $\tau$ in the input sequence. The conditions imposed on the recovering algorithm require for prefix $\alpha$ to be arbitrary and may require for the initial state $q$ and suffix $\delta$ to be arbitrary or existent, that is, the variable $\alpha$ is always bound by the universal quantifier and each of variables $q$ and $\delta$ may be bound by any of quantifiers — universal ($\forall$) or existential ($\exists$) one. The variety of information, which can be known to a cryptanalyst, provides many different types of the automaton invertibility and, respectively, many different classes of invertible automata. Thus, in the paper, an invertibility with a finite delay $\tau$ of a finite automaton $A$ is the ability of this automaton to resist recovering or, on the contrary, to allow precise determining any input word $\alpha$ of a length $n$ for the output word $\gamma$ being the result of transforming by the automaton $A$ in its initial state $q$ the input word $\alpha\delta$ with the $\delta$ of length $\tau$ and with the known $n, \tau, A, \gamma$ and $\upsilon\subseteq \{\delta, q, \theta, t\}$ where $q$ and $\delta$ may be arbitrary or some elements in their sets and $\theta $ and $t$ are respectively intermediate and final states of $A$ into which $A$ comes from $q$ under acting of input words $\alpha$ and $\alpha\delta$ respectively. According to this, the automaton $A$ is called invertible with a delay $\tau$ if there exists a function $f(\gamma, \upsilon)$ and a triplet of quantifiers $\varkappa\in\{Q_1x_1Q_2x_2Q_3x_3: Q_ix_i \in\{\forall q, \exists q, \forall\alpha, \forall\delta, \exists\delta\}, i \neq j \Rightarrow x_i \neq x_j\}$ such that $\varkappa[f(\gamma, \upsilon)= \alpha]$; in this case $f$ is called a recovering function, $(\varkappa, \upsilon)$ — an invertibility type, $\varkappa$ — an invertibility degree, $\upsilon$ — an invertibility order of the automaton $A$ and $\exists f \varkappa[f(\gamma, \upsilon)= \alpha]$ — an invertibility condition of type $(\varkappa, \upsilon)$ for the automaton $A$. So, 208 different types of the automaton $A$ invertibility are defined at all. The well known types of (strong) invertibility and weak invertibility described for finite automata earlier by scientists (D. A. Huffman, A. Gill, Sh. Even, A. A. Kurmit, Z. D. Dai, D. F. Ye, K. Y. Lam, R. Tao and many others) in our theory belong to types $(\forall q\forall\alpha\forall\delta, \emptyset)$ and $(\forall q\forall\alpha\forall\delta, \{q\})$ respectively. For every invertibility type, we have defined a class of automata with this type of invertibility and described the inclusion relation on the set of all these classes. It has turned out that the graph of this relation is the union of twenty nine lattices with thirteen of them each containing sixteen classes and sixteen lattices each containing thirteen classes. To solve the scientific problems (invertability tests, synthesis of inverse automata and so on) related to the different and concrete invertibility classes, we hope to continue these investigations.
Ключевые слова: finite automata, information-lossless automata, automata invertibility, cryptanalytic invertibility.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 17-01-00354_а
The author is supported by the RFBR-grant no. 17-01-00354.
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.7
Язык публикации: английский
Образец цитирования: G. P. Agibalov, “Cryptanalytic concept of finite automaton invertibility with finite delay”, ПДМ, 2019, no. 44, 34–42
Цитирование в формате AMSBIB
\RBibitem{Agi19}
\by G.~P.~Agibalov
\paper Cryptanalytic concept of~finite~automaton invertibility with finite delay
\jour ПДМ
\yr 2019
\issue 44
\pages 34--42
\mathnet{http://mi.mathnet.ru/pdm659}
\crossref{https://doi.org/10.17223/20710410/44/3}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000476644400003}
\elib{https://elibrary.ru/item.asp?id=38555960}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/pdm659
  • https://www.mathnet.ru/rus/pdm/y2019/i2/p34
  • Эта публикация цитируется в следующих 5 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Прикладная дискретная математика
    Статистика просмотров:
    Страница аннотации:217
    PDF полного текста:72
    Список литературы:30
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024