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

23 views

It is mentioned in the famous paper Making a Faster Cryptanalytic Time-Memory Trade-Off (pdf) by Philippe Oechslin that: The total number of calculations we have to make is thus $\frac{t(t−1)}{2}... 1answer 158 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 ... 0answers 47 views ### Quantum complexity of LWE As per my understanding LWE is quantum secure because there is no known quantum algorithm to solve LWE in polynomial time. Due to the reductions given by Regev et al. If there is any algorithm that ... 0answers 37 views ### Computing cost for a trillionaire to compute GNFS in RFC 3766 RFC 3766, Section 4.1 discusses picking$n$to achieve some target cost for employing the GNFS, i.e.,$T$is known and$N$is unknown in the below equation:$$T = \kappa \cdot \exp{\left(c \cdot (\ln{... 0answers 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-... 0answers 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 ... 0answers 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 ... 0answers 166 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 ... 0answers 129 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 ... 0answers 9 views ### Weakly Sublinear Compact FE from Succinct FE and XiO I'm confused about a problem these days and I decided to seek an answer here. The question is about the section 4.1 of the paper LPST16. Let me recall the weakly sublinear compact FE scheme$\textrm{...
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 ...