Questions tagged [semantic-security]

produces ciphertext that, by itself, does not reveal information about the original message besides its length

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

Proof that semantic security implies key-recovery security

I'm trying to prove that semantic security implies key-recovery security. There is already a question that addresses this, but it doesn't explain the setup of the security reduction, which is what I'm ...
cmplx96's user avatar
  • 113
0 votes
0 answers
60 views

El Gamal encryption variant and its security

We are given an El Gamal variant and are requested to find the decryption scheme and the security of the encryption. The variant operates on a group $\mathbb{G}$ of prime order q and g, h are two ...
Giorgos Mitropoulos's user avatar
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 ...
joshlf's user avatar
  • 267
0 votes
1 answer
56 views

If a stream cipher uses a truly random, injective function, can we get rid of epsilon?

Imagine an encryption scheme defined as follows for a fixed $|k|$ and $|m| > |k|$: $K = \{0, 1\}^{|k|}$ $K' = M = C = \{0, 1\}^{|m|}$ $G: K \rightarrow K'$ is a truly random injective function $E(...
joshlf's user avatar
  • 267
1 vote
0 answers
60 views

Semantically secure public-key encryption scheme

Suppose that $(\mathrm{Gen},\mathrm{Dec},\mathrm{Enc})$ is a semantically secure public-key encryption scheme. I define $E' = (E(e,m)\oplus m)\parallel (E(e,m)\oplus e)$. Clearly, this is now not ...
matheg's user avatar
  • 131
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
3 votes
1 answer
343 views

Is the secret key kept constant in IND-CPA game?

I read the Wikipedia Page on ciphertext indistinguishability. Here it gives the following outline of the IND-CPA game: The challenger generates a key pair PK, SK based on some security parameter k (e....
Riemann's user avatar
  • 221
1 vote
2 answers
205 views

What's the purpose of implicit rejection

In IND-CCA encryption, one way to ensure semantic security is to return an error symbol on malformed ciphertext. Some post-quantum KEM algorithms however doesn't do this - instead, they return a "...
DannyNiu's user avatar
  • 9,207
1 vote
0 answers
66 views

Proving 2-way nesting security

I recently came across the theorem about $n$-way nesting. It states that if $\mathcal{E}=(E, D)$ is semantically secure, then $\mathcal{E}$ is secure for $n$-way nesting. I'm trying to prove the ...
libre's user avatar
  • 11
2 votes
1 answer
321 views

Using embeddings to anonymize information

This might be a stupid question, so bear with me. I was wondering if LLM embeddings can be used to anonymize input text. I couldn't find any information online that says that embeddings can be 1:1 ...
funerr's user avatar
  • 123
1 vote
1 answer
450 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
  • 432
0 votes
1 answer
172 views

Proof for secure stream cipher implies secure PRG

I am self studying "A Graduate Course in Applied Cryptography" by Boneh-Shoup. I am not sure if my proof for the following problem in the book is correct. The problem asks to prove that if a ...
cryptolearner's user avatar
3 votes
0 answers
111 views

Semantic Security equivalent to Real/Random Semantic Security

I'm reading Boneh and Shoup's book "A Graduate Course in Applied Cryptography." Im doing one of the questions at the end of the stream ciphers chapter. I'm not sure how to do this problem: ...
cryptolearner's user avatar
1 vote
1 answer
106 views

What schemas are possible for the following encryption algorithms?

I'm trying to practice and to understand possible scenarios and the basics of symmetric encryption schemes. For the scenarios I listed below, I am not 100% sure of scenarios 1 and 3. A symmetric ...
Marian Valentin's user avatar
3 votes
0 answers
82 views

Semantic Security of Modified Textbook/Raw RSA

Here's a modification of the textbook RSA scheme, in an attempt to achieve semantic security. Key generation: chooses public key $pk = (N,e)$ and secret key $sk = d$ as in any RSA-based encryption ...
user759's user avatar
  • 31
2 votes
1 answer
283 views

Proving semantic security implies security from key-recovery attack

I am working on problem 2.11 from the book: A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup. The problem reads as follows: Problem 2.11: Let $\mathcal{E} = (E, D)$ be a cipher ...
Tom Finet's user avatar
  • 125
0 votes
0 answers
89 views

Semantically secure RSA with Multiplicative Homomorphism

Most real-world RSA implementations add padding and such that break the multiplicative homomorphism of raw RSA. However, this multiplicative homomorphism can be useful. I haven't seen any existing ...
Zarquan's user avatar
  • 313
3 votes
3 answers
139 views

Why we need to consider a probability ensemble and not just a probability distribution in the definition of Security under Simulation?

I'm currently reading this classic paper "How To Simulate It" and on most of the definitions it is using the term probability ensemble to represent the message space. From my understanding a ...
tur11ng's user avatar
  • 962
1 vote
1 answer
56 views

Security of Reusing a One-Time Pad with Complement Messages with Errors

Let's say I have two binary messages ($m_0$ and $m_1$) of length $n$ which are bitwise complements of each other such that $$m_0 \xleftarrow{r} \{0,1\}^n \text{ and } m_1 = \overline{m_0}$$ If I ...
Fishy Sticks's user avatar
0 votes
1 answer
52 views

IPS systems and AES Encrypted data [closed]

I was wondering how "IPS" systems process and react to the AES encrypted data than the DES
Terri Croft's user avatar
2 votes
1 answer
899 views

Security definition for IND-CPA of public key encryption

In the security game between the challenger and the adversary for the security definition of public key encryption, the challenger creates and gives the public key pk to the adversary. The adversary ...
Noel's user avatar
  • 133
1 vote
1 answer
107 views

Question on Simulation based security proof for Oblivious Transfer (OT) against semi-honest adversaries

I'm currently reading this How To Simulate It – A Tutorial on the Simulation Proof Technique. On p. 10, there is a proof using simulation for 1/2-OT, against semi-honest adversaries. Briefly, the ...
tur11ng's user avatar
  • 962
1 vote
1 answer
121 views

Question on notation of random variables in probability ensembles

Let's consider this definition of computational indistinguishability. Computational indistinguishability. A probability ensemble $X=\{X(a, n)\}_{a \in\{0,1\}^{*} ; n \in \mathbb{N}}$ is an infinite ...
tur11ng's user avatar
  • 962
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$ ...
Mathemagician's user avatar
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
1 vote
1 answer
255 views

What is the definition of semantic secure advantage?

I'm doing sequence-of-game formal security analysis for key exchange protocol. It confuses me a lot how to calculate the adversary's semantic secure (SS) advantage. In Shoup's tutorial "sequences ...
Chandler's user avatar
0 votes
0 answers
104 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 ...
joxavy's user avatar
  • 11
2 votes
0 answers
115 views

ElGamal with elliptic curves and semantic security

To encrypt a group element $P$ with public key $K$ and randomness $r$ using ElGamal on elliptic curves with base point $G$ we do the following $(c_1, c_2) = (r\cdot G; P+r\cdot K)$. When we want to ...
pintor's user avatar
  • 558
1 vote
1 answer
374 views

How are probabilities combined in the game hopping proof technique?

I'm currently studying a paper (Sequences of Games: A Tool for Taming Complexity in Security Proofs) on proving semantic security using the Game Hopping technique by Victor Shoup. On pages 9-11, he is ...
tur11ng's user avatar
  • 962
2 votes
1 answer
164 views

Can semantic security protect against key recovery attack?

Do I need to pay special attention to key recovery attack while focusing on semantic security? The book "A Graduate Course in Applied Cryptography" by Dan Boneh and Victor Shoup doesn't ...
drawlone's user avatar
2 votes
1 answer
164 views

Is the tag generated in MAC equal for equal messages in CBC-MAC?

The Cipher Block Chaining algorithm for generating message authentication codes uses a 0 IV . So my understanding is that same messages will generate same MACs which seems to violate semantic ...
Abhisek Dash'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
1 answer
1k views

Semantic Security Game

I need help understanding semantic security, in particular, the part on the 'game'. But first, from my understanding, is semantic security is a 'weaker' and more flexible way to determine that a ...
Jack's user avatar
  • 43
0 votes
0 answers
118 views

Shamir secret sharing in automated verification tools

Can Shamir secret sharing scheme (SSS) be verified using automated verification tools such as AVISPA? I read in the HLPSL manual that we cannot use arithmetic or relative operations such +,-,< ......
Mona's user avatar
  • 197
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
1 vote
0 answers
63 views

If a different plaintext may produce the same ciphertext, is the system perfectly secure?

Define the injective map $\phi: \Omega\rightarrow \mathbb{N}$, such that $\Omega=\mathcal{A}^n$ denotes the set of all strings of length $n\in\mathbb{N}^*$ from an alphabet $\mathcal{A}$ of elements $...
UNOwen's user avatar
  • 11
1 vote
0 answers
85 views

getting key $k_{2}$ somehow definitely compromise authentication scheme and attacker can see cipher text now...so not secure

I was going through this question of nested encryption: Given $\Pi$ = $({Gen}, {Enc}, {Dec})$ is authentication encryption we have designed new scheme $\Pi^{'}$ = $({Gen^{'}}, {Enc{'}}, {Dec{'}})$ ...
Sam's user avatar
  • 49
