OCTOBER 1999 P1363 MEETING MEETING SUMMARY D11 had passed by an even larger margin than D9 had, however due to ballot comments, the working group had voted to remove the encoding method "EMSR1" and the signature scheme with message recovery "IFSSR" prior to the meeting. We reviewed the ballot comments on P1363-D11 and agreed on appropriate changes to the draft as well as the ballot response. The group agreed that we should re-circulate the latest version of the P1363 draft in November so that it could be submitted to RevCom by the December 17th deadline for review in January. The working group reviewed the first draft of P1363a for content and structure. The content of the document was approved and a list of requested additional supporting material was created. We agreed to hold a vote at the March meeting to limit the content of P1363a to the material that is sufficiently ready for inclusion at that meeting. We agreed not to include material in P1363a that was not already in the current draft or on the list of requested supporting material. We formalized a schedule for the development and completion of P1363a. The group heard presentations on the security properties of TSH-ESIGN and EPOC, and on NTRU. We discussed the possibility of supporting new projects based on topics such as identification schemes, key validation and new families of public-key cryptosystems. We agreed that the Chair should investigate the formation of a study group for new projects. Jerry Solinas was named Webmaster for the group, replacing Leo Reyzin. RECORD OF ELECTRONIC VOTES HELD PRIOR TO THE MEETING IEEE P1363 E-MOTION 1999-2: Remove IFSSR, EMSR1 and all related text from the IEEE P1363 draft. E-voting opens: Thursday, September 2, 1999, 5:00pm EST E-voting closes: Sunday, September 12, 1999, 5:00pm EST Eligible e-voters (as of September 1, 1999): Allen Roginsky; Anand Rajan; Ari Singer; Ben Arazi; Burt Kaliski; David Kravitz; Don Johnson; Franck Leprevost; Jerry Solinas; Louis Finkelstein; Michael Markowitz; Rich Schroeppel; Roger Schlafly; Tatsuaki Okamoto; Terry Arnold; William Whyte Result: Passed (11-0-0) IEEE P1363 OFFICER ELECTIONS (1999) Candidates for two-year terms starting October 15th of the voting year, or the beginning of the first meeting after the election, whichever comes first: Chair: Ari Singer Vice Chair: Don Johnson Treasurer: Dan Lieman E-voting opens: Friday, September 24, 1999, 5:00pm EST E-voting closes: Monday, October 4, 1999, 5:00pm EST Eligible e-voters: same as directly above. Result: Chair: Ari Singer (9) Vice Chair: Don Johnson (8), abstain (1) Treasurer: Dan Lieman (9) MEETING MINUTES Wed. Oct. 27, 1999 Trumbull Marriott Merritt Parkway, Augusta Room We started at 8:30 am. We had in attendance: Dan Bailey Don Johnson* Burt Kaliski* Tetsutaro Kobayashi* David Kravitz* Daniel Lieman* Leo Reyzin Ari Singer* Jerry Solinas* Yiqun Yin (by phone) An asterisk indicates an eligible voter. Motion 1: Approve agenda. (Solinas, Johnson, 7-0-0) Solinas was named Acting Secretary for Wednesday and for Thursday morning. The minutes were reviewed. There was some question of the accuracy of the list of eligible voters. It was decided that the Chair would maintain the active list and discrepancies cleaned up. Several minor corrections were made. The meeting summary was reviewed. Several minor corrections were made. Motion 2: Approve minutes and summary. (Lieman, Solinas, 7-0-0) The new officers were introduced. Ari Singer, Chair Don Johnson, Vice Chair Daniel Lieman, Treasurer The offices of Secretary and Primary Editor are still open. Solinas was named Webmaster. ==== Chair Report: Various IEEE documents were transferred from the old Chair, Burt Kaliski, to the new Chair. Kaliski and Singer discussed the ballot resolution situation with Don Wright, the chair of the IEEE Microprocessor Standards Committee (the sponsor of P1363). The only substantive comment Wright had was that the MSC technically had not addressed the ballot comments. Wright named the P1363 working group to be the ballot resolution committee, enabling it to respond in the name of the MSC. Wright also suggested a kinder gentler approach to dealing with negative comments: writing "NO." at the start of each response lacked tact. Kaliski reported that NIST, holder of the DSA patent, informally approved use of the DSA beyond the FIPS-186 specifications. We hope for an official letter to that effect. Singer listed future action items: 1. Enlisting the Technical Committee on Security and Privacy (sponsor of the annual Oakland conference) as a second sponsor. The TCSP hasn't responded yet, so Singer will follow up. 2. Update the list of patent letters. Ask the patent holders for updates for patents issued since the letters were last sent. 3. Synchronize our list of patent letters with that of IEEE. There was a new submission to the Web page ("HD-RSA" by Pointcheval). One recent contribution was withdrawn. Some questions arose about the withdrawal process. It was decided that withdrawn papers would be retained by the working group but not made available to anyone else. Kaliski suggested a new members-only working-group only mailing list and Web page. This was agreed upon. ==== Vice Chair Report: The Vice Chair is pleased as punch to have this opportunity to serve P1363. ==== Treasurer Report: The committee is solvent but not rich. The IEEE is way behind in collecting our money. ==== P1363 Document Update: The August recirculation ballot was held on Draft 11 and the responses to comments on Draft 9. The document passed, by an even larger margin than before. Several negative comments were reaffirmed, but the only new negative comment involved the ISO 9796 padding scheme (which was broken after its inclusion in P1363). An e-mail ballot had been taken on ISO 9796. The committee had voted to remove the scheme and made appropriate changes elsewhere. The latest draft is Draft 12. There will be further changes after this meeting, producing Draft 13, which will be put to a recirculation ballot. Singer outlined the chronology of future events: -> This meeting: decide on changes. -> Oct 27 to Nov 12: working group makes changes. -> Nov 12: Singer sends list of changes from Draft 11 and asks for a (20-day) recirculation ballot. -> by Dec 17: submit Draft 13 (or 14) to RevCom. -> Jan: if civilization has survived Y2K, RevCom meets. ==== Proposed Responses to Comments on Draft 11: Comments and decisions: We will expand the proposed response to indicate why the IFSSR scheme (the broken ISO one) was removed. We will report that Signatures with Message Recovery are being deferred to P1363a. We will put in a pointer to a URL in the Intro and the Intro to Annex D. The Web page will contain updates, including new developments on security. The list of negative comments will be split to separate the comments on Draft 9 from the new ones on Draft 11. At Johnson's suggestion, we will mention that ANSI X9.62 has declared its intention to adapt P1363's convention on pentanomial representations of binary fields. This renders moot one of the substantive negative comments on Draft 9, and allows us to change a "NO" to an "OK." We will also change "NO" to "OK" on Johnson's comment about RW signature forgeries. We will address in Sect 3 Wright's comment about the committee rejecting the substantive negative comments. We next looked at the proposed responses to comments on Draft 9: General Issues: the only comment was to the pentanomial question (see above). Kravitz brought up the patent comment of Carlisle Adams. There was a philosophical discussion on what it means to be "patented" (does any claim, no matter how far-fetched, force us to treat a scheme as patented?). Decided that Singer will address the issue in a paragraph in the cover letter to RevCom. The new Section 1 will be New Substantive Comments, the new Section 2 will be Old Substantive Comments. A note about the pentanomials will be put at the top of Section 2. Motion 3: Approve responses to comments on Draft 11, as amended. (Kaliski, Kravitz, 7-0-0) ==== List of Changes from Draft 11 to Draft 12. Reyzin: one of the changes we made as a result of dropping the IFSSR scheme is to remove the possibility that the signature is 6 mod 16. The only option remaining is 12. Although message recovery has now been put off to P1363a, we still mention it in connection with the Nyberg-Rueppel signature. Section C.3.4 was rewritten in light of dropping message recovery. In the references, standards documents will be listed now under the standards body rather than the corporate author. References will be added to ANSI X9.80 (prime number generation, testing, and certification) and X9.82 (random number generation). A reference to X9.80 will also be added to A.15. In D.5.2, strengthened the indication that we only do signatures with message recovery. Some minor changes from Solinas to parts of Annex A. Motion 4: Approve list of changes and the future changes to be made by Kaliski, Reyzin, Yin, Solinas, etc. (Solinas , Kaliski, 7-0-0) ==== P1363a Draft Kaliski provided an overview of P1363a. The intent is to fill in the missing pieces from P1363. Including: DL/EC encryption as in ANSI X9.63 DL/EC signatures with message recovery Inversionless signature schemes other than Nyberg-Rueppel. Johnson mentioned that he would give a submission in this area. IF signatures with message recovery (via PSS) Enhanced methods for basis conversion in binary fields (Annex A) Optimal Extension Fields GF(p^m) (Annex A) Reyzin discussed the last issue. There are some technical issues (e.g. conversion to integers and bit strings, checking the field format) and some security considerations (e.g. what are the supersingular elliptic curves?). New Annex A algorithms would be required, e.g. finding irreducibles over GF(p), basis tables, point decompression, fast inversion. Also need guidance in field selection (analogous to p vs. 2^m in P1363) and pseudo-random parameter generation and verification. Kravitz brought up a potential problem in extending the DL schemes, namely the Vaudenay attack on improperly implemented DSA. It was tentatively decided to restrict our attention to EC schemes over optimal extension fields, e.g. GF(p^m) for p slightly less than a power of 2. Bailey offered to write this up. Also, it was decided to look into tower field constructions. Bailey will do this too, in consultation with other interested parties (such as Erik De Win and Rich Schroeppel). Kaliski spoke on DHIES, the DH-based Integrated Encryption Scheme from ANSI X9. The idea is to introduce public parameters as inputs to the encryption and decryption steps. Kaliski diagrammed the proposed process, which involves steps for SVDP, KDF, and MAC, and uses sender ephemeral key pairs, recipient static key pairs, etc. A lengthy technical discussion by the group followed. ============== Thu. Oct. 28, 1999 Trumbull Marriott Merritt Parkway, Augusta Room We started at 8:30 am. We had in attendance: Don Johnson* Burt Kaliski* Tetsutaro Kobayashi* David Kravitz* Daniel Lieman* Ari Singer* Jerry Solinas* Yiqun Yin (by phone) An asterisk indicates an eligible voter. ==== EPOC and ESIGN Kobayashi presented the EPOC and TSH-ESIGN schemes. EPOC stands for Efficient Probabilistic Public-Key Encryption. There are 3 versions: EPOC-1, EPOC-2 OTP, and EPOC-2 Symmetric Encryption. TSH-ESIGN stands for Trisection Size Hash, the latest variant of ESIGN. There was discussion of security of these schemes. Boneh's recent work on factoring p^a q^b doesn't apply to p^2 q so these schemes are not broken thereby. In addition to factoring, ESIGN relies on the AERP (assumption that approximate e'th roots (mod N) are hard to find). Kobayashi presented some timings showing the advantages of his schemes. Singer summarized the schemes' properties on a table, the first step toward a systematic approach to deciding what to include in future P1363 standards. ==== P1363a Kaliski discussed the PSS format. As replacements for the commonly used PKCS and X9.31 formats, Bellare and Rogaway proposed Full Domain Hash (FDH) and Probabilistic Signature Scheme (PSS). The working group in June had decided to support all four formats. Kaliski would like to "favor" PSS because of its provable security properties. PSS is royalty-free. The University of California holds the patent and has granted free use. Kaliski explained the provable security properties. Kaliski listed some PSS issues. We need to specify the implementation, and want to stay aligned with ISO and ANSI, who are also standardizing it. Kaliski mentioned some of the choices that would have to be made when settling on an implementation. There was some discussion of modifying PSS to prevent fault analysis attacks on smart cards. Kaliski presented PSS-R, the variant for use with signatures with message recovery, the proposed replacement for the dropped ISO technique. PSS-R will be licensed according to IEEE requirements but may not be royalty-free. Kaliski returned to a general discussion of P1363a. At the moment, it's mostly a template, but Sec. 10 thru 12 (schemes) have some new material already, as does Sec. 4 (types of cryptographic techniques). Sec. 5 will contain new material on GF(p^m). Sec. 10.4 is the stuff that will replace the ISO format we just dropped from P1363. ==== Break for Lunch ==== P1363 Meeting Thursday Afternoon Attendance: Scott Crenshaw Don Johnson* Burt Kaliski* Tetsutaro Kobayashi* David Kravitz* Dan Lieman* James Muir Ari Singer* Joe Silverman Yiqun Yin* (by phone) [now eligible to vote having attended half the meeting] Silverman gave an informative presentation titled "Lattices, Cryptography and the NTRU Public Key Cryptosystem", supporting the NTRU cryptosystem and the PASS identification scheme. Singer asked whether PASS has a security proof, e.g., whether the difficulty of signature forgery can be reduced to a hard problem such as the Shortest Vector Problem. Silverman said that no proof is known, although arguments for security can be found in the CrypTEC '99 paper on PASS. Singer and Johnson asked about other aspects of NTRU and PASS, such as the role of encoding methods and whether key agreement and key validation are supported. Silverman commented on some of the precautions that had been taken in the cryptosystems. We had some further discussion on how to evaluate new submissions like NTRU and PASS. Lieman suggested a new project specifically for new families of cryptosystems. The scope of P1363a (as we are presently interpreting it) no longer extends to new families. After a short break, Lieman reviewed descriptions for projects on identification schemes and new families of public-key techniques. We observed that the identification schemes for the current three families could be considered within the scope of P1363a or a future P1363b. Lieman offered to lead a discussion at the next P1363 meeting, providing a matrix of candidate schemes. We can then make a decision whether to include identification schemes within P1363a/b or to start a separate project. Johnson suggested some clarifications to the "new families" proposal. We agreed to revise the scope to specifically state that it covers additional families not covered in the IEEE P1363 project. We also agreed to remove the statement that the document would be merged into IEEE P1363. (Considering it as an addendum would introduce additional complexity to the development that may not be beneficial.) Singer then led a discussion on the methodology for choosing future projects and for selecting techniques within a scheme. He listed the following features to be considered in selecting new projects: * interest - write it * ability - sound decision * need - reason for work * feasibility - can we do it? Singer then explored more specific qualifications for each feature: * interest in writing it - editor - scope & purpose - support for editor * ability of the working group to make a sound decision - expertise (within working group and by proponent) - evidence of strength of claims - checks & balances (un-biased) * need, reason for the work - claimed advantages - perceived value of standard to cryptographic or commercial world - lack of other work/standardization * feasibility - IEEE approval - availability of resources - timing - ability to reach consensus ============== Fri. Oct. 29, 1999 Trumbull Marriott Merritt Parkway, Augusta Room We started at 8:30 am. We had in attendance: Don Johnson* Burt Kaliski* Tetsutaro Kobayashi* David Kravitz* Dan Lieman* Ari Singer* Yiqun Yin* (by phone) Singer continued the discussion from Thursday afternoon by outlining the process for developing a project: * suggestion * discussion * preliminary work - research & presentation * determination of satisfaction of features * vote to propose project to IEEE We discussed how the working group should determine how to request new projects, given that the scope of IEEE P1363a is being narrowed. Kaliski observed that a study group would be an appropriate method. Singer agreed to contact the MSC chair to set up such a study group, if one is needed. The purpose of the group would be to determine which new projects to launch. It would be desirable if the working group could act as the study group (or at least host the study group meeting) and manage the new projects; Singer will check with the MSC chair. As an example of how a new project might be decided, in the case of the "new families", the study group might determine the scope of a new project to include "high-speed" schemes, NTRU being one contribution. It is important for the scope to be specific so that it is clear which contributions are appropriate and how they would be evaluated. Singer then reviewed the criteria for evaluating contributions, starting with encryption schemes. This is both for P1363a and other potential projects. He listed the following characteristics of encryption schemes: * provably secure? - under what assumptions? * run-time complexity vs. type of data - consider purpose (i.e., signature, key exchange, data) * key size * key generation complexity * patent status * bandwidth requirements * code size (if expertise exists) * pre-computation * recipient and sender computational complexity * other capabilities * evidence of strength of security claims * security attributes with required assumptions * deployment and standardization * how it fits with other encryption schemes These characteristics could be applied, with extensions, to evaluate other contributions than encryption schemes. Kaliski then presented a rough schedule for the P1363a project: October 1999: draft D1, working group meeting November: request new material for March meeting December: draft D2 with updates, deterministic DSA material, DL/ECSSR February 2000: draft D3 with security considerations, GF(p^m) March: working group meeting, decide on new material April: draft D4 May: draft D5 June: working group meeting July: draft D6, most material included August: working group meeting September: draft D7 October: draft D8 November: working group meeting December: draft D9 February 2001: final review draft March: working group meeting, approve for ballot April: ballot version, start ballot (The chair should check that the status of the current PAR to see whether the projected completion date falls within the allotted time) Singer then outlined the current material for IEEE P1363a: - DL/ECIES tracking and possibly generalizing ANSI X9.63 - PSS/FDH/PSS-R tracking and possibly generalizing ISO/IEC 9796-2 - PKCS #1 v1.5 - DL/ECSSR tracking and possibly generalizing ISO/IEC 9796-3 There is an intent to vote on inclusion in March of the following items: - GF(p^m) material - tower fields material - inversionless signature primitives - EPOC1/2 and TSH-ESIGN - basis conversion The material supporting these items needs to be substantially ready for inclusion in the P1363a draft, but does not need to be in final form. No other major contributions will be considered for P1363a. (If something was inadvertently omitted from this list, the working group reserves the right to correct the list later.) On TSH-ESIGN, Kravitz said it would be important to know why e = 4 is not allowed. In general, the working group would like more assurances on the security of the Approximate e-th Root Problem. We then had three motions: Motion 5: Accept the list above of "current material for IEEE P1363a" (Lieman, Kravitz, 7-0-0) Motion 6: Accept the list above of "intent to vote on inclusion in March" and that no other major contributions will be considered (Johnson, Lieman, 7-0-0) Motion 7: Accept the proposed schedule above for P1363a development (Kaliski, Kravitz, 7-0-0) Singer will commission a study group through MSC for proposing new projects, and then call for proposals. Our three leading candidates for projects appear to be the following: * identification schemes * key validation * new families of public-key cryptosystems Yin offered to represent the working group at MSC meetings, if necessary. Motion 8: Authorize the chair to pursue the formation of a study group for new projects such as those discussed above and to investigate appropriate relationship with IEEE P1363 (Kaliski, Kravitz, 6-0-0) Singer will put out a call for hosts for meetings next year. The tentative date for the next meeting is March 15-17. The deadline for material to be considered at the meeting will be one month before the start of the meeting. Singer will also continue to work on the list of encryption scheme characteristics to provide general guidance on how to evaluate contributions. For the record, the following people are considered to have met the attendance requirements for this meeting (half the meeting): Don Johnson, Burt Kaliski, Tetsutaro Kobayashi, David Kravitz, Dan Lieman, Ari Singer, Jerry Solinas, Yiqun Yin. Summary of action items: * Update P1363 D11 ballot response (Singer, Reyzin) * Update P1363 draft (Reyzin, Yin) * Start recirculation ballot by Nov. 12 (Singer) * Submit P1363 to RevCom by Dec. 17 (Singer) * Update P1363a draft (Kaliski) * Send ISO/IEC 9796-3 to Kaliski, Singer (Johnson) * Pursue study group (Singer) * Request additional P1363a material for March meeting (Singer) * Put out call for meeting hosts (Singer) * Appoint and call for officers (Singer) * Develop evaluation criteria for contributions (Singer) Motion 9: Thank Pitney Bowes for hosting the meeting (Kaliski, Kravitz, acclamation) Motion 10: Adjourn (Kaliski, Lieman, 6-0-0)