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.

Filter by
Sorted by
Tagged with
1 vote
1 answer
66 views

Why is zero knowledge defined via simulation w.r.t. inputs *in* the language?

In every definition of zero-knowledge (ZK) proof systems that I have seen (see, e.g., this one on Wikipedia, or this primer by Goldreich), a proof system $\langle p, v \rangle$ for a language $L$ is ...
2 votes
1 answer
73 views

Hybrid argument for quantum states

The usual hybrid argument tells us that if two efficiently sampled ensembles are computationally indistinguishable based on a single sample, then, computational indistinguishability holds even for ...
0 votes
0 answers
59 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|...
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 ...
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 ...
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 ...
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}(...
14 votes
5 answers
10k 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 ...
1 vote
0 answers
159 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 \...
2 votes
1 answer
182 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 ...
1 vote
1 answer
99 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 ...
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 ...
1 vote
1 answer
88 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
55 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 ...
1 vote
2 answers
188 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
92 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 ...
1 vote
1 answer
455 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, ...
3 votes
2 answers
175 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 ...
1 vote
1 answer
108 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 ...
1 vote
1 answer
105 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 ...
1 vote
0 answers
144 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 & ...
1 vote
1 answer
88 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),...
1 vote
0 answers
151 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 ...
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 ...
0 votes
1 answer
60 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 ...
2 votes
1 answer
473 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}...
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 ...
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 ...
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 ...
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 ...
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$ ...
1 vote
1 answer
105 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 ...
2 votes
1 answer
111 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 ...
2 votes
2 answers
306 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 ...
3 votes
0 answers
198 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 ...
1 vote
1 answer
186 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 ...
1 vote
2 answers
136 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, ...
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 ...
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 ...
0 votes
1 answer
222 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]$ $...
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 (...
4 votes
1 answer
128 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\...
4 votes
1 answer
200 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
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 ...
0 votes
1 answer
87 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
71 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 ...
0 votes
1 answer
253 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
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 ...
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
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| ...