Questions tagged [sat]

For questions involving/related to the Boolean satisfiability problem (SAT).

Filter by
Sorted by
Tagged with
0
votes
1answer
206 views

current state of 3-SAT problem?

In this paper, a quantum algorithm to solve the 3-SAT problem in linear time is presented. Is it true? Did the author make a mistake? What state-of-the-art algorithms exist for this problem?
2
votes
1answer
331 views

Partial Known Message Pre-Image Attack on SHA-1

If the last 448 bits of a sha1 block input are known (only the first 64 bits are unknown). Is it possible to do a preimage attack using SAT solvers or something else? Or do I have to brute force all $...
3
votes
1answer
477 views

How to sequence SHA256 block circuit to obtain hash of a message comprising multiple 512 blocks?

I am trying to obtain a circuit that computes the SHA256 hash for an input message that is greater than 512 bits. I understand how the message is to be padded (we append a 1 and then some zeroes, ...
3
votes
1answer
176 views

Function to polynomial equation in GF(2)

Let F(a,b,c,d,e) be a function that returns the ith bit of 0x3A5C742E, where ...
8
votes
3answers
519 views

SAT-Based Public Key Cryptosystem

I am researching post quantum cryptography and I've stumbled upon this article which presents a PKC with an np-complete (SAT) trapdoor. I was wondering if someone could help me understand the way the ...
4
votes
1answer
104 views

Plotting Running Times of SAT solver

In the the paper "Efficient Methods for Conversion and Solution of Sparse Systems of Low-Degree Multivariate Polynomials over GF(2) via SAT-Solvers" there is a Figure that I can not understand and I ...
5
votes
2answers
267 views

Determine complexity of a SAT problem

Is there a standard way to determine a complexity of the specified SAT problem? I'm researching algebraic cryptanalysis and came to solving multivariate quadratic equation systems using CryptoMiniSat. ...