Страница публикации

DPLL plus ROBDD Derivation Applied to Inversion of Some Cryptographic Functions

Тип публикации: Статья в журнале

Тип материала: Текст

Авторы: Ignatiev A., Semenov A.

Журнал: Theory and Applications of Satisfiability Testing - SAT 2011

Язык публикации: english

Серия книг: Lecture Notes in Computer Science

Том: 6695

Номера страниц: 76-89

Количество страниц: 14

Год публикации: 2011

Отчетный год: 2011

Аннотация: The paper presents logical derivation algorithms that can be applied to inversion of polynomially computable discrete functions. The proposed approach is based on the fact that it is possible to organize DPLL derivation on a small subset of variables appeared in a CNF which encodes the algorithm computing the function. The experimental results showed that arrays of conflict clauses generated by this mode of derivation, as a rule, have efficient ROBDD representations. This fact is the departing point of development of a hybrid DPLL+ROBDD derivation strategy: derivation techniques for ROBDD representations of conflict databases are the same as those ones in common DPLL (variable assignments and unit propagation). In addition, compact ROBDD representations of the conflict databases can be shared effectively in a distributed computing environment.

Индексируется WOS: Q4

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Нет

Индексируется ВАК: Нет

Индексируется CORE: Нет