Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
70 votes

Can a public key be used to decrypt a message encrypted by the corresponding private key?

Q: If you pedal backwards on a fish, does it go backwards? A: ??? A fish is not a bicycle. Similarly, you cannot use a private key to encrypt a message or a public key to decrypt a message. They ...
Gilles 'SO- stop being evil''s user avatar
28 votes

What is an extremely basic asymmetric cipher that I can present at the pub?

If you want to present public key cryptography to your parents or friends, then I suggest you follow some guidelines. First, don't talk about specific functions, nobody cares about SHAxxx, keep your ...
Ariel's user avatar
  • 13.4k
17 votes
Accepted

Problem with the pseudo random number generator One-Time-Pad

You seem to have misunderstood what the key is. In the context of symmetric encryption, the key is a shared secret: something that is known to both the sender and receiver. For OTP, the key is the ...
David Richerby's user avatar
15 votes

What are the flaws in this encryption algorithm?

This is not a secure encryption scheme. It is similar to a Hill cipher, and vulnerable to similar attacks. For instance, it is vulnerable to known-plaintext attacks: an attacker who observes a ...
D.W.'s user avatar
  • 160k
15 votes

Can a public key be used to decrypt a message encrypted by the corresponding private key?

Yes, a message which has encrypted using private key can be decrypted using the public key. In fact, this is implemented to verify the authenticity of the data. In the digital signature, a person ...
Kevin Amipara's user avatar
15 votes

Does there exist an equivalent arithmetic circuit for each computable function?

Any computable boolean function with a fixed-length input can be computed by an arithmetic circuit. Consider any boolean function $f:\{0,1\}^n \to \{0,1\}$. Then there exists a multivariate ...
D.W.'s user avatar
  • 160k
15 votes

What is an extremely basic asymmetric cipher that I can present at the pub?

A common metaphor I hear used is manufacturing a bunch of padlocks, keeping all the keys, and sending out open padlocks to anyone who wants one. Then anyone with such a padlock can send you secret ...
Ben Millwood's user avatar
14 votes
Accepted

If P=NP, are there cryptosystems that would require n^2 time to break?

Yes — in fact, the very first public-key algorithm that was invented outside an intelligence agency worked like that! The first publication that proposed public-key cryptography was "Secure ...
Gilles 'SO- stop being evil''s user avatar
14 votes
Accepted

Why did RSA encryption become popular for key exchange?

There is no strong technical reason. We could have used Diffie-Hellman (with appropriate signatures) just as well as RSA. So why RSA? As far as I can tell, non-technical historical reasons ...
D.W.'s user avatar
  • 160k
14 votes

Why do public key systems involve private keys?

Public key cryptography means that the entire communication between both parties is public, including the setup. Contrast this with the case of two parties $A,B$ meeting in secret, agreeing on some ...
Ariel's user avatar
  • 13.4k
13 votes
Accepted

How are extremely large integers stored and implemented in programming languages?

MPI stands for Multiple Precision Integer. Multiple precision arithmetic is what you need when you work with integer types that go beyond the machine width $w$. The basic idea is simple, you represent ...
Vincenzo's user avatar
  • 3,302
11 votes

Problem with the pseudo random number generator One-Time-Pad

Now to make a more efficient One-Time-Pad you'd use a pseudo-random number generator No, no and once again no. I'm concerned that this is what you're being taught. The absolutely fundamental ...
Paul Uszak's user avatar
  • 1,602
10 votes

What are the flaws in this encryption algorithm?

Cryptosystems which are algebraic in nature are amenable to algebraic cryptanalysis. If you are trying to design a secure cryptosystem for actual use, there is one important maxim that you should ...
Yuval Filmus's user avatar
10 votes

Why did RSA encryption become popular for key exchange?

Diffie–Hellman lacks a crucial feature: authentication. You know you are sharing a secret with someone, but you can't know if it's the recipient or a man in the middle. With RSA, you may have a ...
Jacen's user avatar
  • 1,040
10 votes
Accepted

