Network Working Group A. Kato
Internet-Draft NTT Software Corporation
Intended status: Informational T. Hardjono
Expires: October 27, 2016 MIT
T. Kobayashi
T. Saito
K. Suzuki
NTT
April 25, 2016

FSU Key Exchange
draft-kato-fsu-key-exchange-01

Abstract

This draft proposes an identity-based authenticated key exchange protocol following the extended Canetti-Krawczyk (id-eCK) model. The protocol is currently the most efficient among the id-eCK protocols.

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on October 27, 2016.

Copyright Notice

Copyright (c) 2016 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.


Table of Contents

1. Introduction

Authenticated key exchange (AKE) is a core security function within many deployed systems today. It is a foundational function that allows end-users and systems alike to be authenticated prior to access to resource and services. Over the past two decades key exchange schemes have been proposed, based on symmetric and asymmetric key cryptography.

A more recent approach to AKE protocol has been the introduction of identity binding to the exchange [7] [8], obviating the need to rely on a public key infrastructure in which digital certificates need to be exchanged by users or end-points that wish to communicate signed and/or encrypted messages.

Identity-based AKE (ID-AKE) schemes rely on the use of the trusted intermediary referred to as the Key Generation Center (KGC). The role of the KGC, among others, is to generate a pair of master public and secret keys based on the user's identity and to extract a user's secret key corresponding to his or her identity.

In a 2-pass ID-AKE scheme, an "initiator" entity wishing to share a key with a second entity (referred to as the "responder") sends ephemeral public information to the responder. In its turn, the responder sends another ephemeral public information to the initiator entity. Following this, each entity would then generate a session from a number of parameters, notably their respective secret keys (given by the KGC), their own secret values of the ephemeral information, the identity of the peer they're communicating with, and the ephemeral information they received from that peer.

We propose a provably secure ID-AKE scheme called "FSU" [4] [5] [6] based on the previous model of [9] and which builds on the previous efforts in [10] [11] . The model underlying the FSU was chosen due to the merit of provable security based on an adversarial model in which the adversary has the freedom to choose keys reveal.

1.1. Our Motivation

In order to establish secure communications, the encryption is used, and a key exchange protocol is necessary to use the encryption. If the key exchange protocol has vulnerability, an attacker can intercept all messages, so encrypted session becomes meaningless. In practice, man in the middle attack and a forward security of key exchange protocol are serious issues.

In recent years, IoT technology gathers many attentions. It is expected that 26-30 billion devices will be wirelessly connected by 2020. And to set up a huge number of devices with certificates or passwords for key exchange and to maintain the certificates or passwords require many costs. Furthermore, the leakage of a secret key for key exchange and a session key for encryption likely to occur because of resource restriction of device and installation environment of device.

To resolve above problems, we propose an ID-based authenticated key exchange protocol FSU. In usual PKI based cryptography, a device must set up password or generate own secret key. On the other hand, in the FSU protocol the trusted third party generate the secret key for a huge number of IoT devices, so the manufacture and users of the devices can maintain secret key for the devices unitarily. The FSU Protocol use existing ID, which can be any string, e.g., e-mail address and serial number, as public key instead of certificate or password. Thus, the authentication server is not required to manage the certificates and the passwords of device any more. Finally, the FSU protocol provides the highest security against leakages of secret keys. Thus, security of a session key is preserved even if some secret keys are leaked because of resource restriction and installation environment of devices.

2. Requirements Terminology

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this memo are to be interpreted as described in [1].

3. Notation

This section shows notation used in this memo.

Let F_q be a finite field with q = p^n elements for a prime p and an integer n and let E(F_q) be an elliptic curve with an order r and an embedding degree k defined over F_q. An embedding degree k is defined as a minimum integer k such that r is a divisor of q^k - 1.

