CONFIDENTIAL TREATMENT REQUESTED AMENDED AND RESTATED

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 are accomplished, subject to the requirement that Consultant shall at all times comply with applicable law.

(b) Employment Taxes and Benefits. Consultant will report as self-employment income all compensation received by Consultant pursuant to this Agreement. Consultant will indemnify VeriSign and hold it harmless from and against all claims, damages, losses and expenses, including reasonable fees and expenses of attorneys and other professionals, relating to any obligation imposed by law on VeriSign to pay any withholding taxes, social security, unemployment or disability insurance, or similar items in connection with compensation received by Consultant pursuant to this Agreement. Consultant will not be entitled to any vacation or illness payments, or to participate in any plans, arrangements, or distributions by VeriSign pertaining to any bonus, stock option, employee stock purchase plan, profit sharing, insurance or similar benefits for VeriSign’s employees as a result of providing the Services to VeriSign as a Consultant.

(c) Liability Insurance. Consultant will maintain adequate insurance to protect Consultant from the following: (i) claims under worker’s compensation and state disability acts; (ii) claims for damages because of bodily injury, sickness, disease or death which arise out of any negligent act or omission of Consultant; and (iii) claims for damages because of injury to or destruction of tangible or intangible property, including loss of use resulting therefrom, which arise out of any negligent act or omission of Consultant.

4. Confidential Information. Consultant acknowledges and agrees that the Assignment of Invention, Nondisclosure and Nonsolicitation Agreement which was signed by the Consultant on October 1, 2008 (the “Confidentiality Agreement”) remains in full force and effect. Nothing in this Agreement alters the terms and conditions of the Confidentiality Agreement.

4

5. Term and Termination.

(a) Term. Consultant shall serve as a consultant to VeriSign under the terms and conditions of this Agreement commencing on January 1, 2009 and continuing until the earlier of December 31, 2009 or this Agreement is terminated by either party as set forth in 5(b) below. The term of this Agreement is continuous with the term of the Consulting Agreement which covered the provision of Services from December 17, 2007 through December 31, 2008.

(b) Termination of Agreement. VeriSign may terminate this Agreement effective immediately at any time for Cause (as defined below). Either party may terminate this Agreement without Cause, for any reason or no reason, by providing thirty (30) calendar days’ advance written notice of termination to the other party. In the event the Agreement is terminated by VeriSign or Consultant, VeriSign will pay to Consultant all unpaid Retainer Fees accrued as of such termination date. For purposes of this Agreement, “Cause” means any of the following: (i) Consultant’s continued or repeated failure to perform one or more of the duties listed in Exhibit C; (ii) Consultant’s commission of any act of fraud, gross misconduct or dishonesty with respect to VeriSign, any of its subsidiaries or their employees or directors; (iii) conviction of Consultant, or Consultant’s plea of guilty or “no contest,” to a felony or a crime involving moral turpitude; or (iv) Consultant’s material breach of this Agreement and/or the Confidentiality Agreement. In addition, this Agreement shall terminate upon the death or disability of Consultant.

6. Effect of Termination. Upon the termination of this Agreement for any reason each party will be released from all obligations to the other arising after the date of termination, except that termination of this Agreement will not relieve Consultant of his obligations or VeriSign of its rights under Section 4 and Consultant will promptly notify VeriSign of all VeriSign property in Consultant’s possession and, in accordance with VeriSign’s instructions, will promptly deliver to VeriSign all such VeriSign property. Regardless of the efforts of Consultant prior to termination, no payments under Sections 2(b) (ii), (iii) or (iv) shall be payable to Consultant after termination unless any and all conditions for the earning of such payments have been completely satisfied prior to the date of termination of this Agreement.

7. Limitation of Liability. EXCEPT FOR DAMAGES RESULTING FROM THE VIOLATION OF ANY CONFIDENTIALITY OBLIGATIONS ARISING UNDER THIS AGREEMENT, IN NO EVENT SHALL EITHER PARTY BE LIABLE FOR ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND IN CONNECTION WITH THIS AGREEMENT, EVEN IF INFORMED IN ADVANCE OF THE POSSIBILITY OF SUCH DAMAGES. VERISIGN’S LIABILITY IN ANY AND ALL EVENTS IS FURTHER LIMITED TO THE AMOUNT PAYABLE TO CONSULTANT UNDER SECTION 2(b) IN THIS AGREEMENT.

5

8. General.

(a) Assignment. Consultant may not assign Consultant’s rights or delegate Consultant’s duties under this Agreement either in whole or in part without the prior written consent of VeriSign. Any attempted assignment or delegation without such consent will be void.

