Questions tagged [sat]
For questions involving/related to the Boolean satisfiability problem (SAT).
7
questions
0
votes
1answer
222 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
360 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
510 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
181 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
545 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
106 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
278 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. ...
