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.

27 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4 votes
1 answer
179 views

How to explain indistinguishability obfuscation (iO) to my grandmother?

At the risk of oversimplification, how do I explain indistinguishability obfuscation (iO) to my grandmother?
Nathan Aw's user avatar
  • 2,277
3 votes
0 answers
197 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 ...
trivicious's user avatar
2 votes
0 answers
86 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 ...
Newbie's user avatar
  • 21
2 votes
0 answers
563 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 ...
apapapa's user avatar
  • 121
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 ...
Erfan Hosseini's user avatar
1 vote
0 answers
37 views

Are semantic security and indistinguishability equivalent for symmetric key cryptosystems?

I've seen a lot written about how, in the context of public key cryptosystems, these definitions are equivalent. Is the same true of symmetric key cryptosystems? If so, what are the precise statements ...
joshlf's user avatar
  • 267
1 vote
0 answers
155 views

How to achieve $d-$privacy considering some secrets?

We have a set of secrets $S = \{x_1, x_2, \dots, x_n\}$ known to an adversary. Each $x_i \in S$ belongs to user $u_i$ who needs to obfuscate his secret using the notion of $d-$privacy defined in the ...
Amirhossein Adavoudi's user avatar
1 vote
0 answers
158 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 \...
Steven's user avatar
  • 11
1 vote
0 answers
142 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 & ...
John Pham's user avatar
1 vote
0 answers
150 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 ...
Lee Seungwoo's user avatar
1 vote
0 answers
38 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 ...
Newbie's user avatar
  • 11
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 ...
Anon's user avatar
  • 403
1 vote
0 answers
35 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$ ...
Mathemagician's user avatar
1 vote
0 answers
134 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 (...
IngIng's user avatar
  • 11
1 vote
0 answers
56 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 ...
Erfan Hosseini's user avatar
1 vote
0 answers
20 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| ...
akjsdhas's user avatar
1 vote
0 answers
93 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 ...
jaykopp's user avatar
  • 21
1 vote
0 answers
41 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 ...
akjsdhas's user avatar
0 votes
0 answers
58 views

Is it possible to prove this function is computationally intistinguishable from PRF?

Background I have constructed a function $F':X × K → Y$, which has a characteristic that the quantity of $x\in X$ mapping to a single $y\in Y$ follows a binomial distribution $B(\frac{1}{2}, 2\frac{|X|...
queen killer's user avatar
0 votes
0 answers
76 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 ...
Doron's user avatar
  • 99
0 votes
0 answers
51 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}(...
js wang's user avatar
  • 327
0 votes
0 answers
15 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 ...
Sumana bagchi's user avatar
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 ...
donaastor's user avatar
  • 125
0 votes
0 answers
38 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 ...
mike's user avatar
  • 41
0 votes
0 answers
64 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 ...
Sean's user avatar
  • 99
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 $...
costola's user avatar
0 votes
0 answers
247 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 ...
Manish Adhikari's user avatar