IEEE P1363 Working Group:
Standard Specifications for Public-Key Cryptography

March 16-17, 2000
Technische Universitaet Berlin
Fachbereich Mathematik

MINUTES

Handouts:

* Meeting agenda
* October 1999 meeting minutes (unapproved)
* Unofficial list of working group members prior to March 2000 meeting
* IEEE P1363a / D3 (draft 3)
* "Public-Key Cryptography with Arbitrary Finite Fields," contribution to IEEE
P1363a, by Daniel V. Bailey and Christof Paar
* "Storage-Efficient Basis Conversion Techniques," contribution to IEEE P1363a,
by Leo Reyzin and Burt Kaliski
* Patent assurance letter from RSA Security Inc. to Ari Singer re: U.S. Patent
5,854,759
* "Security of Biased Sources for Cryptographic Keys", draft, by Preda
Mihailescu
* "Doing More with Fewer Bits", from Advances in Cryptology - Asiacrypt '99, by
A.E. Brouwer, R. Pellikaan and E.R. Verheul
* "Proposal to IEEE P1363a", Tatsuaki Okamoto
* "Pintsov-Vanstone Signature Primitives and Message Encoding", by Daniel R.L.
Brown and Don Johnson
* "Pintsov-Vanstone Signature Scheme with Recovery" by Daniel R.L. Brown
(handwritten)


THURSDAY, MARCH 16

In attendance:

*Ari Singer (chair), Pitney Bowes
*Don Johnson (vice chair), Certicom
*Dan Lieman (treasurer), NTRU

Dan Bailey, WPI
Daniel Brown, Certicom
Ernst Giessmann, Deutsche Telekom Berlin
*Burt Kaliski, RSA Laboratories
*David Kravitz, Wave Systems Corp.
Franck Leprevost (host), CNRS-Paris & TU Berlin
Stefan Löwe, Deutsche Telekom Berlin
Preda Mihailescu, ETH Zürich
*Tatsuaki Okamoto, NTT
Martin Rehwald, University of Münster
Holger Reif, Smart Ring
*Allen Roginsky, IBM
Martin Schulze, University of Bonn

An asterisk indicates an eligible voter.

Morning session

1. Approval of Agenda

Singer reviewed the agenda and pointed out two minor clarifications: Kaliski's
presentation Friday on Ben Arazi's signature scheme will be broadened to address
DL/EC signature schemes in general; Victor Shoup's presentation on the Advanced
Cryptographic Engine was given yesterday.

MOTION 1. Approve agenda. (Kravitz, Roginsky, PASSED by acclamation)

2. Approval of Minutes of October Meeting

Singer reviewed the list of working group members, then turned to the minutes.
There were several minor editorial changes and the following clarifications:

* in initial discussion of the P1363a draft, to add that Johnson had mentioned
he would give a submission in the area of inversionless signature schemes;

* in later discussion, to move the "the proposed replacement for the dropped ISO
technique" to PSS-R instead of PSS, and to add that PSS-R will be licensed
according to IEEE requirements but may not be royalty-free.

MOTION 2. Accept minutes as amended (Johnson, Kaliski, PASSED by acclamation)

3. Discuss action items for P1363 document

Singer said he had not yet contacted the Technical Committee on Security and
Privacy about co-sponsorship, but intended to do so. Since the last meeting he
had dealt with a couple patent matters. The list of patent letters is not yet
synchronized with IEEE.

Lieman said that the working group collected $500 at the last meeting and that
he spent $1 opening a new bank account. The old account was still open, and some
money is still due to IEEE. Meeting fee for this meeting will be $10 or DM
21/half day.

Singer indicated that there has been one electronic vote since the last meeting:
the bylaws-required override vote on his appointment of William Whyte as
secretary, which failed by 0-5-0 (i.e., the appointment was confirmed).

RevCom approved the IEEE P1363 document at its January meeting. Several
balloters changed their vote to yes in the final recirculation; the approval
rate increased to 91% from 81%. Some final style edits remain to be done by
IEEE; Jennifer Longman is the editor. She will send a hardcopy to Singer for
review. Kaliski and Johnson each requested copies; Kaliski will forward copies
to Leo Reyzin and Yiqun Lisa Yin.

Several new submissions were received and are posted on the Web page, including
those from Johnson, Bailey, Mihailescu, Kaliski, and Okamoto.

