Despite the notable advances in the development of high-assurance, verified implementations of cryptographic protocols, such implementations typically face significant performance overheads, particularly due to the penalties induced by formal verification and automated extraction of executable code. In this paper, we address some core performance challenges facing computer-aided cryptography by presenting a formal treatment for accelerating such verified implementations based on multiple generic optimizations covering parallelism and memory access. We illustrate our techniques for addressing such performance bottlenecks using the Line-Point Zero-Knowledge (LPZK) protocol as a case study. Our starting point is a new verified implementation of LPZK that we formalize and synthesize using EasyCrypt; our first implementation is developed to reduce the proof effort and without considering the performance of the extracted executable code. We then show how such (automatically) extracted code can be optimized in three different ways to obtain a 3000x speedup and thus matching the performance of the manual implementation of LPZK of lpzkv2.[13] We obtain such performance gains by first modifying the algorithmic specifications, then by adopting a provably secure parallel execution model, and finally by optimizing the memory access structures. All optimizations are first formally verified inside EasyCrypt, and then executable code is automatically synthesized from each step of the formalization. For each optimization, we analyze performance gains resulting from it and also address challenges facing the computer-aided security proofs thereof, and challenges facing automated synthesis of executable code with such an optimization.

Fully Homomorphic Encryption (FHE) enables offloading computation to untrusted servers with cryptographic privacy. Despite its attractive security, FHE is not yet widely adopted due to its prohibitive overheads, about 10,000X over unencrypted computation. Recent FHE accelerators have made strides to bridge this performance gap. Unfortunately, prior accelerators only work well for simple programs, but become inefficient for complex programs, which bring additional costs and challenges.

MPC-in-the-Head (MitH) is a general framework that enables constructing efficient zero-knowledge (ZK) protocols for NP relations from secure multiparty computation (MPC) protocols. In this paper we present the first machine-checked implementations of MitH.

Secure Multiparty Computation (MPC) enables a group of n</> distrusting parties to jointly compute a function using private inputs. MPC guarantees correctness of computation and confidentiality of inputs if no more than a threshold t</> of the parties are corrupted. Proactive MPC (PMPC) addresses the stronger threat model of a \emphmobile adversary that controls a changing set of parties (but only up to t</> at any instant), and may eventually corrupt all n</> parties over a long time. This paper takes a first stab at developing high-assurance implementations of (P)MPC. We formalize in \EasyCrypt, a tool-assisted framework for building high-confidence cryptographic proofs, several abstract and reusable variations of secret sharing and of (P)MPC protocols building on them. Using those, we prove a series of abstract theorems for the proactive setting. We implement and perform computer-checked security proofs of concrete instantiations of the required (abstract) protocols in \EasyCrypt. We also develop a new tool-chain to extract high-assurance executable implementations of protocols formalized and verified in \EasyCrypt. Our tool-chain uses \Why as an intermediate tool, and enables us to extract executable code from our (P)MPC formalizations. We conduct an evaluation of the extracted executables by comparing their performance to performance of manually implemented versions using \textsfPython -based \textsfCharm framework for prototyping cryptographic schemes. We argue that the small overhead of our high-assurance executables is a reasonable price to pay for the increased confidence about their correctness and security.

Remote Attestation ( RA) is a security service that enables a trusted verifier ( Vrf) to measure current memory state of an untrusted remote prover ( Prv). If correctly implemented, RA allows Vrf to remotely detect if Prv's memory reflects a compromised state. However, RA by itself offers no means of remedying the situation once P rv is determined to be compromised. In this work we show how a secure RA architecture can be extended to enable important and useful security services for low-end embedded devices. In particular, we extend the formally verified RA architecture, VRASED, to implement provably secure software update, erasure, and system-wide resets. When (serially) composed, these features guarantee to Vrf that a remote Prv has been updated to a functional and malware-free state, and was properly initialized after such process. These services are provably secure against an adversary (represented by malware) that compromises Prv and exerts full control of its software state. Our results demonstrate that such services incur minimal additional overhead (0.4% extra hardware footprint, and 100-s milliseconds to generate combined proofs of update, erasure, and reset), making them practical even for the lowest-end embedded devices, e.g., those based on MSP430 or AVR ATMega micro-controller units (MCUs). All changes introduced by our new services to VRASED trusted components are also formally verified.

