# Questions tagged [cryptography]

Questions about the construction and analysis of protocols and algorithms for secure computation and communication (including authentication, integrity, and privacy aspects).

186 questions
Filter by
Sorted by
Tagged with
10k views

### Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?

Most of today's encryption, such as the RSA, relies on the integer factorization, which is not believed to be a NP-hard problem, but it belongs to BQP, which makes it vulnerable to quantum computers. ...
34k views

### How to verify number with Bob without Eve knowing?

You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob ...
4k views

### Meaning of: “'If factoring large integers is hard, then breaking RSA is hard,' is unproven”

I was reading CLRS and is said: If factoring large integers is easy, then breaking the RSA cryptosystem is easy. Which makes sense to me because with the knowledge of $p$ and $q$, it is easy to ...
3k views

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

I'm trying to explain the basics of Bitcoin to my parents. One of the core components of bitcoin, is signing transactions to make sure your identity can't be impersonated, and thus the need to ...
2k views

### Given RSA, why do we not know if public-key cryptography is possible?

I was on wikipedia on list of unsolved computer science problems and found this: Is public-key cryptography possible? I thought RSA encryption was a form of public-key cryptography? Why is this a ...
11k views

### Why is encrypting with the same one-time-pad not good?

To encrypt a message $m_1$ with a one-time-pad key $k$ you do $Enc(m_1,k) = m_1 \oplus k$. If you use the same $k$ to encrypt a different message $m_2$ you get $Enc(m_2,k) = m_2 \oplus k$, and if ...
35k views

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

From what I have seen about usage of a pair of public and private keys, the public key is used for encrypting a message, and the private key is used for decrypting the encrypted message. If a message ...
5k views

### How does an operating system create entropy for random seeds?

On Linux, the files /dev/random and /dev/urandom files are the blocking and non-blocking (respectively) sources of pseudo-random ...
5k views

### Could quantum computing eventually be used to make modern day hashing trivial to break?

Simply put, if one were to build a quantum computing device with the power of, say, 20 qubits, could such a computer be used to make any kind of modern hashing algorithm useless? Would it even be ...
2k views

### Why did RSA encryption become popular for key exchange?

This is a soft question. I don't know a lot about cryptography or its history, but it seems like a common use for RSA is to do key exchange by encrypting a symmetric key to send a longer message (e.g....
300 views

### Are asymptotic lower bounds relevant to cryptography?

An asymptotic lower bound such as exponential-hardness is generally thought to imply that a problem is "inherently difficult". Encryption that is "inherently difficult" to break is thought to be ...
1k views

### How to practically construct regular expander graphs?

I need to construct d-regular expander graph for some small fixed d (like 3 or 4) of n vertices. What is the easiest method to do this in practice? Constructing a random d-regular graph, which is ...
589 views

### Is it possible to create a “Time Capsule” using encryption?

I want to create a digital time capsule which will remain unreadable for some period of time and then become readable. I do not want to rely on any outside service to, for instance, keep the key ...
2k views

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

If P does equal NP, will it still be possible do design a cryptosystem where the optimal cryptanalysis algorithm takes, say, the square of the time taken up by the legitimate encryption and decryption ...
2k views

2k views

97 views

### Completeness of formal definition of 'hardness on the average'

While reading a cryptography textbook, i find the definition of a function that is hard on the average.(More precisely, it is 'hard on the average but easy with auxiliary input', but i omit latter for ...
162 views

### Mental poker: proving dealt hand is fair

I have just read mental poker, described in this fascinating paper(PDF) by cryptographic greats Adi Shamir, Ron Rivest, and Leonard Adleman. Assuming I have a website, (TTP) how can I prove to the ...
98 views

### One way recurrence O(N)->O(1)

Imagine we have a random number generator where g(n+1) = f(g(n)), where f is some function (e.g linear recurrence). I'm trying to find a system where it's fast to find many steps in the future ...