An electronic device, comprising: a wireless communication circuit configured to transmit or receive at least one radio frequency (RF) signal; at least one processor operatively connected with the wireless communication circuit; and a memory operatively connected with the at least one processor, wherein the memory includes instructions that, when executed, enable the electronic device to: generate a first random address of the electronic device , transmit, via the wireless communication circuit, a first advertising packet including the first random address , receive, from an external electronic device via the wireless communication circuit, a scan request corresponding to the first advertising packet , generate a first encrypted random address resulting from encrypting the first random address and a second encrypted random address resulting from encrypting a second random address corresponding to reception of the scan request , transmit, to the external electronic device via the wireless communication circuit, a scan response including the first encrypted random address and the second encrypted random address , transmit, via the wireless communication circuit, a second advertising packet including the second random address , receive, from the external electronic device, a connection request corresponding to the second advertising packet, and establish a Bluetooth connection with the external electronic device based on the connection request. a wireless communication circuit configured to transmit or receive at least one radio frequency (RF) signal; at least one processor operatively connected with the wireless communication circuit; and a memory operatively connected with the at least one processor, wherein the memory includes instructions that, when executed, enable the electronic device to: generate a first random address of the electronic device , transmit, via the wireless communication circuit, a first advertising packet including the first random address , receive, from an external electronic device via the wireless communication circuit, a scan request corresponding to the first advertising packet , generate a first encrypted random address resulting from encrypting the first random address and a second encrypted random address resulting from encrypting a second random address corresponding to reception of the scan request , transmit, to the external electronic device via the wireless communication circuit, a scan response including the first encrypted random address and the second encrypted random address , transmit, via the wireless communication circuit, a second advertising packet including the second random address , receive, from the external electronic device, a connection request corresponding to the second advertising packet, and establish a Bluetooth connection with the external electronic device based on the connection request. generate a first random address of the electronic device , transmit, via the wireless communication circuit, a first advertising packet including the first random address , receive, from an external electronic device via the wireless communication circuit, a scan request corresponding to the first advertising packet , generate a first encrypted random address resulting from encrypting the first random address and a second encrypted random address resulting from encrypting a second random address corresponding to reception of the scan request , transmit, to the external electronic device via the wireless communication circuit, a scan response including the first encrypted random address and the second encrypted random address , transmit, via the wireless communication circuit, a second advertising packet including the second random address , receive, from the external electronic device, a connection request corresponding to the second advertising packet, and establish a Bluetooth connection with the external electronic device based on the connection request. <EOS>