0 votes
0 answers
53 views

Not getting idea how to formally chose chosen cipher attack so adversay wins with non-negligible probability

I was going through this question and intuition came that same message can be used to break security but I an not able formalize it well...can someone help how to create chosen ciphertext attack ...
Sam's user avatar
  • 49
2 votes
0 answers
430 views

An exercise to show that CBC Chain is insecure

The CBC-Chain mode of operation is a CBC variant in which the IV that is used for the very first message to be encrypted is randomly selected, whereas the IV used for each subsequent encrypted message ...
Sayantan's user avatar
0 votes
0 answers
156 views

Semantic Security in Formal Security Proofs

I have a trivial question, and I hope someone can help me. I am reading several papers on formal security proofs based on the indistinguishably game. Specifically, the adversary is challenged in an ...
Mona's user avatar
  • 197
3 votes
7 answers
701 views

Understanding why Semantic Security implies Message Recovery Security

I am stuck in the proof where it says $$p_0=\frac{1}{|M|},$$ I just do not understand how we can infer this equality. Also, am I right in understanding that B is defined as choosing his two messages ...
PhantomR's user avatar
  • 131
2 votes
1 answer
652 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
546 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/...
mike's user avatar
  • 41
6 votes
1 answer
705 views

Why is encrypting a key under itself dangerous?