A study group for new public-key standards was established by the Microprocessor
Standards Committee, and met the previous day. Singer had been appointed
chair by Don Wright. The study group is coordinated with P1363 but
operates independently.

P1363a is still on the schedule agreed at the last meeting. Singer confirmed
that the schedule is within the timetable given in the PAR.

On the question of why e = 4 is not allowed in TSH-ESIGN, as raised at the last
meeting, Okamoto indicated that this is to provide a security margin.

All action items mentioned at the end of the last minutes were done, with the
exception that a primary editor has not yet been appointed, and not much has
been done on evaluation criteria for submissions.

Johnson asked whether the working group was deprecating tower fields. Bailey
said that he would address this later, but recommended not to allow GF(2^m) with
m composite (and hence not tower fields) for elliptic curves, in light of recent
attacks.

4. Review of P1363a Draft

Kaliski gave an overview of P1363a draft D3, starting with a status report:

Current content

* DL/EC primitives for SSR - added per ISO/IEC 9796-3
* DL/ECSP-NR, -DSA - added note on precomputation
* DL/ECSSR - added per ISO/IEC 9796-3
* IFSSA - updated to allow additional encoding methods
* IFSSR - updated, to align with ISO/IEC 9796-2
* DL/ECIES - added per ANSI X9.63
* encoding methods, aux. functions - support schemes
* security considerations - support schemes; RNG alternatives

Possible new content
* GF(p^m), tower fields, medium Galois fields - Bailey to present
* inversionless signature primitives - Brown, Kaliski to present
* EPOC1/2 and TSH-ESIGN - Okamato to present
* basis conversion - Kaliski to present
* generating provable primes - Mihailescu to present (if time)

As agreed at the last meeting, a goal of this meeting is to decide whether to
include the first four items on the list. The fifth was not considered
previously.

Kaliski next gave blackboard presentations of the new schemes.

IFSSR / IFSSA with EMSA3. The versions of PSS-R and PSS in these schemes have
been updated to address implementation issues and merged into a single, general
scheme. EMSA3 also provides functionality equivalent to Full Domain Hash, which
now is no longer included as a separate encoding method. Kaliski
described the significant changes as follows:

* message is hashed first without the salt, and the salt is instead applied to
the hash. This makes integration with present applications easier, since there
may not be a convenient place to carry the salt in an application protocol.
While the salt could be recovered from the signature, this may also be
inconvenient if the verifier wants to process the message in a single pass. This
change does not affect the security proof, although it does require that the
hash function is collison-resistant (whereas the previous approach only required
that the hash function is target-collision-resistant). If one is concerned about
the properties of a hash function, in this or another signature scheme, a
separate salt could be combined with the message, independent of PSS or PSS-R.

* salt, length of recoverable message part and hash value are then hashed to
produce hash field of message representative. The length helps with the security
proof.

* padding between salt and recoverable message part is changed to be the same
for message recovery and appendix cases (i.e., 00 00 ... 00 01). (Recoverable
message part is empty in appendix case.)

* header and trailer octets are added to the message representative, to align
with recommendations that have been made by ISO for ISO/IEC 9796-2.

There was significant discussion and several comments. Johnson asked about
whether the lack of an explicit salt length field could lead to a potential
attack. (It is currently a parameter to the encoding method, but is not carried
explicitly, although it is implicitly included via the second hash.) If the salt
length is allowed to vary, it may be better to be explicit. Kaliski said he will
follow up on this.

Kravitz said to be sure that the mask generation function is tightly coupled to
the hash function, if only the hash function is identified.

Johnson also suggested that the header and trailer bytes should not be directly
in the message representative, as they weaken the security proof. Rather, they
should be covered by a mask if possible. Kaliski indicated that the bytes were
there to follow the ISO recommendation, and pointed out that the cc byte (at
least the last two bits of it) is needed for four-way disambiguation in the
Rabin-Williams primitive. A leading 0 bit is also needed to ensure that the
value is less than the RSA modulus. Johnson said he would recommend to ISO not
to put all the header and trailer bytes in the message representative. Kaliski
will follow on this.

