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
2
votes
1answer
42 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, ...
3
votes
1answer
168 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 $$ \...
-1
votes
1answer
18 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. ...
0
votes
2answers
71 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, ...
6
votes
1answer
890 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 ...
1
vote
1answer
28 views

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

If we know that $n = 1363$ and $φ(n) = 1288$, how can we factor $n$?
1
vote
1answer
19 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 ...
0
votes
1answer
24 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)...
4
votes
1answer
71 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?
10
votes
3answers
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 ...
0
votes
1answer
146 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 ...
1
vote
1answer
50 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 (...
1
vote
1answer
37 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 ...
-1
votes
1answer
75 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 ...
0
votes
1answer
36 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 ...
1
vote
1answer
32 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)}{...
1
vote
1answer
76 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 ...
1
vote
1answer
33 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 ...
1
vote
1answer
33 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 ...
1
vote
1answer
82 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 $...
0
votes
1answer
49 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 ...
2
votes
0answers
45 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 ...
1
vote
0answers
46 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 ...
1
vote
1answer
73 views

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

My question is Is is possible to compute a string given that after applying a SHA256 function the result is the same string?
0
votes
0answers
56 views

Books for learning Cryptocurrency

Please suggest a good for mathematical section of studying cryptocurrency.
-2
votes
1answer
72 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 ...
0
votes
3answers
108 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 ...
0
votes
0answers
39 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 ...
1
vote
1answer
33 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 \...
1
vote
0answers
34 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 ...
1
vote
2answers
93 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: ...
0
votes
1answer
59 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 ...
1
vote
0answers
18 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?
1
vote
0answers
76 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 ...
0
votes
0answers
22 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?
0
votes
0answers
23 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 ...
1
vote
0answers
20 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 ...
2
votes
1answer
96 views

Period of sum of two periodic sequences

I was wondering, what is to be the shortest possible key using Vigenere encryption, if a text is ciphered one time with a key of length $i$ using Vigenere and second time with a key of length $j$ ...
2
votes
1answer
105 views

Determining key from plaintext and ciphertext (Vigenère)

I was wondering why mathematically we can know the key in the Vigenère cipher if we know in advance a message and its encryption.
0
votes
0answers
42 views

Is 'the bombe' technically a computer?what is technically meant to be a computer?

Some say that 'the bombe' created by Alan Turing is technically not a computer despite decrypting the codes. Why is it so? Is 'the bombe' technically a computer? First of all what is technically ...
3
votes
1answer
27 views

Solve SUBSET SUM for Reciprocals of Primes

Let $p_1, ..., p_n$ distinct prime numbers with $P = \prod_{i=1}^{n}{p_i}$ and $A=(a_1, ..., a_n)$ with $a_i = P/p_i$. Problem Show the SUBSET SUM problem $(A, \alpha)$ can be solved in polynomial (...
2
votes
2answers
455 views

If current time in milliseconds is considered good enough random seed for a pseudorandom number generator, why not just use that time directly?

I was reading about pseudorandom number generators and how they need a seed and how that seed is usually current system time in milliseconds. One of the most common algorithms is the linear ...
0
votes
1answer
27 views

Cryptography: Play Fair cipher

In our university, we were taught that since all 26 letters cant be placed together in a $5*5$ square matrix we must put $i/j$ together like this represented in the below diagram. Here our key is $...
0
votes
1answer
60 views

Diffie-Hellman and its disadvantage with large primes

I was reading our university slide on the Diffie-Hellman where it is mentioned that one of the disadvantages of D-H is that For large prime, $p-1$ is an even number so, $\mathbb{Z}^*_p$ will have a ...
0
votes
2answers
52 views

What are the elements of the modular ring mod 7? [closed]

Are the elements of a modular ring simply the set of all the numbers from 1 to p−1? in this case p−1 = 6 ? I asked this on the math stack exchange https://math.stackexchange.com/q/3375667 and was ...
1
vote
1answer
42 views

Weaknesses arising from using same key in both channel directions

I came across the following question: Which of the following risk may arise, when same key is used to encrypt both directions of a communication channel, that are not present if using different keys ...
5
votes
1answer
81 views

Perfect Probabilistic Encryption still requires key length about as long as message

Let $(E,D)$ be a probabilistic encryption scheme with $n$-length keys (given a key $k$, we denote the corresponding encryption function by $E_k$) and $n+10$-length messages. Then, show that there ...
1
vote
2answers
75 views

RSA cryptosystem: Encrypting a signed message

I've started to read the section about the RSA cryptosystem in CLRS (page 958) and I don't understand the way it describes how to encrypt a signed message. If Bob wants to send a message $M$ to Alice:...
1
vote
1answer
52 views

Underlying codes for Niederreiter cryptosystems

Niederreiter cryptosystem is usually described by a parity check matrix $H$ over $\mathbb{F}_{2^n}$. The minimum distance $d$ is given by $d := min\lbrace k \text{ such that there are $k$ linearly ...
1
vote
0answers
71 views

A tree-like data structure with rights delegation for distributed computing

Every actor can create a root node and delegate a right to add a child node. Every node contains name of its’ creator or who added it, and value S. Sum of all values S at the same level of the tree ...

1
2 3 4 5