# Questions tagged [cryptography]

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

17 questions
Filter by
Sorted by
Tagged with
13k 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. ...
136 views

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)... 2answers 81 views ### Indexing a random permutation I am curious if there exists a method for specifying a permutation$F_k: X \to X$with a small(ish)$k$. Something that comes very close to my goal is a block cipher, say AES. But block ciphers have ... 1answer 371 views ### Bijective algorithm(s) that can shuffle a range of numbers back and forth I've spent the last hours trying to come up with an algorithm that shuffles an ordered set of numbers (i.e a simple range of numbers) in a way that I can retrieve from a shuffled value the original ... 1answer 87 views ### What are the examples of the easily computable "wild" permutations? I am looking for the function$y=f(x)$that would map the integer interval$[0,n)$into itself$[0,n)$. The function must be bijective, so it is a permutation of n elements. It should "randomize" the ... 6answers 66k 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 ... 12answers 38k 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 ... 2answers 6k 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 ... 2answers 921 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 ... 4answers 732 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 ... 1answer 365 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) \... 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 ... 1answer 3k 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 ... 5answers 15k views ### Why is encrypting with the same one-time-pad not good? To encrypt a messagem_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 ... 1answer 3k 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, ...
I was wondering how should I proceed in order to show that the composition of (say) two one-way functions (either weak or strong or both together) is not a one-way function? Specifically: Say $f$ and ...