# 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
Filter by
Sorted by
Tagged with
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 ...
32 views

1 vote
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 (...
122 views

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\... 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 ... 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$... 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 ... 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| ... 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 ... 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 ... 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 ... 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$...
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 ...