Minimizing the Two-Round Even–Mansour Cipher

The r-round (iterated) Even–Mansour cipher (also known as key-alternating cipher) defines a block cipher from r fixed public n-bit permutations \(P_1,\ldots ,P_r\) as follows: Given a sequence of n-bit round keys \(k_0,\ldots ,k_r\), an n-bit plaintext x is encrypted by xoring round key \(k_0\), applying permutation \(P_1\), xoring round key \(k_1\), etc. The (strong) pseudorandomness of this construction in the random permutation model (i.e., when the permutations \(P_1,\ldots ,P_r\) are public random permutation oracles that the adversary can query in a black-box way) was studied in a number of recent papers, culminating with the work of Chen and Steinberger (EUROCRYPT 2014), who proved that the r-round Even–Mansour cipher is indistinguishable from a truly random permutation up to \(\mathcal {O}(2^{\frac{rn}{r+1}})\) queries of any adaptive adversary (which is an optimal security bound since it matches a simple distinguishing attack). All results in this entire line of work share the common restriction that they only hold under the assumption that the round keys \(k_0,\ldots ,k_r\) and the permutations \(P_1,\ldots ,P_r\) are independent. In particular, for two rounds, the current state of knowledge is that the block cipher \(E(x)=k_2\oplus P_2(k_1\oplus P_1(k_0\oplus x))\) is provably secure up to \(\mathcal {O}(2^{2n/3})\) queries of the adversary, when \(k_0\), \(k_1\), and \(k_2\) are three independent n-bit keys, and \(P_1\) and \(P_2\) are two independent random n-bit permutations. In this paper, we ask whether one can obtain a similar bound for the two-round Even–Mansour cipher from just one n-bit key and one n-bit permutation. Our answer is positive: When the three n-bit round keys \(k_0\), \(k_1\), and \(k_2\) are adequately derived from an n-bit master key k, and the same permutation P is used in place of \(P_1\) and \(P_2\), we prove a qualitatively similar \(\widetilde{\mathcal {O}}(2^{2n/3})\) security bound (in the random permutation model). To the best of our knowledge, this is the first “beyond the birthday bound” security result for AES-like ciphers that does not assume independent round keys.     

Automata Evaluation and Text Search Protocols with Simulation-Based Security

This paper presents efficient protocols for securely computing the following two problems: (1) The fundamental problem of pattern matching. This problem is defined in the two-party setting, where party \(P_1\) holds a pattern and party \(P_2\) holds a text. The goal of \(P_1\) is to learn where the pattern appears in the text, without revealing it to \(P_2\) or learning anything else about \(P_2\)’s text. This problem has been widely studied for decades due to its broad applicability. We present several protocols for several notions of security. We further generalize one of our solutions to solve additional pattern matching-related problems of interest. (2) Our construction from above, in the malicious case, is based on a novel protocol for secure oblivious automata evaluation which is of independent interest. In this problem, party \(P_1\) holds an automaton and party \(P_2\) holds an input string, and they need to decide whether the automaton accepts the input, without learning anything else. Our protocol obtains full security in the face of malicious adversaries.     

Characterization of Secure Multiparty Computation Without Broadcast

A major challenge in the study of cryptography is characterizing the necessary and sufficient assumptions required to carry out a given cryptographic task. The focus of this work is the necessity of a broadcast channel for securely computing symmetric functionalities (where all the parties receive the same output) when one third of the parties, or more, might be corrupted. Assuming all parties are connected via a point-to-point network, but no broadcast channel (nor a secure setup phase) is available, we prove the following characterization:

• A symmetric n-party functionality can be securely computed facing \(n/3\le t<n/2\) corruptions (i.e., honest majority), if and only if it is \((n-2t)\) -dominated; a functionality is k-dominated, if any k-size subset of its input variables can be set to determine its output to some predetermined value.
• Assuming the existence of one-way functions, a symmetric n-party functionality can be securely computed facing \(t\ge n/2\) corruptions (i.e., no honest majority), if and only if it is 1-dominated and can be securely computed with broadcast.

It follows that, in case a third of the parties might be corrupted, broadcast is necessary for securely computing non-dominated functionalities (in which “small” subsets of the inputs cannot determine the output), including, as interesting special cases, the Boolean XOR and coin-flipping functionalities.

     

