買專利賣專利找龍圖騰，真高效！ 查專利查商標用IPTOP,全免費！專利年費監控用IP管家,真方便！

龍圖騰網獲悉齊魯工業大學(山東省科學院);山東省計算中心(國家超級計算濟南中心)申請的專利一種滿足K跳約束的加密圖最短路徑查詢方法獲國家發明授權專利權，本發明授權專利權由國家知識產權局授予，授權公告號為：CN119696907B 。

龍圖騰網通過國家知識產權局官網在2025-09-02發布的發明授權授權公告中獲悉：該發明授權的專利申請號/專利號為：202411890563.2，技術領域涉及：H04L9/40；該發明授權一種滿足K跳約束的加密圖最短路徑查詢方法是由楊明;高雅;吳曉明;唐勇偉;穆超;王鑫;陳振婭;劉臣勝;賀云鵬設計研發完成，并于2024-12-20向國家知識產權局提交的專利申請。

本一種滿足K跳約束的加密圖最短路徑查詢方法在說明書摘要公布了：本發明屬于保密通信的技術領域，更具體地，涉及一種滿足K跳約束的加密圖最短路徑查詢方法。所述方法包括：圖數據擁有者生成授權令牌并通過安全信道發送給圖數據查詢者；圖數據查詢者加密查詢請求并發送給圖數據擁有者；圖數據擁有者解密查詢請求對原始圖數據進行處理并加密圖數據信息發送給云服務器；云服務器接收到加密的數據處理查詢最短路徑發送給數據查詢用戶；圖數據查詢者接收到查詢的結果，利用授權令牌的sk進行解密，得到明文結果。本發明解決了現有技術數據容易泄露，查詢效率低下的問題。

本發明授權一種滿足K跳約束的加密圖最短路徑查詢方法在權利要求書中公布了：1.一種滿足k跳約束的加密圖最短路徑查詢方法，其特征在于，所述方法包括： S1、圖數據擁有者生成一個授權令牌，并通過安全信道發送給圖數據查詢者； （1） 式（1）中，sk是非對稱加密算法RSA生成的密鑰對sk,pk中的私鑰，sk必須保密，只有密鑰對的持有者才能知道，用來解密數據；pk是非對稱加密算法RSA生成的密鑰對sk,pk中的公鑰，用于加密查詢請求；k1和k2是使用偽隨機函數生成兩個密鑰k1和k2，k1用于加密后續加密路徑鄰接表，k2用于同態加密過程中加密權值，為填充邊的虛擬節點，用來混淆加密； S2、圖數據查詢者接收到授權令牌之后，將自身的查詢請求使用授權令牌中公鑰pk進行加密并發送給圖數據擁有者； S3、圖數據擁有者接收到圖數據查詢者加密后的查詢請求，使用私鑰sk進行解密，得到原始的查詢請求；然后，圖數據擁有者根據解密后的查詢請求，在圖中構建滿足k跳限制的s-t的簡單路徑，并確定需要發送給云服務器LP與RP鄰接表，最后將LP與RP鄰接表進行加密并發送給云服務器，具體的步驟包括： S31、圖數據擁有者使用sk進行解密查詢請求，獲取跳躍約束k，起點s以及終點t； S32、根據解密之后的跳躍約束k、起點s和終點t,對原圖G進行修剪，生成簡化圖； S33、對新生成的簡化圖進行中間點分割，在簡化圖中，掃描所有節點，確定哪些節點作為中間點vc，每個中間點vc將路徑分為兩部分，包括從起點s到中間點vc的路徑lp和從終點t到中間點vc的路徑rp： （2） 對應的將路徑索引分為LP和RP鄰接表，LP用于存儲從起點s到中間點vc的路徑，RP用于存儲從終點t到中間點vc的路徑； LP存儲的路徑需要滿足以下條件： （3） 式（3）中，lenlp表示從起點s到中間點vc的路徑lp的長度，Distt[vc]表示從vc到終點t的距離，k表示跳躍約束； RP存儲的路徑需要滿足以下條件： （4） 式（4）中，表示從中間點vc到終點t的路徑rp的長度，表示從起點s到中間點vc的距離； 對于每個中間點vc，存儲從起點s出發，長度從1到的所有路徑，存儲從終點t出發，長度從1到的所有路徑，LP和RP的鄰接表結構表示如下： （5） （6） 式（5）和式（6）中，表示用來存儲從s到vc的長度為i的路徑的路徑集合；表示用來存儲從中間點vc到終點t的長度為j的路徑的路徑集合；此時LP與RP鄰接表中，存儲著中間點vc以及對應的路徑集合； S34、圖數據擁有者將加密的鄰接表LP和RP發送給云服務器； 所述將LP與RP鄰接表進行加密是指，使用哈希函數H對每個遍歷到的中間點vc進行加密，將中間點的唯一標識符轉換為固定長度的哈希值，得到加密后的中間點標識Hvc；對于路徑加密，使用密鑰k1對路徑中的每個中間點標識進行加密；對于圖中邊的權值，使用同態加密算法和密鑰k2對圖中邊的權值進行加密，加密后的權值表示為[n]pkp，其中pkp表示使用同態加密算法和密鑰k2進行加密后的結果，n表示未加密的權值； S4、云服務器接收到圖數據擁有者發送的加密的鄰接表；然后，云服務器對收到的鄰接表數據對路徑信息中的權值進行比較，并將路徑信息中權值最小的路徑發送給圖數據查詢者，具體步驟如下： S41、云服務器接收圖數據擁有者發送的兩個加密鄰接表和，云服務器對中的每個中間點vc進行遍歷，尋找與中相匹配的中間點，所述相匹配是指哈希函數Hvc的值相同，一旦找到匹配的中間節點，云服務器將中的邊信息與中的邊信息進行連接形成簡單路徑；連接操作包括將左右兩邊的路徑合并，并且使用同態加密技術對邊信息中的權值進行相加； S42、云服務器將連接后的簡單路徑以及計算出的權值存儲到一個新的鄰接表path中，鄰接表path包含了從起點s到終點t的簡單路徑，以及每條路徑的總權值； S43、云服務器需要對所有連接后的簡單路徑進行比較，只保留滿足k跳躍約束的路徑，并對滿足條件的路徑中權值的大小進行比較，挑選出權值最小的路徑； S44、云服務器將挑選出的權值最小的所有路徑信息發送給圖數據查詢者； S5、圖數據查詢者接收到查詢的結果，利用授權令牌的sk進行解密，得到明文結果。

如需購買、轉讓、實施、許可或投資類似專利技術，可聯系本專利的申請人或專利權人齊魯工業大學(山東省科學院);山東省計算中心(國家超級計算濟南中心)，其通訊地址為：250000 山東省濟南市長清區西部新城大學科技園；或者聯系龍圖騰網官方客服，聯系龍圖騰網可撥打電話0551-65771310或微信搜索“龍圖騰網”。