Graph Coloring Applied to Secure Computation in Non-Abelian Groups

We study the natural problem of secure n-party computation (in the computationally unbounded attack model) of circuits over an arbitrary finite non-Abelian group (G,?), which we call G-circuits. Besides its intrinsic interest, this problem is also motivating by a completeness result of Barrington, stating that such protocols can be applied for general secure computation of arbitrary functions. For flexibility, we are interested in protocols which only require black-box access to the group G (i.e. the only computations performed by players in the protocol are a group operation, a group inverse, or sampling a uniformly random group element). Our investigations focus on the passive adversarial model, where up to t of the n participating parties are corrupted. Our results are as follows. We initiate a novel approach for the construction of black-box protocols for G-circuits based on k-of-k threshold secret-sharing schemes, which are efficiently implementable over any black-box (non-Abelian) group G. We reduce the problem of constructing such protocols to a combinatorial coloring problem in planar graphs. We then give three constructions for such colorings. Our first approach leads to a protocol with optimal resilience t<n/2, but it requires exponential communication complexity $O({\binom{2 t+1}{t}}^{2} \cdot N_{g})$ group elements and round complexity $O(\binom{2 t + 1}{t} \cdot N_{g})$ , for a G-circuit of size N _g . Nonetheless, using this coloring recursively, we obtain another protocol to t-privately compute G-circuits with communication complexity $\mathcal{P}\mathit{oly}(n)\cdot N_{g}$ for any t∈O(n ^1?? ) where ? is any positive constant. For our third protocol, there is a probability δ (which can be made arbitrarily small) for the coloring to be flawed in term of security, in contrast to the first two techniques, where the colorings are always secure (we call this protocol probabilistic, and those earlier protocols deterministic). This third protocol achieves optimal resilience t<n/2. It has communication complexity O(n ^5.056(n+log?δ ^?1)²?N _g ) and the number of rounds is O(n ^2.528?(n+log?δ ^?1)?N _g ).     

Almost-Everywhere Secure Computation with Edge Corruptions

We consider secure multi-party computation (MPC) in a setting where the adversary can separately corrupt not only the parties (nodes) but also the communication channels (edges), and can furthermore choose selectively and adaptively which edges or nodes to corrupt. Note that if an adversary corrupts an edge, even if the two nodes that share that edge are honest, the adversary can control the link and thus deliver wrong messages to both players. We consider this question in the information-theoretic setting, and require security against a computationally unbounded adversary.In a fully connected network the above question is simple (and we also provide an answer that is optimal up to a constant factor). What makes the problem more challenging is to consider the case of sparse networks. Partially connected networks are far more realistic than fully connected networks, which led Garay and Ostrovsky [Eurocrypt’08] to formulate the notion of (unconditional) almost everywhere (a.e.) secure computation in the node-corruption model, i.e., a model in which not all pairs of nodes are connected by secure channels and the adversary can corrupt some of the nodes (but not the edges). In such a setting, MPC among all honest nodes cannot be guaranteed due to the possible poor connectivity of some honest nodes with other honest nodes, and hence some of them must be “given up” and left out of the computation. The number of such nodes is a function of the underlying communication graph and the adversarial set of nodes.In this work we introduce the notion of almost-everywhere secure computation with edge corruptions, which is exactly the same problem as described above, except that we additionally allow the adversary to completely control some of the communication channels between two correct nodes—i.e., to “corrupt” edges in the network. While it is easy to see that an a.e. secure computation protocol for the original node-corruption model is also an a.e. secure computation protocol tolerating edge corruptions (albeit for a reduced fraction of edge corruptions with respect to the bound for node corruptions), no polynomial-time protocol is known in the case where a constant fraction of the edges can be corrupted (i.e., the maximum that can be tolerated) and the degree of the network is sublinear.We make progress on this front, by constructing graphs of degree O(n ^? ) (for arbitrary constant 0<?<1) on which we can run a.e. secure computation protocols tolerating a constant fraction of adversarial edges. The number of given-up nodes in our construction is μn (for some constant 0<μ<1 that depends on the fraction of corrupted edges), which is also asymptotically optimal.     

More Efficient Oblivious Transfer Extensions

