CONFIDENTIAL TREATMENT REQUESTED AMENDED AND RESTATED CONSULTING AGREEMENT

EXHIBIT 10.04

CONFIDENTIAL TREATMENT REQUESTED

AMENDED AND RESTATED

CONSULTING AGREEMENT

This Amended and Restated Consulting Agreement (“Agreement”) is made by and between VeriSign, Inc. , a Delaware corporation with offices at 487 E. Middlefield Road, Mountain View, California 94043 (“VeriSign”), and Roger Moore , a United States citizen, with his principal residence at [***] (“Consultant”).

RECITALS

WHEREAS, VeriSign and Consultant entered into a Consulting Agreement dated October 1, 2008, for a term which commenced on December 17, 2007, a copy of which is attached hereto as Exhibit A (the “Consulting Agreement”);

WHEREAS, VeriSign and Consultant desire to amend and restate the Consulting Agreement and enter into this Agreement in connection with the sale of certain VeriSign businesses (“Communications Business Bundle”) as set forth on Exhibit B hereto;

WHEREAS, Consultant desires to perform, and VeriSign desires to have Consultant perform certain consulting services (“Services”) as set forth on Exhibit C hereto in connection with the Sale of the Communications Business Bundle in accordance with the terms and conditions of this Agreement;

WHEREAS, the Compensation and Audit Committees of the Board have each considered and approved the provision of the Services by Consultant to VeriSign on the material terms contained in this Agreement by resolutions passed on February 23, 2009, and February 24, 2009, respectively;

WHEREAS, Consultant resigned from the Audit Committee of the Board on December 20, 2007 and is not a member of any other Committee of the Board; and

WHEREAS, VeriSign and Consultant desire to set out in this Agreement the terms and conditions for the provision of the Services by Consultant to VeriSign.

NOW, THEREFORE, in consideration of the mutual promises made herein, VeriSign and Consultant hereby agree as follows:

1. Definitions .

“ Sale ” means the merger, asset purchase or other disposition of the entire Communications Business Bundle. VeriSign shall retain at all times the right to conclude and consummate any such Sale.

1

“ Closing Date ” means the effective date upon which the closing of the Sale of Communications Business Bundle occurs as defined in the Definitive Agreement.

“ Definitive Agreement ” means the agreement memorializing the merger, asset purchase or other disposition of the Communications Business Bundle with Purchaser.

“ Purchaser ” means the entity or entities to whom the Sale of the Communications Business Bundle is made.

2. Services, Payments and Start Date .

(a) Performance by Consultant and Start Date . Consultant has performed the Services under the Consulting Agreement since December 17, 2007 and will perform the Services under this Agreement until this Agreement is terminated as set forth in Section 5. The Consultant will provide the Services under this Agreement commencing on January 1, 2009 ( “Start Date”). In this endeavor, Consultant shall use his independent judgment consistent with his training, skill, and experience and his services shall be performed in a thorough, efficient and workmanlike manner, promptly and with due diligence and care, and in accordance with that standard of care and skill ordinarily exercised by members of the profession doing similar services. Consultant assumes all personal risk and responsibility for his services under this Agreement.

(b) Payments to Consultant . VeriSign shall pay Consultant the following fees for performance of the Services as set forth in (i)-(iv) below.

(i) Retainer Fee . VeriSign shall pay Consultant a consulting retainer fee in the amount of Ten Thousand Dollars ($10,000) per month (the “Retainer”) for each full calendar month Consultant provides the Services until termination of this Agreement. For any less than full calendar month in which Consultant performs Consultant Services, such as at the start of this Agreement or at the termination of this Agreement, VeriSign shall pay Consultant a proportionate share of the monthly Retainer fee for that portion of the calendar month. Consultant shall be responsible for the submittal of invoices at the end of every full month. Invoices shall be paid within 30 days.

(ii) First Transaction Success Fee . In addition to the Retainer, VeriSign shall pay Consultant Three Hundred Thousand Dollars ($300,000.00) if the Closing Date for Sale of the Communications Business Bundle is on or before December 31, 2009 (“First Transaction Success Fee”). If the Closing Date for Sale of the Communications Business Bundle is after December 31, 2009, or if there is no Closing Date, Consultant shall not be entitled to any First Transaction Success Fee. If this Agreement is terminated, whether for or without cause by VeriSign or Consultant, prior to a Closing Date, Consultant shall not be entitled to any First Transaction Success Fee. The First Transaction Success Fee, if earned, is payable to Consultant either: (i) within fifteen (15) days after the Closing Date if the Purchaser has not offered Consultant an acceptable employment position; or (ii) upon the earlier of (A) the six month