Let G_1 (resp. G_2) be an additive group with an order r generated by E(F_q) (resp. E'(F_q)). Let G_T be multiplicative groups with the same order r. Let P_1, P_2 be generators of G_1, G_2 respectively. We say that (G_1, G_2, G_T) are bilinear map groups if there exists a pairing e: (G_1, G_2) -> G_T satisfying the following properties:

  1. Bilinearity: for any Q_1 in G_1, for any Q_2 in G_2, for any a, b in Z_r, we have the relation e(aQ_1, bQ_2) = e(Q_1,Q_2)^{ab}.
  2. Non-degeneracy: for any Q_1 in G_1, e(Q_1,Q_2) = 1 only if Q_2 = O_{G_2} and for any Q_2 in G_2, e(Q_1,Q_2) = 1 only if Q_1 = O_{G_1}.
  3. Computability: for any Q_1 in G_1, for any Q_2 in G_2, the bilinear map is efficiently computable.

This pairing is described in specification of optimal ate pairing specification[3]. It is defined by Pairing-Parm-ID following way.

   Pairing-Param-ID = {
       G1-Curve-ID,
       G2-Curve-ID
       GT-Field-ID
   }

G1-Curve-ID and G2-Curve-ID is an identifiers of elliptic curve. And GT-Field-ID is an identifier of the G_T range of finite field. G1-Curve-ID , G2-Curve-ID and GT-Field-ID are described in [2] the following way.

   G1-Curve-ID = {
       p_b    : A prime specifying base field F_p.
       A, B   : The coefficients of the equation y^2 = x^3 A * x + B
               defining E.
       G = (x, y) : The base point, i.e., a point with x and y
                being its x- and y-coordinates in E, respectively.
       r      : The prime order of the group generated by G.
       h      : The cofactor of G in E.
  }
   G2-Curve-ID = {
       p_b    : A prime specifying base field F_p.
       e2     : The constant of an irreducible polynomial specifying
                extension field F_{p^2} = Fp[u] / (u^2 - e2).
       A', B' : The coefficients of the equation y^2 = x^3 A' * x + 
                  B' defining E'.
       G' = (x', y') : The base point, i.e., a point with x' and y'
                being its x- and y-coordinates in E', respectively.
       r'      : The prime order of the group generated by G'.
       h'      : The cofactor of G' in E'.
  }

  GT-Filed-ID = {
       p_b    : A prime specifying base field.
       r      : The prime order of the subgroup of F_{p^12}.
       e2     : The constant of the irreducible polynomial of F_{p^2} =
                F_p [u] / (u^2 - e2).
       e6     : The constant of the irreducible polynomial of F_{p^6} =
                F_{p^2}[v] / (v^3 - e6).
       e12    : The constant of the irreducible polynomial of F_{p^12}
                = F_{p^6}[w] / (w^2 - e12).
       h''    : The cofactor of G_T
   }

In addition, this memo uses the following functions.

floor(x) : The function returning an integer such that max{x' in Z | x' <= x}.

ceil(x) : The function returning an integer such that min{x' in Z | x' >= x}.

O_E : The point at infinity over elliptic curve E.

4. Data Type and Its Conversions

This section describes data type and its conversion used in this memo.

4.1. BitString-to-OctetString Conversion (BS2OSP)

This memo uses conversion from bit strings to octet strings. Informally, the idea is to pad the bit string with 0's on the left to make its length a multiple of 8, then chop the result up into octets. Formally, the conversion routine, BS2OSP(B), is specified in Appendix A.1

4.2. OctetString-to-BitString Conversion (OS2BSP)

This memo uses conversion from octet strings to bit strings. Informally, the idea is simply to view the octet string as a bit string. Formally, the conversion routine, OS2BSP(M), is specified in Appendix A.2

4.3. FieldElement-to-Integer Conversion (FE2IP)

This memo uses conversion from field elements to integers. An finite field element should be represented as a polynomial with subfield coefficients, which can be represented as a sequence of the coefficients. Informally, the idea is simply to view the sequence of the coefficients as the radix-p^m representation of the base field elements, where p^m is the number of the subfield elements. Formally, the conversion routine, FE2IP(a), is specified in Appendix A.3

4.4. Integer-to-FieldElement Conversion (I2FEP)

This memo uses conversion from integers to field elements. A field element should be represented as a polynomial with subfield coefficients, and it can be represented as a sequence of the coefficients. Informally, the idea is to represent the integer with radix-p^m positional number system where p^m is the number of the subfield element, and then convert the each digit to the each coefficient of the polynomial. Formally, the conversion routine, I2FEP(x), is specified in Appendix A.4:

4.5. FieldElement-to-OctetString Conversion (FE2OSP)

This memo uses conversion from field elements to octet strings. This conversion is constructed by using FE2IP and I2SOP conversions. Formally, the conversion routine, FE2OSP(a), is specified in Appendix A.5.

4.6. OctetString-to-FieldElement Conversion (OS2FEP)

This memo uses conversion from octet strings to field elements. This conversion is constructed by using OS2IP and I2FEP conversions. Formally, the conversion routine, OS2FEP(M), is specified in Appendix A.6.

4.7. EllipticCurvePoint-to-OctetString Conversion (ECP2OSP)

This memo uses conversion from elliptic curve points to octet strings. Informally the idea is that, if point compression is being used, the compressed y-coordinate is placed in the leftmost octet of the octet string along with an indication that point compression is on, and the x-coordinate is placed in the remainder of the octet string; otherwise if point compression is off, the leftmost octet indicates that point compression is off, and remainder of the octet string contains the x-coordinate followed by the y-coordinate. Formally, the conversion routine, ECP2OSP(P,R), is specified in Appendix A.7.

4.8. OctetString-to-EllipticCurvePoint Conversion (OS2ECPP)

This memo uses conversion from octet strings to elliptic curve points. Informally, the idea is that, if the octet string represents a compressed point, the compressed y-coordinate is recovered from the leftmost octet, the x-coordinate is recovered from the remainder of the octet string, and then the point compression process is reversed; otherwise the leftmost octet of the octet string is removed, the x-coordinate is recovered from the left half of the remaining octet string, and the y-coordinate is recovered from the right half of the remaining octet string. Formally, the conversion routine, OS2ECPP(M), is specified in Appendix A.8.

5. Building Block of FSU Key Exchange

This section describes building block for constructing FSU Key Exchange.

5.1. Key Derivation Function

MGF1 is a mask generation function, parameterized by a hash function. MGF1(M,n) is defined as follows:

System parameters:

Input:

Output:

Method:

  1. Let n_0 be the octet length of M. If n_0 + 4 is greater than the input limitation for the hash function, output INVALID and stop.
  2. Set cThreshold = ceil(n / hashLen)
  3. If cThreshold > 2^32, output INVALID and stop
  4. Let M' be the empty octet string
  5. Set counter = 0
  6. B = B_{0}, ..., B{31} such that counter = B_{31} + B_{30}*2 + ... + B_{0}*2^{31}
  7. Compute C = BS2OSP(B)
  8. Compute H = Hash(M||C)
  9. Set M' = M'||H
  10. Set counter = counter + 1
  11. If counter < cThreshold, go back to step 6.
  12. Set mask = M'_0M'_1...M'_{n-1} where M' = M'_0M'_1M'_2...
  13. Output mask

5.2. Hashing to Point

Hashed value should be converted to elliptic curve point as described in this section. Formally, the conversion routine, HASHINGTOPOINT(Curve-ID, Hash, M), is specified as follows:

Input:

Output:

Method:

  1. Set i = 0
  2. B = B_{0}, ..., B{15} such that counter = B_{15} + B_{14}*2 + ... + B_{0}*2^{15}
  3. Compute C = BS2OSP(B)
  4. x_0 = OS2FQE(C||M, Hash, F_{p^m}) in F_{p^m}
  5. t = x_0^3 + A * x_0 + B
  6. If t=0, set P =(x_0, 0) and output h'*P
  7. If t is not square in F_{p^m}, set i = i + 1 and go back to step 2
  8. Set alpha be one of square roots of t. Then, -alpha is another square root of t.
  9. Set y_1 = FE2IP(alpha)
  10. Set y_2 = FE2IP(-alpha)
  11. If y_1 > y_2, set y_0 = -alpha
  12. Else (i.e. y_1 <= y_2), set y_0 = alpha
  13. Set P = (x_0, y_0)
  14. Output h * P

5.2.1. IHF1

Bit string should be converted to hashed non-negative integer less than an assigned integer as described in this section. Formally, the conversion routine, IHF1(s,n,Hash) is defined as follows:

Input:

Output:

Method:

  1. Set hashLen be the length of the output of the hash function Hash
  2. Set h_0 be the zero string of length hashLen
  3. h_1 = Hash(h_0 || s)
  4. B = B_0,...,B_{l-1} = OS2BSP(h_1)
  5. a_1 = sum_{i = 0}^{l-1} 2^{l-1-i} * B_{i}
  6. h_2 = Hash(h_1 || s)
  7. B = B_0,...,B_{l-1} = OS2BSP(h_2)
  8. a_2 = sum_{i=0}^{l-1} 2^{l-1-i} * B_{i}
  9. v = 2^{hashLen} * a_1 + a_2 mod n
  10. Output v

5.2.2. OS2FQE

Octet string should be converted to hashed finite field element as described in this section. Formally, the conversion routine, OS2FQE(s,Hash,F_{p^m}) is defined as follows:

Input:

Output:

Method:

  1. Set i = 0
  2. B = B_{0}, ..., B{31} such that counter = B_{31} + B_{30}*2 + ... + B_{0}*2^{31}
  3. Compute C = BS2OSP(B)
  4. Compute t_i = IHF1(C||s,p,Hash)
  5. If i < m, set i = i + 1 and go back to step2
  6. Compute a = sum_{i=0}^{m-1} t_i * beta^i where beta is the variable of the polynomial
  7. Output a

5.3. Group Membership Test Function

GROUPMEMBERSHIPTEST(Curve-ID, P) is a test function that an elliptic curve point is on the correct curve and group. GROUPMEMBERSHIPTEST is defined as follows:

Input:

Output:

Method:

  1. If P = O_E, then output 1
  2. If y^2 != x^3 + A * x + B, then output 0
  3. If h != 1 && r * P != O_E, then output 0
  4. Output 1

6. FSU Key Exchange

This section provides the specification of ID-based authenticated key exchange protocol FSU [4] that is an extension of FSU (Fujioka-Suzuki-Ustaoglu) protocol standardized in ISO/IEC11770-3 [5] [6].

6.1. System Parameter Setup

Key Generation Center (KGC) defines the following system parameters in FSU:

KGC generates the master secret key MSK and master public key MPK from system parameters as following.

  1. KGC selects a random integer z in Z_r.
  2. KGC computes Z_v = z * P_v for v is in {1, 2}.
  3. KGC sets MSK = z and MPK = (Z_1, Z_2).

Hash function H_v are defined as H_v(M) = HASHINGTOPOINT(Gv-Curve-ID, Hash, "FSU"||ECP2OSP(Z_1, R)||ECP2OSP(Z_2, R)||M) for v in {1, 2}. Hash function H is defined as H(M) = MGF1("FSU"||ECP2OSP(Z_1, R)||ECP2OSP(Z_2, R)||M, n).

6.2. Key Distribution by KGC

This subsection explains operations of key distribution by KGC. There are two types of static secret key in FSU Key Exchange, respectively static secret key based on cyclic groups in G_1 and in G_2. FSU Key Exchange requires that an initiator and a responder use static secret key with different types, respectively. Hence, KCG needs to define a rule for key distribution for users. For example, clients use static secret keys in G_1 and servers use them in G_2.

KGC generates static secret key D_{i, v} for an identifier ID_i for i in {A, B} of user in G_v as following.

  1. Let MPK be (Z_1, Z_2) and MSK be z.
  2. KGC Compute D_{i ,v} = z*H_v(ID_i).
  3. Distribute D_{i ,v} to a user with ID_i.

6.3. FSU Key Exchange Protocol

This subsection describes FSU Key Exchange Protocol in an initiator U_A with an identifier ID_A and static secret key D_{A,1} and a responder U_B with an identifier ID_B and static secret key D_{B,2}.

Computation of ephemeral public key by U_A

  1. U_A selects a random integer x_A in Z_r.
  2. U_A computes the ephemeral public key X_{A,v} = x_A * P_v for v in {1,2}.
  3. U_A computes XOS_{A,v} = ECP2OSP(X_{A,v}, R) for v in {1,2}.
  4. U_A sends (ID_A, ID_B, XOS_{A,1}, XOS_{A,2}) to U_B.

Computation of ephemeral public key by U_B

  1. U_B receives (ID_A, ID_B, XOS_{A,1}, XOS_{A,2}).
  2. U_B computes X_{A,v} = OS2ECPP(XOS_{A,v}) for v in {1,2}.
  3. If (GROUPMEMBERSHIPTEST(G1-Curve-ID, X_{A,1}) = 0 || GROUPMEMBERSHIPTEST(G2-Curve-ID, X_{A,2}) = 0 || e(X_{A,1}, P_2) != e(P_1, X_{A,2})), then abort.
  4. U_B selects a random ephemeral secret key x_B in Z_r.
  5. U_B computes the ephemeral public key X_{B,v} = x_B * P_v for v in {1,2}.
  6. U_B computes XOS_{B,v} = ECP2OSP(X_{B,v}, R) for v in {1,2}.
  7. U_B sends (ID_B, ID_A, XOS_{B,1}, XOS_{B,2}) to U_A.

Computation of session key by U_B

  1. U_B computes sigma_1 = e(H_1(ID_A), D_{B,2}).
  2. U_B computes sigma_2 = e(H_1(ID_A) + X_{A,1}, D_{B,2} + x_B * Z_2).
  3. U_B computes sigma_3 = x_B * X_{A,1}.
  4. U_B computes sigma_4 = x_B * X_{A,2}.
  5. U_B computes sigmaOS_j = FE2OSP(sigma_j) for j in {1,2}.
  6. U_B computes sigmaOS_j' = ECP2OSP(simga_j',R) for j' in {3,4}.
  7. Set sid = (ID_A||ID_B||XOS_{A,1}||XOS_{A,2}||XOS_{B,1}||XOS_{B,2}).
  8. U_B computes session key K = H(sigmaOS_1||sigmaOS_2||sigmaOS_3||sigmaOS_4||sid).