DL/ECSSR. Kaliski presented this signature scheme, which is based on ISO/IEC
9796-3. To specify it, three new primitives were introduced in each of the DL
and EC families: PSP-NR and SP-NR2, which split the Nyberg-Rueppel signature
primitive to provide access to the ephemeral public key; and VP-NR2, which also
recovers the ephemeral public key. The ephemeral public key is needed in the new
encoding method. Several issues were discussed; one is that the scheme should be
broadened to include other options in ISO/IEC 9796-3, such the two possible hash
lengths being specified as parameters, and including a hash algorithm ID.
Security considerations are also needed to guide the selection of the hash
lengths.

Johnson observed that in the deterministic alternative where the one-time key
pair is generated as a function of the private key and the message, it is
possible that a message might not have a valid signatures. (This is an extremely
rare event, which would happens only if the resulting c = i + f = 0 mod r in the
signature primitive.)

There was also some discussion about the general model for signature schemes
with message recovery, which was deferred to Friday's session on DL/EC signature
schemes.

DL/ECIES. Kaliski concluded with an overview of this new encryption scheme,
which is based on ANSI X9.63, and is similar to what has been presented
previously. Brown pointed out that the key derivation function currently in
P1363 outputs a fixed-length key, so is not directly suitable for use in this
scheme, which needs a variable-length key. Kaliski said he would check how X9.63
does it.

There were suggestions to broaden the specification to allow other encryption
functions than exclusive-or (perhaps AES). Kaliski suggested that the entire
combination of key derivation, message authentication and encryption could be
replaced with a method that combines the key and the message, the current
combination being a recommended method. This would allow for future alternatives
by adding new methods, rather than changing the scheme. For instance, the IBM
"swizzle" method discussed in previous meetings could be introduced this way.


Afternoon session

5. Review of P1363a Draft (continued)

Kaliski continued the P1363a discussion with a tour of the current draft. It is
written as an update to IEEE P1363 rather than a separate document; he will
confirm with IEEE that this is the appropriate style. In addition to a number of
editorial changes, the working group asked that the following substantive issues
be addressed (in addition to those noted above):

* definition of signature scheme with message recovery (Sec. 3): Johnson said
this is not aligned with the ISO definition.

* DLSP-NR and DLSP-DSA notes (Sec. 6) and corresponding notes in EC section:
Kravitz noted that these might be confusing in the case that the one-time key
pair is generated as a function of the private key and the message. Kaliski will
rewrite and point to Annex D for further discussion.

* DLSP-NR2 and elsewhere: The term "discarded" (in connection with ephemeral
private keys) should be replaced with something more emphatic about the keys
being protected from disclosure.

* general model of signature scheme (Sec. 10): Definition of message recovery,
use of "conveyed" and "transmitted" (regarding the message) should be rewritten
in terms of which values can and can't be recovered from the signature. Also, a
discussion should be added on why one might choose appendix vs. total message
recovery vs. partial message recovery.

* DL/ECSSR: Following up on the comment above about a message possibly not
having a valid signature, Johnson suggested that an alternative be considered to
avoid this situation, like incrementing a counter.

* EMSA3 and EMSR2 (Sec. 12): Reif suggested to merge these specifications into a
common subroutine, since they are intended to be special cases of a more general
format.

* EMSR1: Johnson said that the standard should be clear that a conforming
implementation may claim conformance with EMSR1 for total message recovery but
not partial message recovery.

* Note on precomputation and alternatives random number generation (Annex D)
will be updated to address options and their relationships more clearly. Also,
example methods will be added to Annex A.

* Encoding and key derivation parameters: Text will be added on security
considerations if ephemeral key pair is used more than once.

* Kaliski will also add diagrams to the schemes to help with the exposition.

6. Review of P1363 submission material

6a) Dan Bailey - Arbitrary Finite Fields

