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.
59
questions
0
votes
1
answer
45
views
Indistinguishability of $(G_0(x), G_1(x))$ from $(G_0(x), t)$ where $G(x) = G_0(x) \| G_1(x)$ is a PRG
Suppose, $G:\{0,1\}^{\lambda} \rightarrow \{0,1\}^{2\lambda}$ is a length doubling pseudorandom generator (PRG). Such a PRG is used to build PRF $F: \{0,1\}^{\lambda} \rightarrow \{0,1\}^{\lambda}$ ...
- 729
1
vote
1
answer
70
views
Is there any notion of key-recovery attacks security (perhaphs using games) that is equivalent to IND-CPA?
I am talking about Symmetric Cryptography only in the following.
We know that Semantic Security (in the presence of eavesdropper) implies security against message recovery (in the presence of ...
3
votes
1
answer
137
views
Hybrid argument for repeated but alternating sequence
In the usual hybrid argument, it is shown that if two efficiently samplable distributions, $X$ and $Y$, are indistinguishable given a single sample, then they remain indistinguishable with any ...
- 87
1
vote
1
answer
82
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 ...
3
votes
1
answer
114
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 ...
- 87
0
votes
0
answers
62
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
48
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 ...
- 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 ...
0
votes
0
answers
82
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 ...
- 99
0
votes
0
answers
56
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}(...
- 361
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 ...
- 171
1
vote
0
answers
162
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
170
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 ...
- 468
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
95
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-...
