Run Regedit.exe
Navigate to HKEY_CURRENT_USER\SOFTWARE\Microsoft\Windows\CurrentVersion\Search
Look for ‘BingSearchEnabled’, if you don't see it you will need to create it (right-click in a blank area, pick ‘New DWORD’ 32 bit. Type in ‘BingSearchEnabled’
Open BingSearchEnabled, set it to 0, press OK.
Look for ‘CortanaConsent’, again create it if you don’t have it using the method above. Also set it to 0.
Reboot.