Bailey started with a presentation on arbitrary finite fields. IEEE P1363
currently supports GF(p^m) for (typically) large p with m = 1 ("odd
characteristic"), and p = 2 with m > 1 ("even characteristic"). The contribution
defines support for p >= 3 with m > 1, which may have some additional
implementation benefits, for instance in software with p near the maximum value
that can be stored in a word.

He pointed out that an Internet draft by Donald Eastlake and Rich Schroeppel for
protecting the Domain Name Service with elliptic curve cryptography allows
arbitrary finite fields.

Odd-characteristic extension fields are "the rest" of the finite fields, where p
is an odd prime and m is a positive integer. Field elements can be represented
by polynomials with coefficients less than p; field arithmetic is performed
modulo an irreducible polynomial. Some choices of p and m lead to more efficient
implementation than others.

Johnson asked whether there are security concerns with composite m for elliptic
curves, by analogy with GF(2^m) with m composite. Mihailescu and Bailey
indicated that this may be the case.

Optimal extension fields are a special class of odd-characteristic extension
fields. The design principles are as follows:

* p should be close to the maximum value that can be stored in a processor word,
for fast subfield multiplication (many CPUs are highly optimized for this
operation)

* p = 2^n +- c for "small" c, for fast subfield modular reduction

* there should be an irreducible binomial mod p, x^m-\omega, for fast
polynomial reduction. (\omega=2 is very nice, since multiplying by \omega is
just a shift.)

Mihailescu commented that there are also some advantages in exponentiation for
these fields.

Elliptic curve cryptosystems are the same as presently in IEEE P1363 for p > 3.
For p = 3, there are slight differences.

Even composite fields are finite fields with p = 2 and composite m. These are
attractive for implementation if operations are performed in a subfield GF(2^r)
where r divides m, but Gaudry, Hess and Smart have recently given a severe
attack. To compensate, key lengths have to grow large enough to cancel any speed
gains (e.g., to m > 512 for equivalent security to ordinary 160-bit curves).
(Currently, the attack doesn't apply if the coefficients of the curve are in the
subfield, and it doesn't extend to odd p.)

Bailey recommended to prohibit even composite fields for elliptic curve
cryptosystems, just as supersingular curves are prohibited. An alternative is to
allow composite fields and give a warning about the attack. Even composite
fields would still be appropriate for discrete logarithm systems and would also
be useful for new systems such as XTR.

Johnson asked for an update to IEEE P1363, before publication, to mention the
new attack.

Mihailescu observed that for DSA, p^m-1 should be divisible by a 160-bit
prime r. However, if p is selected with the form p = 2^n +- c for small
c, then p^m-1 will need to be factored to find r. This may only be
efficient for some values of p, and means that p^m-1 will probably have
small factors as well. (In contrast, for m = 1, r can be selected first,
then p generated so that p is prime and p-1 is divisible by r, but here
there might not be a p such that p^m-1 is divisible by a pre-selected
r.)

Bailey continued with an overview of his and Christof Paar's contribution to
IEEE P1363a. It includes the following:

* Section 5: definitions of even composite fields and odd characteristic
extension fields, with new conversion operations for odd characteristic
extension fields. (Johnson said that the conversion algorithm to an octet string
should specify the length of the octet string.)

* Sections 6 and 7: edits to allow GF(p^m) for p >= 3 and m > 1.

There was some discussion on whether there is sufficient confidence in the new
fields to add them to IEEE P1363a. While no specific attacks are suspected,
Mihailescu suggested that the distribution of prime factors of p^m-1 should be
evaluated. Johnson said that GF(2^m) has a better foundation, given that it has
been studied longer, and NIST supports GF(2^m) in its recommended elliptic
curves.

Singer also pointed out that there are also some products supporting GF(2^m),
such as those from Certicom. Bailey said that NTT has products supporting the
new fields. Kaliski commented that since the working group asked Bailey to
prepare this submission, but had not previously raised these security concerns,
it would be fair to give the submission serious consideration. Mihailescu
offered to prepare a (short) list of research questions to be addressed to make
the submmission acceptable.

Additional information on the finite field methods is available from
http://ece.wpi.edu/Research/crypt.



FRIDAY, MARCH 17, 2000

In attendance:

*Ari Singer (chair), Pitney Bowes
*Don Johnson (vice chair), Certicom
*Daniel Lieman (treasurer), NTRU and Univ. of MO
 Dan Bailey, WPI
Daniel Brown, Certicom
*Burt Kaliski, RSA Laboratories
*David Kravitz, Wave Systems Corp.
Franck Leprevost (host), CNRS Paris
Stefan Löwe, Deutsche Telekom Berlin
Preda Mihailescu, ETH Zürich
*Tatsuaki Okamoto, NTT
Martin Rehwald, University of Münster
Holger Reif, Smart Ring
*Allen Roginsky, IBM


Morning session

Singer began with a roadmap for the day:

8:00-8:30 Discuss content of submissions - Singer
8:30-9:00 Finish review of arbitrary finite fields - Bailey (6a)
9:00-9:30 Storage-efficient basis conversion - Kaliski (6b)
9:30-10:30 EPOC and ESIGN - Okamoto (7a)
10:30-11:30 PV signatures - Brown (7b)
11:30-12:00 Signature schemes - Kaliski (7c)
12:00-1:00 Lunch and payment of meeting fees - Lieman
1:00-1:30 Prime generation - Mihailescu (new)
1:30-2:00 Discussion of future plans and registry idea - Singer
2:00-3:00 Discuss inclusion criteria - Singer
3:00-5:00 Discussion and votes on final inclusions - Singer
  1) arbitrary finite fields 2) signature schemes 3) EPOC & ESIGN 4) basis