Remote Attestation (RA) of embedded/smart/IoT devices is a very important issue on today's security landscape. RA enables a verifier to measures the current internal memory state of an untrusted remote device (prover). RA helps the verifier establish a static or dynamic root of trust in prover. Despite much prior work, state-of-the-art RA techniques unfortunately still lack any solid foundation and offer no ironclad security, safety or robustness guarantees. This paper argues that computer-aided formal verification, and synthesis of executables, of RA protocols and hybrid (software-hardware) architectures is required and currently unaddressed. We believe that this is achievable with current (computer-aided) formal methods frameworks and tools, and that this can help advance and mature RA research if used to establish more rigorous and clear security arguments. To support our opinion, we highlight several examples where subtle issues were missed in the design and security analysis of RA techniques. Despite deceptive simplicity of such protocols, manual analyses and ad hoc implementations often lead to over-simplification of (and subsequent glossing over) important details in the underlying processor and system architectures. Computer-aided formal verification forces a more scrupulous and disciplined consideration of such details, since, otherwise, verification simply fails. The key objective of the research direction we propose is to increase confidence in correctness and security guarantees of current and future RA techniques and their implementations.

Assuring integrity of information (e.g., data and/or software) is usually accomplished by cryptographic means, such as hash functions or message authentication codes (MACs). Computing such integrity-ensuring functions can be time-consuming if the amount of input data is large and/or the computing platform is weak. At the same time, in real-time or safety-critical settings, it is often impractical or even undesirable to guarantee atomicity of computing a time-consuming integrity-ensuring function. Meanwhile, standard correctness and security definitions of such functions assume that input data (regardless of its size) remains consistent throughout computation. However, temporal consistency may be lost if another process interrupts execution of an integrity-ensuring function and modifies portions of input that either or both: (1) were already processed, or (2) were not processed yet. Lack of temporal consistency might yield an integrity result that is non-sensical or simply incorrect. Such subtleties and discrepancies between (implicit) assumptions in definitions and implementations can be a source of inconsistenceies, which might lead to vulnerabilities.

Remote attestation (RA) is a means of malware detection, typically realized as an interaction between a trusted verifier and a potentially compromised remote device (prover). RA is especially relevant for low-end embedded devices that are incapable of protecting themselves against malware infection. Most current RA techniques require on-demand and uninterruptible (atomic) operation. The former fails to detect transient malware that enters and leaves between successive RA instances; the latter involves performing potentially time-consuming computation over prover's memory and/or storage, which can be harmful to the device's safety-critical functionality and general availability. However, relaxing either on-demand or atomic RA operation is tricky and prone to vulnerabilities. This paper identifies some issues that arise in reconciling requirements of safety-critical operation with those of secure remote attestation, including detection of transient and self-relocating malware. It also investigates mitigation techniques, including periodic self-measurements as well as interruptible attestation modality that involves shuffled memory traversals and various memory locking mechanisms.

While the cyber insurance market has been growing significantly in recent years, its insurance providers face several challenges: first, there is a lack of standardized frameworks to rate ""cyber""; second, there's a shortage of relevant data to calculate premiums; and third, security postures of insured organizations constantly change. Unlike other types of insurance, cyber insurance requires creating a continuous feedback loop between customers and insurers. In this article, we introduce BlockCIS, a blockchain-based continuous monitoring and processing system for cyber insurance. BlockCIS aims to realize an automated, real-time, and immutable feedback loop between the insurer, its customer, third parties and potential auditors. As an example instantiation, we prototype BlockCIS using the open source Hyperledger Composer blockchain framework.

