Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [cryptography]

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

106
votes
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. ...
48
votes
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 ...
29
votes
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 ...
29
votes
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 ...
22
votes
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 ...
19
votes
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 ...
18
votes
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 ...
17
votes
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 ...
16
votes
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....
16
votes
1answer
296 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 ...
14
votes
5answers
32k 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 ...
14
votes
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 ...
14
votes
4answers
574 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 ...
13
votes
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 ...
13
votes
1answer
2k views

Choosing taps for Linear Feedback Shift Register

I am confused about how taps are chosen for Linear Feedback Shift Registers. I have a diagram which shows a LFSR with connection polynomial $C(X) = X^5 + X^2 + 1$. The five stages are labelled: $R4, ...
13
votes
1answer
333 views

Break an authentication protocol based on a pre-shared symmetric key

Consider the following protocol, meant to authenticate $A$ (Alice) to $B$ (Bob) and vice versa. $$ \begin{align*} A \to B: &\quad \text{“I'm Alice”}, R_A \\ B \to A: &\quad E(R_A, K) \...
13
votes
1answer
297 views

Proving the security of Nisan-Wigderson pseudo-random number generator

Let $\cal{S}=\{S_i\}_{1\leq i\leq n}$ be a partial $(m,k)$-design and $f: \{0,1\}^m \to \{0,1\}$ be a Boolean function. The Nisan-Wigderson generator $G_f: \{0,1\}^l \to \{0,1\}^n$ is defined as ...
12
votes
5answers
547 views

How is the key in a private key encryption protocol exchanged?

Windows NT used a point-to-point protocol where a client can communicate "securely" with a server by using a stream cipher to encrypt an array of messages with some key $k$. The server also encrypts ...
12
votes
2answers
4k views

How does a wifi password encrypt data using WEP and WPA?

How does the password that we enter (to connect to a wireless network) encrypt the data on the wireless network? Through my reading I am not sure if the password that we enter is the same as the ...
10
votes
2answers
2k views

What is the difference between classical crypto and post-quantum crypto?

Will there be a need to change the definitions of security if we have quantum computers? What cryptographic constructions will break? Do you know a survey or an article that explains what will be ...
10
votes
2answers
699 views

Weak hashing function for memorable IPv6 addresses

IPv6 addresses in the form of 862A:7373:3386:BF1F:8D77:D3D2:220F:D7E0 are much harder to memorize or even transcribe than the 4 octets of IPv4. There have been ...
9
votes
6answers
360 views

Could program verification techniques prevent bugs of the genre of Heartbleed from occurring?

On the matter of the Heartbleed bug, Bruce Schneier wrote in his Crypto-Gram of 15th April: '"Catastrophic" is the right word. On the scale of 1 to 10, this is an 11.' I read several years ago that a ...
9
votes
2answers
780 views

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

I have heard about all these Man-In-The-Middle Attack preventions and I am wondering, how this can possibly work if the man in the middle only listens to your stream and does not want to change the ...
9
votes
2answers
864 views

What mathematics can be interesting for these CS areas?

For my CS degree I have had most of the "standard" mathematical background: Calculus: differential, integral, complex numbers Algebra: pretty much the concepts up until fields. Number Theory: XGCD ...
9
votes
1answer
340 views

Attack on hash functions that do not satisfy the one-way property

I am revising for a computer security course and I am stuck on one of the past questions. Here is it: Alice ($A$) wants to send a short message $M$ to Bob ($B$) using a shared secret $S_{ab}$ to ...
9
votes
1answer
538 views

Is WPA2 with pre-shared key an example of a zero-knowledge proof?

When setting up an access point and selecting WPA2, one must manually enter a pre-shared key (a password), PSK, into both the AP and the STA. Both parties, AP and STA, must authenticate each other. ...
9
votes
1answer
354 views

How to measure the complexity of the discrete logarithm problem?

The answers to this question on Crypto Stack Exchange basically says that, to measure the complexity of the logarithm problem, we have to take the length of the number representing the size of the ...
8
votes
5answers
402 views

How can encryption involve randomness?

If an encryption algorithm is meant to convert a string to another string which can then be decrypted back to the original, how could this process involve any randomness? Surely it has to be ...
8
votes
1answer
296 views

NP Problems with unique solution

Is there any class of NP problems that have one unique solution? I'm asking that, because when I was studying cryptography I read about the knapsack and I found very interesting the idea.
8
votes
3answers
1k views

Key secrecy vs Algorithm secrecy

it's a well known statement that "Cryptographic security must rely on a secret key instead of a secret algorithm." I would like to ask about some details about it. And which are their differences? ...
8
votes
2answers
87 views

Running an algorithm on data remotely and ensuring answer has not been tampered with

I´ve been thinking about this particular computing/crypto/database problem for years and I just want to know if there are already solutions to it. To be honest I don´t even know what field this ...
8
votes
2answers
259 views

How hard is it to solve for $P$ in $A = PBP^{-1}$?

From graph isomorphism, we know that two graphs A and B are isomorphic if there is a permutation matrix P such that $A = P \times B \times P^{-1}$ So, to solve the problem, if two graphs are ...
8
votes
1answer
556 views

Is there a continuous hash?

Questions: Can there be a (cryptographically secure) hash that preserves the information topology of $\{0,1\}^{*}$? Can we add an efficiently computable closeness predicate which given $h_k(x)$ and $...
7
votes
3answers
2k views

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

I've started learning cryptography in class and we've come across One-Time-Pads, in which the key (uniformally agreed upon) is as long as the message itself. Then you turn the message into bits, do $...
7
votes
2answers
1k views

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

Does there exist an equivalent arithmetic circuit for each computable function? I've been trying to wrap my head around the statement above, but haven't found a counter example although I believe ...
7
votes
2answers
147 views

Zero-knowledge proof: Abstract example

So I was reading about ZKP on wikipedia, the abstract example in summary goes like this: Peggy wants to prove to Victor that she knows the secret to a door inside a cave that connect A and B ...
7
votes
1answer
1k views

If xor-ing a one way function with different input, is it still a one way function?

Suppose $f(x)$ is a one way function. What about $h(x)=f(x_1) \, \oplus \,f(x_2)$, where $x=x_1 || x_2$ and $\lvert x_1 \rvert = \lvert x_2\rvert$? $\oplus$ is exclusive disjunction (xor) $||$ is ...
7
votes
3answers
324 views

1-to-1 cryptographically secure bit shuffling

Given an input item (N bytes), I'm looking for a function that will map this to an output (still N bytes). The function should have the following qualities: It should be 1-to-1 so that all inputs ...
7
votes
1answer
1k views

Length-preserving one-way functions

Unfortunately my background in computational complexity is still weak, but I am working on it. As I understand, the question of existence of one-way functions is very important in the field. Assume ...
7
votes
1answer
235 views

Examples of NP Complete key exchange algorithms

There's a number of questions on the internet (this site and others; e.g. Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems? ) discussing NP hardness of ...
7
votes
1answer
854 views

Quadratic residue and integer factoring

I often read that deciding whether or not a number $r$ is a quadratic residue modulo $n$ is an interesting (and hard) problem from number theory (especially if $n$ is not prime). I am looking at the ...
6
votes
4answers
586 views

After implementing a novel encryption algorithm, how would one go about analyzing its security or get help from others in doing so?

Preface: This question was originally asked on Theoretical Computer Science, and the kind people there referred me to this web site. It is being repeated here in an attempt to find a satisfying answer....
6
votes
1answer
1k views

In the Miller-Rabin primality test, for a composite number, why are at least $\frac{3}{4}$ of the bases witnesses of compositeness?

The following is an excerpt from the Wikipedia article on the Miller-Rabin primality test: It can be shown that for any odd composite $n$, at least $\frac{3}{4}$ of the bases $a$ are witnesses for ...
6
votes
1answer
2k views

Negligible Function in Cryptography

In the field of Cryptography and Computation Complexity there is a notion of negligible function. I have some difficulties in understanding intuition behind this notion. The following are some ...
6
votes
2answers
97 views

Invertible function that randomizes order

I am looking for an invertible discrete function $f:\{0,1,2,\dots,n-1\} \to \{0,1,2,\dots,n-1\}$ for some given integer $n$. I want $f(0),f(1),\dots,f(n-1)$ to return all the integers in range $[0..n)...
6
votes
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 ...
6
votes
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 ...
5
votes
3answers
97 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 ...
5
votes
4answers
343 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) ...
5
votes
1answer
740 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 ...