Questions tagged [perfect-secrecy]

Confidentiality in a very strong sense. Ciphers reaching perfect-secrecy can't be broken to disclose informations over the plaintext from the ciphertext, even with unlimited computing power. The most known example cipher reaching perfect screcy is the one-time-pad.

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

How can I distribute a set of anonymous tokens digitally among a known limited population to do anonymous voting?

TL:DR How can I give a population of N people the chance to randomly pick one token each person guaranteeing those: Nobody knows noone else's token. Noone can pick more than one token. Every person ...
user avatar
3 votes
1 answer
73 views

Information Theoretic Security for Public Key Encryption

Do there exist information theoretic secure public key crypto-systems? Are they useful in any way, or are they just mathematical curiosities?
user avatar
0 votes
0 answers
27 views

Difference of unconditional and perfect security in terms of IND-Game

Both unconditional and perfect security were very clear to me, until I bumped upon different sources that confused me. For example : 1 2 3. Also in 3 the DH76 paper is referenced and it doesn't ...
user avatar
  • 635
1 vote
1 answer
56 views

What is the Work Factor of the one time pad?

Work Factor is defined as the minimum amount of work (can be the length of the key) to determine the secret key of an cryptosystem (HAC, Menezes, Alfred J. et al). And One time pad have unconditional ...
user avatar
  • 143
0 votes
0 answers
37 views

How to securely implement a deadpool in a PoW blockchain?

Imagine you have a blockchain where the Proof of Work scheme is integer factorization. There is an opcode that takes two integers $N,M$ where it returns true if $M\not\in \{0,1,N\}$ and $N \mod M \...
user avatar
  • 21
2 votes
1 answer
62 views

Proving two definitions of perfect security are equivalent

I'm trying to prove that the following two definitions are equivalent: $\forall m\in M $ and $c\in C$ $\Pr[C=c \mid M=m]=\Pr[C=c]$ $\forall m_1,m_2 \in M $, $E_k(m_1)=E_k(m_2)$, where $E_k(m_i)$ ...
user avatar
  • 191
0 votes
0 answers
59 views

Perfect security - is this definition correct?

I have this definition: each ciphertext is equally probable for a given plaintext and key chosen at random I know that perfect security can be defined as $$\forall c \in \mathcal{C} \ \forall m_1,...
user avatar
  • 123
2 votes
2 answers
105 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 ...
user avatar
0 votes
0 answers
46 views

difference between unconditionally sure, perfect confidentiality, and semantically sure, adversary-wise and advatnage-wise?

can anyone please tell me the difference between unconditionally secure, perfect confidentiality and semantically secure? I know that for perfect confidentiality, we have an adversary A that has an ...
user avatar
  • 1
1 vote
1 answer
63 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 ...
user avatar
  • 247
2 votes
1 answer
102 views

Katz/Lindell 2.4 - Generalizing from 2 messages to any message space?

I'm trying to solve problem 2.4 in "Introduction to Modern Cryptography" (2nd edition) for self-study. The problem asks to prove that perfect secrecy $$ Pr[M = m | C = c] = Pr[M = m] $$ ...
user avatar
  • 247
0 votes
1 answer
168 views

Perfect Secrecy for Shift Cipher

I've read the definition of perfect secrecy as the following: A cryptosystem has perfect secrecy if $\Pr(x | y) = \Pr(x)$, for all $x \in P$ and $y \in C$, where $P,C$ are respectively the set of ...
user avatar
0 votes
1 answer
167 views

Why are stream ciphers computationally secure?

In case multiple stream ciphers exist, I'm refering to this specific instance in which you generate a key that is just as long as the msg, M, as a function of a nonce and a smaller key K. My textbook ...
user avatar
0 votes
0 answers
22 views

Secure protocols by implementing cheap talk instead on a centralized mediator to compute any function $f(s_1,...,s_n) = (y_1,...,y_n)$?

Based on this paper a protocol is secure if and only if it satisfies secrecy and resiliency. Most of the papers in ecnomic and computer since deal with the following problem. They consider the case ...
user avatar
1 vote
1 answer
59 views

Secret sharing is based in random variables that are uniformly distributed?

In Rabin and Ben-Or, their basic assumption is that each participant can broadcast a message to all other participants and that each pair of participants can communicate secretly. Hence, they design a ...
user avatar
2 votes
0 answers
32 views

Equivalent conditions for perfect secrecy of a symmetric crypto system

