Filename:107-PBC.txt
Title:The pairing-based key negotiation protocol
Version:0.0.1
Last modified:10-March-2007
Author:Watson Ladd
Created:9-March-2007
Status:Open

Overview: This document describes a new version of the tor protocol
	  that uses pairing-based cryptography following [1].

Motivation: The protocol described in [1] is much more efficient in both
	    bandwith and CPU then the current protocol.

Backwards-compatability: Sadly, use of the VERSION cell will negate some of the
			 advantages of the new protocol. This is very much
			 a work in progress. Current solution is a new cell
			 type.

Proposal:
Section 0.0: Magic Numbers
Section 1.0: Precomputation
Section 1.1: Circuit Creation
Section 2.1: The distributed PKG.

Section 0.0: Magic Numbers
	This document tacitly presumes that the Pairing Based Cryptography libray[2] is being used.
	Pairing d225 is used. A new cell type CREATE_WARPSPEED is defined. All cipher modes, key lengths,
	initialization methods, etc. are inherited from the tor specification. All timestamps are big-endian
	representations of the number of seconds since the Unix epoch, 64 bits in length. All hashes are SHA-256.
	The master key validity period(MKVP) is 24 hours in duration. The private key validity period (PKVP)
	is 1 hours. All other magic numbers are inherited from Tor.

Section 1.0: Precomputation.
	As described in Section 2.1 the PKG creates a signed tuple (v, U, sU) where v is a timestamp indicating
	the begining of the current MKVP, U is a random point in G1 of d225, and sU is U added to itself s times.
	The signature is any strong scheme (probably RSA). The OP obtains this tuple from a Directory server, along
	with a list ID[i] of the ID's of the OR's. The OP may precompute the public keys of the OR's by taking
	Q[i]=H(ID[i]||v_m) where v_m is a timestamp indicating the begining of the current private key validity
	period. The ID's are the fingerprints of the RSA public keys of the OR's. The OP may also let r[i] be
	an array of randomly generated integers in Z_r of the pairing (as computed by element_init_Zr). They may then
	take A[i]=r[i]*U. They may then take K[i]=P(sU,Q[i])*r[i].
	Any of these computations may be delayed until use/not performed if not needed.

Section 1.1:Circuit creation
	Let the nodes in the circuit be A, B, and C. Then let us index arrays with A,B,C to take the entry
	corresponding to the node. Then let us abuse notation and write {stuff}_K[i] to denote encrypting stuff
	with the appropriate key derived from the ith entry of K. Then OP will send a CREATE_WARPSPEED cell with
	the following payload to A, and a previously unused CircID:
	A[A],{B,A[B],{C, A[C]{$Padding}_K[C]}_K[B]}_K[A]

	Padding consists of sufficent null bytes to fill out the cell to 512 bytes. A, B, and C are the IP addresses
	of the OR's being used. On recipt of this cell A will compute P(A[A],S[A]) where S[A] is A's secret key.
	A will then decrypt the rest of the payload and find out who B is. A will then send a CREAT_WARPSPEED cell
	using a previously unused CircID to B, whoes contents are the rest of the encrypted section of the payload.

	B behaves similarly. When C sees the padding he realizes that the circuit has been extended to him, and
	sends back a CREATED cell. Traffic is then passed as normal.

Section 2.1: The distributed PKG
	Every PKVP a trusted central server creates the private keys for the OR's. The central server then splits
	them into t shares among m servers, using a polynomial secret sharing scheme. The servers know which OR
	corresponds to which share, and only send a share after encypting it with the RSA key of the OR.