In the last decade, Remote Attestation (RA) emerged as a distinct security service for detecting attacks on embedded devices, cyber-physical systems (CPS) and Internet of Things (IoT) devices. RA involves verification of current internal state of an untrusted remote hardware platform (prover) by a trusted entity (verifier). RA can help the latter establish a static or dynamic root of trust in the prover and can also be used to construct other security services, such as software updates and secure deletion. Various RA techniques with different assumptions, security features and complexities, have been proposed for the single-prover scenario. However, the advent of IoT brought about the paradigm of many interconnected devices, thus triggering the need for efficient collective attestation of a (possibly mobile) group or swarm of provers. Though recent work has yielded some initial concepts for swarm attestation, several key issues remain unaddressed, and practical realizations have not been explored.

Attacking cloud-enabled storage is becoming increasingly lucrative as more personal and enterprise data moves to the cloud. Traditional security mechanisms temporarily limit such attacks, but over a long period of time attackers will eventually find vulnerabilities; this can lead to compromising large amounts of valuable data and lead to large-scale privacy breaches. This paper addresses this problem by incorporating proactive security guarantees into cloud-enabled storage. Proactive security deals with an adversary's ability to eventually compromise all involved servers in a distributed storage or computation system. While there are several proactively secure secret sharing protocols that can be used to improve confidentiality of data stored in the cloud, their high overhead has traditionally limited them to less than ten parties and to only 100s of bytes typical for cryptographic keys. Realizing proactively secure cloud storage for larger data (e.g, MBs) requires careful design and calibration of system parameters, and faces several challenges. In this paper we design, implement and assess performance of the first system for Proactively Secure Cloud-Enabled Storage (PiSCES) of data larger than cryptographic keys. Based on our practical performance results we advocate that the high level of resilience and long-term security and confidentiality guarantees enabled by proactive security should be considered in future distributed and cloud-based storage and computing services.

Self-stabilization refers to the ability of systems to recover after temporal violations of conditions required for their correct operation. Such violations may lead the system to an arbitrary state from which it should automatically recover. Today, beyond recovering functionality, there is a need to recover security and confidentiality guarantees as well. To the best of our knowledge, there are currently no self-stabilizing protocols that also ensure recovering confidentiality, authenticity, and integrity properties. Specifically, self-stabilizing systems are designed to regain functionality which is, roughly speaking, desired input output relation, ignoring the security and confidentiality of computation and its state. Distributed (cryptographic) protocols for generic secure and privacy-preserving computation, e.g., secure Multi-Party Computation (MPC), usually ensure secrecy of inputs and outputs, and correctness of computation when the adversary is limited to compromise only a fraction of the components in the system, e.g., the computation is secure only in the presence of an honest majority of involved parties. While there are MPC protocols that are secure against a dishonest majority, in reality, the adversary may compromise all components of the system for a while; some of the corrupted components may then recover, e.g., due to security patches and software updates, or periodical code refresh and local state consistency check and enforcement based on self-stabilizing hardware and software techniques. It is currently unclear if a system and its state can be designed to always fully recover following such individual asynchronous recoveries. This paper introduces Secure Self-stabilizing Computation which answers this question in the affirmative. Secure self-stabilizing computation design ensures that secrecy of inputs and outputs, and correctness of the computation are automatically regained, even if at some point the entire system is compromised. We consider the distributed computation task as the implementation of virtual global finite satiate machine (FSM) to present commonly realized computation. The FSM is designed to regain consistency and security in the presence of a minority of Byzantine participants, e.g., one third of the parties, and following a temporary corruption of the entire system. We use this task and settings to demonstrate the definition of secure self-stabilizing computation. We show how our algorithms and system autonomously restore security and confidentiality of the computation of the FSM once the required corruption thresholds are again respected.

