Abstract-Vi anser att ett nätverk där användare kan utfärda certifikat som identifierar de allmänna nycklarna för andra användare i nätverket. De utfärdade certifikaten i ett nätverk utgör en uppsättning certifikatkedjor mellan användarna. En användare u kan få den allmänna nyckeln till en annan användare v från en certifikatkedja från u till v i nätverket. För certifikatkedjan från u till v, u kallas källan till kedjan och v kallas destinationen för kedjan. Certifikaten i varje kedja är spridda mellan kedjans källa och destination så att följande villkor är uppfyllda: Om någon användare u måste säkert skicka meddelanden till någon annan användare v i nätverket, då u kan använda certifikat som lagras i u och v för att få den öppna nyckeln i v (då u kan använda den öppna nyckeln i v för att ställa in en delad nyckel med v för att säkert skicka meddelanden till v). Kostnaden för att sprida certifikat i en uppsättning kedjor bland käll- och destinationsanvändare i ett nätverk mäts med det totala antalet certifikat som behöver lagras i alla användare. En spridning av en uppsättning certifikatkedjor i ett nätverk är optimal om ingen annan spridning av samma kedja har en strikt lägre kostnad. I detta dokument visar vi att problemet med att beräkna optimal spridning av en given kedjeuppsättning är NP-komplett. Således minimera det totala antalet certifikat som lagras i alla användare är NP-komplett. Vi identifierar tre speciella klasser av kedjeuppsättningar som är av praktiska intressen och utformar tre polynom-tidsalgoritmer som beräknar optimala spridningar för varje klass. Vi presenterar också två polynom-tid förlängningar av dessa algoritmer för mer allmänna klasser av kedjeuppsättningar.
Jung, Elmallah och Gouda REF visar att dataspridning med minimalt antal certifikat i allmänhet är NP-Complete, och presenterade tre algoritmer för att beräkna optimal spridning för klasser av certifikatdiagram.
Optimal Dispersal of Certificate Chains
{'venue': 'IEEE Transactions on Parallel and Distributed Systems', 'journal': 'IEEE Transactions on Parallel and Distributed Systems', 'mag_field_of_study': ['Computer Science', 'Geography']}