CAS CS538: Cryptography. Spring 2023 Instructor: , Ran Canetti
A note on secure communication schemes
March 3, 2023
We define secure message transmission schemes. These are schemes that allow parties to communicate while guaranteeing both secrecy and authenticity of the communicated plaintexts. That is, we consider a setting where one party (Alice) is tasked to sent multiple messages to another designated party (Bob). A secure message transmission scheme guarantees that an adversary that completely controls the communication channel can neither learn anything about any of the messages sent by Alice, nor cause Bob to accept any messages other than the ones sent by Alice.
Copyright By PowCoder代写 加微信 powcoder
We note that the scheme cannot, of course, prevent the adversary from failing to deliver messages to Bob. It also cannot prevent the adversary from making Bob receive the same message multiple times; however duplicate delivery can be easily mitigated by additional processing of the received messages (e.g. by including sequence numbers in the messages).
The object in question is again a triple of algorithms (Gen, Enc, Dec) (except that here Enc stands for Encode, and Dec stands for Decode). Correctness of decoding is formulated in a straightforward way. The secrecy and unforgeability requirements and blended into a single game, which guarantees that no feasible adversary is able to tell the difference between the case where it is given oracle access to Enc(k,·) and Dec(k,·) (keyed by a random key k) and the case where it is given access to idealized versions of the encoding and decoding algorithms, where it is guaranteed that the messages sent are perfectly hidden, and only messages that were previously encoded can ever be decoded successfully.
The definition does not fully specify the idealize encoding and decoding algorithms. Instead, it allows the proof of security to specify the details the these algorithms, but does in a way that guarantees perfect hiding and perfect authentication regardless of the specific choice of the ideal encoding and decoding algorithms.
We note that SMT schemes are a more permissive variant of the notion of authenticated encryption (AE) defined in Boneh-Shoup. That is, any AE scheme is in particular an SMT scheme, wherever there may well exist SMT schemes that are not AE. (In particular, SMT schemes do not mandate separate encryption and authentication stages, nor does it require the use of strong MA schemes or the authentication of ciphertexts.) Still we argue that SMT scheme suffice for guaranteeing secure communication.
Definition 1. A triple of algorithms (Gen, Enc, Dec) is a secure message transmission (SMT) scheme with respect to message domain M if:
Correctness: For any m ∈ M, and any λ ∈ N we have Prob[k ←$ Gen(1λ);c ←$ Enc(k,m) : Dec(k,c) = m] = 1. Unforgeability and secrecy: There exist polytime algorithms (IE, ID) and a negligible function ν(λ) such that
for any feasible adversary A = {Aλ}λ∈N and all large enough λ we have
Prob[k ←$ Gen(1λ) : AREAL(k,·) = 1] − Prob[k ←$ Gen(1λ) : AIDEAL(k,·) = 1] < ν(λ)
REAL(k, ·) is defined as follows:
– on input (ENC,m) returns c ←$ Enc(k,m)
– on input (DEC, c) returns m ←$ Dec(k, c)
IDEAL(k,·) is a stateful oracle defined as follows:
– given the ith input of the form (ENC,m), computes (c,s) ←$ IE(k,i), records (m,s) and returns ciphertext c.
– given an input of the form (DEC,c): Compute s ← ID(k,c). If a triple of the form (m,s) is recorded then return m. Else return ⊥.
We now show that the Encrypt-Then-MAC scheme discussed in class is an SMT scheme:
Theorem 1. Let (Gene,Ence,Dece) be a CPA-secure encryption scheme with message space M and ciphertext space C, and let (Gena, Auth, V er) be an EU-CMA message authentication scheme with respect to message space C. Then the scheme (Gensc, Encsc, Decsc) where:
(ka, ke) ←$ (Gensc(1λ), where ka ←$ Gena(1λ) and ke ←$ Gene(1λ).
Encsc((ka,ke),m) = (c,τ), where c ←$ Ence(ke,m) and τ ←$ Auth(ka,c).
Decsc((ka,ke),(c,τ))=⊥ if Ver(ka,c,τ)=0, and Dec(ke,c) otherwise
is an SMC scheme.
Proof. Correctness is straightforward. To show unforgeability and secrecy, we first define the ideal encryption
(IE) and ideal decryption (ID) algorithms. On input k, i, where k = (ka, ke), algorithm IE runs γ ←$ Ence(ke, 0),
τ ←$ Auth(ka,γ) and outputs ciphertext (γ,τ) and internal state s = γ. On input k,c, where k = (ka,ke) and c=(γ,τ),algorithmIDrunsb←Ver(ka,γ,τ). Ifb=0IDoutputs⊥,elseγ.
Now, consider a feasible adversary A = {Aλ}λ∈N and let
Prob[k ←$ Gensc(1λ) : AREAL(k,·) = 1] − Prob[k ←$ Gensc(1λ) : AIDEAL(k,·) = 1] = ε(λ).
We construct adversaries A′ and A′′ such that either A′ breaks the CPA security of (Gene,Ence,Dece) with λλλ
advantage ε(λ)/2, or else A′′ breaks the EU-CMA unforgeability of (Gena, Auth, V er) with probability ε(λ)/2. λ
Adversary A′λ runs Aλ and proceeds as follows: First, A′λ chooses ka ←$ Gena(1λ). Next, whenever Aλ makes an (ENC,m) query, Aλ sends the query (m0 = 0,m1 = m) to its own encryption oracle, and obtains the
ciphertext γ. Aλ then computes τ ←$ Auth(ka,γ) and returns c = (γ,τ) to Aλ. Whenever Aλ makes an (DEC,c) query,wherec=(γ,τ),A′λ computesb←Ver(ka,γ,τ). Ifb=0thenA′λ returns⊥toAλ. Ifb=1andγisa ciphertext that was provided to A′λ in response to a query (0, m), then A′λ returns m to Aλ. If b = 1 and γ is a ciphertext that was never given to A′λ before, then A′λ stops the simulation and outputs a random bit. (We call this event a forgery.) When Aλ halts, A′λ outputs 1 iff Aλ outputs 1. Else, A′λ outputs 0.
Adversary A′′ runs Aλ and proceeds as follows: First, A′′ chooses ke ←$ (Gene(1λ). Next, whenever Aλ makes λλ
an (ENC,m) query, A′′ computes γ ←$ Enc(ke,m), sends the query γ to its own authetication oracle, obtains λ
the tag τ, and returns c = (γ,τ) to Aλ. Whenever Aλ makes an (DEC,c) query, where c = (γ,τ), A′′ calls its λ
verification oracle on query (γ,τ). If verification fails, then A′′ returns ⊥ to Aλ. If verification succeds and γ was λ
generated by A′′ before as an encryption of a message m, then A′′ returns m to Aλ. If verification succeeds and λλ
γ was not generated before by A′′, then A′′ outputs (γ,τ) as a forgery. λλ
Now, assume that the challenger in the CPA game chose the bit b = 0, which means that all the ciphertexts that A′λ receives are encryptions of 0. In this case, conditioned on the forgery event not occurring, the interacaction seen by the underlying Aλ is exactly the interaction with IDEAL(k,·). Similarly, assume that the challenger in the CPA game chose the bit b = 1, which means that each ciphertext that A′λ receives is an encryption of the message m generated by the underlying Aλ. In this case, conditioned on the forgery event not occurring, the interacaction seen by the underlying Aλ is exactly the interaction with REAL(k,·). This means that, as long as the forgery event occurs with probability at most ε(λ)/2, A′λ breaks the CPA security of (Gene, Ence, Dece) with advantage ε′(λ)/2.
On the other hand, observe than whenever the forgery event happens, adversary A′′ wins the EU-CMA un- λ
forgeability game against (Gena, Auth, V er). This means that as soon as the forgery event occurs with probability
at least ε(λ)/2, A′′ breaks the EU-CMA security of(Gena, Auth, V er) with probability at least ε(λ)/2. λ
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com