The Security of Tandem-DM in the Ideal Cipher Model

We prove that Tandem-DM, one of the two “classical” schemes for turning an n-bit blockcipher of 2n-bit key into a double-block-length hash function, has birthday-type collision resistance in the ideal cipher model. For \(n=128\), an adversary must make at least \(2^{120.87}\) blockcipher queries to achieve chance 0.5 of finding a collision. A collision resistance analysis for Tandem-DM achieving a similar birthday-type bound was already proposed by Fleischmann, Gorski and Lucks at FSE 2009. As we detail, however, the latter analysis is wrong, thus leaving the collision resistance of Tandem-DM as an open problem until now. Our analysis exhibits a novel feature in that we introduce a trick never used before in ideal cipher proofs. We also give an improved bound on the preimage security of Tandem-DM. For \(n=128\), we show that an adversary must make at least \(2^{245.99}\) blockcipher queries to achieve chance 0.5 of inverting a randomly chosen point in the range. Asymptotically, Tandem-DM is proved to be preimage resistant up to \(2^{2n}/n\) blockcipher queries. This bound improves upon the previous best bound of \({{\varOmega }}(2^n)\) queries and is optimal (ignoring log factors) since Tandem-DM has range of size \(2^{2n}\).     

An Optimally Fair Coin Toss

We address one of the foundational problems in cryptography: the bias of coin-flipping protocols. Coin-flipping protocols allow mutually distrustful parties to generate a common unbiased random bit, guaranteeing that even if one of the parties is malicious, it cannot significantly bias the output of the honest party. A classical result by Cleve (Proceedings of the 18th annual ACM symposium on theory of computing, pp 364–369, 1986) showed that for any two-party \(r\)-round coin-flipping protocol there exists an efficient adversary that can bias the output of the honest party by \(\varOmega (1/r)\). However, the best previously known protocol only guarantees \(O(1/\sqrt{r})\) bias, and the question of whether Cleve’s bound is tight has remained open for more than 20 years. In this paper, we establish the optimal trade-off between the round complexity and the bias of two-party coin-flipping protocols. Under standard assumptions (the existence of oblivious transfer), we show that Cleve’s lower bound is tight: We construct an \(r\)-round protocol with bias \(O(1/r)\).     

Fast Cut-and-Choose-Based Protocols for Malicious and Covert Adversaries

In the setting of secure two-party computation, two parties wish to securely compute a joint function of their private inputs, while revealing only the output. One of the primary techniques for achieving efficient secure two-party computation is that of Yao’s garbled circuits (FOCS 1986). In the semi-honest model, where just one garbled circuit is constructed and evaluated, Yao’s protocol has proven itself to be very efficient. However, a malicious adversary who constructs the garbled circuit may construct a garbling of a different circuit computing a different function, and this cannot be detected (due to the garbling). In order to solve this problem, many circuits are sent and some of them are opened to check that they are correct while the others are evaluated. This methodology, called cut-and-choose, introduces significant overhead, both in computation and in communication, and is mainly due to the number of circuits that must be used in order to prevent cheating. In this paper, we present a cut-and-choose protocol for secure computation based on garbled circuits, with security in the presence of malicious adversaries, that vastly improves on all previous protocols of this type. Concretely, for a cheating probability of at most \(2^{-40}\), the best previous works send between 125 and 128 circuits. In contrast, in our protocol 40 circuits alone suffice (with some additional overhead). Asymptotically, we achieve a cheating probability of \(2^{-s}\) where \(s\) is the number of garbled circuits, in contrast to the previous best of \(2^{-0.32s}\). We achieve this by introducing a new cut-and-choose methodology with the property that in order to cheat, all of the evaluated circuits must be incorrect, and not just the majority as in previous works. The security of our protocol relies on the decisional Diffie–Hellman assumption.     

How Many Queries are Needed to Distinguish a Truncated Random Permutation from a Random Function?

