Previous studies have revealed that gait rhythm fluctuations convey important information, which is useful for understanding certain types of neurodegenerative diseases such as Amyotrophic Lateral Sclerosis (ALS), Huntington's disease (HD) and Parkinson's disease (PD). However, previous investigations only focused on the locomotor patterns of each individual foot rather than the relations between both feet. Therefore, in our study, phase synchronization (the index ρ) and conditional entropy (Hc) were applied to the five types of time series pairs of gait rhythms (stride time, swing time, stance time, % swing time and % stance time). The results revealed that compared with the patients with ALS, HD and PD, gait rhythms of normal subjects have the strongest phase synchronization property and minimum conditional entropy value. In addition, the indices ρ and Hc cannot only significantly differentiate among the four groups of subjects (ALS, HD, PD and control) but also have the ability to discriminate between any two of these subject groups. Finally, three representative classifiers were utilized in order to evaluate the possible capabilities of the indices ρ and Hc to distinguish the patients with neurodegenerative diseases from the healthy subjects, and achieved maximum area under the curve (AUC) values of 0.959, 0.928 and 0.824 for HD, PD and ALS detection, respectively. In summary, our study provides insight into the relational analysis between gait rhythms measured from both feet, and suggests that it should be considered seriously in the future studies investigating the impact of neurodegenerative disease and potential therapeutic intervention.