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
0 votes
1 answer
15 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 ...
user avatar
1 vote
0 answers
64 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$ ...
user avatar
  • 219
1 vote
0 answers
19 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 ...
user avatar
  • 11
1 vote
1 answer
54 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 ...
user avatar
  • 111
1 vote
0 answers
36 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 ...
user avatar
  • 51
2 votes
1 answer
51 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 ...
user avatar
  • 51
0 votes
2 answers
38 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 ...
user avatar
  • 51
1 vote
0 answers
27 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?
user avatar
0 votes
1 answer
38 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 ...
user avatar
2 votes
3 answers
62 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 ...
user avatar
  • 35
2 votes
2 answers
98 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) ...
user avatar
  • 133
1 vote
2 answers
41 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)<...
user avatar
  • 13
0 votes
1 answer
37 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 ...
user avatar
3 votes
1 answer
105 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, ...
user avatar
  • 131
3 votes
1 answer
174 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 $$ \...
user avatar
-1 votes
1 answer
34 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. ...
user avatar
0 votes
2 answers
116 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, ...
user avatar
  • 103
6 votes
1 answer
922 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 ...
user avatar
1 vote
1 answer
35 views

Factor $n$ in RSA if we know $φ(n)$

If we know that $n = 1363$ and $φ(n) = 1288$, how can we factor $n$?
user avatar
1 vote
1 answer
26 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 ...
user avatar
  • 21
0 votes
1 answer
37 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)...
user avatar
  • 21
4 votes
1 answer
117 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?
user avatar
  • 413
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 ...
user avatar
0 votes
1 answer
380 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 ...
user avatar
  • 120
1 vote
1 answer
54 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 (...
user avatar
1 vote
1 answer
46 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 ...
user avatar
0 votes
1 answer
101 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 ...
user avatar
0 votes
1 answer
52 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 ...
user avatar
  • 293
1 vote
1 answer
36 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)}{...
user avatar
  • 163
1 vote
1 answer
180 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 ...
user avatar
  • 39
1 vote
1 answer
46 views

Check if a linear function or an affine function can be a pseudo random function

Let $G = \{0, \cdots , p-1 \}$ be a field. Let $K = G^{m \times n}$ and $F:K \times G^n \to G^m$ be a family of functions. For $A \in G^{m \times n}$ and $x \in G^n$ we have $F(A,x) = Ax$. I need to ...
user avatar
  • 293
1 vote
1 answer
37 views

If there is an algorithm $A$ that guesses the entire message, given an encryption, with probability of $0.2$, then it's not $(O(A) +O(n), 0.1)$-secure

Let $(E,D)$ be a cipher with message space $M = \{0,1\}^n$ and key space $K = \{0,1\}^n$. Assume that there is an algorithm $A\colon \{0,1\}^n \to \{0,1\}^n$ of size $T$ that given an encryption of a ...
user avatar
  • 293
1 vote
1 answer
93 views

Connection between Pseudo random generators and hardness

For a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$ $H_{avg}(f)$ is defined as the largest $S(n)$ s.t. for all circuit $C_n$ of size $S(n)$, $\Pr_{x\in U_n}[C_n(x)=f(x)]<1/2+1/S(n)$. Here $...
user avatar
0 votes
1 answer
74 views

Cryptosystems whose hardness depends on solving the halting problem?

There has been a lot of work on building cryptosystems whose general security guarantees are attached to famous complexity classes. This post Gives a list of some famous cryptosystems whose underlying ...
user avatar
2 votes
0 answers
48 views

Permutation with stable partitions

I am searching a fast pseudo-random permutation function with the following requirements. Given a predefined set of values $V$ and an integer $k$. Split $V$ to $k$ subset, and iterate over any subset ...
user avatar
1 vote
0 answers
72 views

Non-Interactive Zero Knowledge Proofs: zk-snarks and zk-stark

I read up on an abstract example of ZKPs (the cave and the door), but I'm trying to understand NIZKs (specifically zk-snarks and zk-stark). All the examples I can find online seem to have some ...
user avatar
2 votes
1 answer
92 views

Is there any neutral element for the cryptographic hash function SHA256? (or its variants)

My question is the following: Is it possible to compute a string given that after applying a SHA256 function the result is the same string? Edit for clarification: If my string A is a neutral element ...
user avatar
0 votes
0 answers
96 views

Books for learning Cryptocurrency

Please suggest a good for mathematical section of studying cryptocurrency.
user avatar
-2 votes
1 answer
101 views

Manually Performing ECB & CBC

I am learning about block ciphers and while I understand the concept of Electronic Codeblock mode and cipher block chaining, I could not find any relevant practical examples online. Can someone ...
user avatar
  • 167
0 votes
3 answers
119 views

Undetectable error correcting codes

I have a 256 bit string (indistinguishable from random) which I wish to encode into a greater length string using an error correction code. The result must also be indistinguishable from random. It ...
user avatar
0 votes
0 answers
40 views

Asking for your help with LFSR, linear automaton

I am a software developer new to the site. I am currently learning about LFSR (linear feedback shift register). Every day I solve a question which is given to me, but today I am lost. I can not solve ...
user avatar
1 vote
1 answer
54 views

One-way function is not injective when it is in NP

Let us $\Sigma = \{0,1\}$ and $f: \Sigma^* \rightarrow \Sigma^* \in FP$ for which is valid that $\exists k: \forall x \in \Sigma^* : \lvert x \rvert ^ {1/k} \leq \lvert f(x) \rvert \leq \lvert x \...
user avatar
1 vote
0 answers
36 views

Accessible CS Math Job [closed]

I am a CS undergrad and a huge enthusiast of pure math. I have been doing competitive programming and proofs for a while. My ambition is to become an academic in theoretical computer science. The ...
user avatar
1 vote
2 answers
131 views

Decryption of RSA

How can we decrypt an RSA message if we only have the public key? For example, Message: 21556870,12228498 Public Key: ...
user avatar
  • 167
0 votes
1 answer
122 views

How to perform matrix multiplication in Mixing Columns step of AES?

I am studying AES and trying to implement it. But I am having difficulty understanding the Mixing Column step. In that step we have to perform matrix multiplication between the state matrix and ...
user avatar
1 vote
0 answers
25 views

Converting Smart Contracts into Arithmetic Circuits [closed]

Are there any existing programs available to convert smart contracts into Arithmetic Circuits with which I can implement and experiment with Secure Multiparty Computation (MPC) protocols?
user avatar
1 vote
0 answers
83 views

Absolute limit in Huffman encoding

I have computed the average code length using the Huffman encoding. Now, I am asked to compare the average code length with Absolute limit but I ain't sure about the absolute limit here is :( Could ...
user avatar
  • 11
0 votes
0 answers
30 views

Extracting text from a hidden image

Say i have cropped an image and have hidden some part of it, like shown below Is it possible for anyone to download this image and able to decipher what the hidden text is?
user avatar
  • 1,162
0 votes
0 answers
26 views

Abusing ElGamal in order to attack a known encrypted text

I saw a very interesting question regarding Elgamal cryptosystem that I don't know its answer. It is really interesting and I would be very happy if you could elaborate on it and explain the tricky ...
user avatar
1 vote
0 answers
28 views

equivalent sub-keys in DES encryption

i am trying to understand the DES cryptosystem and was wondering: what would've happened if all of the sub-keys were equal? does it reduce the security? can we actually find the keys if we know all ...
user avatar

1
2 3 4 5