I've been reading about perfect secrecy in crypto systems and I've ran across two definitions which turn out to be equivalent. The first is Shannon secrecy: A crypto system $(\cal K, \cal M$, $\text{...
user avatar
  • 121
0 votes
0 answers
21 views

Perfect secrecy of the reverse of a crypto system that has perfect secrecy

I am trying to solve a problem that reads as follows: Let $E_1 = (\text{Gen}_1, \text{Enc}_1, \text{Dec}_1)$ be a crypto system that has perfect secrecy. Denote the message space $\mathbb M_1$, the ...
user avatar
  • 121
0 votes
1 answer
98 views

One-time pad without zero: proof check

I started learning cryptography and tried to work through this problem: consider one-time pad where $\mathcal{M}=\mathcal{C}=\{0,1\}^n$ and $\mathcal{K}=\{0,1\}^n\setminus 0^n$ (call this scheme $\Pi$)...
user avatar
  • 21
2 votes
0 answers
127 views

An exercise from a textbook

Let $\varepsilon>0$ be a constant. Say an encryption scheme is $\varepsilon$-perfectly secret if for every adversary $\mathcal{A}$ it holds that $$ \operatorname{Pr}\left[\operatorname{PrivK}_{\...
user avatar
2 votes
1 answer
1k views

Is OTP still perfectly secure if we limit message and key space

If we have a message space M {0,1,2,3,4,5,6} and likewise keyspace is K = {0,1,2,3,4,5,6} (generator choosen uniform keys k) We define our encryption to be the XOR of their bitwise rep on K and M ...
user avatar
  • 43
0 votes
2 answers
110 views

Question on double-asymmetric encryption and split knowledge

Moin moin, Let‘s assume there are two keypairs (d1,e1) and (d2,e2), where d1 and ...
user avatar
  • 9
2 votes
1 answer
317 views

Proving that a scheme is $\epsilon$-perfectly secret

I am currently trying to solve the following problem (2.18) from the book "Introduction to Modern Cryptography (3rd edition)" by Katz and Lindell: Let $\epsilon > 0$ be a constant. Say an ...
user avatar
  • 23
0 votes
1 answer
40 views

AKE using Noise_NNpsk2 vs Noise_NKpsk2

I am working on an implementation based on the Disco library, which itself is based on Noise and strobe framework. The goal is to do bilaterally entity-authenticated key agreement with perfect forward ...
user avatar
  • 101
3 votes
1 answer
204 views

perfectly secret with key chosen uniformly

Prove or refute: Every encryption scheme for which the size of the keyspace equals the size of the message space, and for which the key is chosen uniformly from the keyspace, is perfectly secret. My ...
user avatar
  • 41
0 votes
1 answer
116 views

How to solve this decryption algorithm given the encryption algorithm?

Consider the following cryptosystem with plaintexts from the set $M$ and ciphertexts from the set $S$ with $M = S = \{0, 1\}^4$ . A plaintext $P = (P_1, P_2, P_3, P_4)$ is encrypted to a ciphertext $C ...
user avatar
-1 votes
1 answer
106 views

Advantage of existing Cryptosystems

I have read about the concept of perfect secrecy and statistical distance. The perfect secrecy is impossible to be implemented on real world scenario. So the cryptosystems used at various websites ...
user avatar
1 vote
2 answers
530 views

Perfect Secrecy and Message distribution

I have been trying to come up with a proof of the following statement, Suppose a cryptosystem achieves perfect secrecy for a particular plaintext probability distribution then Prove that perfect ...
user avatar
  • 31
0 votes
0 answers
115 views

Formal proof that the following definitions of perfect secrecy are equivalent

I've seen the following two definitions of perfect secrecy for an encryption scheme (Gen, Enc, Dec). ...
user avatar
  • 1
4 votes
3 answers
255 views

Can you have perfect secrecy with countable message/key spaces by dropping countable additivity?

This classic paper by Chor and Kushilevitz shows that if the key space and the message space are both countably infinite, then it is impossible to have a perfectly secure private-key encryption scheme....
user avatar
2 votes
3 answers
453 views

Is it possible to have perfectly secure public-key cryptography with oracles?

It is a basic theorem of cryptography that it is impossible to have a perfectly secure public-key encryption scheme. That’s because the adversary can search through all possible private keys. But I’m ...
user avatar
1 vote
1 answer
361 views

Why don't most encryption algorithms use perfect secrecy?

Isn't it possible to make algorithms that are both computationally complex and have many possible answers if you try to crack them without knowing the password? Why aren't many popular algorithms like ...
user avatar
  • 647
0 votes
1 answer
112 views

Using HMAC with AES modes that do NOT require padding [closed]

I'm trying to use HMAC with AES modes that do not require any sort of padding. Although I am aware that modes like AES-GCM and ...
user avatar
2 votes
1 answer
308 views

A generalisation of Shannon's theorem of perfect secrecy

The proof I'm struggling with is the following: Let $\mathcal{E}$ be a cipher defined over $(K, M, C)$. Suppose that $SSadv[A, \mathcal{E}] ≤ \epsilon$ for all adversaries $A$, even including ...
user avatar
2 votes
1 answer
192 views

Perfect secrecy and block ciphers

Consider a block cipher that encrypts bit strings of length $n$, where the key-space of the block cipher is of size $2^{kn}$, $k \geq 1$. My understanding of perfect secrecy is that a system is ...
user avatar
2 votes
1 answer
200 views

How many perfect secrecy systems are there?

How many non-trivial*, interesting perfect secrecy systems are there other than the one-time-pad? Does it seem that the one-time-pad and perfect secrecy are synonymous, but are there any other ...
user avatar
1 vote
1 answer
368 views

Proving equivalency of two security definitions of symmetric encryption schemes

how to prove definition 3.8 and 3.9 are equivalence ? picture is from book an introduction to modern cryptography (2nd edition) by j. katz and y. lindell pdf and https://repo.zenk-security.com/...
user avatar
  • 31
0 votes
1 answer
164 views

Adding the same noise to all element of a vector is Differential privacy

In Differential privacy, if we add a $N$-dimension private vector with $N$-dimension Laplace or Gauss noise, we obtain differential privacy. However, if we only generate a 1-dimension noise to add it ...
user avatar
0 votes
0 answers
69 views

Perfectly secure cryptosystem as many keys as plaintexts

Is a cryptosystem perfectly secure if there are at least as many keys as there are plaintexts? My guess is yes but I am not sure, new to cyptosystems
user avatar
  • 1
0 votes
2 answers
243 views

ISAKMP 'master key' PFS (phase I) vs Ipsec session key PFS (Phase II)

A question for the crypto-experts to help out a somewhat confused guy: why does PFS (perfect forward secrecy) also exist in phase II as well as in phase I? Rationale: In phase I ISAKMP, the result ...
user avatar
  • 1
1 vote
3 answers
189 views

Why use an OTP if you already have a secure channel

Let's say I have some sensitive information, and I want to encrypt it with a OTP and send it to the FBI or something. Now, in order for the recipient to successfully decrypt the message, he needs to ...
user avatar
1 vote
0 answers
66 views

One Time Pad proof for Perfect Secrecy

In the book "Introduction to Cryptography with Coding Theory" by Trappe, in the paragraph about the security of the One Time Pad, is it told that given the set of possible plaintexts $P$, the set of ...
user avatar
  • 441
0 votes
2 answers
252 views

What operations provide perfect secrecy other than modulo addition

As far as I know OTP is the only algorithm proven to provide perfect secrecy. It can work with XOR which is addition modulo 2 and obviously it can work with additions modulo N. What other operations ...
user avatar
  • 103
2 votes
1 answer
241 views

Does an information-theoretically secure hash function exist?

Does an information theoretically secure hash function exist? (By exist I mean is discovered/invented and implemented, not whether it could exist.)
user avatar
1 vote
2 answers
137 views

Is it possible to use an algorithm to generate an OTP?

I am a software developer, not a cryptologist. I like the idea of perfect secrecy and would like to use a one-time pad (OTP) to encrypt/decrypt files up to, say, 50Mb. Is there a way that I can use ...
user avatar
1 vote
0 answers
39 views

Computationally indistinguishably vs Perfect Indistinguishably [duplicate]

I know that perfect security means absolutely no information about the plaintext is leaked to the adversary while computational secrecy is okay with a tiny amount of leak. But, what is the difference ...
user avatar
2 votes
1 answer
411 views

Almost (epsilon) perfect secrecy - lower bound of keyspace size

As a newcomer to cryptography, I'm working on Exercise 2.12 in the book, Introduction to Modern Cryptography. Using the proof of the theorem that says if $E$ is a perfectly secret encryption scheme, ...
user avatar
  • 21
3 votes
5 answers
1k views

Read-once memory

So I've been reading about cryptography and one-time pads, which seem to provide theoretically perfect secrecy. My question is does any form of technology today allow data to be stored in a practical ...
user avatar
0 votes
1 answer
364 views

Why perfectly secrecy needs the key space to be as large as the message space?

Why perfectly secrecy needs the key space to be as large as the message space? I think the definition (1) $\Pr[M=m\mathrel|C=c]= Pr[M=m]$ still holds. Let $M(c)$ be the set of messages that can be ...
user avatar
  • 147
0 votes
1 answer
233 views

If we know the pre-shared key of an IPSec tunnel, can PFS help us to stay encrypted?

Or if the "attacker" has the pre-shared key, then PFS won't help? Ex.: Heard something about China that it blocks IPSec and only allows it when you give them your pre-shared key, thus they can see ...
user avatar
1 vote
1 answer
240 views

What is the "single-letter characterization of the secrecy capacity"?

I'm reading a paper [1] in which secrecy capacity are being discussed under the following terms: A single-letter characterization of the secrecy capacity that holds for the general case remains ...
user avatar