Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
10 votes

SAT-Based Public Key Cryptosystem

There are known impossibility results regarding basis public-key cryptography on NP-complete problems. In this paper by Goldreich and Goldwasser they show that under common types of reductions, it is ...
Yehuda Lindell's user avatar
5 votes
Accepted

Plotting Running Times of SAT solver

Disclaimer: I'm answering without any knowledge on the content of the paper in question. Why there are numbers in this Figure 1, that are placed in vertical form? Because otherwise the figure ...
tum_'s user avatar
  • 286
4 votes
Accepted

Is SAT the mathematical problem behind SHA-2 and SHA-3?

Cryptographic problems should be hard in average. NP-Complete problems such that SAT are supposed to be hard in the worst case. But, for many practical distributions, SAT is not hard in average. If ...
Ievgeni's user avatar
  • 2,595
4 votes

Determine complexity of a SAT problem

We do not know how to bound the complexity of a SAT problem. There are several special form SATs known to be solveable efficiently, but there is no finite list of such special problems. You can use a ...
Meir Maor's user avatar
  • 11.8k
2 votes
Accepted

How to use smt solvers in order to restrict the possible key search where a portion of the private key and a portion of the public key hash is known?

search for the public key which then… That's infeasible if we hash public keys that are not chosen according to what's known of the private key. It would require about $2^{160}$ hashes to find one ...
fgrieu's user avatar
  • 142k
2 votes

SAT-Based Public Key Cryptosystem

I do not have enough high reputation to comment so I am writing here. I have also looked at the paper so I would like to share my thoughts. I think that in order to understand whether the bit is in ...
Kristina Dedndreaj's user avatar
2 votes
Accepted

Function to polynomial equation in GF(2)

The formula $$ d+e+ac+ae+bc+be+cd+de+ade+ace+abd+abc $$ is in algebraic normal form (ANF). That is the unique representation of our boolean function with respect to the $\mathbb F_2$-basis $\{a^ib^jc^...
yyyyyyy's user avatar
  • 12.1k
2 votes
Accepted

current state of 3-SAT problem?

I do not know if the result is true, since I did not check it, but note that this algorithm is not in the standard model of quantum computation. As the author himself put it: The Deutsch model of ...
Geoffroy Couteau's user avatar
1 vote

Partial known message pre-image attack on SHA-1

If you know the last 448 bits, we can assume that this part actually the padding part with length at the end, then you will have 64-bit unknown data for the input to pre-image attack. Since you know ...
kelalaka's user avatar
  • 48.7k
1 vote

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

One can't use the circuit exactly as given. To build a two-blocks SHA-256, the second round must be fed as input both the second 512-bit (padded) block, and the 256-bit output by the first round. The ...
fgrieu's user avatar
  • 142k
1 vote

SAT-Based Public Key Cryptosystem

I think, the original question has been well answered by Carl Löndahl in the comments. Each of the terms you add does not only consist of "random variables" but may well contain a constant (1). In ...
Echsecutor's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible