Questions tagged [indistinguishability]
Ciphertext indistinguishability is property of randomised encryption schemes where it is computationally infeasible to tell if two ciphertexts are encryptions of the same plaintext.
51
questions
0
votes
0
answers
67
views
Distinguishing between two DDH-like tuples
Given a group generator $g$ (in a group where DDH is hard). Let $X_1=g^{x_1}$ and $X_2=g^{x_2}$ be two public elements, where $x_1$ and $x_2$ are selected randomly and kept secret.
Consider a game ...
- 79
0
votes
0
answers
32
views
Is BGV encryption using different secret keys indistinguishable?
Assume that the same message is encrypted using two different keys within the BGV encryption scheme. Can we assume that the resulting ciphertext are indistinguishable?
I.e., given $c_1 = \text{Enc}(...
- 327
14
votes
5
answers
9k
views
Does Grover's algorithm really threaten symmetric security proofs?
By Shannon's theorem of perfect security, if I give you a ciphertext 'LOUPL', you can do a brute-force attack and then you would find plaintexts like 'HELLO', 'APPLE', 'SPOON', but you can't ...
- 171
1
vote
0
answers
141
views
If G is a PRG, is G' necessarily a PRG?
Given:
A function $$G: \{0,1\}^{3n} \to \{0,1\}^{6n}$$ which is known to be a secure Pseudorandom Generator (PRG).
A derived function $$G'(x_1 \| x_2) = G_b(x_1\|0^n\|x_2), \text{ where } x_1, x_2 \...
- 11
1
vote
1
answer
59
views
Unbounded distinguishers and statistical indistinguishability
In constructing a SHVZK simulator for a sigma protocol I am working on I have encountered some fairly basic questions, but ones which are not often discussed in textbooks and papers - consider the two ...
- 413
0
votes
0
answers
12
views
Partition/Range wise privacy
Consider two data streams $a_1,\cdots, a_n \in [a_{min}, a_{max}]$ and $b_1,\cdots, b_n \in [b_{min}, b_{max}]$, Such that $[a_{min}, a_{max}]$ and $[b_{min}, b_{max}]$ do not overlap.
A Differential ...
1
vote
1
answer
81
views
Are RSA-KEM key exchange material cyphertexts indistinguishable from random noise?
First of all, I know that I should not be using RSA in 2023, and that I'm better off with Elligator2 + ECIES for a variety of reasons.
However, I am thinking about whether RSA-KEM can be used for PURB-...
2
votes
0
answers
53
views
NIST statistical tests [duplicate]
I'm having trouble testing a not-so-popular algorithm that I haven't found an implementation of, so I wrote it myself and now I'd like to test it with nist tests, but I have a suspicion that I'm doing ...
- 143
1
vote
1
answer
81
views
Is AES distinguishable if the attacker has an decryption oracle?
Let the following game be given:
G^IND-CCA':
Prepare a key k <- KeyGen(1^Kappa)
Choose a hidden bit h <- {0, 1} uniformly random
Prepare a decryption oracle O_Dec. Given a cipher text c, it ...
- 11
1
vote
2
answers
156
views
Showing that CPA encryption schemes cannot preserve the length of a message
I am self studying "A Graduate Course in Applied Cryptography" by Boneh-Shoup. I am stuck on the following problem.
Let $\mathcal{E}$ be be an encryption scheme where messages and ...
1
vote
1
answer
288
views
KEM security definition - IND-CCA vs IND-CCA2
When researching about PQ KEM's I have come across two different definitions of indistinguishability under (adaptive) chosen ciphertext attack. IND-CCA (https://eprint.iacr.org/2017/604.pdf page 10, ...
- 382
3
votes
2
answers
155
views
Privacy intuition vs formal definition
Suppose we define privacy as a game where a machine $M$ has a coin $b$, and on input $M_0, M_1$ always replies with encrypted $M_0$ if $b=0$ and encrypted $M_1$ if $b=1$. The adversary can send as ...
- 548
1
vote
1
answer
84
views
Definition of Polynomial-Time Indistinguishability
We call two ensembles $X$ and $Y$ indistinguishable in polynomial time if for every probabilistic polynomial-time algorithm $D$ and for every positive polynomial $p(\cdot)$, and all sufficiently large ...
- 299
1
vote
0
answers
95
views
Essential requirement for IND-CCA1 and IND-CCA2
I am learning about the concept of two security notions called IND-, which include IND-CPA, IND-CCA1 and IND-CCA2. While I got some grasp understanding about the scenarios between the challenger & ...
- 85
1
vote
1
answer
62
views
Security Goal Indistinguishability
I am currently reading a book called Serious Cryptography written by Aumasson to learn about Security. There was a paragraph talking about the security goal named indistinguishability (attached below),...
- 85
1
vote
0
answers
107
views
Are real-or-random model and LR-model are equivalent?
Are real-or-random(rr) model and LR-model are equivalent?
In the definition of ciphertext indistinguishability, LR-model is used. However I think rr model and LR model are somewhat equivalent.
Here is ...
- 363
1
vote
0
answers
37
views
Can the proof only be the stateful?
Let SE be stateful encryption.
Then, it is well known that the oracle for the security proof becomes stateful too. (We only consider the IND-CPA security game.)
On the other hand, assume that E is ...
- 11
0
votes
1
answer
59
views
Can the indistinguishability obfuscator leak the password when obfuscating the password checking function?
Suppose I have a dumb password checking function:
def dumb_checker(password):
return password == "my_secret_key_that_should_not_be_revealed"
One can ...
- 257
2
votes
0
answers
75
views
Noise flooding with Renyi divergence
According to this question, I found papers that deal with noise flooding with Renyi divergence. However, the answer is still unclear to me on how to use Renyi divergence on the noise flooding ...
- 21
2
votes
1
answer
332
views
About the definition of distinguishing advantage and computational indistinguishability
Given a polynomial-time adversary $A$ with binary output, the distinguishing advantage of $A$ with respect two games $G, H$ is defined as
$$
\newcommand{\adv}{\mathbf{Adv}}
\newcommand{\pr}{\mathbf{Pr}...
- 821
1
vote
0
answers
87
views
Is the following statistically close to uniform? (and how does one prove such claims in general)
For every $a \in \{0,1\}^n$ define:
$$h_a : \{0,1\}^n\to \{0,1\}$$
$$ h_a(b)=\langle a,b \rangle$$
So $\{h_a\}_{a \in \{0,1\}^n}$ is known to be a universal hash function family.
This means that if we ...
- 383
0
votes
0
answers
67
views
Is there a public-key, "deal-less", all-or-nothing, "secret-length message" cryptosystem or some easy way to derive it?
I want to make an ecryption algorithm that is secure in, well, really many ways, which is hard I see, so I came up with some ideas of how to implement it using some primitives that I know and I ...
- 125
0
votes
0
answers
36
views
Secuirty definion of a ad hoc multi-input functional encryption scheme
I have to write an essay on the paper ad hoc multi-input functional encryption, and can't understand the security definition. In a nutshell it is a primitive that allow sources to supply encrypted ...
- 41
1
vote
0
answers
34
views
Computability of the messages of the Adversary for Semantic Security
Semantic Security may be defined using the distinguishability experiment/game, which we recall as follows:
Let $(E,D)$ be an encryption scheme. After the challenger chooses a security parameter $n$ ...
- 111
1
vote
1
answer
100
views
"randomized" indistinguishability vs "deterministic" indistinguishability
Let $X$ be a measurable space. For each $n\in\mathbb N$, let $P_n$ and $Q_n$ be probabilities on $X$. We say that $(P_n)_{n\in\mathbb N}$ and $(Q_n)_{n\in\mathbb N}$ are statistically ...
- 145
1
vote
1
answer
106
views
Adversarial Indistinguishability with more messages
Suppose that we play the game from Adversarial Indistinguishability but adversarial can choose three messages $m_0, m_1, m_2$. Of course, $Pr[M=m_i]=1/3$ for $i=0,1,2$. I suppose that to have ...
- 123
2
votes
1
answer
102
views
How small is the negligible advantage for DDH?
The well known Decisional Diffie Hellman assumption (DDH) assert that for any $n = \log q$ and generator $g$ of $\mathbb{Z}_q$, for uniformly i.i.d $A, B, C \sim U(\mathbb{Z}_q)$, the following are ...
- 113
2
votes
2
answers
247
views
Ideal cipher vs Ideal encryption scheme
Ideal cipher is a random permutation for every key in its key space.
And, ideal encryption scheme is the one which has perfect secrecy/indistinguishability.
For an encryption scheme, random ...
- 63
3
votes
0
answers
175
views
Is it necessary for a round function $F$ in a Feistel cipher to be pseudorandom?
I stumbled across this question where the questioner asked for specific requirements for the round function $F$ in a Feistel network so that the construction is secure. The answer explained that a ...
- 31
1
vote
1
answer
147
views
Katz/Lindell - 2.10: Is exhaustive search over the key-space allowed in perfect indistinguishability?
I am self studying using "Introduction to Modern Cryptography (2nd edition)"
I am trying to understand how the solution to the following problem is valid:
Prove that a scheme satisfying ...
- 247
1
vote
2
answers
135
views
What does the syntax Pr[D = 1] mean?
I'm looking at this PDF to understand the hybrid argument: http://www.cs.columbia.edu/~tal/4261/F14/hybrid.pdf
The first few lines go as follows:
Suppose you have two oracles, or input distributions, ...
- 247
2
votes
1
answer
140
views
Indistinguishability versus Indifferentiability
What is the Indifferentiability of Feistel Network?
Why is the concept of Indifferentiability useful and how it is applicable in the real world?
How is Indifferentiability compared to ...
5
votes
1
answer
66
views
What is the definition of function index
I'm reading through Indistinguishability Obfuscation from Well-Founded Assumptions and in Definition 3.1 describing sPRG, it mentions "samples a function index I." Can someone explain what a ...
- 53
2
votes
0
answers
512
views
Should I normalize adversary's advantage in IND-XXX Game?
The Cryptography made simple (page 207, under Fig 11.12)(Nigel Smart) say that adversary's advantage of IND-PASS Game is $Adv1 = 2\times|Pr[b=b']-\frac{1}{2}|$.
The reason for multiplying by 2 is to ...
- 121
0
votes
1
answer
196
views
Multiple COA-security (IND-EAV-Mult security) cipher
Be this the Experiment for multiple COA-security:
$PrivK_{\mathcal{A},\Pi}^{mult}(n)$:
$(m_0^1 , ... , m_0^t,m_1^1 , ... , m_1^t) \leftarrow \mathcal{A}(1^n), |m_0^i|=|m_1^i| \forall i \in [1,t]$
$...
- 2,120
1
vote
0
answers
131
views
One time pad, Proof for a problem
We know 2 plaintexts of length L and 2 ciphertexts of length L(we don't know which one belongs which), assuming each given ciphertext is generated by encrypting one of the given plaintexts by XOR'ing (...
- 11
4
votes
1
answer
122
views
Distinguishers and next bit predictors without the uniform distribution
Consider a probability distribution $D$ over $n$ bit strings. Denote $U$ to be the uniform distribution over $n$ bit strings and $U_{n}$ to be the uniform distribution over integers $\{1, 2, \ldots, n\...
- 357
4
votes
1
answer
191
views
Are there different definitions of secure two-party computation?
While reading tutorials on two-party computation I encountered two (at least formally) different definitions of security (with semi-honest adversaries).
What I want to know is whether these ...
0
votes
0
answers
61
views
How Can Indistinguishability be Proven?
I'm curious on how computational indistinguishably is proved.
For instance, would the following be computational indistinguishable? If it is, how do we prove it?
Let $P_a$ be a probabilistic machine ...
- 99
0
votes
1
answer
82
views
Computational indistinguishability
Given a multiplicative group of order $q$ and modulus $p$. Given two constants $a$ and $b$ randomly sampled from $Z_q$. Let random variable $x_a$ be a pair $(x, x^a \mod p)$ and
random variable $x_b$ ...
- 99
3
votes
1
answer
66
views
Hybrid argument without efficient samplability
Let's say I have $k$ distributions, where $k$ is polynomially large, $D_1, D_2, \ldots, D_k$ such that each $D_i$ is computationally indistinguishable from the uniform distribution.
Is it true that ...
- 357
1
vote
0
answers
53
views
composition of RLWE distributions
Assume we have the polynomial space $R_q$ defined as $R_q = Z_q/(X^n + 1)$. Additionally, we define the error distribution $\chi$ as a discrete centred Gaussian bounded by $B$.
Let $s,t \in R_q$ be ...
2
votes
0
answers
50
views
RLWE like problem
Assume we have the polynomial space $R_q$ defined as $R_q = Z_q/(X^n + 1)$. Additionally, we define the error distribution $\chi$ as a discrete centred Gaussian bounded by $B$.
Let $s \gets R_q$ be a ...
1
vote
0
answers
19
views
What is the reduction between "random challenge" version of indistinguishability and the more "formal" version?
The main definition of computational indistinguishability is that, for any ppt $A$, and distribution ensembles $\{C_n\}, \{D_n\}$, $$\bigg| \Pr_{x\sim C_n}[A(x) = 1] - \Pr_{x\sim D_n}[A(x) = 1] \bigg| ...
- 21
1
vote
0
answers
59
views
Proving the security of the public key BGV scheme
The security proof basically comes down to the following based on this paper.
We want to show that two distributions are statistically indistinguishable.
Say we have that $a,a′,x,x′$ are drawn from an ...
- 21
0
votes
1
answer
209
views
Definition of soundness (a different approach) in "Witness Indistinguishable and Witness Hiding Protocols"
In any other context where I encountered the concept of soundness it was very simple: if the input does not belong to the language then the protocol fails or fails with great probability.
But in the ...
- 21
1
vote
0
answers
38
views
If the distinguishing advantage of A wrt distribution D_n, E_n is 1/poly(n) with probability .1, then are they not computationally indistinguishable?
As in the title, but to make more clear:
If, with probability 0.1, an algorithm A can distinguish between two ensembles D_n, E_n (indexed by sec. paramater n), then are D_n, E_n not computationally ...
- 21
0
votes
0
answers
30
views
Symmetric and Asymmetric indistinguishabilty experiment
In each of those experiments, we have a function $Gen(x)$ who generates the key or a pair of keys respectively for symmetric or asymmetric algorithms. $x = 1^n$ : I read on other questions that is a $...
- 1
0
votes
0
answers
224
views
Simple XOR cipher with pseudo random plain text of arbitrary length
We all know that simple repeated XOR cipher over plaintext is trivially vulnerable to known plaintext attack, even when just a part of plain text is known and even to ciphertext only attack if you ...
- 561
0
votes
1
answer
59
views
what's the reason of the notational difference between statistical and computational indistinguishabilities?
Statistical: $|\Pr[E_K(m_0)\in T]-\Pr[E_K(m_1)\in T]|\leq\epsilon$
Computational: $|\Pr[A(E_K(m_0))=1]-\Pr[A(E_K(m_1))=1]|\leq\epsilon(n)$
What is the $1$ doing there? Why isn't it $Pr[A(E_K(m_0))\in ...
- 121