Journal articles on the topic 'Round and communication complexity'
To see the other types of publications on this topic, follow the link: Round and communication complexity.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 journal articles for your research on the topic 'Round and communication complexity.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.
1
Kremer, I., N. Nisan, and D. Ron. "On Randomized One-round Communication Complexity." Computational Complexity 8, no. 1 (June 1, 1999): 21–49. http://dx.doi.org/10.1007/s000370050018.
Full text
2
Kremer, Ilan, Noam Nisan, and Dana Ron. "Errata for: "On randomized one-round communication complexity"." Computational Complexity 10, no. 4 (December 1, 2001): 314–15. http://dx.doi.org/10.1007/s000370100003.
Full text
3
Pandurangan, Gopal, Peter Robinson, and Michele Scquizzato. "On the Distributed Complexity of Large-Scale Graph Computations." ACM Transactions on Parallel Computing 8, no. 2 (June 30, 2021): 1–28. http://dx.doi.org/10.1145/3460900.
Full textAbstract:
Motivated by the increasing need to understand the distributed algorithmic foundations of large-scale graph computations, we study some fundamental graph problems in a message-passing model for distributed computing where k ≥ 2 machines jointly perform computations on graphs with n nodes (typically, n >> k). The input graph is assumed to be initially randomly partitioned among the k machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation. Our main contribution is the General Lower Bound Theorem , a theorem that can be used to show non-trivial lower bounds on the round complexity of distributed large-scale data computations. This result is established via an information-theoretic approach that relates the round complexity to the minimal amount of information required by machines to solve the problem. Our approach is generic, and this theorem can be used in a “cookbook” fashion to show distributed lower bounds for several problems, including non-graph problems. We present two applications by showing (almost) tight lower bounds on the round complexity of two fundamental graph problems, namely, PageRank computation and triangle enumeration . These applications show that our approach can yield lower bounds for problems where the application of communication complexity techniques seems not obvious or gives weak bounds, including and especially under a stochastic partition of the input. We then present distributed algorithms for PageRank and triangle enumeration with a round complexity that (almost) matches the respective lower bounds; these algorithms exhibit a round complexity that scales superlinearly in k , improving significantly over previous results [Klauck et al., SODA 2015]. Specifically, we show the following results: PageRank: We show a lower bound of Ὼ(n/k 2 ) rounds and present a distributed algorithm that computes an approximation of the PageRank of all the nodes of a graph in Õ(n/k 2 ) rounds. Triangle enumeration: We show that there exist graphs with m edges where any distributed algorithm requires Ὼ(m/k 5/3 ) rounds. This result also implies the first non-trivial lower bound of Ὼ(n 1/3 ) rounds for the congested clique model, which is tight up to logarithmic factors. We then present a distributed algorithm that enumerates all the triangles of a graph in Õ(m/k 5/3 + n/k 4/3 ) rounds.
4
Zhao, Bo, Zhihong Chen, Hai Lin, and XiangMin Ji. "A Constant Round Write-Only ORAM." Applied Sciences 10, no. 15 (August 3, 2020): 5366. http://dx.doi.org/10.3390/app10155366.
Full textAbstract:
The write-only oblivious RAM (ORAM) is proposed to efficiently protect the privacy of applications such as cloud storage synchronization and encrypted hidden volumes. For N blocks with size B = Ω(log2N), the most efficient write-only ORAM, DetWoORAM, achieves O(B) communication complexity with O(logN) rounds per logical write. We propose a two-level write-only ORAM and achieve O(B) communication complexity with O(1) rounds. Similar to the traditional bucket-based ORAM schemes, we set a rate for the write operation to further reduce the communication complexity. The top-level stores data blocks in a flat array and the write pattern is protected by writing blocks uniformly at random. The second level employs a binary tree to store the position map of data blocks. To avoid recursive storage, a static position map for blocks in the second level is used. Both the analysis and experiments show that, besides the achieved low communication complexity and rounds, the stash sizes in the top level and the second level are bounded to O(B) and ω(B), respectively.
5
Apon, Daniel, Jonathan Katz, and Alex J. Malozemoff. "One-round multi-party communication complexity of distinguishing sums." Theoretical Computer Science 501 (August 2013): 101–8. http://dx.doi.org/10.1016/j.tcs.2013.07.026.
Full text
6
TSE, SAVIO S. H., and FRANCIS C. M. LAU. "ON THE COMPLEXITY OF SOME ADAPTIVE POLLING ALGORITHMS IN GENERAL NETWORKS." International Journal of Foundations of Computer Science 10, no. 02 (June 1999): 211–23. http://dx.doi.org/10.1142/s0129054199000150.
Full textAbstract:
We study the problem of adaptive polling in undirected general networks. Polling, also known as broadcast-confirm, consists a propagation round and a feedback round. In adaptive polling, a spanning tree of unknown topology is built dynamically during the propagation round, and feedback messages are free to choose their paths in order to adapt to traffic and fault situations. We study three adaptive polling algorithms and analyze their worst-case communication bit complexities in the propagation round. Then, we prove a lower bound on the worst-case communication bit complexity of Ω(e+n log n) in the propagation round for all algorithms of the same kind as the three algorithms we study, where n is the number of nodes, and e the number of edges. We conclude that the cost introduced into the network due to the running of an adaptive polling algorithm is mild.
7
Wagh, Sameer. "Pika: Secure Computation using Function Secret Sharing over Rings." Proceedings on Privacy Enhancing Technologies 2022, no. 4 (October 2022): 351–77. http://dx.doi.org/10.56553/popets-2022-0113.
Full textAbstract:
Machine learning algorithms crucially depend on non-linear mathematical functions such as division (for normalization), exponentiation (for softmax and sigmoid), tanh (as an activation function), logarithm (for crossentropy loss), and square root (for back-propagation of normalization layers). However, when machine learning is performed over secure computation, these protocols incur a large communication overhead and high round complexity. In this work, we propose new multi-party computation (MPC) protocols for such functions. Our protocols achieve constant round complexity (3 for semi-honest, 4 for malicious), an order of magnitude lower communication (54 − 121× lower than prior art), and high concrete efficiency (2−1163× faster runtime). We rely on recent advances in function secret sharing (FSS) to construct these protocols. Our contributions can be summarized as follows: (1) A constant round protocol to securely evaluate nonlinear functions such as division, exponentiation, logarithm, and tanh (in comparison to prior art which uses round complexity proportional to the rounds of iterative methods/required precision) with high accuracy. This construction largely follows prior work in look-up style secure computation. (2) Our main contribution is the extension of the above protocol to be secure in the presence of malicious adversaries in the honest majority setting. We provide a malicious sketching protocol for FSS schemes that works over rings and in order to prove its security, we extend (and prove) a corresponding form of SchwartzZippel lemma over rings. This is the first such extension of the lemma and it can be of independent interest in other domains of secure computation. (3) We implement our protocol and showcase order of magnitude improvements in runtime and communication. Given the low round complexity and substantially lower communication, our protocols achieve even better performance over network constrained environments such as WAN. Finally, we showcase how such functions can lead to scalability in machine learning. Note that techniques presented are applicable beyond the application of machine learning as the protocols effectively present an efficient 1-out-of-N oblivious transfer or an efficient private information retrieval protocol.
8
Zhang, Kai, Xuejia Lai, Lei Wang, Jie Guan, Bin Hu, Senpeng Wang, and Tairong Shi. "Related-Key Multiple Impossible Differential Cryptanalysis on Full-Round LiCi-2 Designed for IoT." Security and Communication Networks 2022 (May 25, 2022): 1–11. http://dx.doi.org/10.1155/2022/3611840.
Full textAbstract:
LiCi-2 is an ultralightweight block cipher designed for constrained IoT devices. It is a successor of LiCi and has even better performance in both software and hardware implementation. In this paper, based on the idea of related-key multiple impossible differential cryptanalysis, a key recovery attack on full-round LiCi-2 is proposed. First, an interesting property is revealed that, with a single bit difference in the related key, a 10-round differential character with probability of 1 exists on LiCi-2. With an automatic approach, the boundaries of impossible differential distinguishers in terms of single-key setting and related-key setting are explored. Under our construction method, the longest length is 8 rounds for single-key setting and 18 rounds for related-key setting. Finally, based on these 18-round distinguishers, a 25-round key recovery attack is proposed with adding 3 rounds before and 4 rounds after the distinguisher. Our attack needs one related key. The time complexity for our attack is O(2123.44), the memory complexity is O(294), and the data complexity is O(260.68). As far as we know, no full-round attack has previously been reported on LiCi-2.
9
Tse, Savio S. H. "Belated Analyses of Three Credit-Based Adaptive Polling Algorithms." International Journal of Foundations of Computer Science 27, no. 05 (August 2016): 579–94. http://dx.doi.org/10.1142/s0129054116500179.
Full textAbstract:
We study the problem of credit-based adaptive polling in undirected arbitrary point-to-point asynchronous networks. Polling consists of two rounds, namely propagation (broadcast) and feedback (confirmation, response) rounds. By adaptive polling, a spanning tree of unknown topology is built dynamically during the propagation round, and feedback messages are free to choose their paths back to the initiator — a specific node who initiates the polling algorithm. The freedom in the feedback round relies on the use of credits in the propagation round. We re-visit three existing algorithms and analyse their average case communication bit complexities incurred by the credits in the propagation round, and these analyses match with the numerical results. We also give an optimal lower bound on the worst case bit message complexity for the case when the number of nodes in the network is unknown.
10
Magniez, Frédéric, and Ashwin Nayak. "Quantum Distributed Complexity of Set Disjointness on a Line." ACM Transactions on Computation Theory 14, no. 1 (March 31, 2022): 1–22. http://dx.doi.org/10.1145/3512751.
Full textAbstract:
Given \( x,y\in \lbrace 0,1\rbrace ^n \) , Set Disjointness consists in deciding whether \( x_i=y_i=1 \) for some index \( i \in [n] \) . We study the problem of computing this function in a distributed computing scenario in which the inputs \( x \) and \( y \) are given to the processors at the two extremities of a path of length \( d \) . Each vertex of the path has a quantum processor that can communicate with each of its neighbours by exchanging \( \operatorname{O}(\log n) \) qubits per round. We are interested in the number of rounds required for computing Set Disjointness with constant probability bounded away from \( 1/2 \) . We call this problem “Set Disjointness on a Line”. Set Disjointness on a Line was introduced by Le Gall and Magniez [ 14 ] for proving lower bounds on the quantum distributed complexity of computing the diameter of an arbitrary network in the CONGEST model. However, they were only able to provide a lower bound when the local memory used by the processors on the intermediate vertices of the path is severely limited. More precisely, their bound applies only when the local memory of each intermediate processor consists of \( \operatorname{O}(\log n) \) qubits. In this work, we prove an unconditional lower bound of \( \widetilde{\Omega }\big (\sqrt [3]{n d^2}+\sqrt {n} \, \big) \) rounds for Set Disjointness on a Line with \( d + 1 \) processors. This is the first non-trivial lower bound when there is no restriction on the memory used by the processors. The result gives us a new lower bound of \( \widetilde{\Omega } \big (\sqrt [3]{n\delta ^2}+\sqrt {n} \, \big) \) on the number of rounds required for computing the diameter \( \delta \) of any \( n \) -node network with quantum messages of size \( \operatorname{O}(\log n) \) in the CONGEST model. We draw a connection between the distributed computing scenario above and a new model of query complexity. In this model, an algorithm computing a bi-variate function \( f \) (such as Set Disjointness) has access to the inputs \( x \) and \( y \) through two separate oracles \( {\mathcal {O}}_x \) and \( {\mathcal {O}}_y \) , respectively. The restriction is that the algorithm is required to alternately make \( d \) queries to \( {\mathcal {O}}_x \) and \( d \) queries to \( {\mathcal {O}}_y \) , with input-independent computation in between queries. The model reflects a “switching delay” of \( d \) queries between a “round” of queries to \( x \) and the following “round” of queries to \( y \) . The information-theoretic technique we use for deriving the round lower bound for Set Disjointness on a Line also applies to the number of rounds in this query model. We provide an algorithm for Set Disjointness in this query model with round complexity that matches the round lower bound stated above, up to a polylogarithmic factor. This presents a barrier for obtaining a better round lower bound for Set Disjointness on the Line. At the same time, it hints at the possibility of better communication protocols for the problem.
11
Nisan, Noam, and Avi Wigderson. "Rounds in Communication Complexity Revisited." SIAM Journal on Computing 22, no. 1 (February 1993): 211–19. http://dx.doi.org/10.1137/0222016.
Full text
12
Badanidiyuru, Ashwinkumar, Arpita Patra, Ashish Choudhury, Kannan Srinathan, and C. Pandu Rangan. "On the trade-off between network connectivity, round complexity, and communication complexity of reliable message transmission." Journal of the ACM 59, no. 5 (October 2012): 1–35. http://dx.doi.org/10.1145/2371656.2371657.
Full text
13
Braverman, Mark, Ankit Garg, Young Kun Ko, Jieming Mao, and Dave Touchette. "Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness." SIAM Journal on Computing 47, no. 6 (January 2018): 2277–314. http://dx.doi.org/10.1137/16m1061400.
Full text
14
Xing, Zhaohui, Wenying Zhang, and Guoyong Han. "Improved Conditional Differential Analysis on NLFSR-Based Block Cipher KATAN32 with MILP." Wireless Communications and Mobile Computing 2020 (November 23, 2020): 1–14. http://dx.doi.org/10.1155/2020/8883557.
Full textAbstract:
In this paper, a new method for constructing a Mixed Integer Linear Programming (MILP) model on conditional differential cryptanalysis of the nonlinear feedback shift register- (NLFSR-) based block ciphers is proposed, and an approach to detecting the bit with a strongly biased difference is provided. The model is successfully applied to the block cipher KATAN32 in the single-key scenario, resulting in practical key-recovery attacks covering more rounds than the previous. In particular, we present two distinguishers for 79 and 81 out of 254 rounds of KATAN32. Based on the 81-round distinguisher, we recover 11 equivalent key bits of 98-round KATAN32 and 13 equivalent key bits of 99-round KATAN32. The time complexity is less than 2 31 encryptions of 98-round KATAN32 and less than 2 33 encryptions of 99-round KATAN32, respectively. Thus far, our results are the best known practical key-recovery attacks for the round-reduced variants of KATAN32 regarding the number of rounds and the time complexity. All the results are verified experimentally.
15
Weng, Tianling, Tingting Cui, Ting Yang, and Yinghua Guo. "Related-Key Differential Attacks on Reduced-Round LBlock." Security and Communication Networks 2022 (September 16, 2022): 1–15. http://dx.doi.org/10.1155/2022/8464960.
Full textAbstract:
LBlock, as one of the typical lightweight encryption schemes, is a 32-round block cipher with 64 bit block and 80 bit master key. It can be widely applied in the IoT environment because of its friendly software and hardware implementations. Since it came out, it has encountered many attacks. In this paper, we evaluate LBlock’s ability against related-key differential attack more accurately based on SMT method. On the one hand, we propose tighter lower bounds on the minimal number of active S-boxes for up to 19 rounds of LBlock, which are 8 more rounds than previous ones. Then, we propose the upper bounds of total probabilities for up to 19 rounds of LBlock for the first time. On the other hand, with a suitable 17-round related-key differential distinguisher, we propose attacks on 22- and 23-round LBlock. Each of these attacks has lower time complexity and data complexity than previous ones for the same rounds of LBlock.
16
Gao, Hongchang, An Xu, and Heng Huang. "On the Convergence of Communication-Efficient Local SGD for Federated Learning." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 9 (May 18, 2021): 7510–18. http://dx.doi.org/10.1609/aaai.v35i9.16920.
Full textAbstract:
Federated Learning (FL) has attracted increasing attention in recent years. A leading training algorithm in FL is local SGD, which updates the model parameter on each worker and averages model parameters across different workers only once in a while. Although it has fewer communication rounds than the classical parallel SGD, local SGD still has large communication overhead in each communication round for large machine learning models, such as deep neural networks. To address this issue, we propose a new communication-efficient distributed SGD method, which can significantly reduce the communication cost by the error-compensated double compression mechanism. Under the non-convex setting, our theoretical results show that our approach has better communication complexity than existing methods and enjoys the same linear speedup regarding the number of workers as the full-precision local SGD. Moreover, we propose a communication-efficient distributed SGD with momentum, which also has better communication complexity than existing methods and enjoys a linear speedup with respect to the number of workers. At last, extensive experiments are conducted to verify the performance of our proposed two methods. Moreover, we propose a communication-efficient distributed SGD with momentum to accelerate the convergence, which also has better communication complexity than existing methods and enjoys a linear speedup with respect to the number of workers. At last, extensive experiments are conducted to verify the performance of our proposed methods.
17
Jain, Rahul, Attila Pereszlényi, and Penghui Yao. "A Direct Product Theorem for Two-Party Bounded-Round Public-Coin Communication Complexity." Algorithmica 76, no. 3 (December 18, 2015): 720–48. http://dx.doi.org/10.1007/s00453-015-0100-0.
Full text
18
Blumrosen, L., N. Nisan, and I. Segal. "Auctions with Severely Bounded Communication." Journal of Artificial Intelligence Research 28 (March 8, 2007): 233–66. http://dx.doi.org/10.1613/jair.2081.
Full textAbstract:
We study auctions with severe bounds on the communication allowed: each bidder may only transmit t bits of information to the auctioneer. We consider both welfare- and profit-maximizing auctions under this communication restriction. For both measures, we determine the optimal auction and show that the loss incurred relative to unconstrained auctions is mild. We prove non-surprising properties of these kinds of auctions, e.g., that in optimal mechanisms bidders simply report the interval in which their valuation lies in, as well as some surprising properties, e.g., that asymmetric auctions are better than symmetric ones and that multi-round auctions reduce the communication complexity only by a linear factor.
19
Michail, Othon, George Skretas, and Paul G. Spirakis. "Distributed computation and reconfiguration in actively dynamic networks." Distributed Computing 35, no. 2 (December 19, 2021): 185–206. http://dx.doi.org/10.1007/s00446-021-00415-5.
Full textAbstract:
AbstractWe study here systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also exploit network reconfiguration to carry out a given task. Also, the distributed task itself may now require a global reconfiguration from a given initial network $$G_s$$ G s to a target network $$G_f$$ G f from a desirable family of networks. To formally capture costs associated with creating and maintaining connections, we define three edge-complexity measures: the total edge activations, the maximum activated edges per round, and the maximum activated degree of a node. We give (poly)log(n) time algorithms for the task of transforming any $$G_s$$ G s into a $$G_f$$ G f of diameter (poly)log(n), while minimizing the edge-complexity. Our main lower bound shows that $$\varOmega (n)$$ Ω ( n ) total edge activations and $$\varOmega (n/\log n)$$ Ω ( n / log n ) activations per round must be paid by any algorithm (even centralized) that achieves an optimum of $$\varTheta (\log n)$$ Θ ( log n ) rounds. We give three distributed algorithms for our general task. The first runs in $$O(\log n)$$ O ( log n ) time, with at most 2n active edges per round, a total of $$O(n\log n)$$ O ( n log n ) edge activations, a maximum degree $$n-1$$ n - 1 , and a target network of diameter 2. The second achieves bounded degree by paying an additional logarithmic factor in time and in total edge activations. It gives a target network of diameter $$O(\log n)$$ O ( log n ) and uses O(n) active edges per round. Our third algorithm shows that if we slightly increase the maximum degree to polylog(n) then we can achieve $$o(\log ^2 n)$$ o ( log 2 n ) running time.
20
Liu, Wenhao, and Yang Yang. "The 7-Round Subspace Trail-Based Impossible Differential Distinguisher of Midori-64." Security and Communication Networks 2021 (November 9, 2021): 1–15. http://dx.doi.org/10.1155/2021/6269604.
Full textAbstract:
This paper analyzes the subspace trail of Midori-64 and uses the propagation law and mutual relationship of the subspaces of Midori-64 to provide a 6-round Midori-64 subspace trail-based impossible differential key recovery attack. The data complexity of the attack is 2 54.6 chosen plaintexts, and the computational complexity is 2 58.2 lookup operations. Its overall complexity is less than that of the known 6-round truncated impossible differential distinguisher. This distinguisher is also applicable to Midori-128 with a secret S -box. Additionally, utilizing the properties of subspaces, we prove that a subspace trail-based impossible differential distinguisher of Midori-64 contains at most 7 rounds. This is 1 more than the upper bound of Midori-64’s truncated impossible differential distinguisher which is 6. According to the Hamming weights of the starting and ending subspaces, we classify all 7-round Midori-64 subspace trail-based impossible differential distinguishers into two types and they need 2 59.6 and 2 51.4 chosen plaintexts, respectively.
21
Enright, Helen Patricia, and Amy Gray. "Unpacking the learning on consultant-led ward rounds: Lessons from ethnography in paediatrics." Focus on Health Professional Education: A Multi-Professional Journal 21, no. 3 (December 1, 2020): 30–43. http://dx.doi.org/10.11157/fohpe.v21i3.336.
Full textAbstract:
Introduction: Consultant-led ward round education in a busy paediatric setting is a complex process and is often ad hoc. We aimed to observe ward rounds to better understand the education opportunities available.Methods: Drawing on Argyris and Schön's (1974) theory of action, we used an ethnographic approach to observe 30 general medical ward rounds over a 3-month period, from September to December 2016. For this study we analysed the learning opportunities and the content that is explicitly taught in relation to the domains of professional practice that we espouse to teach.Results: There were many layers of learning potential observed in ward round practice. These included clinical learning, communication, professional skills and identity and institutional cultural context. Clinical learning was prioritised; however, other learning domains remained implicit and were often ignored.Discussion: Our findings highlight great complexity in ward round learning and teaching. There was significant missed educational potential in the ward round environment as well as a need for a major shift in educational focus from clinical to other professional domains. Following Argyris and Schön (1974), it is necessary to examine what we espouse against our actual educational practice. This can inform a planned or structured approach to exploit the maximum potential of ward round learning and teaching.Conclusions: Ward round education is a priority that benefits from observation, reflection and development of new models of practice. If we are not conscious of what we are teaching on rounds, and how this is occurring, we risk losing opportunities to draw on all of the learning potential available.
22
Liu, Yu, Xiaolei Liu, and Yanmin Zhao. "Security Cryptanalysis of NUX for the Internet of Things." Security and Communication Networks 2019 (June 12, 2019): 1–12. http://dx.doi.org/10.1155/2019/2062697.
Full textAbstract:
In order to adopt the restricted environment, such as radio frequency identification technology or sensor networking, which are the important components of the Internet of Things, lightweight block ciphers are designed. NUX is a 31-round iterative ultralightweight cipher proposed by Bansod et al. In this paper, we examine the resistance of NUX to differential and linear analysis and search for 1~31-round differential characteristics and linear approximations. In design specification, authors claimed that 25-round NUX is resistant to differential and linear attack. However, we can successfully perform 29-round differential attack on NUX with the 22-round differential characteristic found in this paper, which is 4 rounds more than the limitation given by authors. Furthermore, we present the key recovery attack on 22-round NUX using a 19-round linear approximation determined in this paper. Besides, distinguishing attack, whose distinguisher is built utilizing the property of differential propagation through NUX, is implemented on full NUX with data complexity 8.
23
Rao, Ch Koteswara, Kunwar Singh, and Anoop Kumar. "Oblivious stable sorting protocol and oblivious binary search protocol for secure multi-party computation." Journal of High Speed Networks 27, no. 1 (March 29, 2021): 67–82. http://dx.doi.org/10.3233/jhs-210652.
Full textAbstract:
Multi-party computation (MPC) sorting and searching protocols are frequently used in different databases with varied applications, as in cooperative intrusion detection systems, private computation of set intersection and oblivious RAM. Ivan Damgard et al. have proposed two techniques i.e., bit-decomposition protocol and bit-wise less than protocol for MPC. These two protocols are used as building blocks and have proposed two oblivious MPC protocols. The proposed protocols are based on data-dependent algorithms such as insertion sort and binary search. The proposed multi-party sorting protocol takes the shares of the elements as input and outputs the shares of the elements in sorted order. The proposed protocol exhibits O ( 1 ) constant round complexity and O ( n log n ) communication complexity. The proposed multi-party binary search protocol takes two inputs. One is the shares of the elements in sorted order and the other one is the shares of the element to be searched. If the position of the search element exists, the protocol returns the corresponding shares, otherwise it returns shares of zero. The proposed multi-party binary search protocol exhibits O ( 1 ) round complexity and O ( n log n ) communication complexity. The proposed multi-party sorting protocol works better than the existing quicksort protocol when the input is in almost sorted order. The proposed multi-party searching protocol gives almost the same results, when compared to the general binary search algorithm.
24
Briet, Jop, and Jeroen Zuiddam. "On the orthogonal rank and impossibility of quantum round elimination." Quantum Information and Computation 17, no. 1&2 (January 2017): 106–16. http://dx.doi.org/10.26421/qic17.1-2-6.
Full textAbstract:
After Bob sends Alice a bit, she responds with a lengthy reply. At the cost of a factor of two in the total communication, Alice could just as well have given Bob her two possible replies at once without listening to him at all, and have him select which one applies. Motivated by a conjecture stating that this form of “round elimination” is impossible in exact quantum communication complexity, we study the orthogonal rank and a symmetric variant thereof for a certain family of Cayley graphs. The orthogonal rank of a graph is the smallest number d for which one can label each vertex with a nonzero d-dimensional complex vector such that adjacent vertices receive orthogonal vectors. We show an exp(n) lower bound on the orthogonal rank of the graph on {0, 1} n in which two strings are adjacent if they have Hamming distance at least n/2. In combination with previous work, this implies an affirmative answer to the above conjecture.
25
Luo, Siqiang. "Distributed PageRank Computation: An Improved Theoretical Study." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 4496–503. http://dx.doi.org/10.1609/aaai.v33i01.33014496.
Full textAbstract:
PageRank is a classic measure that effectively evaluates the node importance in large graphs, and has been applied in numerous applications ranging from data mining, Web algorithms, recommendation systems, load balancing, search, and identifying connectivity structures. Computing PageRank for large graphs is challenging and this has motivated the studies of distributed algorithms to compute PageRank. Previously, little works have been spent on the distributed PageRank algorithms with provably desired complexity and accuracy. Given a graph with n nodes and if we model the distributed computation model as the well-known congested clique model, the state-of-the-art algorithm takes O(√logn) communication rounds to approximate the PageRank value of each node in G, with a probability at least 1−1/n. In this paper, we present improved distributed algorithms for computing PageRank. Particularly, our algorithm performs O(log log√n) rounds (a significant improvement compared with O(√logn) rounds) to approximate the PageRank values with a probability at least 1−1/n. Moreover, under a reasonable assumption, our algorithm also reduces the edge bandwidth (i.e., the maximum communication message size that can be exchanged through an edge during a communication round) by a O(logn) factor compared with the state-of-the-art algorithm. Finally, we show that our algorithm can be adapted to efficiently compute another variant of PageRank, i.e., the batch one-hop Personalized PageRanks, in O(log logn) communication rounds.
26
Haddad, Mohammed, Colette Johnen, and Sven Köhler. "Polynomial Silent Self-Stabilizing p-Star Decomposition†." Computer Journal 63, no. 2 (November 17, 2019): 253–66. http://dx.doi.org/10.1093/comjnl/bxz102.
Full textAbstract:
Abstract We present a silent self-stabilizing distributed algorithm computing a maximal $\ p$-star decomposition of the underlying communication network. Under the unfair distributed scheduler, the most general scheduler model, the algorithm converges in at most $12\Delta m + \mathcal{O}(m+n)$ moves, where $m$ is the number of edges, $n$ is the number of nodes and $\Delta $ is the maximum node degree. Regarding the time complexity, we obtain the following results: our algorithm outperforms the previously known best algorithm by a factor of $\Delta $ with respect to the move complexity. While the round complexity for the previous algorithm was unknown, we show a $5\big \lfloor \frac{n}{p+1} \big \rfloor +5$ bound for our algorithm.
27
Kovalev, I. V., N. A. Testoyedov, D. I. Kovalev, and S. G. Efa. "Analysis of the influence of natural and climatic conditions in the Arctic and the Far North on the stability of air traffic." IOP Conference Series: Earth and Environmental Science 981, no. 3 (February 1, 2022): 032044. http://dx.doi.org/10.1088/1755-1315/981/3/032044.
Full textAbstract:
Abstract The analysis of the influence of natural and climatic conditions of the Arctic and Far North on the stability of air connection is investigated in this article. The provision of year-round mainline, interregional and regional air transportation is associated with the complexity of controlling the flight path of aircraft in extreme Arctic conditions. For the Arctic zone, the possibility of using a constellation of low-orbit satellite communication systems is being considered for transmitting data on the position of an aircraft to a control tower located on the ground. In this case, data transmission is possible both using GSM communication through ground stations, and using inter-satellite communication lines.
28
Baggaley, Martin, Gary Inglis, and Andrea Malizia. "The writing is on the wall: use of an LCD projector to aid communication at the ward round." Psychiatric Bulletin 29, no. 5 (May 2005): 180–81. http://dx.doi.org/10.1192/pb.29.5.180.
Full textAbstract:
A key element of good in-patient psychiatric care is the multidisciplinary review, with accurate and legible recording of the outcome of the discussion. Traditionally, the junior doctor and nurse act as ‘scribes' on the ward rounds, recording the outcomes in the multidisciplinary or separate medical and nursing notes. There are a number of ways in which this process can fail. First, the scribe may simply misunderstand the decision of the team, given the complexity and variety of decisions in a psychiatric setting. Second, the scribe may understand what to record, but what is written may be illegible. Finally, people present at the ward round can have different beliefs about what has been decided, but unless they immediately review what has been written, they may not realise the discrepancy. One or more of these failings can result in serious untoward incidents, such as a patient being allowed off the ward on unescorted leave when the responsible medical officer believed the team had decided against permitting such leave. It is only when there is a serious incident that discrepancies can and do emerge.
29
Hosseini Beghaeiraveri, Seyed Amir, Mohammad Izadi, and Mohsen Rezvani. "Broadcast Complexity and Adaptive Adversaries in Verifiable Secret Sharing." Security and Communication Networks 2020 (August 1, 2020): 1–10. http://dx.doi.org/10.1155/2020/9428457.
Full textAbstract:
Verifiable secret sharing (VSS) is one of the basic problems in the theory of distributed cryptography and has an important role in secure multiparty computation. In this case, it is tried to share a confidential data as secret, between multiple nodes in a distributed system, in the presence of an active adversary that can destroy some nodes, such that the secret can be reconstructed with the participation of certain size of honest nodes. A dynamic adversary can change its corrupted nodes among the protocol. So far, there is not a formal definition and there are no protocols of dynamic adversaries in VSS context. Also, another important question is, would there exist a protocol to share a secret with a static adversary with at most 1 broadcast round? In this paper, we provide a formal definition of the dynamic adversary. The simulation results prove the efficiency of the proposed protocol in terms of the runtime, the memory usage, and the number of message exchanges. We show that the change period of the dynamic adversary could not happen in less than 4 rounds in order to have a perfectly secure VSS, and then we establish a protocol to deal with this type of adversary. Also, we prove that the lower bound of broadcast complexity for the static adversary is (2,0)-broadcast rounds.
30
Leermakers, Daan, and Boris Skoric. "Quantum Alice and silent Bob: Qubit-based Quantum Key Recycling with almost no classical communication." Quantum Information and Computation 21, no. 1&2 (February 2021): 0001–18. http://dx.doi.org/10.26421/qic21.1-2-1.
Full textAbstract:
We answer an open question about Quantum Key Recycling (QKR): Is it possible to put the message entirely in the qubits without increasing the number of qubits compared to existing QKR schemes? We show that this is indeed possible. We introduce a prepare-and-measure QKR protocol where the communication from Alice to Bob consists entirely of qubits. As usual, Bob responds with an authenticated one-bit accept/reject classical message. Compared to Quantum Key Distribution (QKD), QKR has reduced round complexity. Compared to previous qubit-based QKR protocols, our scheme has far less classical communication. We provide a security proof in the universal composability framework and find that the communication rate is asymptotically the same as for QKD with one-way postprocessing.
31
Jones, Helene Markham, Ffion Curtis, Graham Law, Christopher Bridle, Dorothy Boyle, and Tanweer Ahmed. "Evaluating follow-up and complexity in cancer clinical trials (EFACCT): an eDelphi study of research professionals’ perspectives." BMJ Open 10, no. 2 (February 2020): e034269. http://dx.doi.org/10.1136/bmjopen-2019-034269.
Full textAbstract:
ObjectivesTo evaluate patient follow-up and complexity in cancer clinical trial delivery, using consensus methods to: (1) identify research professionals’ priorities, (2) understand localised challenges, (3) define study complexity and workloads supporting the development of a trial rating and complexity assessment tool (TRACAT).DesignA classic eDelphi completed in three rounds, conducted as the launch study to a multiphase national project (evaluating follow-up and complexity in cancer clinical trials).SettingMulticentre online survey involving professionals at National Health Service secondary care hospital sites in Scotland and England varied in scale, geographical location and patient populations.ParticipantsPrincipal investigators at 13 hospitals across nine clinical research networks recruited 33 participants using pre-defined eligibility criteria to form a multidisciplinary panel.Main outcome measuresStatements achieving a consensus level of 70% on a 7-point Likert-type scale and ranked trial rating indicators (TRIs) developed by research professionals.ResultsThe panel developed 75 consensus statements illustrating factors contributing to complexity, follow-up intensity and operational performance in trial delivery, and specified 14 ranked TRIs. Seven open questions in the first qualitative round generated 531 individual statements. Iterative survey rounds returned rates of 82%, 82% and 93%.ConclusionsClinical trials operate within a dynamic, complex healthcare and innovation system where rapid scientific advances present opportunities and challenges for delivery organisations and professionals. Panellists highlighted cultural and organisational factors limiting the profession’s potential to support growing trial complexity and patient follow-up. Enhanced communication, interoperability, funding and capacity have emerged as key priorities. Future operational models should test dialectic Singerian-based approaches respecting open dialogue and shared values. Research capacity building should prioritise innovative, collaborative approaches embedding validated review and evaluation models to understand changing operational needs and challenges. TRACAT provides a mechanism for continual knowledge assimilation to improve decision-making.
32
Wang, Huijiao, Jiapeng Tian, Xin Zhang, Yongzhuang Wei, and Hua Jiang. "Multiple Differential Distinguisher of SIMECK32/64 Based on Deep Learning." Security and Communication Networks 2022 (September 14, 2022): 1–12. http://dx.doi.org/10.1155/2022/7564678.
Full textAbstract:
Currently, deep learning has provided an important means to solve problems in various fields. Intelligent computing will bring a new solution to the security analysis of lightweight block cipher as its analysis becomes more and more intelligent and automatic. In this study, the novel multiple differential distinguishers of round-reduced SIMECK32/64 based on deep learning are proposed. Two kinds of SIMECK32/64’s 6–11 rounds deep learning distinguishers are designed by using the neural network to simulate the case of the multiple input differences and multiple output differences in multiple differential cryptanalysis. The general models of the two distinguishers and the neural network structures are presented. The random multiple ciphertext pairs and the associated multiple ciphertext pairs are exploited as the input of the model. The generation method of the data set is given. The performance of the two proposed distinguishers is compared. The experimental results confirm that the proposed distinguishers have higher accuracy and rounds than the distinguisher with a single difference. The relationship between the quantity of multiple differences and the performance of the distinguishers is also verified. The differential distinguisher based on deep learning needs less time complexity and data complexity than the traditional distinguisher. The accuracy of filtering error ciphertext of our 8-round neural distinguisher is up to 96.10%.
33
Zhang, Kai, Xuejia Lai, Lei Wang, Jie Guan, and Bin Hu. "Slide Attack on Full-Round ULC Lightweight Block Cipher Designed for IoT." Security and Communication Networks 2022 (April 23, 2022): 1–8. http://dx.doi.org/10.1155/2022/4291000.
Full textAbstract:
To meet the security demand for IoT devices, many new lightweight block ciphers are proposed. ULC is a lightweight block cipher designed for the IoT. It has many advantages in terms of memory use, efficiency, and security. In this paper, a slide attack on full-round ULC is proposed in a related key setting. First, two properties on ULC are discovered. The first property is presented to illustrate the property of a slid pair for ULC. The second property is introduced to construct a link between some round key bits and some master key bits. Based on these properties, a key recovery attack on ULC is proposed. In this attack, with the condition of one related key, all the 80 master key bits can be recovered with the data complexity of O(232), the memory complexity of O(232), and the time complexity of O(263). The result of this paper indicates that ULC can’t resist slide attack in related key settings.
34
FRIEDMAN, ROY, ACHOUR MOSTEFAOUI, and MICHEL RAYNAL. "$\diamondsuit {\mathcal P}_{mute}$-BASED CONSENSUS for ASYNCHRONOUS BYZANTINE SYSTEMS." Parallel Processing Letters 15, no. 01n02 (March 2005): 169–82. http://dx.doi.org/10.1142/s0129626405002131.
Full textAbstract:
This paper presents a consensus protocol for asynchronous distributed systems made up of n processes, where up to f<n/4 processes can behave arbitrarily (Byzantine processes). The protocol assumes that the underlying system is equipped with an unreliable failure detector of the class [Formula: see text]. The failure detectors of the class [Formula: see text] ensure that (1) all mute processes are detected (a mute process is a process that, after some time, stops sending protocol messages), and (2) after some unknown but finite time, no correct process is suspected (mute processes are a subset of the Byzantine processes). The proposed protocol enjoys the following properties. It is based on the round coordinator paradigm and its design principle is particularly simple. Its message complexity is O(n2) per round. In addition to a round number, the message size is O(1), except for one message per round (sent by the round coordinator) whose size is O(n). The protocol does not use message "proofs", certificates, or application level signatures. When no process is faulty, all processes propose the same value, and the failure detector makes no mistake, the processes decide in one round (4 communication steps). Finally, when a process decides, it only needs a simple unreliable broadcast mechanism to prevent the other processes from deadlocking. All these features make the protocol attractive to cope with the net effect of Byzantine failures and asynchrony.
35
SEHYR, ZED SEVCIKOVA, BRENDA NICODEMUS, JENNIFER PETRICH, and KAREN EMMOREY. "Referring strategies in American Sign Language and English (with co-speech gesture): The role of modality in referring to non-nameable objects." Applied Psycholinguistics 39, no. 5 (April 17, 2018): 961–87. http://dx.doi.org/10.1017/s0142716418000061.
Full textAbstract:
ABSTRACTAmerican Sign Language (ASL) and English differ in linguistic resources available to express visual–spatial information. In a referential communication task, we examined the effect of language modality on the creation and mutual acceptance of reference to non-nameable figures. In both languages, description times reduced over iterations and references to the figures’ geometric properties (“shape-based reference”) declined over time in favor of expressions describing the figures’ resemblance to nameable objects (“analogy-based reference”). ASL signers maintained a preference for shape-based reference until the final (sixth) round, while English speakers transitioned toward analogy-based reference by Round 3. Analogy-based references were more time efficient (associated with shorter round description times). Round completion times were longer for ASL than for English, possibly due to gaze demands of the task and/or to more shape-based descriptions. Signers’ referring expressions remained unaffected by figure complexity while speakers preferred analogy-based expressions for complex figures and shape-based expressions for simple figures. Like speech, co-speech gestures decreased over iterations. Gestures primarily accompanied shape-based references, but listeners rarely looked at these gestures, suggesting that they were recruited to aid the speaker rather than the addressee. Overall, different linguistic resources (classifier constructions vs. geometric vocabulary) imposed distinct demands on referring strategies in ASL and English.
36
Bagchi, Susmit, Hafizur Rahaman, and Purnendu Das. "MDVM System Concept, Paging Latency and Round-2 Randomized Leader Election Algorithm in SG." Journal of Advanced Computational Intelligence and Intelligent Informatics 10, no. 5 (September 20, 2006): 752–60. http://dx.doi.org/10.20965/jaciii.2006.p0752.
Full textAbstract:
The future trend in the computing paradigm is marked by mobile computing based on mobile-client/server architecture connected by wireless communication network. However, the mobile computing systems have limitations because of the resource-thin mobile clients operating on battery power. The MDVM system allows the mobile clients to utilize memory and CPU resources of Server-Groups (SG) to overcome the resource limitations of clients in order to support the high-end mobile applications such as, m-commerce and virtual organization (VO). In this paper the concept of MDVM system and the architecture of cellular network containing the SG are discussed. A round-2 randomized distributed algorithm is proposed to elect a unique leader and co-leader of the SG. The algorithm is free from any assumption about network topology, buffer space limitations and is based on dynamically elected coordinators eliminating single point of failure. The algorithm is implemented in distributed system setup and the network-paging latency values of wired and wireless networks are measured experimentally. The experimental results demonstrate that in most cases the algorithm successfully terminates in first round and the possibility of second round execution decreases significantly with the increase in the size of SG (|<I>Na</I>|). The overall message complexity of the algorithm is O(|<I>Na</I>|). The comparative study of network-paging latencies indicates that 3G/4G mobile communication systems would support the realization of MDVM system.
37
Cadilhac, Michael. "Review of Communication Complexity and Applications by Anup Rao and Amir Yehudayoff." ACM SIGACT News 52, no. 3 (October 17, 2021): 11–13. http://dx.doi.org/10.1145/3494656.3494660.
Full textAbstract:
At its core, communication complexity is the study of the amount of information two parties need to exchange in order to compute a function. For instance, Alice receives a string of characters, Bob receives another, and they should decide whether these strings are the same with as few rounds of communication as possible. Multiple settings are conceivable, for instance with multiple parties or with randomness. Upper and lower bounds for communication problems rely on a wealth of mathematical tools, from probability theory to Ramsey theory, making this a complete and exciting topic. Further, communication complexity finds applications in different aspects of theoretical computer science, including circuit complexity and data structures. This usually requires to take a "communication" view of a problem, which in itself can be an eye-opening vantage point.
38
Aldawsari, Layla S., and Tom Altman. "Naming in Multichannel with Beeps in the Strong Model." Applied Sciences 10, no. 20 (October 14, 2020): 7164. http://dx.doi.org/10.3390/app10207164.
Full textAbstract:
In this paper, a system of anonymous processes is considered that communicates with beeps through multiple channels in a synchronous communication model. In beeping channels, processes are limited to hearing either a beep or a silence from the channel with no collision detection. A strong model is assumed in which a process can beep on any single channel and listen on any specific channel during a single round. The goal is to develop distributed naming algorithms for two models where the number of processes is either known or unknown. A Las Vegas algorithm was developed for naming anonymous processes when the number of processes is known. This algorithm has an optimal time complexity of O(nlogn) rounds and uses O(nlogn) random bits, where n is the number of processes for the largest group. For the model with an unknown number of processes, a Monte Carlo algorithm was developed, which has an optimal running time of O(nlogn) rounds and a probability of success that is at least 1−12Ω(logn). The algorithms solve the naming problem in new models where processes communicate through multiple channels.
39
Hao, Xiang Ning, Xue Min Wang, and Li Qiong Deng. "A New Protocol for Secure Distributed Multiplication of Two Polynomial Shared Values." Advanced Materials Research 1042 (October 2014): 110–16. http://dx.doi.org/10.4028/www.scientific.net/amr.1042.110.
Full textAbstract:
In view of practical applications, it is a high priority to optimize the efficiency of methods for secure multi-party computations. A classic problem is described as following: there are two secrets, α and β, shared among n players using Shamir (t+1,n)-threshold secret sharing scheme, and how to make their product αβshared among n players using the same way. The protocol of Gennaro, Rabin and Rabin (1998) is a well known and efficient protocol for this purpose. It requires one round of communication and O(n2klog2n+nk2) bit-operations per player, where k is the bit size of the computing field and n is the number of players. In a previous paper (2007), the author presented a modification of this protocol, which reduced its complexity toOn2k+nk2. In 2009, Peter Lory reduced its complexity to On2k. A new protocol is presented in our paper, which reduces this complexity further to Onklog2k. It is better than Gennaro protocol unconditionally. And as to Peter Lory protocol, the reduction is profitable in situation where log2k is smaller than n.
40
Lenzini, L., E. Mingozzi, and G. Stea. "Tradeoffs Between Low Complexity, Low Latency, and Fairness With Deficit Round-Robin Schedulers." IEEE/ACM Transactions on Networking 12, no. 4 (August 2004): 681–93. http://dx.doi.org/10.1109/tnet.2004.833131.
Full text
41
Labao, Alfonso, and Henry Adorna. "Cryptographic Rational Secret Sharing Schemes over General Networks." Cryptography 6, no. 4 (October 1, 2022): 50. http://dx.doi.org/10.3390/cryptography6040050.
Full textAbstract:
We propose cryptographic rational secret sharing protocols over general networks. In a general network, the dealer may not have direct connections to each player, and players may not have direct connections to each of the other players. We present conditions on the network topology for which our proposed protocols are computational strict Nash equilibria and (k−1)-resilient, along with analysis on their round and communication complexity. We also present new notions of equilibria such as Φ-resilient computational Nash equilibria, whereby a protocol is resilient to coalitions that satisfy conditions in Φ, regardless of the coalition’s size. We also propose (n−1)-key leakage-tolerant equilibria applicable to cryptographic protocols involving secret keys, whereby the equilibrium holds even if some players acquire (n−1) tuples of secret keys.
42
Jiang, Zilong, and Chenhui Jin. "Multiple Impossible Differential Attacks for ForkAES." Security and Communication Networks 2022 (June 29, 2022): 1–11. http://dx.doi.org/10.1155/2022/5360032.
Full textAbstract:
To yield a highly efficient authentication encryption design for very short messages, the tweakable forkcipher is proposed, which is a tweakable block cipher that uses forking construction to produce two output blocks. The designers also presented ForkAES, a forkcipher that is based on the round function of AES and the tweakable variant of KIASU. Therefore, the security of ForkAES is found on the block ciphers AES and KIASU. However, from the perspective of new forking construction, attackers may obtain some unique properties. Impossible differential attacks are widely used on block ciphers. This paper studies the security of ForkAES against multiple impossible differential cryptanalysis. Based on the property of the forking construction, two types of impossible differential distinguishers have been constructed. We first use the tweak with different truncated differences to build more attack trails. Then, we first propose the multiple impossible differential attack for ForkAES- ∗ -5-4. Thus, only a single round would remain as a security margin. Utilizing multiple attack trails, our attack scenario obtains more subkey bytes and enhances the subkey’s sieving efficiency without increasing complexity. Furthermore, we carefully consider the process of recovering the master key, which can efficiently reject wrong candidate keys. In reconstruction queries, our attack reaches the longest number of rounds for ForkAES in impossible differential analysis, with 2 100.8 lookups, 2 85.8 chosen ciphertexts, and 2 92.7 memory blocks to store AES states. In encryption queries, we improve the previous attacks on ForkAES by attacking one more round (i.e., ForkAES- ∗ -5-4), with 2 118.2 lookups, 2 111.4 plaintexts, and 2 92.7 memory blocks to store AES states.
43
Peng, Ningduo, Guangchun Luo, Ke Qin, and Aiguo Chen. "Query-Biased Preview over Outsourced and Encrypted Data." Scientific World Journal 2013 (2013): 1–13. http://dx.doi.org/10.1155/2013/860621.
Full textAbstract:
For both convenience and security, more and more users encrypt their sensitive data before outsourcing it to a third party such as cloud storage service. However, searching for the desired documents becomes problematic since it is costly to download and decrypt each possibly needed document to check if it contains the desired content. An informative query-biased preview feature, as applied in modern search engine, could help the users to learn about the content without downloading the entire document. However, when the data are encrypted, securely extracting a keyword-in-context snippet from the data as a preview becomes a challenge. Based on private information retrieval protocol and the core concept of searchable encryption, we propose a single-server and two-round solution to securely obtain a query-biased snippet over the encrypted data from the server. We achieve this novel result by making a document (plaintext) previewable under any cryptosystem and constructing a secure index to support dynamic computation for a best matched snippet when queried by some keywords. For each document, the scheme hasO(d)storage complexity andO(log(d/s)+s+d/s)communication complexity, wheredis the document size andsis the snippet length.
44
Alwazani, Hibatallah, and Anas Chaaban. "IRS-Enabled Ultra-Low-Power Wireless Sensor Networks: Scheduling and Transmission Schemes." Sensors 22, no. 23 (November 27, 2022): 9229. http://dx.doi.org/10.3390/s22239229.
Full textAbstract:
Passive technologies, including intelligent reflecting surfaces (IRS), are gaining traction thanks to their ability to enhance communication systems while maintaining minimal cost and low complexity. They can assist a wireless sensor network (WSN) by achieving low power requirements for sensors and aid communication needs in many applications, for instance, environmental monitoring. In this paper, we propose an IRS-equipped WSN which describes sensors equipped with IRSs instead of active radio frequency (RF) electronics. The IRS sensor node (ISN) intercepts a dedicated signal from a power source such as a base station (BS) and modulates the transmission of that signal to an intended recipient. In order to enable multiple sensors to transmit to the receiver, we study opportunistic scheduling (OS) utilizing multi-sensor diversity while considering blind IRS operation, and compare it with round-robin (RR), proportional fairness (PF), and a theoretical upper bound. We study the effect of the choice of the number of IRS elements N and number of ISNs L on the average throughput of the system under OS. Finally, we provide pertinent comparisons for the different scheduling schemes and IRS configurations under relevant system performance metrics, highlighting different scenarios in which each scheme performs better.
45
Bravyi, S., D. P. DiVincenzo, R. Oliveira, and B. M. Terhal. "The complexity of stoquastic local Hamiltonian problems." Quantum Information and Computation 8, no. 5 (May 2008): 361–85. http://dx.doi.org/10.26421/qic8.5-1.
Full textAbstract:
We study the complexity of the Local Hamiltonian Problem (denoted as LH-MIN) in the special case when a Hamiltonian obeys the condition that all off-diagonal matrix elements in the standard basis are real and non-positive. We will call such Hamiltonians, which are common in the natural world, stoquastic. An equivalent characterization of stoquastic Hamiltonians is that they have an entry-wise non-negative Gibbs density matrix for any temperature. We prove that LH-MIN for stoquastic Hamiltonians belongs to the complexity class \AM{}--- a probabilistic version of \NP{} with two rounds of communication between the prover and the verifier. We also show that $2$-local stoquastic LH-MIN is hard for the class \MA. With the additional promise of having a polynomial spectral gap, we show that stoquastic LH-MIN belongs to the class \POSTBPP=\BPPpath --- a generalization of \BPP{} in which a post-selective readout is allowed. This last result also shows that any problem solved by adiabatic quantum computation using stoquastic Hamiltonians is in PostBPP.
46
Gupta, Kanav, Deepak Kumaraswamy, Nishanth Chandran, and Divya Gupta. "LLAMA: A Low Latency Math Library for Secure Inference." Proceedings on Privacy Enhancing Technologies 2022, no. 4 (October 2022): 274–94. http://dx.doi.org/10.56553/popets-2022-0109.
Full textAbstract:
Secure machine learning (ML) inference can provide meaningful privacy guarantees to both the client (holding sensitive input) and the server (holding sensitive weights of the ML model) while realizing inferenceas-a-service. Although many specialized protocols exist for this task, including those in the preprocessing model (where a majority of the overheads are moved to an input independent offline phase), they all still suffer from large online complexity. Specifically, the protocol phase that executes once the parties know their inputs, has high communication, round complexity, and latency. Function Secret Sharing (FSS) based techniques offer an attractive solution to this in the trusted dealer model (where a dealer provides input independent correlated randomness to both parties), and 2PC protocols obtained based on these techniques have a very lightweight online phase. Unfortunately, current FSS-based 2PC works (AriaNN, PoPETS 2022; Boyle et al. Eurocrypt 2021; Boyle et al. TCC 2019) fall short of providing a complete solution to secure inference. First, they lack support for math functions (e.g., sigmoid, and reciprocal square root) and hence, are insufficient for a large class of inference algorithms (e.g. recurrent neural networks). Second, they restrict all values in the computation to be of the same bitwidth and this prevents them from benefitting from efficient float-to-fixed converters such as Tensorflow Lite that crucially use low bitwidth representations and mixed bitwidth arithmetic. In this work, we present LLAMA – an end-to-end, FSS based, secure inference library supporting precise low bitwidth computations (required by converters) as well as provably precise math functions; thus, overcoming all the drawbacks listed above. We perform an extensive evaluation of LLAMA and show that when compared with non-FSS based libraries supporting mixed bitwidth arithmetic and math functions (SIRNN, IEEE S&P 2021), it has at least an order of magnitude lower communication, rounds, and runtimes. We integrate LLAMA with the EzPC framework (IEEE EuroS&P 2019) and demonstrate its robustness by evaluating it on large benchmarks (such as ResNet-50 on the ImageNet dataset) as well as on benchmarks considered in AriaNN – here too LLAMA outperforms prior work.
47
Braun, Lennart, Daniel Demmler, Thomas Schneider, and Oleksandr Tkachenko. "MOTION – A Framework for Mixed-Protocol Multi-Party Computation." ACM Transactions on Privacy and Security 25, no. 2 (May 31, 2022): 1–35. http://dx.doi.org/10.1145/3490390.
Full textAbstract:
We present MOTION, an efficient and generic open-source framework for mixed-protocol secure multi-party computation (MPC) . MOTION is built in a user-friendly, modular, and extensible way, intended to be used as a tool in MPC research and to increase adoption of MPC protocols in practice. Our framework incorporates several important engineering decisions such as full communication serialization, which enables MPC over arbitrary messaging interfaces and removes the need of owning network sockets. MOTION also incorporates several performance optimizations that improve the communication complexity and latency, e.g., \( 2\times \) better online round complexity of precomputed correlated Oblivious Transfer (OT) . We instantiate our framework with protocols for N parties and security against up to \( N-1 \) passive corruptions: the MPC protocols of Goldreich-Micali-Wigderson (GMW) in its arithmetic and Boolean version and OT-based BMR (Ben-Efraim et al., CCS’16), as well as novel and highly efficient conversions between them, including a non-interactive conversion from BMR to arithmetic GMW. MOTION is highly efficient, which we demonstrate in our experiments. Compared to secure evaluation of AES-128 with \( N=3 \) parties in a high-latency network with OT-based BMR, we achieve a 16 \( \times \) better throughput of 16 AES evaluations per second using BMR. With this, we show that BMR is much more competitive than previously assumed. For \( N=3 \) parties and full-threshold protocols in a LAN, MOTION is \( 10\times \) – \( 18\times \) faster than the previous best passively secure implementation from the MP-SPDZ framework, and \( 190\times \) – \( 586\times \) faster than the actively secure SCALE-MAMBA framework. Finally, we show that our framework is highly efficient for privacy-preserving neural network inference.
48
Qiu, Xueying, Yongzhuang Wei, Samir Hodzic, and Enes Pasalic. "Integral Distinguishers of the Full-Round Lightweight Block Cipher SAT_Jo." Security and Communication Networks 2021 (September 18, 2021): 1–9. http://dx.doi.org/10.1155/2021/5310545.
Full textAbstract:
Integral cryptanalysis based on division property is a powerful cryptanalytic method whose range of successful applications was recently extended through the use of Mixed-Integer Linear Programming (MILP). Although this technique was demonstrated to be efficient in specifying distinguishers of reduced round versions of several families of lightweight block ciphers (such as SIMON, PRESENT, and few others), we show that this method provides distinguishers for a full-round block cipher SAT_Jo. SAT_Jo cipher is very similar to the well-known PRESENT block cipher, which has successfully withstood the known cryptanalytic methods. The main difference compared to PRESENT, which turns out to induce severe weaknesses of SAT_Jo algorithm, is its different choice of substitution boxes (S-boxes) and the bit-permutation layer for the reasons of making the cipher highly resource-efficient. Even though the designers provided a security analysis of this scheme against some major generic cryptanalytic methods, an application of the bit-division property in combination with MILP was not considered. By specifying integral distinguishers for the full-round SAT_Jo algorithm using this method, we essentially disapprove its use in intended applications. Using a 30-round distinguisher, we also describe a subkey recovery attack on the SAT_Jo algorithm whose time complexity is about 2 66 encryptions (noting that SAT_Jo is designed to provide 80 bits of security). Moreover, it seems that the choice of bit-permutation induces weak division properties since replacing the original bit-permutation of SAT_Jo by the one used in PRESENT immediately renders integral distinguishers inefficient.
49
Zheng, Qiuhua, Yinhao Hu, Tao Pei, Shengwang Xu, Junzhe Yu, Ting Wu, Yanzhao Shen, Yingpei Zeng, and Tingting Cui. "Improved Single-Key Attacks on 2-GOST." Security and Communication Networks 2020 (October 15, 2020): 1–10. http://dx.doi.org/10.1155/2020/8886032.
Full textAbstract:
GOST, known as GOST-28147-89, was standardized as the Russian encryption standard in 1989. It is a lightweight-friendly cipher and suitable for the resource-constrained environments. However, due to the simplicity of GOST’s key schedule, it encountered reflection attack and fixed point attack. In order to resist such attacks, the designers of GOST proposed a modification of GOST, namely, 2-GOST. This new version changes the order of subkeys in the key schedule and uses concrete S-boxes in round function. But regarding single-key attacks on full-round 2-GOST, Ashur et al. proposed a reflection attack with data of 2 32 on a weak-key class of size 2 224 , as well as the fixed point attack and impossible reflection attack with data of 2 64 for all possible keys. Note that the attacks applicable for all possible keys need the entire plaintext space. In other words, these are codebook attacks. In this paper, we propose single-key attacks on 2-GOST with only about 2 32 data instead of codebook. Firstly, we apply 2-dimensional meet-in-the-middle attack combined with splice-cut technique on full-round 2-GOST. This attack is applicable for all possible keys, and its data complexity reduces from previous 2 64 to 2 32 . Besides that, we apply splice-cut meet-in-the-middle attack on 31-round 2-GOST with only data of 2 32 . In this attack, we only need 8 bytes of memory, which is negligible.
50
Hung, Yung, Sophie Hieke, Klaus Grunert, and Wim Verbeke. "Setting Policy Priorities for Front-of-Pack Health Claims and Symbols in the European Union: Expert Consensus Built by Using a Delphi Method." Nutrients 11, no. 2 (February 14, 2019): 403. http://dx.doi.org/10.3390/nu11020403.
Full textAbstract:
Despite the fact that front-of-pack nutrition labels such as health claims and symbols have received growing attention in consumer behavior research, comprehensive conclusions could not yet be drawn to develop concrete policy actions, owing to the complexity of the subject and a constantly changing market environment. In this study, evidence-based policy recommendations and communication guidelines have been derived from the findings of the EU FP7 project CLYMBOL (“Role of health-related CLaims and sYMBOLs in consumer behavior”, Grant Agreement 311963), and have been evaluated and prioritized by European stakeholders using a three-round Delphi method. A moderate level of consensus was achieved and results suggest that policy priority should focus on ways to improve consumer motivation and interest in healthy eating. Consumers’ interest in healthy eating could be increased by adopting appropriate communication strategies such as using innovative ways to communicate the importance of healthy eating, which may aim to change the possible negative association between healthiness and tastiness. The highest-rated finding was related to consumers’ favorable attitude towards health claims with shorter and less complex messages and health symbols with a visible endorsement. Meanwhile, there was a clear consensus that health claims need to be scientifically substantiated and credible but phrased without using overly complex scientific wordings, in order to be meaningful for consumers. Furthermore, stakeholders from academia and industry believe that consumer awareness about existing health claims should be increased. The identified policy recommendations and communication guidelines stem from recent empirical evidence and provide useful insights that guide future policy development aligning consumer protection issues as well as public health and food marketing communication interests.