Better Security for Deterministic Public-Key Encryption: The Auxiliary-Input Setting

Deterministic public-key encryption, introduced by Bellare, Boldyreva, and O’Neill (CRYPTO ’07), provides an alternative to randomized public-key encryption in various scenarios where the latter exhibits inherent drawbacks. A deterministic encryption algorithm, however, cannot satisfy any meaningful notion of security when the plaintext is distributed over a small set. Bellare et al. addressed this difficulty by requiring semantic security to hold only when the plaintext has high min-entropy from the adversary’s point of view. In many applications, however, an adversary may obtain auxiliary information that is related to the plaintext. Specifically, when deterministic encryption is used as a building block of a larger system, it is rather likely that plaintexts do not have high min-entropy from the adversary’s point of view. In such cases, the framework of Bellare et al. might fall short from providing robust security guarantees. We formalize a framework for studying the security of deterministic public-key encryption schemes with respect to auxiliary inputs. Given the trivial requirement that the plaintext should not be efficiently recoverable from the auxiliary input, we focus on hard-to-invert auxiliary inputs. Within this framework, we propose two schemes: the first is based on the d-linear assumption for any d≥1 (including, in particular, the decisional Diffie–Hellman assumption), and the second is based on a rather general class of subgroup indistinguishability assumptions (including, in particular, the quadratic residuosity assumption and Paillier’s composite residuosity assumption). Our schemes are secure with respect to any auxiliary input that is subexponentially hard to invert (assuming the standard hardness of the underlying computational assumptions). In addition, our first scheme is secure even in the multi-user setting where related plaintexts may be encrypted under multiple public keys. Constructing a scheme that is secure in the multi-user setting (even without considering auxiliary inputs) was identified by Bellare et al. as an important open problem.     

Jitter-approximation tradeoff for periodic scheduling

We consider an asymmetric wireless communication setting, where a server periodically broadcasts data items to different mobile clients. The goal is to serve items into a prescribed rate, while minimizing the energy consumption of the mobile users. Abstractly, we are presented with a set of jobs, each with a known execution time and a requested period, and the task is to design a schedule for these jobs over a single shared resource without preemption. Given any solution schedule, its period approximation is the maximal factor by which the average period of a job in the schedule is blown up w.r.t. its requested period, and the jitter is roughly the maximal variability of times between two consecutive occurrences of the same job. Schedules with low jitter allow the mobile devices to save power by having their receivers switched off longer. In this paper we consider a scenario where clients may be willing to settle for non-optimal period approximation so that the jitter is improved. We present a parametric jitter-approximation tradeoff algorithm that allows us to choose various combinations between jitter optimality and period optimality for any given set of jobs. Zvika Brakerski was born in 1981. He received a masters’ degree from Tel-Aviv University in 2002 and is currently employed as an Electric Engineer. Boaz Patt-Shamir received his PhD from MIT in 1995. He was an assistant professor in Northeastern University until 1997, and then he joined the Dept. of Electrical Engineering in Tel Aviv University, where he directs the Computer Communication and Multimedia Laboratory. He held visiting positions at MIT, Boston University, Bellcore, and HP Labs.     

Obfuscating Conjunctions

We show how to securely obfuscate the class of conjunction functions (functions like \(f(x_1, \ldots , x_n) = x_1 \wedge \lnot x_4 \wedge \lnot x_6 \wedge \cdots \wedge x_{n-2}\)). Given any function in the class, we produce an obfuscated program which preserves the input–output functionality of the given function, but reveals nothing else. Our construction is based on multilinear maps, and can be instantiated using the recent candidates proposed by Garg, Gentry and Halevi (EUROCRYPT 2013) and by Coron et al. (CRYPTO 2013). We show that the construction is secure when the conjunction is drawn from a distribution, under mild conditions on the distribution. Security follows from multilinear entropic variants of the Diffie–Hellman assumption. We conjecture that our construction is secure for any conjunction, regardless of the distribution from which it is drawn. We offer supporting evidence for this conjecture, proving that our obfuscator is secure for any conjunction against generic adversaries.     

Distributed discovery of large near-cliques

Given an undirected graph and 0 ￡ e ￡ 1{0\le\epsilon\le1}, a set of nodes is called an e{\epsilon}-near clique if all but an e{\epsilon} fraction of the pairs of nodes in the set have a link between them. In this paper we present a fast synchronous network algorithm that uses small messages and finds a near-clique. Specifically, we present a constant-time algorithm that finds, with constant probability of success, a linear size e{\epsilon}-near clique if there exists an e³{\epsilon^3}-near clique of linear size in the graph. The algorithm uses messages of O(log n) bits. The failure probability can be reduced to n ^−Ω(1) by increasing the time complexity by a logarithmic factor, and the algorithm also works if the graph contains a clique of size Ω(n/(log log n) ^α ) for some a ? (0,1){\alpha \in (0,1)}. Our approach is based on a new idea of adapting property testing algorithms to the distributed setting.     