Oblivious transfer (OT) is one of the most fundamental primitives in cryptography and is widely used in protocols for secure two-party and multi-party computation. As secure computation becomes more practical, the need for practical large-scale OT protocols is becoming more evident. OT extensions are protocols that enable a relatively small number of “base-OTs” to be utilized to compute a very large number of OTs at low cost. In the semi-honest setting, Ishai et al. (Advances in cryptology—CRYPTO’03, vol 2729 of LNCS, Springer, 2003) presented an OT extension protocol for which the cost of each OT (beyond the base-OTs) is just a few hash function operations. In the malicious setting, Nielsen et al. (Advances in cryptology—CRYPTO’12, vol 7417 of LNCS, Springer, 2012) presented an efficient OT extension protocol for the setting of malicious adversaries that is secure in a random oracle model. In this work, we improve OT extensions with respect to communication complexity, computation complexity, and scalability in the semi-honest, covert, and malicious model. Furthermore, we show how to modify our maliciously secure OT extension protocol to achieve security with respect to a version of correlation robustness instead of the random oracle. We also provide specific optimizations of OT extensions that are tailored to the use of OT in various secure computation protocols such as Yao’s garbled circuits and the protocol of Goldreich–Micali–Wigderson, which reduce the communication complexity even further. We experimentally verify the efficiency gains of our protocols and optimizations.     

无线信道中的Polar码协商

近年来,无线通信物理层安全逐渐成为一个研究热点,而密钥协商是物理层密码技术的关键部分。针对无线信道特征密钥提取技术中获得的信道特征不完全一致的问题,论文提出了一种基于Polar码的逆向密钥协商方案。合法用户(Alice和Bob)分别通过信道估计获得自已的原始密钥,然后Bob对原始密钥进行Polar码逆编码,并将冻结位信息传输给Alice。在冻结位及其位置信息的基础上,Alice进行Polar码译码后,再通过Polar的编码,获得与Bob一致的密钥序列。仿真结果表明基于Polar码的密钥协商协议,密钥的一致性得到显著提升,且与同等条件下的基于低密度奇偶校验码协商协议相比,可获得更高的纠错成功率。      

Input Locality and Hardness Amplification

We establish new hardness amplification results for one-way functions in which each input bit influences only a small number of output bits (a.k.a. input-local functions). Our transformations differ from previous ones in that they approximately preserve input locality and at the same time retain the input size of the original function. Let f:{0,1} ⁿ →{0,1} ^m be a one-way function with input locality d, and suppose that f cannot be inverted in time $\exp(\tilde{O}(\sqrt{n}\cdot d))$ on an ε-fraction of inputs. Our main results can be summarized as follows:

• If f is injective then it is equally hard to invert f on a (1?ε)-fraction of inputs.
• If f is regular then there is a function g:{0,1} ⁿ →{0,1} ^m+O(n) that is d+O(log³ n) input local and is equally hard to invert on a (1?ε)-fraction of inputs.

A natural candidate for a function with small input locality and for which no sub-exponential time attacks are known is Goldreich’s one-way function. To make our results applicable to this function, we prove that when its input locality is set to be d=O(logn) certain variants of the function are (almost) regular with high probability. In some cases, our techniques are applicable even when the input locality is not small. We demonstrate this by extending our first main result to one-way functions of the “parity with noise” type.     

Exploit Network Coding Over GF(2 q ) for Multi-user Cooperative Wireless Networks

In this paper, we present a decode-and-forward network coded (DFNC) scheme over GF(2 ^q ) for the multi-user cooperative communication systems. In particular, we consider a cooperative network with m users transmitting independent packets to the same destination. These users form a cooperation set to help each other by using linear network coding. We propose a coding coefficients construction method which can efficiently reduce the transmission overhead from m(q + log₂ m) to m bits compared with conventional random network coding. Furthermore, we propose a novel decoding algorithm—credit-based updating algorithm in order to improve the solvability of decoding set of equations at the destination. The proposed decoding algorithm is combined with channel decoding and is applied on symbol-level. It can fully make use of the error recovery property of network coding while conventional decoding algorithms (e.g., Gaussian elimination) overlook it. We theoretically analyze the diversity performance in terms of information outage probability, and the results show that diversity order of m + 1 can be achieved for a m-user cooperation system. Moreover, we conduct extensive simulations to show that DFNC outperforms other transmission schemes in terms of symbol error rate and achieves higher diversity order. We also demonstrate that the proposed decoding algorithm provides significant performance gain over conventional decoding algorithm.     

GOAL: A parsimonious geographic routing protocol for large scale sensor networks

