\documentclass[11pt]{article}


\title{ {\Huge ROUGH DRAFT} \\
        A Rough Sketch of a Simple Group Membership System }
\author{Chris Laas}
\date{June {42}, 2000}

\pagestyle{myheadings}
\markright{Chris Laas \hfil A Rough Sketch of a Simple Group Membership System}





\def\H{\mathcal{H}}

\def\Sign{\mbox{\it Sign}}
\def\Verify{\mbox{\it Verify}}


\usepackage{amsmath}
\usepackage{amsfonts}
\DeclareMathSymbol{\Z}{\mathalpha}{AMSb}{"5A}
\def\Zp{\Z_p}
\def\Zps{\Zp^*}
\def\Zq{\Z_q}
\def\Zqs{\Zq^*}
\def\inr{\in_\mathcal{R}}






\begin{document}
\maketitle

{\center \small
 \verb|$Id: basic-group.tex,v 1.1 2000/07/19 06:55:33 golem Exp $|}



\section{Introduction}




\section{System initialization}

Before system initialization time, the following algorithms are agreed upon:
\begin{itemize}
\item A signature scheme $(\Sign_{sk}, \Verify_{pk})$ for the CA (e.g. DSA)
\item A collision-intractable hash function $\H: \Zqs \to \Zqs$ (e.g. SHA)
\end{itemize}

At system initialization time, the CA generates the following values:

\begin{itemize}
\item A key pair $(sk, pk)$ for the aforementioned signature scheme
\item Large primes $p$, $q$ such that $q$ divides $p-1$.
\item A generator $g \in \Zps$ of order $q$ (i.e. $g^q = 1 \mod{p}$)
\end{itemize}

Programmed into each device at initialization are the following parameters:

\begin{itemize}
\item $\Verify_{pk}$ and the CA's public key $pk$ (which may be
updated by a key management protocol external to this document)
\item $\H$
\item $p$, $q$, $g$
\end{itemize}

In addition, registration of individuals with the CA is assumed to be
an external operation and is not addressed here, although it may
become part of the system in further drafts.  It is assumed that
individuals can prove their identity and that each has a unique
identifier $I$.



\section{Group creation and destruction}

To create a group, a party submits a signed request to the CA
containing the following information:
\begin{itemize}
\item Proof of authorization to create a group (the form of which is
external to this specification)
\item The group's owner (which may be an individual, another group, or
an external party)
\item A list of initial members (individuals or groups)
\item A list of verifiers (``interested parties'', such as door locks)
\item A ``key resynchronization interval'' $\ell$, which should be
greater than the number of days expected until a new group public key
sequence is started.  (This may be a system parameter.  Currently I'm
unsure how to bootstrap the public key sequences other than by
e.g. publishing a hash fingerprint in a newspaper, which is silly.)
\item Any auxiliary information
\end{itemize}

The CA checks the signature and the authorization status of the
signator.  If it accepts, the CA generates a unique group identifier
$G$, which it stores along with the creation request.  It then
generates a random value $x_\ell \inr \Zqs$ not equal to 1, and stores
those in the database along with $G$.  ($x_\ell$ is a CA secret key.)
The value $x_0 = \H^\ell(x_\ell)$ is computed, and the value
$h_0 = g^{x_0} \mod p$ is published as the initial public key for the
group: it might be printed in a newspaper, or submitted to a
third-party timestamping service, etc.  (Needs further work.)

To destroy a group, the owner submits a signed destruction request,
and the CA marks the group as destroyed.  The CA may remove the group
from the active database and put the records in cold storage, but the
group identifier $G$ should never be reused.



\section{Addition and removal of members}

To add or remove a member, the group owner simply submits a signed
request to the CA, which updates the database.  The affected
individual may be notified by the group owner, the CA, or by some
other out-of-band means.  No further action need by taken by the CA
until the individual requests certificates.

There is no CRL mechanism to allow revocations to take effect before
the current batch of ``day'' certificates expires.  (This is the goal
of the ``enhanced'' mechanism I'm working on.)





\section{Group membership certificate issuing protocol}

To obtain certificates for day $k$, an individual Alice establishes an
encrypted, authenticated channel with the CA Carol, and requests
certificates for a group $G$.  The protocol proceeds as follows:
\begin{enumerate}
\item After checking that Alice (identified by $I$) is in $G$, Carol
generates the following values:
  \begin{itemize}
  \item $x_k = \H^{\ell-k}(x_\ell)$
  \item $h_k = g^{x_k} \mod p$
  \item $\sigma_k = \Sign_{sk}(G ; k ; h_k)$
  \end{itemize}
Carol sends $(x_k ; h_k ; \sigma_k)$ to Alice.
\item Alice checks the following relations:
  \begin{itemize}
  \item $x_{k-1} = \H(x_k)$, or, if $x_{k-1}$ is not known,
        $h_0 = g^{\H^k(x_k)}$
  \item $h_k = g^{x_k} \mod p$
  \item $\Verify_{pk}(\sigma_k, (G ; k ; h_k))$
  \end{itemize}
  Alice accepts if all three are true.  
\end{enumerate}

The first and second checks ensure that the CA could not attempt to
make members of the group distinguishable by giving them different
public keys.  (For this to work, members of the group must compare
public keys at some point to ensure that the CA is not cheating.  One
way to accomplish this might be for a new member to obtain a $x_k$
from an old member, but this is not very practical; this part is a
flaw in the system, and needs further work.)  The third check verifies
the CA's signature on the certificate's public key $h_k$.

Alice stores $(G ; k ; h_k ; \sigma_k ; x_k)$ as the certificate for
the day.





\section{Interactive proof of membership}

To prove membership in the group $G$, Alice first shows the
certificate $(G ; k ; h_k ; \sigma_k)$ as proof that $h_k$ is the
day's public key for $G$; then, Alice proves knowledge of a value
$x_k$ such that $h_k = g^{x_k} \mod p$.





\section{Flaws in this system}

\begin{itemize}
\item
It's not clear how to establish veracity of public-key 0-token $h_0$.

\item
Revocation has to wait till certificates expire.  Especially, in case
of key compromise, there is no way to selectively revoke the
certificates of individuals.

\end{itemize}


\section{Possible modifications}

\begin{itemize}
\item
Put some subset of $p, q, g$ in the short-lived ``day''
certificate.

Pros: additional flexibility, especially if those values are
compromised (turn out to be weak).

Cons: larger certificates; the protocols become more complex.  Also,
this is tricky because it must be possible for group members to verify
that each member gets the same values.

\end{itemize}



\end{document}