Method and apparatus for generating forward secure pseudorandom numbers

摘要

Methods and apparatus are provided for generation of forward secure pseudorandom numbers. A forward secure pseudorandom number is generated by obtaining a first state s_i corresponding to a current leaf node v_i in a hierarchical tree, wherein the current leaf v_i produces a first pseudorandom number r_i−t and wherein the hierarchical tree comprises at least one chain comprised of a plurality of nodes on a given level of the hierarchical tree; updating the first state s_i to a second state s_i+t corresponding to a second leaf node v_i+t; and computing a second pseudorandom number r_i+t−1 corresponding to the second leaf node v_i+t. The variable t may be an integer greater than one. Updating the state does not require generation of all pseudorandom numbers produced by leaf nodes between the current leaf node v_i and the second leaf node v_i+t.