Naaman received a Ph.D in Computer Science from Stanford University in 2005, where he was advised by computer scientist Héctor García-Molina. He also earned an undergraduate degree from Tel Aviv University.