An oracle chooses a function f from the set of n bits strings to itself, which is either a randomly chosen permutation or a randomly chosen function. When queried by an n-bit string w, the oracle computes f(w), truncates the m last bits, and returns only the first \(n-m\) bits of f(w). How many queries does a querying adversary need to submit in order to distinguish the truncated permutation from the (truncated) function? In Hall et al. (Building PRFs from PRPs, Springer, Berlin, 1998) showed an algorithm for determining (with high probability) whether or not f is a permutation, using \(O(2^{\frac{m+n}{2}})\) queries. They also showed that if \(m < n/7\), a smaller number of queries will not suffice. For \(m > n/7\), their method gives a weaker bound. In this note, we first show how a modification of the approximation method used by Hall et al. can solve the problem completely. It extends the result to practically any m, showing that \(\varOmega (2^{\frac{m+n}{2}})\) queries are needed to get a non-negligible distinguishing advantage. However, more surprisingly, a better bound for the distinguishing advantage, which we can write, in a simplified form, as \(O\left( \min \left\{ \frac{q^2}{2^n},\,\frac{q}{2^{\frac{n+m}{2}}},\,1\right\} \right) ,\) can be obtained from a result of Stam published, in a different context, already in 1978. We also show that, at least in some cases, this bound is tight.     

Multilevel heterogeneous network model for wireless sensor networks

The lifetime of a network can be increased by increasing the network energy. The network energy can be increased either increasing the number of sensors or increasing the initial energy of some sensors without increasing their numbers. Increasing network energy by deploying extra sensors is about ten times costlier than that using some sensors of high energy. Increasing the initial energy of some sensors leads to heterogeneous nodes in the network. In this paper, we propose a multilevel heterogeneous network model that is characterized by two types of parameters: primary parameter and secondary parameters. The primary parameter decides the level of heterogeneity by assuming the values of secondary parameters. This model can describe a network up to nth level of heterogeneity (n is a finite number). We evaluate the network performance by applying the HEED, a clustering protocol, on this model, naming it as MLHEED (Multi Level HEED) protocol. For n level of heterogeneity, this protocol is denoted by MLHEED-n. The numbers of nodes of each type in any level of heterogeneity are determined by the secondary model parameter. The MLHEED protocol (for all level heterogeneity) considers two variables, i.e., residual energy and node density, for deciding the cluster heads. We also consider fuzzy implementation of the MLHEED in which four variables are used to decide the cluster heads: residual energy, node density, average energy, and distance between base station and the sensor nodes. In this work, we illustrate the network model up to seven levels (\(1\le n\le 7\)). Experimentally, as the level of heterogeneity increases, the rate of energy dissipation decreases and hence the nodes stay alive for longer time. The MLHEED-m, \(m=2,3,4,5,6,7\), increase the network lifetime by \(73.05, 143.40, 213.17, 267.90, 348.60, 419.10\,\%\), respectively, by increasing the network energy as \(40, 57, 68.5, 78, 84, 92.5\,\%\) with respect to the original HEED protocol. In case of fuzzy implementation, the MLHEEDFL-m, \(m=2,3,4,5,6,7,\) increases the network lifetime by \(282.7, 378.5, 435.78, 498.50, 582.63, 629.79\,\%\), respectively, corresponding to the same increase in the network energy as that of the MLHEED (all levels) with respect to the original HEED. The fuzzy implementation of the HEED, MLHEEDFL-1, increases the network lifetime by \(176.6\,\%\) with respect to the original HEED with no increase in the network energy.     

Merkle’s Key Agreement Protocol is Optimal: An $$O(n^2)$$ Attack on Any Key Agreement from Random Oracles

We prove that every key agreement protocol in the random oracle model in which the honest users make at most n queries to the oracle can be broken by an adversary who makes \(O(n^2)\) queries to the oracle. This improves on the previous \({\tilde{\Omega }}(n^6)\) query attack given by Impagliazzo and Rudich (STOC ’89) and resolves an open question posed by them. Our bound is optimal up to a constant factor since Merkle proposed a key agreement protocol in 1974 that can be easily implemented with n queries to a random oracle and cannot be broken by any adversary who asks \(o(n^2)\) queries.     

Efficient Slide Attacks