Remote Attestation (RA) allows a trusted entity (verifier) to securely measure internal state of a remote untrusted hardware platform (prover). RA can be used to establish a static or dynamic root of trust in embedded and cyber-physical systems. It can also be used as a building block for other security services and primitives, such as software updates and patches, verifiable deletion and memory resetting. There are three major types of RA designs: hardware-based, software-based, and hybrid, each with its own set of benefits and drawbacks.

In a secret sharing scheme a dealer shares a secret s among n parties such that an adversary corrupting up to t parties does not learn s, while any t+1 parties can efficiently recover s. Over a long period of time all parties may be corrupted thus violating the threshold, which is accounted for in Proactive Secret Sharing (PSS). PSS schemes periodically rerandomize (refresh) the shares of the secret and invalidate old ones. PSS retains confidentiality even when all parties are corrupted over the lifetime of the secret, but no more than t during a certain window of time, called the refresh period. Existing PSS schemes only guarantee secrecy in the presence of an honest majority with less than n2 total corruptions during a refresh period; an adversary corrupting a single additional party, even if only passively, obtains the secret. This work is the first feasibility result demonstrating PSS tolerating a dishonest majority, it introduces the first PSS scheme secure against t<n passive adversaries without recovery of lost shares, it can also recover from honest faulty parties losing their shares, and when tolerating e faults the scheme tolerates t<n-e passive corruptions. A non-robust version of the scheme can tolerate t

Most current digital currency schemes and associated ledgers are either centralized or completely distributed similar to the design adopted by Bitcoin. Centralized schemes enable accountability, but leave the privacy of users' identities and transactions in the hands of one organization. Distributed schemes can ensure better privacy but provide little accountability. In this paper we design a privacy-preserving proactively-secure distributed ledger and associated transaction protocols that can be used to implement an accountable digital currency that inherits the ledger's privacy and security features. One of the main technical challenges that we address is dealing with the increase in ledger size over time, an unavoidable aspect as the currency spreads and the ledger is required to be maintained for a long time in the future. We accomplish this by reducing the distributed (secret-shared) storage footprint and the required bandwidth and computation for proactively refreshing the ledger to ensure long-term confidentiality and security. In the full version, we provide performance analysis of some of the subprotocols to estimate the time required to perform transactions and the proactive refreshing of the ledger.

In this paper we argue that privacy-preserving digital coins with low computation and communication overhead can be utilized as micropayments to harden online applications and services. We call such digital coins App Coins, and the applications that use them App Coins-hardened applications. Our thesis is that App Coins-hardened applications can greatly increase the financial cost (to the attackers) of large classes of malicious behavior on the Internet. App Coins can also be used to incentivize and reward cooperative and honest online behavior. We develop cryptographic protocols for such privacy-preserving non-malleable and double-spending resistant App Coins. We show how to modify two sample applications, email and onion routing, to utilize such App Coins. Our performance analysis demonstrates that our protocols are practical and can be easily implemented using commodity hardware.

