# Questions tagged [cryptography]

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

262 questions
Filter by
Sorted by
Tagged with
166 views

### If Q* can break encryption would that prove P=NP?

At 12:11 in this video the creator talks about unverified rumors the Q* algorithm can break AES-192 encryption. If this is true, would this mean P = NP?
1 vote
45 views

### Converting encrypted messages to unencrypted results of an equally hard to reverse function

If we have some function, $f$ with an exponentially sized domain, mapping the set $\{0, 1\}^N$ to $\{0, 1\}$, could we do something like this: For ease, let's say $E(x) = x^e (\text{mod} \; n)$. This ...
26 views

### Data structure for detecting duplicate entries efficiently

In search of an efficient data structure to store some sort of list hash that I can compare to a value to obtain a probability of it already being in the list. Perhaps it makes more sense defined as ...
25 views

### (Zero-knowledge?) Proof of Connection

I have a conundrum to solve but am not knowledgeable enough about cryptography to know whether it's possible to do, and if so, what method to use. I am a Provider and my task is to prove to some ...
39 views

### What is the definition of security of universal hashing

As a cryptographic primitive, universal hashing should have somewhat a criterion on its security. How is its (computational) security defined? Or, in other words, what "breaks" a universal ...
14 views

### Are there any typical papers on the impossibility of black-box reduction of circuits?

I am now considering the impossibility of black-box reductions between error-correcting codes and universal hashing without multiplicative overhead in depth. I could hardly find any classical papers ...
39 views

### Does there exist some partial" universal hashing?

Suppose we have sets $X$ and $Y$, $|X|=m$, $|Y|=n$. $H$ is a universal family of hash functions from $X$ to $Y$. Let $S\subsetneq X$ be a proper subset of $X$. Does there exist some "partial"...
39 views

### On the equivalence between two definitions of universal hashing

Let $H=\{h|h:X\to Y\}$, $|X|=n$, $|Y|=m$. $H$ is a universal hash family if Def 1. For any $x_1,\ x_2\in X$, $x_1\neq x_2$, $\left|\left\{h\in H\middle| h(x_1)=h(x_2)\right\}\right|\leq |H|/m$. (or ...
1 vote
18 views

### How difficult are lattice algorithms for low-dimensional lattices?

Most lattice problems, such as the shortest vector problem, the closest vector problem, shortest basis problem, etc, are NP-hard and thus conjectured to be worst-case exponential time in the rank of ...
25 views

### If the data that I input for locality sensitive hashing is sensitive, should its resulting hash also be considered sensitive?

Is it correct to assume that if the input that I hash is sensitive, that I should also consider the locality-sensitive hash generated for that input to be sensitive? I presume that, if an attacker has ...
25 views

### Asymmetric communication between two symmetric parties?

(sci-fi-esque question inspired by Counterpart). A portal between our world (called $A$) and a parallel world that's exactly the same (called $B$) opens up. Bob sees himself through this portal. $A$-...
16 views

### Reversible computing as a path to a useful PRNG or hash function?

There's a question I've long had about reversible computing: do non-trivial algorithms usually end up generating strongly pseudorandom data as an artifact of the computation? The most straightforward ...
19 views

### Protocol Proposed by Arthur-Merlin, and Zero Knowledge

Why there is a need for Arthur Merlin protocol. What are the cause and differences between arthur-merlin protocol and Zero knowledge protocol ?
1 vote
41 views

### Is Miller-Rabin not a suitable algortihm for the RSA key generation or am I missing something?

I'm trying to recreate the RSA key generator, from what I understood you must create two prime numbers of 256 bytes long, p and q...
94 views

### Self referential hash function possible?

Is there a hashing function $f$ that for each input $x$ if $f(x) = y$, then $f(x \, || \, y) = y$? In other words, if we concatenate its output with the input, the result will not change. Furthermore, ...
27 views

### Interactive ZKP of possession of a signed message

Suppose Alice has a verifiable (message, signature) pair from Cedric, who would not cooperate and routinely uses an algo (ecdsa, eddsa, rsa, or insert yours here) to sign messages. Alice wants to ...
29 views

### Is this restatement of one-way functions accurate?

I realize this is sort of a trivial ask, but I want to make sure I understand OWFs and it's usually explained with some jargon that I don't find clarifying. So, I'd just like to know whether or not my ...
58 views

### Does a random phenomenon have a pre defined probability distribution? what does it mean for something to be random?

While studying Shannon's notion of perfect secrecy I came upon the idea that a bit is perfectly random if it happens to be 0 or 1 with an equal probability. What does this mean? Also, what can we say ...
1 vote
74 views

### LWE with a low rank matrix

Consider the decision LWE setting, where we have to distinguish between $(A, As + e)$ and $(A, u)$, for a randomly chosen $m \times n$ matrix $A$, an $n \times 1$ secret vector $s$, an $m \times 1$ ...
1 vote
37 views

### Reference for the formal definition of sigma protocol

I'm looking for a book that contains the formal definition of sigma protocol (something like: A sigma protocol for a relation $R$ and a challenge space $C$ is... that satisfies the properties of ...
1 vote
60 views

### How can I prove the file on DVD is the original?

I have an old file written to a DVD-R several decades ago, and it turned out this file can potentially has some value as NFT (non-fungible token). The file was published online and have been copied ...
1 vote
38 views

### Where does 2^32 come from with bitcoin?

Several months ago I was doing research into calculating mining revenue for several crypto currencies. When trying to calculate BTC revenue I found this value 1/2^32 which was described somewhere ...
57 views

### How do these Crypto terms relate to each other and what do they all mean?

Alright this is another day of my pursuit to learn about how crypto works. I have several terms that I have found linked together. I was trying to do research on how the Target Hash is determined and ...
46 views

### What happens in the event of a collision in a crypto hash function?

I was reading about hash functions in crypto and a website had mentioned that they were collision free, which obviously isn't possible if there are infinite input values that are mapped to outputs of ...
1 vote
76 views

### How MAC (Mandatory Access Control) model prevents trojan horse attacks?

I've heard that the MAC Model prevents Trojans to charm files on the system. How is it possible? Can somebody show any example that MAC model protects us against it?
57 views

### What is the use or how can we implement zero-knowledge proof system in Elections?

I recently heard about the concept of zero-knowledge proof. However, I still do not get how it is possible to make it a solution to some real-world problems. One thing I heard is that zero-knowledge ...
86 views

### Why is M^e mod N the ciphertext and not just M^e

I watched a video on why the RSA algorithm works and it said that $(M^e \bmod N)^d \mod N = M^{ed} \bmod N$ which makes sense if $M^e$ is smaller than $N$. Would $M^e$ not be smaller than $N$, the ...
270 views

### If someone has an encrypted message and it's original plaintext, could he guess the private key if it's the one used to encrypt the message?

In digital signatures, the private key is used to encrypt a (hashed) message and the public key is used to decrypt it. This made me wonder since the receiver has the cipher text (digital signature) ...
1 vote