21 citations · 71 across the 12 of their papers we have counts for
7 papers · 1 filter
Efficient Parallel Algorithm for Decomposing Hard CircuitSAT Instances
Victor Kondratiev, Irina Gribanova, Alexander Semenov
We propose a novel parallel algorithm for decomposing hard CircuitSAT instances. The technique employs specialized constraints to partition an original SAT instance into a family o…
On Cryptographic Attacks Using Backdoors for SAT
Alexander Semenov, Oleg Zaikin, Ilya Otpuschennikov +2
Propositional satisfiability (SAT) is at the nucleus of state-of-the-art approaches to a variety of computationally hard problems, one of which is cryptanalysis. Moreover, a number…
Using Automatic Generation of Relaxation Constraints to Improve the Preimage Attack on 39-step MD4
Irina Gribanova, Alexander Semenov
In this paper we construct preimage attack on the truncated variant of the MD4 hash function. Specifically, we study the MD4-39 function defined by the first 39 steps of the MD4 al…
Encoding Cryptographic Functions to SAT Using Transalg System
Ilya Otpuschennikov, Alexander Semenov, Irina Gribanova +2
In this paper we propose the technology for constructing propositional encodings of discrete functions. It is aimed at solving inversion problems of considered functions using stat…
Using Monte Carlo method for searching partitionings of hard variants of Boolean satisfiability problem
Alexander Semenov, Oleg Zaikin
In this paper we propose the approach for constructing partitionings of hard variants of the Boolean satisfiability problem (SAT). Such partitionings can be used for solving corres…
Transalg: a Tool for Translating Procedural Descriptions of Discrete Functions to SAT
Ilya Otpuschennikov, Alexander Semenov, Stepan Kochemazov
In this paper we present the Transalg system, designed to produce SAT encodings for discrete functions, written as programs in a specific language. Translation of such programs to…
On estimating total time to solve SAT in distributed computing environments: Application to the SAT@home project
Alexander Semenov, Oleg Zaikin
This paper proposes a method to estimate the total time required to solve SAT in distributed environments via partitioning approach. It is based on the observation that for some si…