2022 Developer Survey is open! Take survey.

# Questions tagged [indistinguishability]

The tag has no usage guidance.

30 questions
Filter by
Sorted by
Tagged with
48 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 ...
• 113
25 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 ...
• 31
1 vote
22 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
62 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 ...
• 145
1 vote
69 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 ...
• 123
65 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 ...
• 113
96 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 ...
• 63
71 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
58 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 ...
• 247
1 vote
118 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, ...
• 247
1 vote
43 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 ...
56 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 ...
• 53
258 views

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 ...
• 121
75 views

• 285
146 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 ...
52 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 ...
• 113
67 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$ ...
• 113
46 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 ...
• 285
1 vote
35 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 ...
47 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
16 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| ...
• 21
1 vote
29 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 ...
• 21
85 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 ...
• 21
1 vote
30 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 ...
• 21
30 views

• 121