Geographic routing is well suited for large scale sensor networks, because its per node state is independent of the network size. However, the local minimum caused by holes/obstacles results in the worst-case path stretch of Ω(c²), where c is the path length of the optimal route. Recently, a geographic routing protocol based on the visibility graph (VIGOR) showed that a path stretch of Θ(c) can be achieved. This path stretch, however, is achieved at the cost of communication and storage overhead, which makes the practical deployment of VIGOR in large scale sensor networks challenging. To this end, we propose GOAL (Geometric Routing using Abstracted Holes), a routing protocol that provably achieves a path stretch of Θ(c), with lower communication and storage overhead. To compactly describe holes, we develop a novel distributed convex hull algorithm, which improves the message complexity O(n log² n) of state of art distributed convex hull algorithm to O(n log n). The concise representation of a hole is used by nodes to make locally optimal routing decisions. Our theoretical analysis proves the correctness of the proposed algorithms and the path stretch of Θ(c). Through extensive simulations and experiments on a testbed with 42 EPIC motes, we demonstrate the effectiveness of GOAL and its feasibility for resource constrained wireless sensor networks; specifically, we show that GOAL eliminates part of communication overhead of VIGOR and reduces the memory overhead of VIGOR by up to 51%.     

Fusion function placement for Active Networks paradigm in wireless sensor networks

Active Networks paradigm integrated with distributed data fusion has the potential to significantly reduce energy dissipation in wireless sensor networks, where energy conservation is the most challenging issue. This work aims to minimize energy cost when distributed data fusion is deployed for the Active Networks computing paradigm. First we propose an optimal solution for mapping task graph of distributed data fusion application into network. Optimal solution uses an exhaustive search algorithm for finding the placements with minimized power consumption. However, optimal solution has high computational complexity—O(mn ^k ), where n denotes the number of network nodes, m is the number of fusion functions, and k is the maximum number of children a fusion function has in task graph and its children are also fusion functions. Then, an approximate solution with low complexity (O(mlog n + log² m)) is proposed called P2lace, which includes two phases, task graph partition and task graph placement. Finally, an extensive evaluation compares approximate solution with optimal solution. The results show that approximate solution is scalable with different task graph characteristics and network size and only causes slightly more transmission cost than optimal solution. And the algorithm without optimizing is shown to be applicable to the network, where the sink node does not have global information of entire network.     

基于d维Bell纠缠态的量子安全直接通信方案

为提高昌燕等提出的量子安全直接通信的通信效率和安全性,设计了基于d维Bell纠缠态的量子安全直接通信方案.通信前发送方(Alice)对d维Bell态粒子进行幺正变换来编码秘密信息,将变换后的d维Bell态粒子二序列发送给接收方(Bob),利用通信双方各自的POVM测量结果和Bell态粒子的纠缠特性,结合部分经典信息实现秘密消息的传输.采用熵理论、概率论分析协议的安全性,结果表明提出方案是安全的,且比昌燕等提出方案的传输效率高,窃听探测率也提高了11％.     

Preserving privacy against external and internal threats in WSN data aggregation

In this paper, we propose two efficient and privacy-preserving data aggregation protocols for WSNs: PASKOS (Privacy preserving based on Anonymously Shared Keys and Omniscient Sink) and PASKIS (Privacy preserving based on Anonymously Shared Keys and Ignorant Sink)—requiring low overhead. Both protocols guarantee privacy preservation and a high data-loss resilience. In particular, PASKOS effectively protects the privacy of any node against other nodes, by requiring O(log?N) communication cost in the worst case and O(1) on average, and O(1) as for memory and computation. PASKIS can even protect a node’s privacy against a compromised sink, requiring only O(1) overhead as for computation, communication, and memory; however, these gains in efficiency are traded-off with a (slightly) decrease in the assured level of privacy. A thorough analysis and extensive simulations demonstrate the superior performance of our protocols against existing solutions in terms of privacy-preserving effectiveness, efficiency, and accuracy of computed aggregation.     

Low Thermal Conductivity in High-Z Thermoelectric Materials with Controlled Nanodispersions