I'm currently self-studying to try and understand more about cryptography for work. I'm on question 2.16 on A Graduate Course in Applied Cryptography . For part a), we're given a cipher $E$ that's ...
AeonNeo's user avatar
  • 161
2 votes
1 answer
428 views

Proofs that NM-CPA implies IND-Cpa and $\text{IND-CCA} \leftrightarrow \text{NM-CCA}$

I am looking for a proof for the following two claims from "Serious Cryptography" by Aumasson. NM-CPA implies IND-CPA. [...] IND-CCA and NM-CCA are equivalent notions that imply the presence of the ...
securitymensch's user avatar
0 votes
0 answers
703 views

Perfectly secure and indistinguishability property

I'm studying cryptography for my university course, but some doubts arose from reading a book. In this book the author says: "Now we present another equivalent definition of perfect secrecy. This is ...
Lorenzoi's user avatar
1 vote
0 answers
579 views

Game-based proofs and semantic security

After reading this question, I understood that "game-based" and "simulation-based" have to do with the way that security properties are postulated. In particular, IND-CPA is a canonical example of ...
CTN's user avatar
  • 11
0 votes
0 answers
47 views

Is this simple proposed scheme semantically secure?

Suppose we have two parties, including $P_1$ and $P_2$ using a type of symmetric encryption algorithm, say, AES256. Let's assume the shared key is: $K$. Encryption: Each party generate a key such ...
Amirhossein Adavoudi's user avatar
1 vote
1 answer
159 views

Does adding OWF of the private key to encryption scheme hurts security?

Suppose I have a symmetric semantic-secure encryption system $\Pi = (Enc, Dec)$ and an OWF $f$. Now, define the following encryption scheme $\Pi^{'} = (Enc^{'}, Dec^{'})$ where , $Dec^{'} = Dec$ and $...
Bartolinio's user avatar
5 votes
3 answers
1k views

Nonce-misuse-resistance scheme applied after the fact to AES-GCM for defense in depth?

This is a follow-up to a previous question about encrypting IV/MAC results from AEAD ciphers. I have a system I'm working on that needs to use standard (NIST/FIPS) cryptography, at least for its ...
Adam Ierymenko's user avatar