Computation of session key by U_A

  1. U_A computes X_{B,v} = OS2ECPP(XOS_{B,v}) for v in {1,2}.
  2. If (GROUPMEMBERSHIPTEST(G1-Curve-ID, X_{B,1}) = 0 || GROUPMEMBERSHIPTEST(G2-Curve-ID, X_{B, 2}) = 0 || e(X_{B,1}, P_2) != e(P_1, X_{B,2})), then abort.
  3. U_A computes sigma_1 = e(D_{A,1}, H_2(ID_B)).
  4. U_A computes sigma_2 = e(D_{A,1} + x_A * Z_1, H_2(ID_B) + X_{B,2}).
  5. U_A computes sigma_3 = x_A * X_{B,1}.
  6. U_A computes sigma_4 = x_A * X_{B,2}.
  7. U_A computes sigmaOS_j = FE2OSP(sigma_j) for j in {1,2}.
  8. U_A computes sigmaOS_j' = ECP2OSP(simga_j',R) for j' in {3,4}.
  9. Set sid = (ID_A||ID_B||XOS_{A,1}||XOS_{A,2}||XOS_{B,1}||XOS_{B,2}).
  10. U_A compute session key K = H(sigmaOS_1||sigmaOS_2||sigmaOS_3||sigmaOS_4||sid).