In PODC 1991 Ostrovsky and Yung [35] introduced the proactive security model, where corruptions spread throughout the network, analogous to the spread of a virus or a worm. PODC 2006 distinguished lecture by Danny Dolev, that also appears in the PODC06 proceedings, lists the above work as one of PODC's "Century Papers at the First Quarter-Century Milestone" [22]. At the very center of this work is the notion of proactive secret sharing schemes. Secret sharing schemes allow a dealer to distribute a secret among a group of parties such that while the group of parties jointly possess the secret, no sufficiently small subset of the parties can learn any information about the secret. The secret can be reconstructed only when a sufficient number of shares are combined together. Most secret sharing schemes assume that an adversary can only corrupt some fixed number of the parties over the entire lifetime of the secret; such a model is unrealistic in the case where over a long enough period of time, an adversary can eventually corrupt all parties or a large enough fraction that exceeds such a threshold. More specifically, in the proactive security model, the adversary is not limited in the number of parties it can corrupt, but rather in the rate of corruption with respect to a "rebooting" rate. Ostrovsky and Yung proposed the first proactive secret sharing scheme, which received a lot of follow-up attention. In the same paper, Ostrovsky and Yung also showed that constructing a general purpose secure multiparty computation (MPC) protocol in the proactive security model is feasible as long as the rate of corruption is a constant fraction of the parties. Their result, however, was shown only for stand-alone security and incurred a large polynomial communication overhead for each gate of the computation. Following the initial work defining the proactive security model, numerous cryptographic primitives and distributed protocols have been adapted to the proactive security model, such as proactively secure threshold encryption, proactive Byzantine agreement, proactive key management, proactive digital signatures, and many others. All these results use proactive secret sharing schemes. In this paper, we introduce a new "packed" proactive secret sharing (PPSS) scheme, where the amortized communication and the amortized computational cost of maintaining each individual secret is optimal (e.g., a constant rate), resolving a long standing problem in this area. Assuming secure point-to-point channels and authenticated, reliable broadcast over a synchronous network, our PPSS scheme can tolerate a 1/3-ε (resp. 1/2-ε) corruption rate against a malicious adversary, and is perfectly (resp. statistically) UC-secure, whereas all previous proactive secret sharing schemes have been secure under cryptographic assumptions only. As an application of our PPSS scheme, we show how to construct a proactive multiparty computation (PMPC) protocol with the same threshold as the PPSS scheme and near-linear communication complexity. PMPC problem is very general and implies, for example, proactive Byzantine Agreement. Our PMPC result also matches the asymptotic communication complexity of the best known MPC results in the "classical" model of stationary faults [19].

Network coding (NC) has frequently been promoted as an approach for improving throughput in wireless networks. Existing work has mostly focused on the fundamental aspects of NC, while constraints arising in real-world network deployments have not received much attention. In particular, NC requires network nodes to overhear each other's packets, which oftentimes contradicts many security standards that attempt to provide link-layer confidentiality, e.g., by utilizing pairwise encryption keys as is the case IEEE 802.11i and ZigBee. There is an inherent trade-off between gains from NC and link-layer security: if many nodes share the secret link-layer key, NC will improve throughput, yet a leakage of the key will affect many nodes. On the other hand, having distinct secret keys will increase resilience against key compromise, but will also minimize the coding gain. We formulate this security vs. performance trade-off as an optimization problem and evaluate the effectiveness of NC under different sizes of key-sharing groups and network topologies. Our results show that increasing the key-sharing group by a single node can result in a maximum coding gain between 1.3% and 13.7%.

In this paper we consider the problem of secure pattern matching that allows single-character wildcards and substring matching in the malicious (stand-alone) setting. Our protocol, called 5PM, is executed between two parties: Server, holding a text of length n, and Client, holding a pattern of leng th m to be matched against the text, where our notion of matching is more general than traditionally considered and includes non-binary alphabets, non-binary Hamming distance and non-binary substring matching. 5PM is the first secure expressive pattern matching protocol designed to optimize round complexity by carefully specifying the entire protocol round by round. 5PM requires only eight rounds in the malicious (static corruptions) model. In the malicious model, 5PM requires O((m+n)k2) communication complexity and O(m+n) encryptions, where m is the pattern length and n is the text length. Further, 5PM can hide pattern size with no asymptotic additional costs in either computation or bandwidth.

Mobile Ad-Hoc Networks (MANETs) are particularly useful and well-suited for critical scenarios, including military, law enforcement as well as emergency rescue and disaster recovery. When operating in hostile or suspicious settings, MANETs require communication security and privacy, especially, in underlying routing protocols. Unlike most networks, where communication is based on long-term identities (addresses), we argue that the location-centric communication paradigm is better-suited for privacy in suspicious MANETs. To this end, we construct an on-demand location-based anonymous MANET routing protocol (PRISM) that achieves privacy and security against both outsider and insider adversaries. We analyze the security, privacy and performance of PRISM and compare it to alternative techniques. Results show that PRISM is more efficient and offers better privacy than prior work.

