An electronic device, comprising: a wireless communication circuit configured to transmit or receive at least one radio frequency 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 (201, 601), transmit, via the wireless communication circuit, a first advertising packet including the first random address (203, 603), 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 (207, 609), 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 (209, 611), transmit, via the wireless communication circuit, a second advertising packet including the second random address (211, 615), 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 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 (201, 601), transmit, via the wireless communication circuit, a first advertising packet including the first random address (203, 603), 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 (207, 609), 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 (209, 611), transmit, via the wireless communication circuit, a second advertising packet including the second random address (211, 615), 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 (201, 601), transmit, via the wireless communication circuit, a first advertising packet including the first random address (203, 603), 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 (207, 609), 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 (209, 611), transmit, via the wireless communication circuit, a second advertising packet including the second random address (211, 615), 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.