# 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
5answers
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. ...
12answers
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 ...
5answers
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 ...
4answers
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 ...
3answers
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 ...
5answers
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 ...
5answers
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 ...
2answers
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 ...
2answers
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 ...
4answers
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....
1answer
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 ...
2answers
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 ...
4answers
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 ...
2answers
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 ...
1answer
2k views

3answers
2k views

1answer
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 ...
1answer
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 ...
3answers
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 ...
4answers
347 views

### Can all NP-complete cryptosystems be broken if one is broken?

I was just reading something about NP-hard problems and cryptosystems. I was thinking: Every NP-complete problem can be reduced to another and every NP-complete problem has an equivalent (NP-hard) ...
1answer
809 views

### Do one way function exist?

I was recently going through the Wiki page List of unsolved Problems in Computer Science. There was a problem which I do not understand Do one-way functions exist ? [Is public-key cryptography ...