The slide attack, presented by Biryukov and Wagner, has already become a classical tool in cryptanalysis of block ciphers. While it was used to mount practical attacks on a few cryptosystems, its practical applicability is limited, as typically, its time complexity is lower bounded by \(2^n\) (where n is the block size). There are only a few known scenarios in which the slide attack performs better than the \(2^n\) bound. In this paper, we concentrate on efficient slide attacks, whose time complexity is less than \(2^n\). We present a number of new attacks that apply in scenarios in which previously known slide attacks are either inapplicable, or require at least \(2^n\) operations. In particular, we present the first known slide attack on a Feistel construction with a 3-round self-similarity, and an attack with practical time complexity of \(2^{40}\) on a 128-bit key variant of the GOST block cipher with unknown S-boxes. The best previously known attack on the same variant, with known S-boxes (by Courtois), has time complexity of \(2^{91}\).     

Error performance of optically preamplified hybrid BPSK-PPM systems with transmitter and receiver imperfections

In this paper, we investigate the impact of the transmitter finite extinction ratio and the receiver carrier recovery phase offset on the error performance of two optically preamplified hybrid M-ary pulse position modulation (PPM) systems with coherent detection. The first system, referred to as PB-mPPM, combines polarization division multiplexing (PDM) with binary phase-shift keying and M-ary PPM, and the other system, referred to as PQ-mPPM, combines PDM with quadrature phase-shift keying and M-ary PPM. We provide new expressions for the probability of bit error for PB-mPPM and PQ-mPPM under finite extinction ratios and phase offset. The extinction ratio study indicates that the coherent systems PB-mPPM and PQ-mPPM outperform the direct-detection ones. It also shows that at \(P_b=10^{-9}\) PB-mPPM has a slight advantage over PQ-mPPM. For example, for a symbol size \(M=16\) and extinction ratio \(r=30\) dB, PB-mPPM requires 0.6 dB less SNR per bit than PQ-mPPM to achieve \(P_b=10^{-9}\). This investigation demonstrates that PB-mPPM is less complex and less sensitive to the variations of the offset angle \(\theta \) than PQ-mPPM. For instance, for \(M=16\), \(r=30\) dB, and \(\theta =10^{\circ }\) PB-mPPM requires 1.6 dB less than PQ-mPPM to achieve \(P_b=10^{-9}\). However, PB-mPPM enhanced robustness to phase offset comes at the expense of a reduced bandwidth efficiency when compared to PQ-mPPM. For example, for \(M=2\) its bandwidth efficiency is 60 % that of PQ-mPPM and \(\approx 86\,\%\) for \(M=1024\). For these reasons, PB-mPPM can be considered a reasonable design trade-off for M-ary PPM systems.     

Electrical Transport Mechanisms and Photoconduction in Undoped Crystalline Flash-Evaporated Lead Iodide Thin Films

The flash-evaporation technique was utilized to fabricate undoped 1.35-μm and 1.2-μm thick lead iodide films at substrate temperatures \( T_{\rm{s}} = 150 \)°C and 200°C, respectively. The films were deposited onto a coplanar comb-like copper (Cu-) electrode pattern, previously coated on glass substrates to form lateral metal–semiconductor–metal (MSM-) structures. The as-measured constant-temperature direct-current (dc)-voltage (\( I\left( {V;T} \right) - V \)) curves of the obtained lateral coplanar Cu-PbI₂-Cu samples (film plus electrode) displayed remarkable ohmic behavior at all temperatures (\( T = 18 - 90\,^\circ {\hbox{C}} \)). Their dc electrical resistance \( R_{\rm{dc}} (T \)) revealed a single thermally-activated conduction mechanism over the temperature range with activation energy \( E_{\rm{act}} \approx 0.90 - 0.98 \,{\hbox{eV}} \), slightly less than half of room-temperature bandgap energy \( E_{\rm{g}} \) (\( \approx \,2.3\, {\hbox{eV}} \)) of undoped 2H-polytype PbI₂ single crystals. The undoped flash-evaporated \( {\hbox{PbI}}_{\rm{x}} \) thin films were homogeneous and almost stoichiometric (\( x \approx 1.87 \)), in contrast to findings on lead iodide films prepared by other methods, and were highly crystalline hexagonal 2H-polytypic structure with c-axis perpendicular to the surface of substrates maintained at \( T_{\rm{s}} { \gtrsim }150^\circ {\hbox{C}} \). Photoconductivity measurements made on these lateral Cu-PbI₂-Cu-structures under on–off visible-light illumination reveal a feeble photoresponse for long wavelengths (\( \lambda > 570\,{\hbox{nm}} \)), but a strong response to blue light of photon energy \( E_{\rm{ph}} \) \( \approx \,2.73 \, {\hbox{eV}} \) (\( > E_{\rm{g}} \)), due to photogenerated electron–hole (e–h) pairs via direct band-to-band electronic transitions. The constant-temperature/dc voltage current–time \( I\left( {T,V} \right) - t \) curves of the studied lateral PbI₂ MSM-structures at low ambient temperatures (\( T < 50^\circ {\hbox{C}} \)), after cutting off the blue-light illumination, exhibit two trapping mechanisms with different relaxation times. These strongly depend on \( V \) and \( T \), with thermally generated charge carriers in the PbI₂ mask photogenerated (e–h) pairs at higher temperatures.     

