Electronic Health Records (EHRs) drive clinical care and medical research, yet hospitals, clinics, and research institutions routinely pool their records into central registries operated by a single party. Such centralization enlarges the attack surface, concentrates trust in the operator, and offers limited protection against misbehavior. Decentralized alternatives mitigate these risks but lack dynamic, fine-grained consent, and their multi-party protocols resist adaptation to this need. We present FeCaD, a deployable architecture that couples decentralized patient discovery through homomorphic encryption with dynamic, per-record consent enforcement. FeCaD allows researchers to submit encrypted predicates over distributed cohorts and to obtain encrypted indicator vectors of matching records without exposing sensitive attributes during processing. Distinctively, a per-query cryptographic consent token authorizes query classes against attribute subsets, replacing enrollment-time policies with cryptographic enforcement at evaluation time. We evaluate our open-source prototype across three representative cohorts, a clinical workload (MIMIC-IV), a domain-specific nuclear-medicine cohort, and a hospital-discharge benchmark (HCUP NIS), and find that consent-bound equality queries over 10 000 records complete on a single provider in 36 s. A hundred-provider federation returns within 14 min, placing biobank-scale discovery in the order of minutes.