In most common mobile ad hoc networking (MANET) scenarios, nodes establish communication based on long-lasting public identities. However, in some hostile and suspicious settings, node identities must not be exposed and node movements should be untraceable. Instead, nodes need to communicate on the basis of their current locations. While such MANET settings are not very common, they do occur in military and law enforcement domains and require high security and privacy guarantees. In this paper, we address a number of issues arising in suspicious location-based MANET settings by designing and analyzing a privacy-preserving and secure link-state based routing protocol (ALARM). ALARM uses nodes' current locations to securely disseminate and construct topology snapshots and forward data. With the aid of advanced cryptographic techniques (e.g., group signatures), ALARM provides both security and privacy features, including node authentication, data integrity, anonymity, and untraceability (tracking-resistance). It also offers protection against passive and active insider and outsider attacks. To the best of our knowledge, this work represents the first comprehensive study of security, privacy, and performance tradeoffs in the context of link-state MANET routing.

Physical-layer identification of wireless devices, commonly referred to as Radio Frequency (RF) fingerprinting, is the process of identifying a device based on transmission imperfections exhibited by its radio transceiver. It can be used to improve access control in wireless networks, revent device cloning and complement message authentication protocols. This paper studies the feasibility of performing impersonation attacks on the modulation-based and transient-based fingerprinting techniques. Both techniques are vulnerable to impersonation attacks; however, transient-based techniques are more difficult to reproduce due to the effects of the wireless channel and antenna in their recording process. We assess the feasibility of performing impersonation attacks by extensive measurements as well as simulations using collected data from wireless devices. We discuss the implications of our findings and how they affect current device identification techniques and related applications.

Mobile Ad-Hoc Networks (MANETs) are particularly useful and well-suited for critical scenarios, including military, law enforcement as well as emergency rescue and disaster recovery. When operating in hostile or suspicious settings, MANETs require communication security and privacy, especially, in underlying routing protocols. This paper focuses on privacy aspects of mobility. Unlike most networks, where communication is based on long-term identities (addresses), we argue that the location-centric communication paradigm is better-suited for privacy in suspicious MANETs. To this end, we construct an on-demand location-based anonymous MANET routing protocol (PRISM) that achieves privacy and security against both outsider and insider adversaries. We analyze security, privacy and performance of PRISM and compare it to alternative techniques. Results show that PRISM is more computationally efficient and offers better privacy than prior work.

In many traditional mobile network scenarios, nodes establish communication on the basis of persistent public identities. However, in some hostile and suspicious MANET settings, node identities must not be exposed and node movements must be untraceable. Instead, nodes need to communicate on the basis of nothing more than their current locations. In this paper, we address some interesting issues arising in such MANETs by designing an anonymous routing framework (ALARM). It uses nodes' current locations to construct a secure MANET map. Based on the current map, each node can decide which other nodes it wants to communicate with. ALARM takes advantage of some advanced cryptographic primitives to achieve node authentication, data integrity, anonymity and untraceability (tracking-resistance). It also offers resistance to certain insider attacks.

Cross-Layer design has been the focus of several recent research efforts. Due to the highly variable nature of the links used in wireless communication systems and the resource-poor nature of the wireless mobile devices, there have been multiple research efforts to improve the performance of the protocol stack by allowing cross-layer interaction in wireless systems. Cross-layer interaction means allowing communication of a layer with any other possibly non-adjacent layer in the protocol stack. Several issues related to the cross-layer design paradigm need to be addressed before it can achieve its promises. One of these issues is to have a well defined framework that manages the interaction between the different layers of the protocol stack, such that the modularity of the stack is preserved while still achieving the flexibility and adaptability which cross-layer design promises. This paper addresses this issue by proposing a cross-layer coordination framework for next generation wireless systems. The proposed framework enables the interaction between non-adjacent layers in a systematic organized way while preserving the modularity of each layer. The proposed framework addresses some of the concerns stated in recent research about cross-layer design. We believe that the existence of such a framework will ease the development of cross-layer design schemes.