We report wet chemical synthesis of a hierarchical nanocomposite thermoelectric material, (Bi,Sb)₂Te₃ + 2 vol.% Sb₂O₃, which exhibits a very high ZT value of 1.5 at 333 K. The key to such a high ZT value is to design the interfacial density (ID) of the nanodispersion and the mean diameter of the matrix (d) in the nanocomposite. To this end, (Bi,Sb)₂Te₃ with Sb₂O₃ nanodispersion was developed using in situ precipitation during solvothermal treatment. Nanocomposite structure was observed in sintered specimens. By evaluation of thermoelectric properties, it was confirmed that phonon scattering on the surface of Sb₂O₃ dispersion and κ _ph correspondingly decreased with ID. The formation of a well-controlled Sb₂O₃ dispersion (mean diameter of dispersion: D = 1.5 nm, ID = 0.06 nm^?1) and fine grains (d = 38 nm) led to an extremely low lattice thermal conductivity of 0.28 W m^?1 K^?1, while reducing the electrical conductivity moderately according to the conventional mixture rule.     

Yield analysis for self-repairable MEMS devices

In this paper, yield analysis for a self-repairable MEMS (SRMEMS) accelerometer design is proposed. The accelerometer consists of (n  +  m) identical modules: n of them serve as the main device, while the remaining m modules act as the redundancy. The yield model for MEMS redundancy repair is developed by statistical analysis. Based upon the yield model, the yield increase after redundancy repair for different m and n numbers is analyzed. ANSYS Monte Carlo simulation is used to estimate the yield of BISR/non-BISR MEMS devices with random point-stiction defects. The simulation results are in good agreement with the theoretical prediction based on our yield model. The simulation results also show that the SRMEMS leads to effective yield increase compared to non-BISRS design, especially for a moderate initial yield.     

Energy constraint clustering algorithms for wireless sensor networks

Using partitioning in sensor networks to create clusters for routing, data management, and for controlling communication has been proven as a way to ensure long range deployment and to deal with sensor network shortcomings such as limited energy and short communication ranges. Choosing a cluster head within each cluster is important because cluster heads use additional energy for their responsibilities and that burden needs to be carefully passed around among nodes in a cluster. Many existing protocols either choose cluster heads randomly or use nodes with the highest remaining energy. We present an Energy Constrained minimum Dominating Set based efficient clustering called ECDS to model the problem of optimally choosing cluster heads with energy constraints. Our proposed randomized distributed algorithm for the constrained dominating set runs in O(log n log Δ) rounds with high probability where Δ is the maximum degree of a node in the graph. We provide an approximation ratio for the ECDS algorithm of expected size 8H_Δ∣OPT∣ and with high probability a size of O(∣OPT∣log n) where n is the number of nodes, H is the harmonic function and OPT means the optimal size. We propose multiple extensions to the distributed algorithm for the energy constrained dominating set. We experimentally show that these extensions perform well in terms of energy usage, node lifetime, and clustering time in comparison and, thus, are very suitable for wireless sensor networks.     

Novel efficient two-pass algorithm for closed polygonal approximation based on LISE and curvature constraint criteria

Given a closed curve with n points, based on the local integral square error and the curvature constraint criteria, this paper presents a novel two-pass O(Fn + mn²)-time algorithm for solving the closed polygonal approximation problem where m(≪n) denotes the minimal number of covering feasible segments for one point and empirically the value of m is rather small, and F (≪n²) denotes the number of feasible approximate segments. Based on some real closed curves, experimental results demonstrate that under the same number of segments used, our proposed two-pass algorithm has better quality and execution-time performance when compared to the previous algorithm by Chung et al. Experimental results also demonstrate that under the same number of segments used, our proposed two-pass algorithm has better quality, but has some execution-time degradation when compared to the currently published algorithms by Wu and Sarfraz et al.     

Joint encryption and message-efficient secure computation

This paper addresses the message complexity of secure computation in the (passive adversary) privacy setting. We show that O(nC) encrypted bits of communication suffice for n parties to evaluate any boolean circuit of size C privately, under a specific cryptographic assumption. This work establishes a connection between secure distributed computation and group-oriented cryptography, i.e., cryptographic methods in which subsets of individuals can act jointly as single agents. Our secure computation protocol relies on a new group-oriented probablistic public-key encryption scheme with useful algebraic properties.Work performed while at Columbia University, with the support of a summer internship at Bellcore and a visiting position at C.W.I.     

Lower Bounds and Impossibility Results for Concurrent Self Composition

