# Tag Info

### Cryptography based on uncomputable problems?

It is impossible to build a cryptographic algorithm using uncomputable problems because you cannot compute them. It would be impossible to execute the encryption. In order to use a problem for ...
• 121
Accepted

### Cryptography based on uncomputable problems?

Encryption, signatures, etc., can always be broken in NP. You can break any encryption scheme if you can solve the following decision problem: "does there exist a secret key and encryption ...
• 13.9k

### Learning the LWE secret with advice

This would be very bad. Assuming that you're calculating $\mod q$ for some $q$, the learner can recover $s$ with at most $3n$ queries even while ignoring the samples. I'll assume that $q$ is even, but ...
• 24.1k

### Discrete log problem - does luck exist?

Examples that use very small parameter and key sizes are mainly provided to let students understand the system. Of course they do provide the same security as expected for the algorithm. The thing is ...
• 93.4k
Accepted

### Testing whether the Euler Totient of a number equals to certain value

Yes, though it is not completely straightforward. There is a tighter form of Euler's theorem for composite numbers that says that $a^{\lambda(n)}\equiv 1\pmod n$ for $(a,n)=1$ where $\lambda(n)$ is ...
• 24.1k
Accepted

### Can the runtime of a reduction help an adversary distinguish the reduction from the adversary's challenger?

I think you're missing the main point of reductions, which I would describe as the following Any adversary $A$ that breaks the cryptographic algorithm can also be used to break the hardness ...
• 13.5k
Accepted

### Decision LWE vs Search LWE: Which one is harder?

The standard answer to this is Micciancio Mol. In general, we normally assume that search LWE is hard (algorithms breaking LWE typically break search LWE), and then connect the hardness of decision ...
• 13.5k

### Asymptotic efficiency of modular multiplication

This seems to be the case for generic moduli $n$ and generic exponents. See the preprint of a chapter entitled "Efficient Modular Multiplication" (available here) from the book Computational ...
• 22.9k
Accepted

### Languages $L$ that have perfect zero-knowledge that do not have any $AM$ proof system that is perfect or zero-knowledge on $L$

In the statistical zero-knowledge ($\mathsf{SZK}$) setting, several results were established by Okamoto. He demonstrated that Private-coin $\mathsf{SZK}$ is equal to Public-coin $\mathsf{SZK}$ where ...
• 729

### Question about P and NP problem

The polynomial time algorithm $\mathcal{R}_{\mathcal{L}}$ serves as a verifier, certifying that $x \in \mathcal{L}$ through the witness/proof $w$. For example, to show that a formula \$\phi(x_1, \dots, ...
• 729
1 vote
Accepted

### Why doesn't the existence of the Quadratic Sieve algorithm imply that integer factorization is in the class SUBEXP?

Yes both QS and NFS (Number Field Sieve) imply that factorization is subexponential. But the exact relationship between SUBEXP and NP is unknown. See the answer to the question here. And as pointed ...
• 22.9k
1 vote

### How to prove that an algorithm is the time optimal algorithm for implementing a problem?

Since you stated interest in how to prove an algorithm is time-optimal, a telescopic summary: This requires proving lower bounds on complexity, which is very difficult in general. I will use "...
• 22.9k
1 vote

### Cryptography based on uncomputable problems?

It is certainly conceivable. The big issue is, most undecidable problems are of the form "create an algorithm which, for all possible inputs ...". Many of these problems are easy to solve ...

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