Authentication in service oriented computing is vulnerable to various security concerns. The core concept of authentication is dependent on credentials offered at the present moment without verifying how or when the credential was obtained by the subject. Secure authentication techniques with multi-factor and cross-platform technologies are adopted by service providers. Unfortunately, such systems require a complex integration procedure of the security frameworks. Moreover, the trend of rapid service development via service composition architectures are impeded due to the diverse models of authentication factors. Hence, the adoptability of newer authentication models are limited and constrained by the feature specifications of the external cross-platform and decentralized authentication and access control frameworks. In general, authentication models are generally based on binary successes and failures, regardless of the level of access required for a given request. The combined outcome of the above complexities results in rigid policies and complex management. Our work in this paper is characterized by notions of real-life social authentication based on the nature, quality, and length of previous encounters. We delineate the fundamental similarity of authentication factors using previous interactions. We introduce the concept of interaction provenance as a unified representation model for all existing authentication factors. We present a standardized representation model for secure interaction provenance based on the W3C Provenance Working Group (PROV) model. We illustrate the practical feasibility of creating interaction provenance graphs for various interactive events in service oriented computing. The paper also presents formal security propositions toward defining secure interaction provenance schemes. We demonstrate how interaction provenance can utilize the causal relationship of past events to leverage service composition, cross-platform integration, and timeline authentication. We posit that our generic interaction provenance model also allows easier adoption of newer authentication and access control schemes. Hence, we apply fuzzy control logic for interaction provenance records to create a novel authentication and threshold based access control model. The paper presents an interaction provenance recording and authentication protocol and a proof-of-concept implementation. We demonstrate the suitability of fuzzy rules to create innovative and flexible security frameworks using linguistic policies and visualization of contour maps. We also performed extensive experiments and comparative evaluation of various provenance preservation schemes to justify the applicability for different service models.