conversion 5) prime generation?
5:00-5:15 Wrap-up

Singer then presented questions to be asked for any submission:

1) What are the claimed attributes? Advantages?
2) Are these attributes provable? Under what assumptions?
3) Is there currently or has there been other standardization work on the
techniques in this submission?
4) What are the current known usage and usage history of the techniques in this
submission?
5) What is the perceived value of standardizing these techniques?
6) What is the current body of work on this submission?
7) What are the best known attacks/exploitations?
8) How much scrutiny have the techniques received in the context intended for
standardization?
9) Can the techniques be "relatively easily" integrated into the standard?
10) What is the known patent status of the submission techniques?
11) What are the tradeoffs?

6a) Dan Bailey - Arbitrary Finite Fields

Singer then gave specific questions about arbitrary finite fields (p > 2, m >
1), which Bailey answered:

1) Where are finite fields not currently allowed in P1363 being used? Which are
being used the most?

NTT is using OEFs. Tetsutaro Kobayashi suggested these techniques to the working
group at Crypto '99. It is used in the elliptic curve case the most. It is not
clear which particular fields are used. Okamoto said this is done in an
experimental product.

2) What is the work that forms the basis of confidence in the use of these
fields?

A FSE '97 paper by Mihailescu and several subsequent papers address the EC
setting. "Doing More with Fewer Bits" from Asiacrypt '99 and ?Using Cyclotomic
Polynomials to Construct Efficient Discrete Logarithm Cryptosystems over Finite
Fields? by Arjen K. Lenstra from Australasia Conference on Security and Privacy
deal with the DL setting.

3) For which 1363 techniques do we have experience with using these fields?

Both EC and DL settings.

4) What is the estimated work factor for generating DL parameters of
"recommended sizes"?

Bailey said it is an "easy problem" based on cyclotomic polynomials and trial
division, and that he will provide pseudocode. Mihailescu said that it is not
clear how long it would take to find such a polynomial, in terms of what can be
proved about probabilities. Bailey said he would also provide a table of DSA
parameters. Canonical generation is an item for further research.

5) What evidence is there that DL schemes using these fields are secure?

Johnson said that Dan Gordon's rump session presentation on "cooking DSA
parameters" should be considered.

6) Has significant work been done to analyze the security of elliptic curves
over GF(p^m) where p > 2, m composite?

Mihailescu's paper was presented in FSE '97, and Bailey's at Crypto '98. The
authors of the new result of GF(p^m) with p = 2 and m composite indicate in
their paper that it cannot be extended to p > 2.

7) Is there a greater concern of small subgroup attacks on elliptic curves over
these fields?

A problem for later inclusion.

8) What are the known weaknesses of using these fields?

Bailey said that there are no known weaknesses. Johnson pointed out
again that Dan Gordon's paper should be considered.

He also addressed the first set of questions. Regarding patents, Mihailescu has
a patent application pending, and is submitting a letter of assurance to the
chair.

6b) Burt Kaliski - Storage-Efficient Basis Conversion Techniques

Kaliski gave a blackboard presentation of a submission to P1363 Annex A on basis
conversion involving only O(m) storage, as opposed to the O(m^2) storage for the
method currently in Annex A. Johnson suggested that simple examples be added;
Kravitz observed that the conversion factors need to be protected from
modification (just like the matrix in the current algorithms). Kaliski then gave
a brief overview of the submission.

7. Review of P1363 submission material (continued)

7a) Tatsuaki Okamoto - EPOC and ESIGN