(b) Equitable Remedies. Because the Services are personal and unique and because Consultant will have access to confidential information of VeriSign, VeriSign may enforce this Agreement and any of its provisions by injunction, specific performance or other equitable relief without prejudice to any other rights and remedies that VeriSign may have for a breach of this Agreement.

(c) Governing Law; Jurisdiction. This Agreement shall be governed by, construed and enforced in accordance with the laws of Virginia, without regard to its conflict of law principles. Any action to enforce or interpret this Agreement shall be commenced and maintained in federal or state courts in Fairfax County, Virginia. The parties to this Agreement submit to the exclusive jurisdiction of the federal and state courts of Fairfax County, Virginia. Should any provision of this Agreement be declared or determined by a court of competent jurisdiction to be invalid or otherwise unenforceable, the remaining parts, terms and provisions shall continue to be valid, legal and enforceable, and will be performed and enforced to the fullest extent permitted by law.

(d) Notices. All notices, consents and other communications required or permitted under this Agreement will be in writing and delivered by confirmed facsimile transmission, by courier or overnight delivery service with written verification of receipt, or by registered or certified mail, return receipt requested, postage prepaid, and in each instance will be deemed given when sent. All such notices, consents and other communications will be sent to the addresses set forth above or to such other address as may be specified by either party to the other in accordance with this Section.

(e) Waiver. The failure by either party to enforce any provision of this Agreement will not constitute a waiver of future enforcement of that or any other provision.

(f) Severability. If any provision of this Agreement is for any reason found to be unenforceable, the remainder of this Agreement will continue in full force and effect.

(g) Counterparts. This Agreement may be executed in counterparts, each of which will be deemed an original, but both of which together will constitute one and the same instrument. This Agreement may be executed via facsimile.

(h) Complete Understanding; Modification. This Agreement, together with the exhibits hereto, constitutes the complete and exclusive understanding and agreement of the parties regarding its subject matter and supersedes all prior understandings and agreements, whether written or oral, with respect to the subject matter hereof. Notwithstanding anything herein, any agreement between Consultant and VeriSign pertaining to the protection of VeriSign’s confidential and/or proprietary information remains enforceable and binding. Any waiver, modification or amendment of any provision of this Agreement will be effective only if in writing and signed by duly authorized representatives of the parties.

6

IN WITNESS WHEREOF, the parties have signed this Agreement as of the dates set out below.

7

EXHIBIT A

Consulting Agreement

8

EXHIBIT B

Communications Business Bundle. The Communications Business Bundle shall include all of the following Product Lines and Product Names.

The following products may, in VeriSign’s sole discretion, be included in the Communications Business Bundle.

9

EXHIBIT C

1. Services.

For the consideration described in the Agreement, Consultant shall, on behalf of VeriSign and during the term of the Agreement, discharge all of the following actions in connection with the Sale of the Communications Business Bundle. Consultant shall report directly to the Chief Executive Officer or his designee on all matters pertaining to the Services and the Communications Business Bundle:

(a) Function as the senior executive of the Communications Business Bundle business;

(b) Maintain and operate the Communications Business Bundle as a going concern to maximize its Sale value;

(c) Prepare the Communications Business Bundle for Sale;

(d) Provide assistance as requested by VeriSign in conjunction with the Sale of the Communications Business Bundle;

(e) Subject to oversight and approval by VeriSign, obtain, facilitate, manage and maintain business relationships with potential purchasers to promote negotiations with VeriSign for the Sale of the Communications Business Bundle;

(f) Introduce VeriSign to potential purchasers in order to foster such negotiations with VeriSign;

(g) Adhere to all VeriSign policies and procedures;

(h) Perform all duties reasonably related to the operation and Sale of the Communications Business Bundle as reasonably requested by VeriSign.

2. Reimbursable Expenses: VeriSign shall reimburse Consultant for expenses incurred by Consultant in performing the Services, provided, such expenses are incurred, approved and reimbursed in accordance with VeriSign’s expense reimbursement policies. Such reimbursement of expenses will be subject to the following conditions: (1) the expenses eligible for reimbursement in one taxable year shall not affect the expenses eligible for reimbursement in any other taxable year; (2) the reimbursement of an eligible expense shall be made no later than the end of the year after the year in which such expense was incurred; and (3) the right to reimbursement or in-kind benefits shall not be subject to liquidation or exchange for another benefit.

Consultant’s Federal Taxpayer ID No. / Social Security Number:

_____________________________________

10