Part 5:
V. PERFORMANCE EVALUATION 
A. SECURITY ANALYSIS 
In our scheme, the outsourced data includes the product information file, ID-AVL tree and PRF tree. The product information files are encrypted symmetrically based on the independent secret keys, and the cloud server does not have 
FIGURE 4. Construction time of the index structures. 
the secret keys. In this case, the plaintext files cannot be decrypted by the cloud server. In the ID-AVL tree, the stored values are the hash values of the product identifiers, and they contain no valuable information about products. The PRF tree is encrypted by the secure kNN algorithm before being out sourced to the cloud server. Though the cloud server knows the encrypted feature vectors in the tree, the cloud server does not know the matrices M1, M2; hence, the plaintext vectors in the tree cannot be recovered. 
B. PRODUCT INFORMATION SEARCH EFFICIENCY In this section, we evaluate the search efficiency of our scheme. First, we evaluate the construction time of the index structures of the product information. Specifically, we com pare our scheme with the MRSE scheme [25]. To decrease the bias of the data manager who is responsible for generating the vectors and the hash values, in this paper we employ the Enron Email Data Set [32] to test our scheme. Specifically, the data set is employed to act as the product information files. Moreover, the vectors of the product are assumed to be extracted from the data set based on the TF-IDF model, and then the vectors are organized by the PRF tree. 
As shown in Fig. 4, with the increasing number of products, the construction time of PRF tree and the index structures in MRSE monotonously increase. This is reasonable consider ing that each product information file needs to be scanned for a time to get the feature vectors. The construction time of the PRF tree is slightly longer than that of the MRSE scheme, because the vectors need to be further inserted to the trees in the PRF tree. Apparently, the ID-AVL tree is considerably simpler, and the construction time can be ignored compared with the other two trees. 
To search the desired product information, the data user needs to first generate the trapdoor, which is sent to the cloud server. The times of constructing the trapdoors with the increasing of the size of the feature dictionary are presented in Fig. 5. The search requests based on the identifiers are independent of the feature dictionary, and hence, the time of constructing the trapdoors for the ID-AVL tree remains stable. However, the construction time of the trapdoors for the MRSE and PRF trees monotonously increase with the 
FIGURE 5. Time of constructing the trapdoor. 
FIGURE 6. Search time with different number of products.
FIGURE 7. Time consumption of inserting a node into the trees.
increasing of the feature dictionary’s size. This is reasonable considering that the size of the product feature vector is equal to the size of the feature dictionary. In addition, the time costs for the MRSE and PRF trees are similar to each other because the processes of generating the trapdoors are similar. 
The search time of a trapdoor in the cloud server is pre sented in Fig. 6. It can be observed that the MRSE scheme consumes the most time to execute a search operation. Moreover, the search time increases monotonously with the increasing of the number of products. This increase can be explained by the fact that in MRSE, the feature vectors are stored in order, and they do not employ any index structure. In this case, the cloud server needs to scan all the product feature vectors to get the search result. The PRF tree organizes the vectors by a height-balanced tree, and most paths in the tree are pruned in the search process. As a consequence, the search efficiency is greatly improved. Finally, we can observe that the ID-AVL tree is the most efficient index structure, which can be explained by the fact that the ID-AVL tree is considerably simpler, and the search process is also very easy.
With the expanding growth of companies, more and more product information needs to be outsourced to the cloud server. Consequently, we need to update the index trees from time to time, and the update efficiency also affects the performance of our scheme significantly. As shown in Fig. 7, the update time of both the PRF tree and the ID-AVL tree increases slightly with the increasing number of products, which is reasonable, considering that we need to search the trees to identify the proper location of the inserted node. In addition, updating the PRF tree consumes much more energy than that of updating the ID-AVL tree. This can be explained by the fact that the ID-AVL tree is much simpler than the PRF tree, and in theory only log(N) nodes need to be searched. Though quite many paths in the PRF tree are pruned in the search process, the number of the search paths is considerably larger than log(N) and more time is thus consumed in the PRF tree.
파트 5:V. 성과 평가 A. 보안 분석 당사의 계획에서 아웃소싱 데이터에는 제품 정보 파일, ID-AVL 트리 및 PRF 트리가 포함됩니다. 제품 정보 파일은 독립적인 비밀 키를 기반으로 대칭적으로 암호화되며, 클라우드 서버에는 다음과 같은 정보가 없습니다. 그림 4. 인덱스 구조의 구축 시간. 비밀 키가 없습니다. 이 경우 일반 텍스트 파일은 클라우드 서버에서 복호화할 수 없습니다. ID-AVL 트리에 저장된 값은 제품 식별자의 해시 값이며 제품에 대한 중요한 정보는 포함하지 않습니다. PRF 트리는 클라우드 서버로 아웃소싱되기 전에 보안 kNN 알고리즘에 의해 암호화됩니다. 클라우드 서버는 트리의 암호화된 특징 벡터는 알고 있지만, 행렬 M1, M2는 알지 못하므로 트리의 일반 텍스트 벡터는 복구할 수 없습니다. B. 상품 정보 검색 효율 이 섹션에서는 제안한 스키마의 검색 효율을 평가합니다. 먼저 상품 정보 인덱스 구조의 구축 시간을 평가합니다. 구체적으로, 우리의 스키마를 MRSE 스키마[25]와 비교합니다. 벡터와 해시값을 생성하는 데이터 관리자의 편견을 줄이기 위해, 본 논문에서는 Enron 이메일 데이터 세트[32]를 사용하여 우리의 체계를 테스트합니다. 특히, 이 데이터 세트는 제품 정보 파일 역할을 하는 데 사용됩니다. 또한, 제품의 벡터는 TF-IDF 모델을 기반으로 데이터 세트에서 추출된 것으로 가정하고 벡터를 PRF 트리로 구성합니다. 그림 4에서 볼 수 있듯이, 상품 수가 증가함에 따라 MRSE에서 PRF 트리와 인덱스 구조의 구성 시간이 단조롭게 증가합니다. 이는 특징 벡터를 얻기 위해 각 제품 정보 파일을 일정 시간 동안 스캔해야 한다는 점을 고려하면 당연한 결과입니다. PRF 트리의 트리에 벡터를 추가로 삽입해야 하기 때문에 PRF 트리의 구성 시간은 MRSE 방식보다 약간 더 깁니다. 분명히 ID-AVL 트리는 상당히 간단하며 다른 두 트리에 비해 구성 시간을 무시할 수 있습니다. 원하는 상품 정보를 검색하려면 데이터 사용자가 먼저 트랩도어를 생성하여 클라우드 서버로 전송해야 합니다. 특징 사전의 크기가 증가함에 따라 트랩도어를 구성하는 시간은 그림 5에 제시되어 있습니다. 식별자에 기반한 검색 요청은 특징 사전과 무관하므로 ID-AVL 트리의 트랩도어 구성 시간은 안정적으로 유지됩니다. 그러나 MRSE와 PRF 트리에 대한 트랩도어의 구성 시간은 다음과 같이 단조롭게 증가합니다. 그림 5. 트랩도어 구성 시간. 그림 6. 제품 수에 따른 검색 시간.그림 7. 트리에 노드를 삽입하는 데 소요되는 시간.특징 사전의 크기 증가. 이는 제품 특징 벡터의 크기가 특징 사전의 크기와 같다는 점을 고려하면 합리적인 결과입니다. 또한 트랩도어를 생성하는 프로세스가 비슷하기 때문에 MRSE와 PRF 트리의 시간 비용은 서로 비슷합니다. 클라우드 서버에서 트랩도어의 검색 시간은 그림 6에 미리 전송되어 있습니다. MRSE 방식이 검색 연산을 실행하는 데 가장 많은 시간을 소비하는 것을 확인할 수 있습니다. 또한 제품 수가 증가함에 따라 검색 시간은 단조롭게 증가합니다. 이러한 증가는 MRSE에서 특징 벡터가 순서대로 저장되고 인덱스 구조를 사용하지 않기 때문으로 설명할 수 있습니다. 이 경우 클라우드 서버는 검색 결과를 얻기 위해 모든 제품 특징 벡터를 스캔해야 합니다. PRF 트리는 높이가 균형 잡힌 트리로 벡터를 구성하며, 트리의 대부분의 경로는 검색 프로세스에서 잘립니다. 결과적으로 검색 효율이 크게 향상됩니다. 마지막으로 ID-AVL 트리가 가장 효율적인 인덱스 구조임을 알 수 있는데, 이는 ID-AVL 트리가 상당히 단순하고 검색 프로세스도 매우 쉽다는 사실로 설명할 수 있습니다.기업의 성장에 따라 점점 더 많은 상품 정보를 클라우드 서버에 아웃소싱해야 합니다. 따라서 인덱스 트리를 수시로 업데이트해야 하며, 업데이트 효율은 우리 체계의 성능에도 큰 영향을 미칩니다. 그림 7에서 볼 수 있듯이 상품 수가 증가함에 따라 PRF 트리와 ID-AVL 트리의 업데이트 시간이 조금씩 증가하는데, 이는 삽입된 노드의 적절한 위치를 파악하기 위해 트리를 검색해야 한다는 점을 고려하면 당연한 결과입니다. 또한 PRF 트리를 업데이트하는 데는 ID-AVL 트리를 업데이트하는 것보다 훨씬 더 많은 에너지가 소모됩니다. 이는 ID-AVL 트리가 PRF 트리보다 훨씬 간단하고 이론적으로 로그(N) 노드만 검색하면 된다는 사실로 설명할 수 있습니다. PRF 트리의 경우 검색 과정에서 상당히 많은 경로가 잘려나가지만, 검색 경로의 수가 log(N)보다 훨씬 많기 때문에 PRF 트리에서 더 많은 시간이 소요됩니다.