Okamato began with a discussion of the history of ESIGN and EPOC. ESIGN is
fairly old and is in the ISO 14888 standard. EPOC is fairly new and is based on
a new encryption function as secure as factoring numbers of the form p^2q. It
also uses a new method for converting a trapdoor function to a encryption scheme
that is secure in the strongest sense (presented at PKC '99 and Crypto '99). He
said the method is preferable to OAEP, which assumes the trapdoor is a
permutation, and to DHIES, which applies only to Diffie-Hellman.

According to Okamoto, several researchers have studied the problem of factoring
p^2q by the elliptic curve factoring algorithm. The improvements over the
traditional solutions have been minor, and are still less efficient than the
Number Field Sieve. Boneh et al.'s attack for moduli of the form p^rq works only
if r is large (>= sqrt(log p)).

Okamoto then gave an overview of the submission to P1363a, which consists of new
primitives and schemes to support EPOC and ESIGN.

The problem of computing approximate e-th roots modulo a composite is
essential to the security of ESIGN. (This is the problem of computing y
such that y^e is approximately equal to x modulo the composite.) Okamoto
reviewed the status of the security. He noted that computing individual
bits of the e-th root (with probability significantly better than 1/2)
is as hard as computing all bits, by a recent result of Hastad and
Naslund. Computing approximate e-th roots does not have a similar
result, but he conjectured that one could be obtained. ESIGN is much
more efficient than RSA.

NTT has agreed to grant royalty-free licenses to ESIGN and EPOC if included in
IEEE P1363a.

Lieman suggested that there should be some additional security considerations
about different properties between factoring (p^2).q and pq, given that the two
kinds of numbers have different properties that may eventually lead to an attack
for one kind but not the other.

7b) Daniel Brown - Pintsov-Vanstone Signatures

Brown gave a presentation on his submission with Johnson. He started by pointing
out some limitations in the present DL/ECSSR. For instance, DL/ECSSR may have a
larger overhead than desirable, and it does not take advantage of redundancy
that may already be present in the message. The scheme was originally designed
for digital postage and is optimized for constrained environments. It offers
provable security in several models.

He suggested that the PV scheme could either replace the DL/ECSSR scheme, or be
added as an alternative.

One area that may be difficult to standardize is the natural redundancy - how
the signer and verifier agree on how to check it.

There was also some discussion on changing the padding rules for EMSR-PV.

Reif observed that before this scheme, the signature schemes in P1363 had a
"green" or "red" light - a signature could be verified without checking the
message for internal redundancy. An implementation would have to check for
redundancy in this scheme. Brown said that the redundancy check could be part of
the scheme. However, this would have to be specified.

Brown also gave a sketch of the security proof for the PV scheme. Bailey raised
some issues about the impact of weak keys if DES is the underlying encryption
function; this needs to be addressed further.

Kravitz asked whether the Schnorr patent might be relevant. Johnson said
Certicom had no comment. There is a patent pending by Pintsov and Vanstone.

7c) Burt Kaliski - Discrete Logarithm Schemes

Kaliski gave some brief comments on the specification of digital signature
schemes. He proposed a new model where the signature operation has two inputs,
in addition to the private key: the recoverable message part, M1, and the
non-recoverable message part, M2, and one output: the signature. The
verification operation has two inputs, in addition to the public key: the
signature and the non-recoverable message part, and one output: either the
recoverable message part or "invalid". The correspondence between the message
parts and the actual message is left to the application. This is different than
the current model where the signature operation selects M1 and M2.

The three types of signature scheme fit into this model as follows:

* appendix: M1 null
* total recovery: M2 null
* partial recovery: the rest

Kaliski next suggested a new way to evaluate signature schemes. Rather than
comparing signature schemes with appendix with one another, and separately
comparing signature schemes with message recovery, one could compare all
signature schemes according to several attributes:

* transparency - how much of the message remains in the clear
* overhead (bandwidth) of the signature
* flexibility in terms of supporting different lengths
* security and efficiency as usual.