Design and Performance Study of Dynamic Fractors in Any of the Four Quadrants

A fractor is a simple fractional-order system. Its transfer function is \(1/Fs^{\alpha }\); the coefficient, F, is called the fractance, and \(\alpha \) is called the exponent of the fractor. This paper presents how a fractor can be realized, using RC ladder circuit, meeting the predefined specifications on both F and \(\alpha \). Besides, commonly reported fractors have \(\alpha \) between 0 and 1. So, their constant phase angles (CPA) are always restricted between \(0^{\circ }\) and \(-90^{\circ }\). This work has employed GIC topology to realize fractors from any of the four quadrants, which means fractors with \(\alpha \) between \(-\)2 and +2. Hence, one can achieve any desired CPA between \(+180^{\circ }\) and \(-180^{\circ }\). The paper also exhibits how these GIC parameters can be used to tune the fractance of emulated fractors in real time, thus realizing dynamic fractors. In this work, a number of fractors are developed as per proposed technique, their impedance characteristics are studied, and fractance values are tuned experimentally.     

Locally Computable UOWHF with Linear Shrinkage

We study the problem of constructing locally computable universal one-way hash functions (UOWHFs) \(\mathcal {H}:\{0,1\}^n \rightarrow \{0,1\}^m\). A construction with constant output locality, where every bit of the output depends only on a constant number of bits of the input, was established by Applebaum et al. (SIAM J Comput 36(4):845–888, 2006). However, this construction suffers from two limitations: (1) it can only achieve a sublinear shrinkage of \(n-m=n^{1-\epsilon }\) and (2) it has a super-constant input locality, i.e., some inputs influence a large super-constant number of outputs. This leaves open the question of realizing UOWHFs with constant output locality and linear shrinkage of \(n-m= \epsilon n\), or UOWHFs with constant input locality and minimal shrinkage of \(n-m=1\). We settle both questions simultaneously by providing the first construction of UOWHFs with linear shrinkage, constant input locality and constant output locality. Our construction is based on the one-wayness of “random” local functions—a variant of an assumption made by Goldreich (Studies in Complexity and Cryptography, 76–87, 2011; ECCC 2010). Using a transformation of Ishai et al. (STOC, 2008), our UOWHFs give rise to a digital signature scheme with a minimal additive complexity overhead: signing n-bit messages with security parameter \(\kappa \) takes only \(O(n+\kappa )\) time instead of \(O(n\kappa )\) as in typical constructions. Previously, such signatures were only known to exist under an exponential hardness assumption. As an additional contribution, we obtain new locally computable hardness amplification procedures for UOWHFs that preserve linear shrinkage.     

Mixed RF/FSO bidirectional system achieving spectral efficiency

