1 %%% Deniably authenticated asymmetric encryption
3 %%% Copyright (c) 2010 Mark Wooding
6 \documentclass[t
]{beamer
}
8 \usefonttheme{professionalfonts
}
9 \usefonttheme[stillsansseriflarge, stillsansserifsmall
]{serif
}
10 \usepackage[T1]{fontenc}
11 \usepackage[utf8
]{inputenc}
12 \usepackage[palatino, helvetica, courier, maths = cmr
]{mdwfonts
}
14 \usepackage{crypto, mdwmath
}
16 shapes.symbols,shapes.callouts,
%
17 decorations.pathreplacing,positioning,calc
}
19 \title{Deniably authenticated asymmetric encryption
}
20 \author[Mark Wooding
]{Mark Wooding \\
\texttt{mdw@distorted.org.uk
}}
23 \def\Xid#1#2{\textsc{$
#1$
}-
#2}
24 \def\proto#1{\Pi_\textsc{#1}}
25 \def\mugshot{\includegraphics[width =
2cm, height =
2.5cm, keepaspectratio
]}
29 mugshot/.style =
{draw, fill = white, inner sep =
0, outer sep =
\jot},
31 shape = cloud callout, cloud ignores aspect, draw, fill = white,
32 cloud puffs =
20, cloud puff arc =
110,
33 callout absolute pointer = (
#1)
35 box/.style =
{draw, minimum size =
16pt, fill =
#1},
36 op/.style =
{box =
#1, shape = circle
},
37 rounded/.style =
{rounded corners =
2mm
},
38 offset/.style =
{transform canvas =
{shift =
{#1}}},
46 \frame{\frametitle{Outline
}\tableofcontents}
47 \AtBeginSubsection{\frame{%
50 sectionstyle = show/shaded,
%
51 subsectionstyle = show/shaded/shaded
]%
54 %%%--------------------------------------------------------------------------
55 \section{Introduction
}
57 \subsection{Motivation: sign-then-encrypt failures
}
59 \begin{frame
}{Sign-then-encrypt
}
63 \node[mugshot
] (bob) at (
0,
0)
{
64 \only<
1-
18>
{\mugshot{bob.png
}}%
65 \only<
19->
{\mugshot{bob-unthrilled.png
}}
68 \node[thought = bob.north
] at ($(bob) + (
2,
3)$)
71 \visible<
5->
{Alice's public key $A$
} \\
75 \node[mugshot
] (alice) at (
10,
0)
{
76 \only<
3-
16>
{\mugshot{alice.png
}}%
77 \only<
17->
{\mugshot{alice-fallen.png
}}
81 \node[mugshot
] (julian) at ($(bob)!
1/
2!(alice)$)
85 \node[thought = alice.north
] at ($(alice) + (-
2,
3)$)
88 \visible<
5->
{Bob's public key $B$
} \\
91 \animatevalue<
9-
15>
{\f}{2}{8}
92 \only<
1-
8>
{\tikzset{message/.style =
{}}}
93 \only<
9->
{\tikzset{message/.style =
{draw, fill = white
}}}
95 \node[message
] at ($(bob.east)!
\f/
10!(alice.west)$)
96 { $
\visible<
8-
15>
{E_A(
}
97 m
\visible<
7->
{, S_b(m)
} \visible<
8-
15>
{)
} $
};
103 \onslide<+-+(
1)> Meet Bob.
\visible<+>
{Bob has a private key.
}
104 \onslide<+-+(
1)> Bob meets Alice online.
\visible<+>
{Alice has a
106 \onslide<+> Magically, they know each other's public keys.
107 \onslide<+> Bob knows a secret. He wants to send it to Alice.
108 \onslide<+> Bob signs his message so that Alice knows it's from him.
109 \onslide<+> He encrypts so nobody else knows what he's telling her.
110 \onslide<+-+(
6)> And then he sends the whole lot to Alice.
111 \addtocounter{beamerpauses
}{6}
112 \onslide<+> Alice decrypts and verifies.
113 \onslide<+> Alice isn't exactly a night in shining armour.
114 \onslide<+> She publishes Bob's message and his signature.
115 \onslide<+> Bob is not completely thrilled.
120 \begin{frame
}{Signatures and public-key encryption
}
121 \begin{itemize
}[<+->
]
122 \item Lots of other problematic scenarios
[Davis~
2001].
123 \item Encrypt-then-sign doesn't help much: recipient can publish NIZK proof
124 of correct decryption.
125 \item Signatures are universally verifiable. Non-repudiation is
126 undesirable when you're up to no good.
127 \item Authenticated encryption is still valuable.
\visible<+>
{Especially
128 when you're up to no good.
}
132 \subsection{Our contributions
}
134 \begin{frame
}{Deniably authenticated asymmetric encryption
}
135 \begin{block
}{The basic idea
}
136 \begin{itemize
}[<+->
]
137 \item Bob sends a message to Alice.
138 \item Nobody else can read it (
\emph{secrecy
}).
139 \item Alice knows that Bob sent it (
\emph{authenticity
}).
140 \item Neither Alice nor Bob can prove that Bob sent it to anyone else
141 (
\emph{deniability
}).
144 \begin{block
}<+->
{We provide
}
145 \begin{itemize
}[<+->
]
146 \item Formal definitions of security and deniability.
147 \item Three constructions with various properties.
152 \subsection{Previous work
}
154 \begin{frame
}{Previous and related work
}
155 \begin{itemize
}[<+->
]
156 \item Deniable authentication since
[Dolev, Dwork, Naor~
1991]; also
[Dwork,
157 Naor, Sahai~
19991],
[Di~Raimondo, Gennaro~
2005]. Intrinsically
159 \item Deniably authenticated key exchange
[Di~Raimondo, Gennaro,
160 Krawczyk~
2006], e.g., SKEME
[Krawczyk~
1996],
\emph{Off the Record
}
161 [Borisov, Goldberg, Brewer~
2004], Wrestlers
[Wooding~
2006]. Also
163 \item Chameleon signatures
[Krawczyk, Rabin~
1998].
164 \item Ring signatures
[Rivest, Shamir, Tauman~
2001].
168 %%%--------------------------------------------------------------------------
169 \section{Definitions
}
171 \subsection{Secrecy and authenticity
}
173 \begin{frame
}{Formal definitions
}{Secrecy and authenticity
}
174 Multiparty outsider
\alert<
5-
7>
{secrecy
} and
\alert<
8>
{authenticity
} [An,
179 \node[mugshot
] (adv) at (
0,
0)
{\mugshot{adv.png
}};
181 \node[mugshot
] (alice) at (-
5,
2)
{\mugshot{alice.png
}};
184 \node[mugshot
] (bob) at (+
5,
2)
{\mugshot{bob.png
}};
187 \path node
[above = of adv
]
188 {{$A$
\visible<
3->
{, $B$
}}} edge
[->
] (adv);
191 \draw[->, offset =
{(
0mm,
5mm)
}]
192 (adv) to node
[above, sloped
] {$m$, $Z$
} (alice);
193 \draw[->, offset =
{(
0mm,
2mm)
}]
194 (alice) to node
[below, sloped
] {$E_a(Z, m)$
} (adv);
195 \draw[->, offset =
{(
0mm,
5mm)
}]
196 (adv) to node
[above, sloped
] {$c$, $Z$
} (bob);
197 \draw[->, offset =
{(
0mm,
2mm)
}]
198 (bob) to node
[below, sloped
] {$D_b(Z, c)$
} (adv);
201 \path[offset =
{(
0mm, -
2mm)
}] node
[right = of adv
]
202 {$m_0$, $m_1$
} edge
[<-
] (adv);
205 \path[offset =
{(
0mm, -
6mm)
}] node
[right = of adv
]
206 {$c^* = E_a(B, m_
\sigma)$
}
210 \path[offset =
{(
0mm, -
10mm)
}] node
[right = of adv
]
211 {Guess $
\sigma =
\textbf?$
}
215 \path[offset =
{(
0mm, -
6mm)
}] node
[right = of adv, text width =
40mm
]
216 {New $c^*$ with \\ $D_b(A, c^*)
\ne \bot$
}
223 \onslide<+> There is always an adversary.
224 \onslide<+> We add a sender, Alice: private key $a$, public key $A$.
225 \onslide<+> And a recipient, Bob: private key $b$, public key $B$.
226 \onslide<+> Makes encryption and decryption queries with arbitrary public
228 \onslide<+> Adversary chooses two messages of equal length.
229 \onslide<+> We encrypt one of them.
230 \onslide<+> Adversary tries to guess which.
231 \onslide<+> Adversary tries to construct forgery.
236 \subsection{Strong deniability
}
238 \begin{frame
}<
1-
8>
[label = deny
]{Formal definitions
}{Deniability
}
242 \begin{tikzpicture
}[every to/.style =
{sloped, font =
\footnotesize}]
243 \node[mugshot
] (alice) at (-
5, -
1.5)
{\mugshot{alice.png
}};
244 \node[mugshot
] (bob) at (+
5, +
1.5)
{\mugshot{bob.png
}};
246 \node[mugshot
] (justin) at (
0,
0)
{\mugshot{judge.png
}};
249 \node[mugshot
] (robot-bob) at (+
5, -
1.5)
{\mugshot{robot-bob.png
}};
252 \node[mugshot
] (robot-alice) at (-
5, +
1.5)
253 {\mugshot{robot-alice.png
}};
257 \draw[->, offset =
{(
0mm, +
4mm)
}] (bob) to
258 node
[above
] {$m$
} node
[below
] {$c = E_a(B, m)$
}
263 ($(bob.east |- justin) - (
3\jot,
0pt)$) -- (justin.east);
266 \draw[<->, offset =
{(
0mm, -
2.5mm)
}] (robot-bob) to
269 \draw[->, offset =
{(
0mm, -
5.5mm)
}] (robot-bob) to
270 node
[below
] {$c' = R_b(A,
\only<
7->
{\alert<
7>
{c
},
} m')$
}
274 \node[below = of justin
] {$a$, $b$
} edge
[->
] (justin);
277 \node[thought = justin.north
] at ($(justin.north) + (
1/
3,
1/
2)$)
283 ($(alice.west |- justin) + (
3\jot,
0pt)$) -- (justin.west);
286 \draw[->, offset =
{(
0mm, -
4mm)
}] (alice) to
287 node
[above
] {$m_0$
} node
[below
] {$c_0 = E_a(B, m_0)$
}
289 \draw[<->, offset =
{(
0mm, -
2.5mm)
}] (robot-bob) to
292 \draw[->, offset =
{(
0mm, -
5.5mm)
}] (robot-bob) to
293 node
[below
] {$c_1 = R_b(A, c_0, m_1)$
}
297 \draw[->, offset =
{(
0mm, +
4mm)
}] (bob) to
298 node
[above
] {$m_1$
} node
[below
] {$c'_1 = E_a(B, m_1)$
}
302 \draw[<->, offset =
{(
0mm, +
5.5mm)
}] (robot-alice) to
305 \draw[->, offset =
{(
0mm, +
2.5mm)
}] (robot-alice) to
306 node
[below
] {$c'_0 = S_a(A, c'_1, m_0)$
}
313 \onslide<+> Start with a sender (Alice) and recipient (Bob).
314 \onslide<+> Bob will try to convince a
\emph{judge
} (Justin) that Alice
316 \onslide<+> Bob gives Justin the ciphertext $c$ and message $m$.
317 \onslide<+> Simulator constructs ciphertext $c'$ for another message
319 \onslide<+> We give Alice and Bob's private keys to Justin.
320 \onslide<+>
\emph{Strong deniability
} if Justin can't distinguish.
321 \onslide<+> Useful relaxation: allow simulator a sample ciphertext.
322 \onslide<+> Unfortunately, this definition is now too simplistic.
323 \onslide<+> We need a richer model.
324 \onslide<+> Scenario $A$: Bob's ciphertext is simulated; Alice has the
326 \onslide<+> Scenario $B$: Bob's ciphertext is genuine.
327 \onslide<+> Alice must construct her own simulated ciphertext.
328 \onslide<+>
\emph{Weak deniability
} if Justin can't distinguish.
333 \subsection{Weak deniability
}
335 \begin{frame
}{Weak deniability
}{What goes wrong?
}
338 \begin{itemize
}[<+->
]
339 \item Simulator accepts sample ciphertext as input.
340 \item If the simulator was used, there must be two related ciphertexts.
341 \item If no simulator was used,
\dots
344 \begin{block
}<+->
{Example: chameleon signatures
[Krawczyk, Rabin
1998]}
345 \begin{itemize
}[<+->
]
346 \item Trapdoor commitments: public key $T$, private key $t$.
347 \begin{itemize
}[<+->
]
348 \item Commitment: choose random $
\rho$, commitment is $c = C_T(m;
350 \item Binding property: hard to find $(m',
\rho')
\ne (m,
\rho)$ with
351 $c = C_T(m';
\rho')$.
352 \item Trapdoor opening: given $t$ and any $m'$, it's easy to find
353 $
\rho'$ with $c = C_T(m';
\rho')$.
355 \item Signatures: recipient (Bob) has trapdoor $t$.
356 \begin{itemize
}[<+->
]
357 \item To sign $m$ for Bob: $c
\gets C_T(m;
\rho)$; $
\sigma \gets S_a(c,
358 B)$: signature is $(c,
\rho,
\sigma)$.
359 \item Bob can forge using his trapdoor. Alice repudiates forgeries by
360 revealing collision in $C_T$.
361 \item But Alice can't repudiate genuine signature: deniability failure.
367 \againframe<
9-
13>
{deny
}
369 \begin{frame
}{Weak deniability
}{Security and authenticity revisited
}
374 \node[mugshot
] (adv) at (
0,
0)
{\mugshot{adv.png
}};
375 \node[mugshot
] (alice) at (-
5,
1.5)
{\mugshot{alice.png
}};
376 \node[mugshot
] (bob) at (+
5,
1.5)
{\mugshot{bob.png
}};
377 \path node
[above = of adv
] {$A$, $B$
} edge
[->
] (adv);
378 \draw[->, offset =
{(
0mm,
5.5mm)
}]
379 (adv) to node
[above, sloped
] {$m$, $Z$
} (alice);
380 \draw[->, offset =
{(
0mm,
2.5mm)
}]
381 (alice) to node
[below, sloped
] {$E_a(Z, m)$
} (adv);
382 \draw[->, offset =
{(
0mm,
5.5mm)
}]
383 (adv) to node
[above, sloped
] {$c$, $Z$
} (bob);
384 \draw[->, offset =
{(
0mm,
2.5mm)
}]
385 (bob) to node
[below, sloped
] {$D_b(Z, c)$
} (adv);
386 \path[offset =
{(
0mm, -
2mm)
}] node
[right = of adv
] {} edge
[<-
] (adv);
387 \path[offset =
{(
0mm, -
6mm)
}] node
[right = of adv
] {} edge
[->
] (adv);
388 \path[offset =
{(
0mm, -
10mm)
}] node
[right = of adv
] {} edge
[<-
] (adv);
390 \node[mugshot
] (robot-bob) at (-
5, -
1.5)
{\mugshot{robot-bob.png
}};
391 \draw[->, offset =
{(
0mm, -
2.5mm)
}]
392 (adv) to node
[above, sloped
] {$m$, $Z$, $c$
} (robot-bob);
393 \draw[<-, offset =
{(
0mm, -
5.5mm)
}]
394 (adv) to node
[below, sloped
] {$R_b(Z, c, m)$
} (robot-bob);
400 \onslide<+> With weak deniability, simulator works on an input
402 \onslide<+> Must therefore allow adversary access to the simulator.
407 %%%--------------------------------------------------------------------------
408 \section{Constructions
}
410 \subsection{Authentication tokens
}
412 \begin{frame
}{Authentication tokens
}{The basic idea
}
417 \node[mugshot
] (alice)
{\mugshot{alice.png
}};
418 \node[mugshot
] (bob) at (
10,
0)
{\mugshot{bob.png
}};
419 \node[mugshot
] (eve) at (
5, -
1.5)
{\mugshot{adv.png
}};
423 {$E_B(
\visible<
3->
{\textrm{`
\texttt{Eve is nosey
}'
},
} m)$
}
428 \setcounter{beamerpauses
}{3}
430 \begin{itemize
}[<+->
]
431 \item Alice and Bob can agree a password to be included in their
433 \item If the encryption is any good, an adversary can't work out the
435 \item So he can't impersonate them to each other.
440 \begin{frame
}{Authentication tokens
}{Definition
}
443 \begin{itemize
}[<+->
]
444 \item Key generation: $G()
\to (x, X)$.
445 \item<
9->
\alert{Binding:
} $B_x(X')
\to \beta$.
446 \item Token construction: $T_x(
\only<.-
8>
{Y
}\only<
9->
{\alert{\beta}})
447 \to \tau \in \
{0,
1\
}^t$.
448 \item Verification: $V_y(X,
\only<
9->
{\alert{\beta},
} \tau)
\to
455 \node[mugshot
] (adv) at (
0,
0)
{\mugshot{adv.png
}};
456 \node[mugshot
] (alice) at (-
5,
1.5)
{\mugshot{alice.png
}};
457 \node[mugshot
] (bob) at (+
5,
1.5)
{\mugshot{bob.png
}};
459 \path[offset =
{(
0mm, -
6mm)
}] node
[left = of adv
]
460 {$A$
\only<
9->
{,
\alert{$
\alpha$
}}, $B$
\only<
9->
{,
\alert{$
\beta$
}}}
464 \draw[->, offset =
{(
0mm,
5mm)
}]
465 (adv) to node
[above, sloped
]
466 {$
\only<-
8>
{Z
}\only<
9->
{\alert{\gamma}}$
} (alice);
467 \draw[->, offset =
{(
0mm,
3mm)
}]
468 (alice) to node
[below, sloped
]
469 {$T_a(
\only<-
8>
{Z
}\only<
9->
{\alert{\gamma}})$
}
473 \draw[->, offset =
{(
0mm,
5mm)
}]
474 (adv) to node
[above, sloped
] {$Z$, $
\tau$
} (bob);
475 \draw[->, offset =
{(
0mm,
3mm)
}]
476 (bob) to node
[below, sloped
]
477 {$V_b(Z
\only<
9->
{,
\alert{\beta}},
\tau)$
} (adv);
480 \path[offset =
{(
0mm, -
6mm)
}] node
[right = of adv, text width =
40mm
]
481 {New $
\tau^*$ with \\
482 $V_b(A
\only<
9->
{,
\alert{\beta}},
\tau^*) =
1$
}
489 \begin{frame
}{Authentication tokens
}{Deniably authenticated encryption
}
491 \column{0.45\textwidth}
494 \begin{tikzpicture
}[node distance =
5mm
]
496 \node[box = yellow!
20, minimum width =
30mm
] (m)
{$m$
};
499 \node[box = green!
20, left = -
0.6pt of m
] (tau)
{$
\tau$
};
500 \node[op = green!
20, above = of tau
] (token)
{$T$
} edge
[->
] (tau);
501 \node[left = of token
] {$x_
\textsc{tok
}$
} edge
[->
] (token);
502 \node[above = of token
] {$
\beta$
} edge
[->
] (token);
505 \draw[decorate, decoration = brace
]
506 (m.south east) -- (tau.south west)
507 coordinate
[pos =
0.5, below =
2.5pt
] (p);
508 \node[op = red!
20, below = of p
] (e)
{$E$
} edge
[<-
] (p);
509 \node[left = of e
] {$Y_
\textsc{ae
}$
} edge
[->
] (e);
510 \node[box = red!
20, minimum width =
30mm +
15.6pt, below = of e
]
515 \column{0.50\textwidth}
517 \begin{description
}[<+->
]
518 \item[Secrecy
] Direct from encryption IND-CCA.
519 \item[Authenticity
] From encryption IND-CCA, token unpredictability,
521 \item[Deniability
] Unconditionally weakly deniable. Strongly deniable
522 if recipient can simulate tokens.
528 \begin{frame
}{Authentication tokens
}{Instantiations
}
530 \begin{block
}<+->
{Simple tokens from signatures
}
531 \begin{itemize
}[<+->
]
532 \item Token key is just a signature key.
533 \item Binding value is simply (hash of) rest of public key.
534 \item Token is signature on recipient's binding value.
535 \item Need constant-length signatures.
536 \item Security directly from signature unforgeability.
539 \begin{block
}<+->
{Deniable tokens from Diffie--Hellman
}
540 \begin{itemize
}[<+->
]
541 \item Group $(G, +)$, generated by $P$; $\#G = p$ prime.
542 \item Token private key $a
\in \gf{p
}$; public key $A = a P$.
543 \item Binding: non-malleable NIZK proof-of-knowledge of $a$ and signature
545 \item Security from NIZK and computational Diffie--Hellman in $G$.
550 \subsection{Signing tags
}
552 \begin{frame
}{Signing tags
}{Background on key-encapsulation mechanisms
}
554 \begin{block
}<+->
{Basic idea
}
555 \begin{itemize
}[<+->
]
556 \item Asymmetric primitives often used to transport symmetric keys.
557 \item Sender doesn't usually care about the key's specific value.
558 \item Can improve efficiency and security by taking advantage of this.
563 \column{0.41\textwidth}
565 \begin{itemize
}[<+->
]
566 \item Key gen: $G()
\to (x, X)$
567 \item Encap: $
\mathcal{E
}_X()
\to (K, u)$
568 \item Decap: $
\mathcal{D
}_x(u)
\to K'$
571 \column{0.55\textwidth}
575 node distance =
15mm,
576 every to/.style =
{font =
\footnotesize}]
577 \node[mugshot
] (adv)
{\mugshot{adv.png
}};
579 \path[offset =
{(
0mm,
8mm)
}]
580 node
[right = of adv
] {$X$, $u^*$
}
584 \node[below left =
4mm and -
10mm of adv, text depth =
2pt
]
585 {$K_0
\inr \
{0,
1\
}^k$
}
587 \node[below right =
4mm and -
10mm of adv, text depth =
2pt
]
590 \draw[dashed
] (adv.south) -- +(
0, -
1);
593 \path[offset =
{(
0mm,
0mm)
}]
594 node
[draw, fill = blue!
20, right = of adv
] (oracle)
595 {$
\mathcal{D
}_x(
\cdot)$
};
596 \draw[offset =
{(
0mm,
1.5mm)
}, ->
]
597 (adv) to node
[above
] {$u$
} (oracle);
598 \draw[offset =
{(
0mm, -
1.5mm)
}, <-
]
599 (adv) to node
[below
] {$
\mathcal{D
}_x(u)$
} (oracle);
602 \path[offset =
{(
0mm, -
10mm)
}]
603 node
[right = of adv
] {\textbf{?
}}
611 \begin{frame
}<
1-
9>
[label = kem
]{Signing tags
}{Weakly deniably authenticated
612 asymmetric encryption
}
614 \column{0.5\textwidth}
617 \begin{tikzpicture
}[node distance =
5mm
]
619 \node[box = yellow!
20, minimum width =
30mm
] (m)
{$m$
};
622 \node[op = red!
20, below = of m
] (enc)
{$E$
}
624 \node[box = red!
20, minimum width =
30mm +
15pt, below = of enc
]
629 \node[box = green!
20, right = -
0.6pt of c
] (sig)
{$
\sigma$
};
630 \node[op = green!
20, above =
10mm
] at (sig |- m) (s)
{$S$
}
632 \node[above = of s
] {$a'$
} edge
[->
] (s);
635 \draw[->
] (s |- enc) -- (enc);
638 \node[box = green!
20, left =
25mm of s, below
] (t2)
{$
\tau$
};
639 \node[box = blue!
20, above = -
0.6pt of t2
] (b2)
{$B$
};
640 \draw[decorate, decoration = brace
]
641 (b2.north east) -- (t2.south east)
642 coordinate
[pos =
0.5, right =
2.5pt
] (sm);
645 \draw[->
] (sm) -- (s);
648 \node[box = green!
20, left = of t2
] (tag)
{$
\tau$
};
649 \node[box = red!
20, left = -
0.6pt of tag
] (k)
{$K$
};
650 \draw[decorate, decoration = brace
]
651 (k.north west) -- (tag.north east)
652 coordinate
[pos =
0.5, above =
2.5pt
] (z);
653 \node[op = blue!
20, above =
8mm of z
] (kem)
{$
\mathcal{E
}$
}
655 \node[box = blue!
20, left = -
0.6pt of c
] (u)
{$u$
};
656 \draw[rounded, ->
] (kem) -| +(-
10mm, -
8mm) |- (u);
657 \node (b) at (kem -| b2)
{$B$
} edge
[->
] (kem);
660 \draw[->
] (tag) -- (t2);
663 \draw[rounded, ->
] (k) |- (enc);
666 \draw[->
] (b) -- (b2);
670 \column{0.45\textwidth}
671 \setcounter{beamerpauses
}{7}
674 \item<.(
0)->
[Secrecy
] From KEM and symmetric IND-CCA.
675 \item<.(
2)->
[Authenticity
] \alt<-.(
2)>
{Fails!
}{From KEM, symmetric
676 INT-CTXT and KEM non-directability.
}
677 \item<.(
1)->
[Deniability
] Weak deniability from message
\slash signature
684 \begin{frame
}{Signing tags
}{Fixing authentication
}
685 \begin{block
}{What causes the problem?
}
686 \begin{itemize
}[<+->
]
687 \item Signatures don't have to hide the message signed.
688 \item So adversary can discover the tag $
\tau$.
689 \item Might construct KEM clue with known $K$ and copied $
\tau$ --
693 \begin{block
}<+->
{KEM non-directability
}
694 \begin{itemize
}[<+->
]
695 \item Say KEM is $(t, n)$-
\emph{non-directable
} if, given $t$-bit strings
696 $r_0$, $r_1$,
\ldots, $r_
{n-
1}$, and a public key~$X$, it's hard to
697 find a clue $u$ such that the last $t$ bits of $D_x(u)$ match any
699 \item We prove non-directability for a large class of random-oracle KEMs.
700 \item How hard is the Cramer--Shoup KEM to direct?
709 \begin{frame
}{NAIADs
}{What's a NAIAD?
}
710 \alert{N
}on-interactive
\alert{A
}symmetric
\alert{I
}ntegrity
711 \alert{A
}lgorithm with
\alert{D
}eniability.
713 \begin{block
}<+->
{The basic idea
}
714 \begin{itemize
}[<+->
]
715 \item Essentially the asymmetric analogue of a MAC.
716 \item Given: private key, recipient's public key, and message, construct
718 \item Given: private key, sender's public key, message, and tag, verify
720 \item Simulator constructs convincing tags given
\emph{recipient's
}
726 \begin{frame
}{NAIADs
}{Definitions
}
729 \begin{itemize
}[<+->
]
730 \item Key generation: $G()
\to (x, X)$.
731 \item Tagging: $T_x(Y, m)
\to \tau$.
732 \item Verification: $V_y(X, m,
\tau)
\to v
\in \
{0,
1\
}$.
733 \item Simulation: $R_y(X, m)
\to \tau'$.
737 \begin{block
}<only@+-+(
4)>
{Authenticity
}
740 \node[mugshot
] (adv)
{\mugshot{adv.png
}};
742 \node[mugshot
] (alice) at (-
5,
1.5)
{\mugshot{alice.png
}};
743 \node[mugshot
] (bob) at (+
5,
1.5)
{\mugshot{bob.png
}};
744 \draw[offset =
{(
0mm, -
4mm)
}]
745 node
[left = of adv
] {$A$, $B$
} edge
[->
] (adv);
748 \path[offset =
{(
0mm, -
4mm)
}] node
[right = of adv, text width =
40mm
]
749 {New $m^*$, $
\tau^*$ with \\ $V_b(A, m^*,
\tau^*) =
1$
}
753 \draw[offset =
{(
0mm, +
5.5mm)
}, ->
]
754 (adv) to node
[above, sloped
]{$Z, m$
} (alice);
755 \draw[offset =
{(
0mm, +
3.5mm)
}, ->
]
756 (alice) to node
[below, sloped
]{$T_a(Z, m)$
} (adv);
759 \draw[offset =
{(
0mm, +
5.5mm)
}, ->
]
760 (adv) to node
[above, sloped
]{$Z, m,
\tau$
} (bob);
761 \draw[offset =
{(
0mm, +
3.5mm)
}, ->
]
762 (bob) to node
[below, sloped
]{$V_b(Z, m,
\tau)$
} (adv);
766 \begin{block
}<only@+->
{Deniability
}
769 \node[mugshot
] (justin)
{\mugshot{judge.png
}};
771 \node[mugshot
] (bob) at (+
5,
1.5)
{\mugshot{bob.png
}};
772 \draw[->, offset =
{(
0mm, +
4mm)
}, sloped
] (bob) to
773 node
[above
] {$m$
} node
[below
] {$
\tau = T_a(B, m)$
}
777 \node[mugshot
] (robot-bob) at (-
5,
1.5)
{\mugshot{robot-bob.png
}};
778 \draw[<->, offset =
{(
0mm,
5.5mm)
}, sloped
] (robot-bob) to
781 \draw[->, offset =
{(
0mm,
2.5mm)
}, sloped
] (robot-bob) to
782 node
[below
] {$
\tau' = R_b(A, m')$
}
786 \draw[offset =
{(
0mm, -
4mm)
}]
787 node
[left = of justin
]
788 {$a$, $b$
} edge
[->
] (justin);
791 \node[thought = justin.north
] at ($(justin.north) + (
1/
3,
1/
2)$)
798 \begin{frame
}{NAIADs
}{Strongly deniably authenticated asymmetric encryption
}
801 \column{0.45\textwidth}
804 \begin{tikzpicture
}[node distance =
5mm
]
806 \node[box = yellow!
20, minimum width =
30mm
] (m)
{$m$
};
809 \node[box = green!
20, right = -
0.6pt of m
] (tau)
{$
\tau$
};
810 \node[op = green!
20, above = of tau
] (t)
{$T$
} edge
[->
] (tau);
811 \node[above = of t
] {$a'$
} edge
[->
] (t);
812 \node[right = of t
] {$B'$
} edge
[->
] (t);
813 \draw[->, rounded
] (m) |- (t);
816 \draw[decorate, decoration = brace
]
817 (tau.south east) -- (m.south west)
818 coordinate
[pos =
0.5, below =
2.5pt
] (p);
819 \node[op = red!
20, below = of p
] (enc)
{$E$
} edge
[<-
] (p);
820 \node[left = of enc
] {$B$
} edge
[->
] (enc);
821 \node[box = red!
20, minimum width =
30mm +
15pt, below = of enc
]
822 (c)
{$c$
} edge
[<-
] (enc);
826 \column{0.50\textwidth}
828 \begin{description
}[<+->
]
829 \item[Secrecy
] Direct from encryption IND-CCA.
830 \item[Authenticity
] From encryption IND-CCA and NAIAD authenticity.
831 \item[Deniability
] From NAIAD deniability.
835 \begin{block
}<+->
{Other constructions
}
836 \begin{itemize
}[<+->
]
837 \item Use $T_a(B, A')$ as a deniable authentication token
838 \item Use NAIAD in place of signature in `signed tag' construction.
843 \begin{frame
}{NAIADs
}{Instantiations
}
844 \begin{block
}<+->
{Existing techniques
}
845 \begin{itemize
}[<+->
]
846 \item Ring signature, with sender and recipient as the signers.
847 \item Some non-disavowable designated-verifier signatures, e.g.,
[Lipmaa,
851 \begin{block
}<+->
{New technique
}
852 Paper describes a new NAIAD, secure in the random oracle model assuming
853 the difficulty of the computational Diffie--Hellman problem.
857 \begin{frame
}{The end
}
861 \Large Thanks for listening.
863 \Huge \sffamily Questions?