Skip to main content
12 votes

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 ...
tsen's user avatar
  • 121
11 votes
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 ...
Mikero's user avatar
  • 13.9k
3 votes

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 ...
Daniel S's user avatar
  • 24.1k
2 votes

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 ...
Maarten Bodewes's user avatar
  • 93.4k
2 votes
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 ...
Daniel S's user avatar
  • 24.1k
2 votes
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 ...
Mark Schultz-Wu's user avatar
  • 13.5k
2 votes
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 ...
Mark Schultz-Wu's user avatar
  • 13.5k
2 votes

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 ...
kodlu's user avatar
  • 22.9k
2 votes
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 ...
Mahesh S R's user avatar
2 votes

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, ...
Mahesh S R's user avatar
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 ...
kodlu's user avatar
  • 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 "...
kodlu's user avatar
  • 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 ...
Ray Morris's user avatar

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