The performance of two-way relay (TWR)-assisted mixed radio-frequency/free-space optical (RF/FSO) system is evaluated in this letter. The proposed system employs decode-and-forward relaying phenomena where the relay is basically an interfacing node between two source nodes \(S_1\) and \(S_2\), where \(S_1\) supports RF signal, while \(S_2\) supports FSO signal. The TWR-assisted system helps in achieving spectral efficiency by managing bidirectional communication in three time slots, thus maximizing the achievable rate of the network. The RF link is subjected to generalized \(\eta -\mu \) distribution, and the optical channel is affected by path loss, pointing errors and gamma–gamma (gg) distributed atmospheric turbulence. The novel expressions for the probability density function and cumulative distribution function of the equivalent end-to-end signal-to-noise ratio (SNR) are derived. Capitalizing on these derived statistics of end-to-end SNR, the expressions of outage probability and the bit-error rate for different binary modulations and M-ary modulations are provided.     

A Dichotomy for Local Small-Bias Generators

We consider pseudorandom generators in which each output bit depends on a constant number of input bits. Such generators have appealingly simple structure: They can be described by a sparse input–output dependency graph \(G\) and a small predicate \(P\) that is applied at each output. Following the works of Cryan and Miltersen (MFCS’01) and by Mossel et al (STOC’03), we ask: which graphs and predicates yield “small-bias” generators (that fool linear distinguishers)? We identify an explicit class of degenerate predicates and prove the following. For most graphs, all non-degenerate predicates yield small-bias generators, \(f:\{0,1\}^n \rightarrow \{0,1\}^m\), with output length \(m = n^{1 + \epsilon }\) for some constant \(\epsilon > 0\). Conversely, we show that for most graphs, degenerate predicates are not secure against linear distinguishers, even when the output length is linear \(m=n+\Omega (n)\). Taken together, these results expose a dichotomy: Every predicate is either very hard or very easy, in the sense that it either yields a small-bias generator for almost all graphs or fails to do so for almost all graphs. As a secondary contribution, we attempt to support the view that small-bias is a good measure of pseudorandomness for local functions with large stretch. We do so by demonstrating that resilience to linear distinguishers implies resilience to a larger class of attacks.     

Fabrication of a <Emphasis Type="Italic">p</Emphasis>–<Emphasis Type="Italic">n</Emphasis> Heterojunction Using Topological Insulator Bi<Subscript>2</Subscript>Te<Subscript>3</Subscript>–Si and Its Annealing Response

A junction device has been fabricated by growing p-type Bi₂Te₃ topological insulator (TI) film on an n-type silicon (Si) substrate using a thermal evaporation technique. Annealing using different temperatures and durations was employed to improve the quality of the film, as confirmed by microstructural study using x-ray diffraction (XRD) analysis and atomic force microscopy (AFM). The p–n diode characteristics of the junction devices were studied, and the effect of annealing investigated. An improved diode characteristic with good rectification ratio (RR) was observed for devices annealed for longer duration. Reduction in the leakage or reverse saturation current (\( I_{\rm{R}} \)) was observed with increase in the annealing temperature. The forward-bias current (\( I_{\rm{F}} \)) dropped in devices annealed above 400°C. The best results were observed for the sample device annealed at 450°C for 3 h, showing figure of merit (FOM) of 0.621 with RR ≈ 504 and \( I_{\rm{R}} \) = 0.25 μA. In terms of ideality factor, the sample device annealed at 550°C for 2 h was found to be the best with \( n \) = 6.5, RR ≈ 52.4, \( I_{\rm{R}} \) = 0.61 μA, and FOM = 0.358. The majority-carrier density \( \left( {N_{\rm{A}} } \right) \) in the p-Bi₂Te₃ film of the heterojunction was found to be on the order of 10⁹/cm³ to 10¹¹/cm³, quite close to its intrinsic carrier concentration. These results are significant for fundamental understanding of device applications of TI materials as well as future applications in solar cells.     

Key Recovery Attacks on Iterated Even–Mansour Encryption Schemes