Analysis of ion diffusion and charging in electronically conducting polydicarbazole films by impedance methods

An electrochemical impedance analysis of the doping kinetics of polydicarbazole films is reported. Polymer films of varying thickness were analyzed using an impedance model that considers spatially-restricted diffusion of ionic species. The main bulk parameters for diffusion and charge accumulation during doping were determined from fits. These parameters resulted independent of film thickness after considering the experimental error. The equilibrium (bulk) capacitance C₀ varies in the range of 100-800 F cm⁻³. The chemical diffusion coefficient D varies within the range of 10⁻¹⁰ to 10⁻⁸ cm² s⁻¹ and increases as the steady-state potential reaches the oxidation peak potential.     

Multi-input Functional Encryption in the Private-Key Setting: Stronger Security from Weaker Assumptions

We construct a general-purpose multi-input functional encryption scheme in the private-key setting. Namely, we construct a scheme where a functional key corresponding to a function f enables a user holding encryptions of \(x_1, \ldots , x_t\) to compute \(f(x_1, \ldots , x_t)\) but nothing else. This is achieved starting from any general-purpose private-key single-input scheme (without any additional assumptions) and is proven to be adaptively secure for any constant number of inputs t. Moreover, it can be extended to a super-constant number of inputs assuming that the underlying single-input scheme is sub-exponentially secure. Instantiating our construction with existing single-input schemes, we obtain multi-input schemes that are based on a variety of assumptions (such as indistinguishability obfuscation, multilinear maps, learning with errors, and even one-way functions), offering various trade-offs between security assumptions and functionality. Previous and concurrent constructions of multi-input functional encryption schemes either rely on stronger assumptions and provided weaker security guarantees (Goldwasser et al. in Advances in cryptology—EUROCRYPT, 2014; Ananth and Jain in Advances in cryptology—CRYPTO, 2015), or relied on multilinear maps and could be proven secure only in an idealized generic model (Boneh et al. in Advances in cryptology—EUROCRYPT, 2015). In comparison, we present a general transformation that simultaneously relies on weaker assumptions and guarantees stronger security.     

Using monte carlo simulation for accurate critical dimension metrology of super small isolated poly‐lines

With the reduction of critical dimensions (CD) of physical gate lines, standard methods for evaluating bottom CD from the scanning electron microscope (SEM) signal become inaccurate. The two peaks, originating from the line edges, merge into a single peak, and the correct position of the topographical top and bottom points is not clear. A general Monte Carlo simulation program, developed to model SEM signals, was used to analyze the signals emerging from ultra small silicon lines. By correlating the simulated signals with the features, we deduced the location of the top and bottom points. This analysis was done for lines with various CDs, sidewall angles, and corner rounding, as well as for different spot sizes. This work shows the feasibility of using SEM for measuring ultranarrow features and supply data for algorithm development.     

The effect of ion-polymer binding on ionic diffusion in dicarbazole-based conducting polymers

An electrochemical polymerization and characterization is reported on a series of eight dicarbazole-type conducting polymers with different attached functional groups. The influence of the electronic character of the subgroup on the ionic conductivity properties of the polymers was examined. Impedance spectroscopy measurements were used to set the ionic chemical diffusion coefficients, D, in the polymer matrix at a variety of doping levels, for each of the polydicarbazoles. We relate D dependency with potential to morphological and electronic processes in the polymer occurring during oxidation. By combination of cyclic voltammetry and impedance spectroscopy for part of the series we reveal that the diffusion of ions in the matrix is easier in polymers were the functional group is highly electron-attracting.     

Star-shaped dendritic molecules based on carboxylated carbazole and pyrrole as peripheral oxidizable units

The synthesis and spectroscopic characterization of three tricarboxylated pyrrole (Pyr)- and carbazole (Cbz)-containing star-shaped dendritic molecules 1–3 have been described here. Clauson–Kaas, amide coupling and debenzylation reactions have been used as key chemical tools. Electropolymerization of these oxidizable molecules has been investigated. The carboxylated Cbz-based molecules upon oxidative electropolymerization produced stable electroactive polyCOOH polyCbz films.