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. ...

learn more… | top users | synonyms

3
votes
0answers
68 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 ...
2
votes
0answers
33 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 ...
1
vote
0answers
107 views

Complexity using RSA

You encrypt a message using the RSA encryption system as $t^e \pmod n$ , where $t, e < n$ and $t$ is the numerical equivalent of the message. The message is written in a $27$-letter alphabet and is ...
1
vote
0answers
138 views

Complexity of verifying OTP secret

What is the minimum number of unique pairs of digests and inputs to a one-time pass needed to verify that a secret is equal to a ...
1
vote
0answers
123 views

How to develop a public key cryptosystem based on a hard problem?

Recently, I found a function that is performed on a sequence to return another sequence. All known algorithms for finding the input, given the output are of exponential complexity. I want to propose ...
0
votes
0answers
58 views

Performance of Fully homomorphic encryption VS Paillier encryption in Practice

Consider two schemes both have computation complexity linear to the input size (i.e. number of inputs). One scheme is based on Paillier encryption and the other one is based on fully homomorphic ...