X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/tripe/blobdiff_plain/56abd1c0e98f874fe0863db3417ea02eee073f53..8c3ad0db9eeb6f48b31e429d315a18f94e9d6eb8:/doc/tripe-protocol.tex

diff --git a/doc/tripe-protocol.tex b/doc/tripe-protocol.tex
index d03a4b1c..2ab00155 100644
--- a/doc/tripe-protocol.tex
+++ b/doc/tripe-protocol.tex
@@ -117,23 +117,22 @@ In addition, there are a few minor subprotocols for various special effects.
 
 \subsection{Operations} \label{sec:dh-group.ops}
 
+An \emph{encoding} on some set of values $S$ is defined by a pair of
+operations \id{enc} and \id{dec}, as follows.
+\begin{itemize}
+\item Given a value $x \in S$, $\id{enc}(x)$ encodes it as an octet string.
+\item Given an octet string $a$, $\id{dec}(a)$ parses and decodes a value $x$
+  and remainder string $a'$ from it.
+\end{itemize}
+Hence, the possible encodings of values form a prefix-free set of strings.
+Furthermore, if $a'$ is any octet string, and $x \in S$ is any value, then it
+must be the case that $x, a' = \id{dec}(\id{enc}(x) \cat a')$.
+
 A \emph{Diffie--Hellman group} consists of a pair of sets $S$ and $G$, of
 \emph{scalars} and \emph{group elements} respectively, a distinguished
 \emph{generator} element $P \in G$, and a number of operations on these
 groups.  In the following descriptions, $x$ and $y$ are scalars; $X$, $Y$,
 and $Z$ are group elements; and $a$ and $a'$ are octet strings.
-
-An \emph{encoding} of group elements is defined by a pair of operations
-\id{enc} and \id{dec}, as follows.
-\begin{itemize}
-\item Given a group element $X$, $\id{enc}(X)$ encodes it as an octet string.
-\item Given an octet string $a$, $\id{dec}(a)$ parses and decodes a group
-  element $X$ and remainder string $a'$ from it.
-\end{itemize}
-Furthermore, if $a'$ is any octet string, and $X$ is any group element, then
-it must be the case that $X, a' = \id{dec}(\id{enc}(X) \cat a')$.  Encodings
-of scalars are defined similarly.
-
 \begin{itemize}
 \item $\id{dh}(x, Y)$ calculates a group element $Z$.  To be a proper
   Diffie--Hellman group, it must be the case that $\id{dh}(x, \id{dh}(y, P))
@@ -144,13 +143,30 @@ of scalars are defined similarly.
 \item $\id{enc-ge-public}$ and $\id{dec-ge-public}$ together define an
   encoding on group elements, for which no special properties are required.
 \item $\id{enc-ge-secret}$ and $\id{dec-ge-secret}$ together define an
-  encoding on group elements where all encodings have the same length.
-\item $\id{enc-ge-hash}$ and $\id{dec-ge-hash}$ together define an
-  encoding on group elements where all encodings should have the same length.
+  encoding on group elements where all encodings have the same length, except
+  with negligible probability.
+\item $\id{enc-ge-hash}$ and $\id{dec-ge-hash}$ together define an encoding
+  on group elements where all encodings \emph{should} have the same length,
+  except with negligible probability.\footnote{%
+    The existence of groups without (mostly) fixed-length hashing encodings
+    is a historical mistake.  If a variable-length encoding is used here,
+    information about group element(s) being hashed may leak to an adversary
+    through timing channels.} %
+  The decoding operation is never invoked, so it need not be possible to
+  implement it efficiently, though it must be theoretically possible to
+  decode encodings unambiguously.
 \item $\id{enc-sc}$ and $\id{dec-sc}$ together define an encoding on scalars,
   where all encodings have the same length.  Let $\id{scsz}$ be the length of
   an encoded scalar.
 \end{itemize}
+In the following descriptions, decoding functions are not described explicitly
+Decoding operations must validate input sufficiently that the $\id{dh}$
+operation can be performed successfully and without leaking secret inputs
+during the computation; but it is \emph{not} necessary to perform further
+precise verification.  For example, an implementation need not verify that an
+incoming group element is actually within the subgroup generated by $P$; and
+an elliptic-curve group need not verify that an incoming pair of coordinates
+actually correspond to a point on the curve.
 \begin{aside}
   In an ideal world, we would only have one group-element encoding rather
   than three.  The present situation is caused by unfortunate historical
@@ -245,7 +261,9 @@ $g \ne 1$ be an element of $\gf{p}^*$ such that $g^q = 1$.  The cyclic
 subgroup $G \subseteq \gf{p}^*$ generated by $g$ is a \emph{Schnorr group};
 the scalars are the finite field $S = \gf{q}$; and the generator is $P = g$.
 \begin{itemize}
-\item The Diffie--Hellman operation is given by $\id{dh}(x, Y) = Y^x$.
+\item The Diffie--Hellman operation is simply exponentiation in $\gf{p}$,
+  given by $\id{dh}(x, Y) = Y^x$.
+\item 
 \end{itemize}
 
 
@@ -261,6 +279,6 @@ the scalars are the finite field $S = \gf{q}$; and the generator is $P = g$.
 
 %%%----- That's all, folks --------------------------------------------------
 
-%  LocalWords:  TrIPE LaTeX encodings endian monic OSP VOSP
+%  LocalWords:  TrIPE LaTeX encodings endian monic OSP VOSP TrIPE's
 
 \end{document}