In this way, a signature scheme with appendix can be compared with a signature
scheme with message recovery. For instance, they may have similar overhead and
the signature scheme with appendix might have transparency (e.g., Schnorr
signatures with a half-size hash), but with a tradeoff in one security attribute
(signer's ability to generate two messages with the same signature).

He also presented an alternative signature scheme proposed by Ben Arazi. The
usual signature operation has the following steps:
* generate ephemeral (u,v)
* convert v to an octet string I
* compute d = u - Hash (M, I) * s
* output (Hash, d)

Arazi proposes replacing the last two steps with the following:
* compute d = Hash (M, I) * u + s (where s is signer's private key)
* output (v, d)

The advantage of Arazi's alternative is that s is a "free addend" - it is not
multiplied by anything. This is helpful in the chained-certification methods he
has previously proposed to the group. It is not clear what patents may apply to
this signature primitive (which is a separate issue from patent coverage on the
chained-certification methods).


Afternoon session

7d) Preda Mihailescu - Prime Generation

Mihailescu gave an overview of prime generation, including constructive
techniques where a prime is generated together with a proof of primality, then
discussed biased key sources, based on his paper distributed at the meeting.

10. Discussion of future activities of P1363 working group  (moved up)

Singer brought up the idea of a future "registry" of public-key algorithms,
which had been proposed at the study group meeting. He asked for working group
feedback. If the working group supports it, the group may need to revisit the
timing for P1363a.

The P1363 document is somewhere in the spectrum between having a "best" method
for each purpose, and many "good" methods. P1363a will move further toward the
"good" end, but not all the way. The registry will provide a vehicle to document
more "good" methods, without having to collect them into an addendum. This will
make the process more incremental.

The registry would list criteria that are important to understand for each
submission. The current P1363 document is not as explicit about these criteria,
and the user has to read the security considerations carefully.

Lieman commented that the process is easier from various perspectives: algorithm
inventors, the working group, and users. Singer expects this to generate a lot
of interest from cryptographers. Bailey gave an analogy to a journal with a
defined call for papers.

Singer observed that there seemed to be general consensus that the registry
option is worth exploring. An important issue is how this affects the timing of
P1363a and other projects. Lieman said he intends to work some of the registry
concepts into the "new families" project. Kaliski will provide an example of a
registry entry for the next meeting.

Singer then turned attention to upcoming meetings. The August meeting (after
Crypto) will focus on the criteria for registry entries. The proposed dates for
the next meeting are May 31 - June 2 or alternatively June 7-9; Lieman will
host. Possible locations are Boston and Toronto. Singer will follow up with
participants by e-mail. Okamoto offered to host a meeting at the end of
November, before Asiacrypt.

8. Discussion of inclusion criteria for techniques

Singer reviewed the 11 criteria presented earlier in the day, in preparation to
apply them to the submissions. He said that the working group could formalize
them at the next meeting. In the meantime, he will circulate them to the mailing
list.

On the subject of "best known attacks", Leprevost noted that P1363 did not say
anything about quantum computing. Bailey pointed out that one might also
consider fault analysis attacks, but since there are many alternatives, it may
be difficult.

Singer then turned to the list of specific questions for encryption scheme.
Based on group discussion, the code-size question (#5) was removed, because it
is difficult to judge. There was also some discussion on comparing efficiencies
of operation, which can be difficult in many cases. Bailey said the group should
leave the statement to the submitter, subject to working group review. However,
the general sense was not to publish actual performance figures, since they are
unreliable. Singer added a new question, "Is it parallelizable?"

Kaliski suggested that in the registry, some answers may be very brief in
tabular form, and others may be more elaborate, such as example algorithms. The
more elaborate answers could address implementation considerations in more
detail.

9. Discussion of final inclusions to P1363a

1) Arbitrary finite fields.

Bailey recommended that all finite fields be allowed, with the exception of even
composite fields in the EC case, modulo the comments on security requested by
the working group.

Singer noted that the working group has the responsibility to report the new
attack on even composite fields. The attack will be announced on the Web site.
The working group will discuss at the next meeting how to update EC domain
parameter handling in P1363a to avoid the attack.

Comments to be considered include:

* compelling reason for including odd composite fields in the EC case
* Dan Gordon's attack on "cooked" parameters
* which schemes can be used with OCEFs
* support of DSA parameter generation for 160-bit primes, canonical methods

MOTION 2. Accept the arbitrary finite fields contribution with the restrictions
and comments noted. (Kaliski, Johnson, PASSED 5-1-0)

Roginsky, who opposed the vote, said he believed the contribution needed more
study, and that he felt the decision should have waited until the next meeting.

2) Signature schemes.

This came from the previous intent to add inversionless signature primitives.
DL/ECSSR is already included, and is inversionless; however, there is interest
in alternate approaches, of which Arazi's suggestion is one possibility, and the
PV scheme is another.