Iterated Even–Mansour (EM) encryption schemes (also named “key-alternating ciphers”) were extensively studied in recent years as an abstraction of commonly used block ciphers. A large amount of previous works on iterated EM concentrated on security in an information-theoretic model. A central question studied in these papers is: What is the minimal number of rounds for which the resulting cipher is indistinguishable from an ideal cipher? In this paper, we study a similar question in the computational model: What is the minimal number of rounds, assuring that no attack can recover the secret key faster than trivial attacks (such as exhaustive search)? We study this question for the two natural key scheduling variants that were considered in most previous papers: the identical subkeys variant and the independent subkeys variant. In the identical subkeys variant, we improve the best known attack by an additional round and show that \(r=3\) rounds are insufficient for assuring security, by devising a key recovery attack whose running time is about \(n/\log (n)\) times faster than exhaustive search for an \(n\)-bit key. In the independent subkeys variant, we also extend the known results by one round and show that for \(r=2\), there exists a key recovery attack whose running time is faster than the benchmark meet-in-the-middle attack. Despite their generic nature, we show that the attacks can be applied to improve the best known attacks on several concrete ciphers, including the full \({\hbox {AES}^{2}}\) (proposed at Eurocrypt 2012) and reduced-round LED-128 (proposed at CHES 2012).     

Secret-Sharing for NP

A computational secret-sharing scheme is a method that enables a dealer, that has a secret, to distribute this secret among a set of parties such that a “qualified” subset of parties can efficiently reconstruct the secret while any “unqualified” subset of parties cannot efficiently learn anything about the secret. The collection of “qualified” subsets is defined by a monotone Boolean function. It has been a major open problem to understand which (monotone) functions can be realized by a computational secret-sharing scheme. Yao suggested a method for secret-sharing for any function that has a polynomial-size monotone circuit (a class which is strictly smaller than the class of monotone functions in \({\mathsf {P}}\)). Around 1990 Rudich raised the possibility of obtaining secret-sharing for all monotone functions in \({\mathsf {NP}}\): in order to reconstruct the secret a set of parties must be “qualified” and provide a witness attesting to this fact. Recently, Garg et al. (Symposium on theory of computing conference, STOC, pp 467–476, 2013) put forward the concept of witness encryption, where the goal is to encrypt a message relative to a statement \(x\in L\) for a language \(L\in {\mathsf {NP}}\) such that anyone holding a witness to the statement can decrypt the message; however, if \(x\notin L\), then it is computationally hard to decrypt. Garg et al. showed how to construct several cryptographic primitives from witness encryption and gave a candidate construction. One can show that computational secret-sharing implies witness encryption for the same language. Our main result is the converse: we give a construction of a computational secret-sharing scheme for any monotone function in \({\mathsf {NP}}\) assuming witness encryption for \({\mathsf {NP}}\) and one-way functions. As a consequence we get a completeness theorem for secret-sharing: computational secret-sharing scheme for any single monotone \({\mathsf {NP}}\)-complete function implies a computational secret-sharing scheme for every monotone function in \({\mathsf {NP}}\).     

A novel optimized neutrosophic <Emphasis Type="Italic">k</Emphasis>-means using genetic algorithm for skin lesion detection in dermoscopy images

This paper implemented a new skin lesion detection method based on the genetic algorithm (GA) for optimizing the neutrosophic set (NS) operation to reduce the indeterminacy on the dermoscopy images. Then, k-means clustering is applied to segment the skin lesion regions. Therefore, the proposed method is called optimized neutrosophic k-means (ONKM). On the training images set, an initial value of \(\alpha \) in the \(\alpha \)-mean operation of the NS is used with the GA to determine the optimized \(\alpha \) value. The Jaccard index is used as the fitness function during the optimization process. The GA found the optimal \(\alpha \) in the \(\alpha \)-mean operation as \(\alpha _{\mathrm{optimal}} =0.0014\) in the NS, which achieved the best performance using five fold cross-validation. Afterward, the dermoscopy images are transformed into the neutrosophic domain via three memberships, namely true, indeterminate, and false, using \(\alpha _{\mathrm{optimal}}\). The proposed ONKM method is carried out to segment the dermoscopy images. Different random subsets of 50 images from the ISIC 2016 challenge dataset are used from the training dataset during the fivefold cross-validation to train the proposed system and determine \(\alpha _{\mathrm{optimal}}\). Several evaluation metrics, namely the Dice coefficient, specificity, sensitivity, and accuracy, are measured for performance evaluation of the test images using the proposed ONKM method with \(\alpha _{\mathrm{optimal}} =0.0014\) compared to the k-means, and the \(\gamma \)–k-means methods. The results depicted the dominance of the ONKM method with \(99.29\pm 1.61\%\) average accuracy compared with k-means and \(\gamma \)–k-means methods.