Un document déclassifié de la CIA au sujet des frontières marocaines au niveau du Sahara oriental, a confirmé le caractère marocain de territoires aujourd'hui considérés comme algériens. Le document déclassifié par la Central Intelligence Agency (CIA), le renseignement américain, en 2004, et révélé par The North Africa Post, a indiqué que la souveraineté du Maroc s'étendait de Hassi Beida (province de Béchar) jusqu'à la ville de Tinjoub (sud de Mhamid Ghizlane). Il indique par ailleurs la responsabilité de la France dans le tracé des frontières et les territoires annexés qui n'appartiennent pas à l'Algérie, à la source du différend territorial entre le Maroc et l'Algérie. Le document explique que l'administration française au Maroc et de l'Algérie avait redéfini à plusieurs reprises la ligne administrative séparant le Maroc de la juridiction algérienne française et qu'elle avait favorisé l'Algérie, qui faisait légalement partie de la France. La CIA qui reconnait de facto à travers ce document la souveraineté marocaine sur le Sahara oriental, « renforce la position juridique et les droits historiques du Maroc pour la libération des derniers territoires sahariens occupés illégalement annexés pendant l'Algérie française au détriment du Maroc », indique pour sa part The North Africa Post. Le document officiel américain déclassifié retrace les dates clés du conflit entre le Maroc et l'Algérie, comme la Guerre des sables de 1963, et explique que le tronçon sud-saharien de la frontière maroco-algérienne de Figuig jusqu'au Sahara n'a jamais été délimité. Les renseignements américains rappellent encore que dès l'indépendance du Maroc en 10 956, la question de la récupération des terres marocaines annexées par la France en Algérie a été posée. Après avoir accédé à l'indépendance en 1956, les Marocains ont soulevé la question de la récupération de leurs territoires sahariens annexés à l'époque de l'Algérie française, ajoute la note de service des services de renseignement américains. En 1958, alors que les rebelles algériens opéraient dans la zone saharienne, la France et le Maroc « se sont mis d'accord de manière informelle » sur des zones opérationnelles respectives afin d'éviter des affrontements entre leurs forces, mais la France a étendu l'occupation au nord et à l'ouest des lignes précédentes, et la nouvelle ligne n'a reçu aucun statut juridique, souligne le document de la CIA. « Cette ligne est pourtant adoptée par les Algériens. Les Marocains insistent sur le fait que la véritable frontière est une ligne antérieure, qui place les postes de Hassi Beida et Tinjoub au Maroc. Ces postes sont importants, car ils se trouvent sur la principale piste caravanière reliant Colomb-Béchar et Tindouf », révèle le document américain. La note de la CIA cite, aussi un accord conclu en 1961 entre feu le Roi Hassan II et Ferhat Abbas, qui était alors Premier ministre du gouvernement provisoire algérien, pour récupérer le Sahara oriental marocain une fois que l'Algérie serait indépendante, mais les dirigeants algériens ont renversé Abbas et ont refusé de restituer les terres marocaines sahariennes orientales.