Kravitz asked whether the intent is for inversionless operation by the signer,
the verifier, or both; this wasn't clear.

Kravitz also pointed out a potential forgery method attack involving 2^56
operations if DES is the encryption function. Johnson said this can be addressed
as a security consideration, where one would select components meeting a certain
security level, such as a 160-bit hash, 160-bit elliptic curve, and 80-bit
symmetric algorithm.

Kaliski said he felt that the PV submission, although useful, was new and needed
some improvements to fit into the P1363a model. For instance, the PV primitives,
as specified, include more than just mathematical operations, which would be the
P1363 norm for primitives. He said that the specification does not yet appear to
be stable. The benefits seem to be the very low overhead (although other schemes
come close, such as Schnorr with the half-length hash); and the opacity
(non-transparency) of the transmitted message.

Handling natural redundancy was also pointed out as a concern.

Singer asked what course to take: whether to instruct the submitters to try to
satisfy the working group's questions for the next meeting, or to say that it's
too late for the P1363a schedule. He said that if the working group feels it
belongs in the document, it should be included, as long as it does not delay the
development of the standard.

MOTION 3. Include the PV scheme in the standard, on the condition that the
material is agreed upon within the schedule for the development of the standard.
(Johnson, Roginsky, PASSED 5-1-0)

(Kaliski opposed for the reasons indicated above.)

3) EPOC & ESIGN.

Johnson asked that A.16.13 and A.16.14 (key generation methods) be specified.
The security considerations section should give additional detail about the
differences between pq and p^2q factorization. The mathematical operations
should be moved into primitives.

MOTION 4. Include the EPOC1, EPOC2 and TSH-ESIGN schemes into P1363a, with the
provisions noted in the paragraph above. (Okamoto, Johnson, PASSED 6-0-0)

4) Basis conversion.

Some examples need to be added. Johnson said he liked the idea but noted that
any methods, including this one, may be subject to further refinement. Singer
said that it's easier to add number-theoretic algorithms than schemes, since
they're informative. Mihailescu suggested that conversion methods for odd
extension fields might be useful, but pointed out that since there is not as
much variability in the choice of basis for such fields, conversion methods are
not as important.

Johnson expressed concern that users might not be aware of the patent status of
this method, given that most of Annex A is unpatented.

MOTION 5. Include the basis conversion submission into P1363a. (Kaliski,
Roginsky, PASSED 6-0-0)

5) Prime generation.

Kaliski suggested that if constructive prime generation is to be added, at least
the methods in ANSI X9.80 should be included. Perhaps Mihailescu's method can be
cast as a generalization of the ANSI X9.80 methods; Mihailescu will investigate
this.

Johnson said it would be useful to include a discussion of how much
variability is added at each step. A note should be included to this effect.

Mihailescu also suggested adding an algorithm for primality proving. He will
check ANSI X9.80 for this as well.

MOTION 6. Request Mihailescu to review ANSI X9.80 methods for possible inclusion
in IEEE P1363a and to report at the next meeting. (Kaliski, Roginsky, PASSED
6-0-0)


In closing, Okamato gave some comments on the security of DL/ECSSR. He said that
the hash should be applied to the value c (defined as i + f mod r) to obtain a
proof. Also, it may be a problem that an attacker can directly control part of
the message representative f, and thereby control part of the value of c. This
kind of influence led to problems in ISO/IEC 9796-1 and -2. However, Kaliski
observed that the equation d = u - sc conceals information about s, since u is a
one-time private key (this is standard with proof of knowledge protocols of this
form). Okamato replied that he had encountered difficulties in previous proofs
based on this equation. He recommended instead to mask M before including it in
the message representative, and to hash the value c in the equation. The value
of i is not hashed with m in this case. The result was presented at Asiacrypt
'99.


11. Adjourn

MOTION 6. Thank the host and the university for accommodations (Kaliski,
Johnson, PASSED by acclamation)

The following people have satisfied attendance requirements for this meeting:

Allen Roginsky, Ari Singer, Burt Kaliski, Dan Lieman, Tatsuaki Okamoto David
Kravitz, Don Johnson, Dan Bailey, Daniel Brown, Franck Leprevost, Holger Reif,
Martin Rehwald, Preda Mihailescu, Stefan Löwe, Martin Schulze, 
Ernst Giessmann

MOTION 7. Adjourn. (Johnson, Kaliski, PASSED by acclamation)