Does there exist an equivalent arithmetic circuit for each computable function?

Arithmetic circuits compute a polynomial in their input. An arithmetic circuit over some field $\mathbb{F}$ with $n$ variables and total degree $d$ can compute functions $f:\mathbb{F}^n\rightarrow\...
Ariel's user avatar
  • 13.4k
10 votes
Accepted

Can you prevent a man in the middle from reading the message?

Can the man in the middle not just take the keys swapped by the opponents, change the keys and then decrypt and encrypt the message again? Yes, they can. A key exchange protocol like (the "textbook" ...
dkaeae's user avatar
  • 5,027
8 votes
Accepted

Is time complexity more important than space complexity?

In fact, when we are talking about algorithms in general, time-complexity is discussed much more frequently than space-complexity. Let me provide a few ideas to support that more general phenomenon ...
John L.'s user avatar
  • 39k
7 votes

Zero-knowledge proof: Abstract example

I believe this is done to illustrate two things. (i) The small probability, that $P$eggy ($P$rover) might be lying. If she really does not know the magic word and $V$ictor ($V$erifier) sees her ...
Riyil's user avatar
  • 138
7 votes

What is an extremely basic asymmetric cipher that I can present at the pub?

The problem with explaining asymmetric cyphers (and the reason why most pop explanations actually fail to explain anything) is that they are entwined with the idea that there exist problems that are (...
quicksort's user avatar
  • 4,262
7 votes

Problem with the pseudo random number generator One-Time-Pad

A pseudorandom generator is a deterministic algorithm, which given a short random seed returns a pseudorandom string fooling certain adversaries (i.e. such adversaries will not be able to distinguish ...
Ariel's user avatar
  • 13.4k
7 votes

Why do public key systems involve private keys?

Security is about protecting yourself from adversaries: it's about achieving something that adversaries can't achieve. Cryptography is a part of security that's about protecting information, to ...
Gilles 'SO- stop being evil''s user avatar
6 votes
Accepted

Examples of NP Complete key exchange algorithms

There are no known public-key cryptographic algorithms that have been proven to be NP-hard to break. None. So we can't provide you examples, because none are known. Answer to your original question:...
D.W.'s user avatar
  • 160k
6 votes
Accepted

Computation of discrete logarithm

As far as we know there is no efficient way to do that. Such a way would constitute a break of the DSA scheme, and no break of the DSA is known. In particular, DSA is believed to be secure, so it is ...
D.W.'s user avatar
  • 160k
5 votes
Accepted

How to measure the complexity of the discrete logarithm problem?

It doesn't matter whether you choose the size of the group $|G|$ or the size of the integer representing it $n$ as a parameter, since $n \approx \log |G|$. There are two reasons that usually the ...
Yuval Filmus's user avatar
5 votes
Accepted

Is it possible to build short proofs of arbitrary folds over a huge list?

Yes, there is a generalization of the construction you mentioned. However, it's utility depends on the function F. The guarantees you get are meaningful only if <...
D.W.'s user avatar
  • 160k
5 votes

How do you rank the strings represented by a regular expression?

Suppose you want to encode an element of $\binom{[n]}{k}$, that is, a subset of $\{1,\ldots,n\}$ of size $k$. There are $\binom{n}{k}$ such subsets. FPE functions know how to handle encoding and ...
Yuval Filmus's user avatar
5 votes
Accepted

Given the hash of a collection, H(X), can I build a proof that F(X) == Y, without having X?

Yes, this is possible. Use a zero knowledge proof (of knowledge). If F is computable in polynomial time, then there exists a polynomial-time zero-knowledge proof ...
D.W.'s user avatar
  • 160k
5 votes

Equivalent expression in English: Set Notation $\{0,1\}^K$

In set theory $B^A$ denotes the set of functions from $A$ to $B$. Thus, an element $f\in B^A$ is a function $f:A\rightarrow B$. In your specific case $\{0,1\}^k$ is the set of functions from the ...
Massimo Ortolano's user avatar

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