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

DPLL plus ROBDD Derivation Applied to Inversion of Some Cryptographic Functions

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

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

Том: 6695


Год: 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: 1

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

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

Публикация в печати: 0

Добавил в систему: