Skip to main content

Questions tagged [cryptography]

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

Filter by
Sorted by
Tagged with
3 votes
1 answer
54 views

Weaknesses of the alternative RSA-like algorithm

Disclaimer: it is a purely out-of-curiosity question. We discussed this implementation with a friend and could not find any breaches, but I have a gut feeling that there might be some. Consider a ...
Ivan Smirnov's user avatar
1 vote
1 answer
45 views

Applications of a SAT Solver Oracle for Determining the Uniqueness of Solutions

I am exploring two kinds of model $𝑝_{π‘š,𝑛,k}$ and $S_{m,n,k}$ within the realm of satisfiability problems (SAT). Formal construction of $𝑝_{π‘š,𝑛,k}$ To construct the $𝑝_{π‘š,𝑛,k}$ model in ...
Jxb's user avatar
  • 338
0 votes
1 answer
33 views

Can you unwind a cryptographic hash function's last round?

Given a cryptographic hash, $ \text{hash}(A || B || C) $, and the last block added to the hash, $ C $, can you determine $ \text{hash}(A || B) $? In other words, can you roll back the last round of a ...
Zaz's user avatar
  • 145
1 vote
2 answers
187 views

Reversible streaming hash function

Do any streaming hash functions exist that provide the same result if the input is reversed? That is to say, is there some hash function, $h$, such that: $$ h(h(h(h(0, x_1), x_2), ...), x_n) = h(h(h(h(...
Zaz's user avatar
  • 145
-3 votes
1 answer
278 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?
Asleepace's user avatar
1 vote
1 answer
49 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 ...
abokifas's user avatar
0 votes
0 answers
30 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 ...
maxy's user avatar
  • 1
-1 votes
1 answer
32 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 ...
Yellow's user avatar
  • 99
3 votes
1 answer
50 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 ...
Kagura Hitoha's user avatar
0 votes
0 answers
18 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 ...
Kagura Hitoha's user avatar
1 vote
1 answer
46 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"...
Kagura Hitoha's user avatar
1 vote
1 answer
55 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 ...
Kagura Hitoha's user avatar
1 vote
0 answers
20 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 ...
Mike Battaglia's user avatar
0 votes
0 answers
28 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 ...
Pierre Duluth's user avatar
0 votes
0 answers
28 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$-...
chausies's user avatar
  • 532
0 votes
1 answer
25 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 ...
Trev's user avatar
  • 306
1 vote
0 answers
43 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...
chyxo's user avatar
  • 11
5 votes
1 answer
157 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, ...
prog's user avatar
  • 105
2 votes
1 answer
32 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 ...
wick's user avatar
  • 123
0 votes
1 answer
33 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 ...
Trev's user avatar
  • 306
-1 votes
1 answer
60 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 ...
Kashish's user avatar
1 vote
0 answers
75 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$ ...
Sid Meier's user avatar
  • 249
1 vote
0 answers
47 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 ...
H5brick's user avatar
  • 11
1 vote
1 answer
62 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 ...
ivan866's user avatar
  • 111
1 vote
0 answers
48 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 ...
Joe's user avatar
  • 51
2 votes
1 answer
59 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 ...
Joe's user avatar
  • 51
0 votes
2 answers
66 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 ...
Joe's user avatar
  • 51
1 vote
0 answers
84 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?
Mordorer's user avatar
0 votes
1 answer
63 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 ...
Aidre Cabrera's user avatar
2 votes
3 answers
97 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 ...
b0red's user avatar
  • 45
2 votes
2 answers
331 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) ...
Manar's user avatar
  • 133
1 vote
2 answers
380 views

Product of polynomial with negligible function is negligible

I want to prove that for every positive polynomial $p(n)$ and any negligible function $negl(n)$ the product $negl(n)p(n)$ is also negligible. This is what I tried so far: $\forall n>n_0:negl(n)<...
UniX's user avatar
  • 13
0 votes
1 answer
38 views

Examples of cryptographic methods using outside randomness

Most cryptographic protocols like pseudorandom number generators run only on "internal" information: that is you set a seed and the next state is a function of its previous state etc.. I am ...
user918212's user avatar
3 votes
1 answer
113 views

Is it possible to write a program that is able to recognize some source-code as being its own source code?

Is it possible to write a program that is able to recognize some source code as being its own source-code? Biological organisms evolved the ability of kin-recognition, and later, self-recognition, ...
scaly's user avatar
  • 131
3 votes
1 answer
209 views

Is the differential privacy definition with lower and upper bound equivalent to the definition with just an upper bound?

According to Wikipedia, given a randomized algorithm $\mathcal{A}$, two neighboring datasets $D_1, D_2$, a real number $\epsilon > 0$, $\mathcal{A}$ provides $\epsilon$-differential privacy, if $$ \...
user3389669's user avatar
-1 votes
1 answer
61 views

Not CPA secure for CBC mode if some code are changed that is if we replaced a function $\pi(k,x)=k\oplus x$

Consider the CBC mode where the block cipher is replaced by a function $\pi$ where $\pi(k,x)=k\oplus x$. Show that the mode is not CPA secure. I am not got how to proceed to solve this question. ...
ram kumar's user avatar
1 vote
2 answers
369 views

What algorithm is prefered to do a x b mod P with big numbers (256 bits)

I'm trying to implement multiple precision arithmetic operations modulo P, with P < 2^256. More specifically, ...
Ervadac's user avatar
  • 113
6 votes
1 answer
1k views

How are extremely large integers stored and implemented in programming languages?

We have data types like int and long etc. which can store just a few bytes of integers. But when we are implementing ...
Yuv's user avatar
  • 139
2 votes
1 answer
67 views

Factor $n$ in RSA if we know $Ο†(n)$

If we know that $n = 1363$ and $Ο†(n) = 1288$, how can we factor $n$?
mariohez's user avatar
1 vote
1 answer
30 views

Is it possible to have a zero knowledge proof with a P Prover?

In the literature, when reading about zero knowledge proofs, the prover (prover/verifier) is always given an unlimited computational power or just capacity to solve NP. Is it necessary for the prover ...
Rafael's user avatar
  • 21
0 votes
1 answer
135 views

Zero knowledge proof - case of graph 3-coloring (not understanding the concept)

In zero knowledge, in the context of graph 3-coloring, I do not understand how the prover is actually showing that he solved the problem. The context: both know the graph (the prover and the verifier)...
Rafael's user avatar
  • 21
5 votes
1 answer
341 views

How to prove that existence of one-way functions implies P≠NP?

Wikipedia: The existence of such one-way functions... would prove that the complexity classes P and NP are not equal. How is this proved?
porton's user avatar
  • 493
9 votes
4 answers
2k views

Why do public key systems involve private keys?

I read up the definition of a public key cryptosystem. It mentions there is a public key and a private key. That's confusing. Why is it called a "public key" system if it involves a private ...
rohit sharma's user avatar
0 votes
2 answers
1k views

What are the advantages of using PRNG over TRNG?

True random number generators use an unpredictable physical means to generate numbers, whereas pseudo-random numbers utilize mathematical formulas to produce a certain sequence of numbers that will ...
Monther's user avatar
  • 118
2 votes
1 answer
84 views

How 'Avalanche Effect' got its name?

I wonder how or why Avalanche Effect got its name. Avalanche Effect is a desirable property of cryptographic algorithms, wherein if an input is changed slightly (...
Midhunraj R Pillai's user avatar
1 vote
1 answer
74 views

NSA Recommended Cryptography Algorithms changes from a single paper

I know that the NSA has recommended cryptography algorithms, such as their A/B suite algorithms and their Commercial National Security Algorithms Suite. I also know that they change their ...
Milo Moses's user avatar
0 votes
1 answer
233 views

Hardcore bit of a one way function

Let $b:\{0,1\}^*\mapsto \{0,1\}$, be a hardcore bit of a one way function $f$. I want to show that $\vert Pr_{x\in U_n}[b(x)=1]-Pr_{x\in U_n}[b(x)=0]\vert=n^{-\omega(1)}$. Intuitively, it looks ...
roydiptajit's user avatar
0 votes
1 answer
76 views

Show that if the discrete log problem is $(T,1-\epsilon)$-hard, then it's $(O(\frac{T}{\frac{1}{\epsilon}log\frac{1}{\epsilon}}-nlogm),\epsilon)$-hard

Show that if the discrete log problem is $(T,1-\epsilon)$-hard, then it's $(O(\frac{T}{\frac{1}{\epsilon}log\frac{1}{\epsilon}}-nlogm),\epsilon)$-hard Let $G$ be a cyclic group of size $m$, and let $g ...
Gabi G's user avatar
  • 325
1 vote
1 answer
42 views

Strengthening a given attack on discrete log

I am trying to prove the following claim: Let $(G,*)$ be a cyclic group of size $m$ with generator $g$. Assume there exists some adversary $A'$ of size $T'=\frac{\left(T-O\left(\log m\right)\right)}{...
Ido's user avatar
  • 163
1 vote
1 answer
353 views

Time estimation for successful brute force attack

If I have a password = "passwordPASSWORD" and the time it takes to encrypt the password successfully is: 353259.545 nano seconds is there a formula that can work out the time taken to ...
Jim's user avatar
  • 39

1
2 3 4 5 6