2

anniversary of the Closing Date or (B) March 15 of the year following the year of the Closing Date, if the Purchaser has offered Consultant an acceptable employment position on or before the Closing date. For the purpose of this section and section (iii) below, the Consultant, in his sole discretion, shall determine whether an employment position is acceptable and shall so notify VeriSign within five (5) days after the Closing Date.

(iii) Second Transaction Success Fee . In addition to the Retainer and First Transaction Success Fee, Consultant will also be eligible to receive up to a maximum of Three Hundred Thousand Dollars ($300,000.00) subject to the valuation requirements set forth in (A) and (B) below (“Second Transaction Success Fee”). The Second Transaction Success Fee, if earned as described below, is payable to Consultant either: (i) within fifteen (15) days after the Closing Date if the Purchaser has not offered Consultant an acceptable employment position, or (ii) upon the earlier of (A) the six month anniversary of the Closing Date, or (B) March 15 of the year after the year in which the Closing Date occurs, if the Purchaser has offered Consultant an acceptable employment position on or before the Closing Date. If this Agreement is terminated, whether for or without cause by VeriSign or Consultant, prior to a Closing Date, Consultant shall not be entitled to any Second Transaction Success Fee.

(A) Valuation . The amount of the Second Transaction Success Fee that Consultant will be eligible to receive is based upon the high and low third-party valuation of the purchase price payable in connection with the Sale of the Communication Business Bundle (the “High Valuation” and “Low Valuation,” respectively, and together, the “Valuation”). The Low Valuation is $225 million ($225,000,000) and the High Valuation is $350 million ($350,000,000). The difference between the High Valuation and the Low Valuation shall be referred to herein as the “Valuation Spread.”

(B) Amount of Second Transaction Success Fee . In the event that the total purchase price paid by the Purchaser (the “Total Purchase Price”) exceeds the Low Valuation (the “Surplus”), the Consultant will be eligible to receive a payment equal to the percentage of the Surplus relative to the Valuation Spread, up to a maximum of 100% (the “Second Transaction Success Fee Percentage”) multiplied by $300,000.00 (such amount, the “Second Transaction Success Fee”). In the event that the Total Purchase Price is equal to or less than the Low Valuation, the Consultant will not be eligible to receive a Second Transaction Success Fee. In no event will the Consultant be eligible for a Second Transaction Success Fee greater than $300,000.00. The formula for the Second Transaction Success Fee can be depicted as follows:

Second Transaction Success Fee = $300,000 X ((Total Purchase Price – Low Valuation) divided by (High Valuation – Low Valuation))

Or

Second Transaction Success Fee = $300,000 X (Surplus divided by Valuation Spread)

Example: Assumptions . (a) the Low Valuation equals $225,000,000; (b) the High Valuation equals $350,000,000; (c) the Valuation Spread equals $125,000,000; (d) the Total Purchase Price equals $300,000,000; (e) the Surplus equals $75,000,000 (i.e., the Total Purchase Price less the Low Valuation).

3

Example: Determine the Second Transaction Success Fee Percentage . First, divide the Surplus ($75,000,000) by the Valuation Spread ($125,000,000), resulting in 60%. Second, multiply 60% by $300,000.00. The Second Transaction Success Fee is $180,000.00

(iv) Payment in the Event of Partial Disposition . In the event of a Sale of less than the entire Communications Business Bundle (in which case no First Transaction Success Fee and no Second Transaction Success Fee shall be payable), the parties agree to negotiate in good faith a success fee amount the parties deem fair and reasonable for the Services rendered by Consultant in connection with the Sale of less than the entire Communications Business Bundle. If this Agreement is terminated, whether for or without cause by VeriSign or Consultant, prior to a Closing Date, Consultant shall not be entitled to any payment under this section 2(b)(iv).

3. Relationship of Parties .

(a) Independent Contractor . Consultant is an independent contractor and is neither an agent nor employee of, and has no authority to bind, VeriSign by contract or otherwise. Consultant will perform the Services under the general direction of VeriSign, but Consultant will determine, in Consultant’s sole discretion, the manner and means by which the Services a