In the setting of concurrent self composition, a single protocol is executed many times concurrently in a network. In this paper, we prove lower bounds and impossibility results for secure protocols in this setting. First and foremost, we prove that there exist large classes of functionalities that cannot be securely computed under concurrent self composition, by any protocol. We also prove a communication complexity lower bound on protocols that securely compute a large class of functionalities in this setting. Specifically, we show that any protocol that computes a functionality from this class and remains secure for m concurrent executions, must have bandwidth of at least m bits. The above results are unconditional and hold for any type of simulation (i.e., even for non-black-box simulation). In addition, we prove a severe lower bound on protocols that are proven secure using black-box simulation. Specifically, we show that any protocol that computes the blind signature or oblivious transfer functionalities and remains secure for m concurrent executions, where security is proven via black-box simulation, must have at least m rounds of communication. Our results hold for the plain model, where no trusted setup phase is assumed. While proving our impossibility results, we also show that for many functionalities, security under concurrent self composition (where a single secure protocol is run many times) is actually equivalent to the seemingly more stringent requirement of security under concurrent general composition (where a secure protocol is run concurrently with other arbitrary protocols). This observation has significance beyond the impossibility results that are derived by it for concurrent self composition. This paper combines results that appeared in extended abstracts in Lindell (35th STOC, pp. 683–692, 2003; 1st Theory of Cryptography Conference (TOC), LNCS, vol. 2951, pp. 203–222, 2004).     

Utilization of Pipeline Technique in AOP Based Multipliers with Parallel Inputs

Heretofore many All-One-Polynomials (AOP) based multipliers are proposed over GF(2 ^m ). Previously proposed multipliers have serial input structure and also suffer from a long critical path delay. In this paper we improve AOP based multipliers by reducing the critical path delay and changing the input structure to parallel. Initially, we modify the wiring of the previously proposed AOP based multipliers. This approach reduces the critical path delay from O(m) to O(log m). In order to further reduce this delay from O(log m) to O(1) the pipeline technique is utilized. The efficiency of the proposed architectures is evaluated based on criteria of time (latency, critical path) and space complexity (gate-latch number).     

Effect of Mn and Nb Doped BaTiO3 in the Dielectric Properties in the Ba(Mn1/2Nb1/2)xTi1−xO3

Polycrystalline samples of BaTi_1?x (Mn_0.5Nb_0.5) _x O₃ with x = 0.025, 0.05, 0.075, 0.1, 0.125, 0.15, and 0.175 have been synthesized by the high-temperature solid-state reaction technique. The effects of cationic substitution of manganese and niobium for titanium at B sites of the BaTiO₃ perovskite lattice on symmetry and dielectric properties were investigated. X-ray diffraction at room temperature and dielectric permittivity in the temperature range from 85 K to 500 K and frequency range from 100 Hz to 2 × 10⁵ Hz were studied. The evolution from a normal ferroelectric to a relaxor ferroelectric is emphasized. T _C or T _m decreases when both manganese and niobium are introduced into the lattice of BaTiO₃. High dielectric constant of around 9000 at T _C = 280 K was found for Ba Ti_0.925(Mn_0.5Nb_0.5)_0.075O₃ ceramic. A relaxor ferroelectric with ΔT _m = 60 K and $ \varepsilon_{\rm{r}}^{\prime } $ of about 3500 at 10 kHz with T _m = 150 K was found for the BaTi_0.85(Mn_0.5Nb_0.5)_0.15O₃ sample.     

Scalable Protocols for Authenticated Group Key Exchange

We consider the problem of authenticated group key exchange among n parties communicating over an insecure public network. A number of solutions to this problem have been proposed; however, all prior provably secure solutions do not scale well and, in particular, require O(n) rounds. Our main contribution is the first scalable protocol for this problem along with a rigorous proof of security in the standard model under the DDH assumption; our protocol uses a constant number of rounds and requires only O(1) "full" modular exponentiations per user. Toward this goal (and adapting work of Bellare, Canetti, and Krawczyk), we first present an efficient compiler that transforms any group key-exchange protocol secure against a passive eavesdropper to an authenticated protocol which is secure against an active adversary who controls all communication in the network. This compiler adds only one round and O(1) communication (per user) to the original scheme. We then prove secure—against a passive adversary—a variant of the two-round group key-exchange protocol of Burmester and Desmedt. Applying our compiler to this protocol results in a provably secure three-round protocol for authenticated group key exchange which also achieves forward secrecy.