Information theoretically secure protocol for mobile proactive secret sharing with near-optimal resilience

Patent metadata

Field	Value
Publication number	US-9558359-B1
Application number	US-201414449115-A
Country	US
Kind code	B1
Filing date	Jul 31, 2014
Priority date	Mar 13, 2013
Publication date	Jan 31, 2017
Grant date	Jan 31, 2017

Abstract

Described, is system for mobile proactive secret sharing. The system initializes a RobustShare protocol to distribute a block of secret data among a set of servers comprising n servers. The block of secret data comprises a plurality of shares of data, wherein each server in the set of servers holds one share of data encoding the block of secret data. At least one Block-Redistribute protocol is initialized to protect against at least one adversary that attempts to corrupt the set of servers. During a Block-Redistribute protocol, the set of servers periodically refreshes its plurality of shares of data such that each server holds a new share of data that is independent of the previous share of data. Finally, a Reco protocol is initialized to reveal the block of secret data.

First claim

What is claimed is:

1. A system for proactive secret sharing amongst a plurality of mobile storage platforms, the system comprising:
one or more processors and a non-transitory computer-readable medium having executable instructions encoded thereon such that when executed, the one or more processors perform operations of:
initializing a RobustShare protocol to distribute a block of secret data among a set of servers comprising n servers of a synchronous network, a plurality of the n servers each being part of a mobile storage platform, wherein the block of secret data comprises a plurality of shares of data, wherein each server in the set of servers holds one share of data encoding the block of secret data, and wherein the plurality of shares of data is transmitted electronically via a secure, authenticated broadcast channel;
initializing at least one Block-Redistribute protocol to protect against at least one adversary that attempts to corrupt the set of servers, wherein during a Block-Redistribute protocol the set of servers periodically refreshes its plurality of shares of data such that each server holds a new share of data that is independent of the previous share of data;
initializing a Reco protocol to reveal the block of secret data,
wherein a communication complexity for each of the protocols is O(W+n 3 ), where W denotes a number of secrets and O represents big O notation; and
periodically erasing, by each server, the plurality of shares of data to preserve security against an adversary.

2. The system as set forth in claim 1 , wherein the block of secret data is of size l, wherein l is the highest power of 2 not greater than n/4, and wherein each block of secret data is stored in a polynomial H of degree≦d=l+2t−1, where t denotes a threshold of corruption defines a maximum number of servers the at least one adversary may corrupt.

3. The system as set forth in claim 2 , wherein n can increase or decrease by a factor of two at each Block-Redistribute protocol regardless of t.

4. The system as set forth in claim 3 , wherein the system provides perfect security, such that provided that the at least one adversary does not corrupt more than t servers, the probability of the at least one adversary compromising the privacy or correctness of the block of secret data is zero.

5. The system as set forth in claim 4 , wherein the threshold of corruption t is ⅓−ε, where ε is an arbitrary positive constant, wherein provided that the at least one adversary corrupts no more than a ⅓−ε fraction of the set of servers, then the system maintains its security.

6. The system as set forth in claim 1 , wherein the at least one mobile storage platform has a secure erasure feature.

7. The system as set forth in claim 1 , wherein a plurality of the mobile storage platforms are cell phones.

8. The system as set forth in claim 1 , wherein as plurality of the mobile storage platforms are vehicles.

9. A computer-implemented method for proactive secret sharing amongst a plurality of mobile storage platforms, comprising:
an act of causing a data processor to execute instructions stored on a non-transitory memory such that upon execution, the data processor performs operations of:
initializing a RobustShare protocol to distribute a block of secret data among a set of servers comprising n servers of a synchronous network, a plurality of the n servers each being part of a mobile storage platform, wherein the block of secret data comprises a plurality of shares of data, wherein each server in the set of servers holds one share of data encoding the block of secret data, and wherein the plurality of shares of data is transmitted electronically via a secure, authenticated broadcast channel;
initializing at least one Block-Redistribute protocol to protect against at least one adversary that attempts to corrupt the set of servers, wherein during a Block-Redistribute protocol the set of servers periodically refreshes its plurality of shares of data such that each server holds a new share of data that is independent of the previous share of data;
initializing a Reco protocol to reveal the block of secret data,
wherein a communication complexity for each of the protocols is O(W+n 3 ) where W denotes a number of secrets and O represents big O notation; and
periodically erasing, by each server, the plurality of shares of data to preserve security against an adversary.

10. The method as set forth in claim 9 , wherein the block of secret data is of size l, wherein l is the highest power of 2 not greater than n/4, and wherein each block of secret data is stored in a polynomial H of degree≦d=l+2t−1, where t denotes a threshold of corruption defines a maximum number of servers the at least one adversary may corrupt.

11. The method as set forth in claim 10 , wherein n can increase or decrease by a factor of two at each Block-Redistribute protocol regardless of t.

12. The method as set forth in claim 11 , wherein the system provides perfect security, such that provided that the at least one adversary does not corrupt more than t servers, the probability of the at least one adversary compromising the privacy or correctness of the block of secret data is zero.

13. The method as set forth in claim 12 , wherein the threshold of corruption t is ⅓−ε, where ε is an arbitrary positive constant, wherein provided that the at least one adversary corrupts no more than a ⅓−ε fraction of the set of servers, then the system maintains its security.

14. The method as set forth in claim 9 , wherein the at least one mobile storage platform has as secure erasure feature.

15. A computer program product for proactive secret sharing amongst a plurality of mobile storage platforms, the computer program product comprising computer-readable instructions stored on a non-transitory computer-readable medium that are executable by a computer having a processor for causing the processor to perform operations of:
initializing a RobustShare protocol to distribute a block of secret data among a set of servers comprising n servers of a synchronous network, a plurality of the n servers each being part of a mobile storage platform, wherein the block of secret data comprises a plurality of shares of data, wherein each server in the set of servers holds one share of data encoding the block of secret data, and wherein the plurality of shares of data is transmitted electronically via a secure, authenticated broadcast channel;
initializing at least one Block-Redistribute protocol to protect against at least one adversary that attempts to corrupt the set of servers, wherein during a Block-Redistribute protocol the set of servers periodically refreshes its plurality of shares of data such that each server holds a new share of data that is independent of the previous share of data;
initializing a Reco protocol to reveal the block of secret data,
wherein a communication complexity for each of the protocols is O(W+n 3 ), where W denotes a number of secrets and O represents big O notation; and
periodically erasing, by each server, the plurality of shares of data to preserve security against an adversary.

16. The computer program product as set forth in claim 15 , wherein the block of secret data is of size l, wherein l is the highest power of 2 not greater than n/4, and wherein each block of secret data is stored in as polynomial H of degree≦d=l+2t−1, where t denotes a threshold of corruption defines a maximum number of servers the at least one adversary may corrupt.

17. The computer program product as set forth in claim 16 , wherein n can increase or decrease b

Assignees

• Hrl Lab Llc

Inventors

• El Defrawy Karim
• Baron Joshua W
• Lampkins Joshua D

Classifications

• G06F21/6263

  during internet communication, e.g. revealing personal data from cookies · CPC title

• H04L2209/601

  Broadcast encryption · CPC title

• G06F21/602

  Providing cryptographic facilities or services · CPC title

• H04L63/06

  for supporting key management in a packet data network (cryptographic mechanisms or cryptographic arrangements for key management H04L9/08) · CPC title

• H04L63/04

  for providing a confidential data exchange among entities communicating through data packet networks · CPC title