7. Security Considerations

This memo specifies identity-based authenticated key exchange protocol FSU [4] [6] [5] which is secure in the id-eCK(id-based extended Canetti-Krawczyk) security model under the GBDH(gap bilinear DH) assumption [4].

id-eCK security model is the most strong security model in the meaning of that it ensures the safety of session key if any non-trivial combinations of master key, static key, and ephemeral key are leaked.

And id-eCK security model guarantees following 4 security notions:

8. Acknowledgements

TBD

9. Algorithm Identifiers

TBD

10. Change log

NOTE TO RFC EDITOR: Please remove this section in before final RFC publication.

11. Test Vectors

TBD

12. References

12.1. Normative References

[1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, March 1997.
[2] Kasamatsu, K., Kanno, S., Kato, A., Scott, M., Kobayashi, T. and Y. Kawahara, "Barreto-Naehrig Curves", Internet-Draft draft-kasamatsu-bncurves-02, 2015.
[3] Kato, A., Scott, M., Kobayashi, T. and Y. Kawahara, "Barreto-Naehrig Curves", Internet-Draft draft-kato-optimal-ate-pairings-01, 2015.

12.2. Informative References

, "
[4] Fujioka, A., Hoshino, F., Kobayashi, T., Suzuki, K., Ustaglu, B. and K. Yoneyama, "id-eCK Secure ID-Based Authenticated Key Exchange on Symmetric and Asymmetric Pairing", Proceedings IEICE Transactions 96-A(6): 1139-1155, 2013.
[5] Fujioka, A., Suzuki, K. and B. Ustaglu, Ephemeral Key Leakage Resilient and Efficient ID-AKEs That Can Share Identities, Private and Master Keys", Proceedings Pairing 2010 Lecture Notes in Computer Science Volume 6487, pp 187-205, 2010.
[6]Information technology -- Security techniques -- Key management -- Part 3: Mechanisms using asymmetric techniques.", ISO/IEC 11770-3: 2015, 2015.
[7] Shamir, A., "Identity-based Cryptosystems and Signature Schemes", Proceedings CRYPTO '84, LNCS 196, pages 47-53, Springer-Verlag, 1984.
[8] Boneh, D. and M. Franklin, "Identity-Based Encryption from the Weil Pairing", Proceedings CRYPTO 2001, LNCS 2139, pages 213-229, Springer-Verlag, 2001.
[9] Huang, H. and Z. Cao, "An ID-based Authenticated Key Exchange Protocol Based on Bilinear Diffie-Hellman Problem", Proceedings the 4th International Symposium on Information, Computer, and Communications Security (ASIACCS '09) pp. 333-342, ACM, 2009.
[10] Canetti, R. and H. Krawczyk, "Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels", Proceedings Eurocrypt 2001 (LNCS2015), pp. 453-474, Springer-Verlag, 2001.
[11] LaMacchia, B., Lauter, K. and A. Mityagin, "Stronger Security of Authenticated Key Exchange", Proceedings in Provable Security (LNCS 4784), pp. 1-16, Springer, 2007.

Appendix A. Construction of Data Conversion

A.1. Construction of BS2OSP

Concrete construction of BS2OSP(B) is specified as follows:

Input:

Output:

Method:

  1. If l = 0, then output empty octet string and stop.
  2. For j in {0,...,8n-1}, if j >= 8n - l, set B'_j = B_{j-(8n-l)}, otherwise set B'_j = 0.
  3. For i in {0,...,n-1}, set M_i = B'_{8i} B'_{8i+1}...B'_{8i+7}.
  4. Output M = M_0 M_1 ... M_{n-1}.

A.2. Construction of OS2BSP

Concrete construction of OS2BSP(M) is specified as follows:

Input:

Output:

Method:

  1. If l = 0, then output empty octet string and stop.
  2. For i in {0, ..., n-1} , j in {0,...,7}, set B_{8i + j} in {0,1} as M_i = B_{8i} B_{8i+1}...B_{8i+7}.
  3. Output B = B_0 B_1 ... B_{l-1}.

A.3. Construction of FE2IP

Concrete construction of FE2IP(a) is specified as follows:

System parameters:

Input:

Output:

Method:

  1. If m_2 = 1 (i.e. F_{p^m_2} is prime field)

  2. Else (i.e. m_2 > 1)

A.4. Construction of I2FEP

Concrete construction of I2FEP(x) is specified as follows:

System parameters:

Input:

Output:

Method:

  1. If m_2 = 1 (i.e. F_{p^m_2} is prime field)

  2. Else (i.e. m_2 > 1)

A.5. Construction of FE2OSP

System parameter:

Input:

Output:

Method:

  1. Compute I = FE2IP(a)
  2. Compute X = x_{0}, ..., X_{n-1} such that I = x_{n-1} + x_{n-2}*2 + ... + x_{1}*2^{n-2} + x_{0}*2^{n-1}
  3. Compute M = BS2OSP(X)
  4. Output M

A.6. Construction of OS2FEP

System parameter:

Input:

Output:

Method:

  1. Compute X = OS2BSP(M)
  2. Let X be x_0,...,x_{l-1}
  3. Compute I = sum_{i=0}^{l-1} 2^{l-1-i} * x_{i}
  4. Compute a = I2FEP(I)
  5. Output a

A.7. Construction of ECP2OSP

Concrete construction of ECP2OSP(P,R), is specified as follows:

System parameters:

Input:

Output:

Method:

  1. If P = O_E

  2. If P = (x,y) != O_E && R = Compressed

  3. If P = (x,y) != O_E && R = Uncompressed

  4. If P = (x,y) != O_E && R = Hybrid

A.8. Construction of OS2ECPP

Concrete construction of OS2ECPP(M), is specified as follows:

System parameters

Input:

Output:

Method:

  1. If M = BS2OSP(00000000), output P = O_E
  2. If M has length ceil(m * log_2 p / 8) + 1

  3. If M has length 2 * floor(m * log_2 p / 8) + 1

Authors' Addresses

Akihiro Kato NTT Software Corporation EMail: kato.akihiro-at-po.ntts.co.jp
Thomas Hardjono MIT EMail: hardjono-at-mit.edu
Tetsutaro Kobayashi NTT EMail: kobayashi.tetsutaro-at-lab.ntt.co.jp
Tsunekazu Saito NTT EMail: saito.tsunekazu-at-lab.ntt.co.jp
Koutarou Suzuki NTT EMail: suzuki.koutarou-at-lab.ntt.co.jp