Malbim: There are three kinds of covenants between nations. (a) Neighboring nations agree not to cross the border and damage each other. This is between the people themselves. (b) They agree to help each other against enemies, or to allow trade. This is between the kings, e.g. the Bris of Shlomo and Chiram. It applies even if the nations are not neighbors, but not if they are at different ends of the world, for then they cannot help each other. (c) One accepts the creed of the other. This is between the people themselves, and can be even if they are at different ends of the world. These emissaries came to the entire nation, and requested a Bris against damage. The people did not believe them, for a Bris with a distant nation is only for help, and is between the kings.