# Tagged Questions

Complexity describes - in simple words - how hard (complex) it is to reach a specific goal; and under which conditions. In cryptography, this mostly ends up in using the complexity theory to analyze things. One of the main goals of complexity theory is to prove lower bounds on the resources (e.g. ...

114 views

### Practical differences between circuits and turing machines for cryptography

In formal cryptography, we model algorithms (mostly our adversaries) as (Probabilistic) Turing Machines or as boolean circuits. In our lecture on formal cryptography, we learned that circuits are more ...
1k views

### What does “running in polynomial time” really mean?

I'm currently learning private-key cryptography. I've been able to see that perfect secrecy is achievable if no assumption is made about the computational power of the attacker. However, perfect ...
2k views

### What is the largest performed/possible bruteforce attack to date?

I've read that cracking 128-bit key is currently out of reach of all humanity. However, I can't seem to find any information on what scope of brute force attacks have been performed or are possible at ...
2k views

64 views

### Majority encryption algorithm?

Assume that I want to leave an encrypted message to a group of $n$ people in a way that they can only decrypt it if they work together in the following sense: For some fixed $k < n$ every sub-...
70 views

### P-Complete hashes, hashing to a larger set

Historically hashes have been from a large set (say 256 characters) to a smaller set (256 bits). Also, hash functions that are P-complete have no known parallel algorithm; they must be computed ...
202 views

693 views

### Differences between Work Factor and Time Complexity

I am interested to know if work factor means the same thing as time complexity. Quoting Work Factor : Uncovering keys in cryptosystems The Work Factor of a cryptosystem is related to its key-...
521 views

### ECC Complexity order of point addition, scalar point multiplication and selecting random point

I am facing this problem in calculating the order of a process which involves ECC point addition: $P+Q$ , scalar multiplication: $aP$, and selecting random points in the group. The group is of prime ...
444 views

### Why does Merkle's Puzzle requires Eve quadratic complexity of effort to break the system?

The way Applied cryptography 2ED explains the puzzle is as follows (I paraphrase it): Bob generates 2^20 messages of the form x,y where ...
37 views

### DSSP reduction to DSSI

In â€œTowards quantum-resistant cryptosystems from supersingular elliptic curve isogenies" by DeFeo, Jao and Plut, a reduction from the Decisional Supersingular Product (DSSP) problem to Decisional ...