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
0 answers
34 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
0 votes
0 answers
74 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
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 ...
Victor Espinoza's user avatar
1 vote
0 answers
155 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
1 answer
85 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 ...
Lev's user avatar
  • 433
0 votes
0 answers
14 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
1 vote
1 answer
86 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-...
Gregory Khvatsky's user avatar
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 ...
wxist's user avatar
  • 143
1 vote
1 answer
91 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 ...
Towdo's user avatar
  • 11
1 vote
2 answers
183 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 ...
cryptolearner's user avatar
1 vote
1 answer
406 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, ...
honzaik's user avatar
  • 392
3 votes
2 answers
174 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 ...
pintor's user avatar
  • 558
1 vote
1 answer
104 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 ...
killertoge's user avatar
1 vote
0 answers
136 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
1 answer
82 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),...
John Pham's user avatar
1 vote
0 answers
145 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
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 ...
mercury0114's user avatar
2 votes
0 answers
83 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
1 answer
456 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}...
AYun's user avatar
  • 841
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
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
37 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
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$ ...
Mathemagician's user avatar
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 ...
zxcv's user avatar
  • 155
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 ...
Awerde's user avatar
  • 123
2 votes
1 answer
109 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 ...
Napoleon's user avatar
  • 113
2 votes
2 answers
297 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 ...
driewguy's user avatar
3 votes
0 answers
194 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
1 vote
1 answer
175 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 ...
Foobar's user avatar
  • 247
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, ...
Foobar's user avatar
  • 247
2 votes
1 answer
173 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 ...
Novice_researcher's user avatar
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 ...
Kamaroyl's user avatar
2 votes
0 answers
562 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
0 votes
1 answer
216 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]$ $...
Titanlord's user avatar
  • 2,244
1 vote
0 answers
132 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
4 votes
1 answer
127 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\...
BlackHat18's user avatar
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 ...
Distinguishable Llama's user avatar
0 votes
0 answers
63 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
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$ ...
Sean's user avatar
  • 99
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 ...
BlackHat18's user avatar
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
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
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
0 votes
1 answer
235 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 ...
Rafael'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
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