*22:17* [Pub][ePrint]
Constructing Confidential Channels from Authenticated Channels---Public-Key Encryption Revisited, by Sandro Coretti and Ueli Maurer and Björn Tackmann
The security of public-key encryption (PKE), a widely-used cryptographic primitive, has received much attention in the cryptographic literature. Many security notions for PKE have been proposed, including several versions of CPA-security, CCA-security, and non-malleability. These security notions are usually defined in terms of a certain game that an efficient adversary cannot win with non-negligible probability or advantage.If a PKE scheme is used in a larger protocol, then the security of this protocol is proved by showing a reduction of breaking a certain security property of the PKE scheme to breaking the security of the protocol. A major problem is that each protocol requires in principle its own tailor-made security reduction. Moreover, which security notion of the PKE should be used in a given context is a priori not evident; the employed games model the use of the scheme abstractly through oracle access to its algorithms, and the sufficiency for specific applications is neither explicitly stated nor proven.

In this paper we propose a new approach to investigating the application of PKE, following the constructive cryptography paradigm of Maurer and Renner (ICS~2011). The basic use of PKE is to enable confidential communication from a sender A to a receiver B, assuming A is in possession of B\'s public key. One can distinguish two relevant cases: The (non-confidential) communication channel from A to B can be authenticated (e.g., because messages are signed) or non-authenticated. The application of PKE is shown to provide the construction of a secure channel from A to B from two (assumed) authenticated channels, one in each direction, or, alternatively, if the channel from A to B is completely insecure, the construction of a confidential channel without authenticity. Composition then means that the assumed channels can either be physically realized or can themselves be constructed cryptographically, and also that the resulting channels can directly be used in any applications that require such a channel. The composition theorem shows that several construction steps can be composed, which guarantees the soundness of this approach and eliminates the need for separate reduction proofs.

We also revisit several popular game-based security notions (and variants thereof) and give them a constructive semantics by demonstrating which type of construction is achieved by a PKE scheme satisfying which notion. In particular, the necessary and sufficient security notions for the above two constructions to work are CPA-security and a variant of CCA-security, respectively.

*19:17* [Pub][ePrint]
Limits of Extractability Assumptions with Distributional Auxiliary Input, by Elette Boyle and Rafael Pass
Extractability, or \"knowledge,\" assumptions (such as the \"knowledge-of-exponent\" assumption) have recently gained popularity in the cryptographic community--leading to the study of primitives such as extractable one-way functions, extractable hash functions, succinct non- interactive arguments of knowledge (SNARKs), and extractable obfuscation, and spurring the development of a wide spectrum of new applications relying on these primitives. For most of these applications, it is required that the extractability assumption holds even in the presence of attackers receiving some auxiliary information that is sampled from some fixed efficiently computable distribution Z.We show that, assuming the existence of collision-resistant hash functions, there exists a pair of efficient distributions Z, Z\'; such that either:

o extractable one-way functions w.r.t. Z do not exist, or

o extractability obfuscations for Turing machines w.r.t. Z do not exist.

A corollary of this result shows that assuming existence of fully homomorphic encryption with decryption in NC1, there exist efficient distributions Z, Z\' such that either

o extractability obfuscations for NC1 w.r.t. Z do not exist, or

o SNARKs for NP w.r.t. Z\' do not exist.

To achieve our results, we develop a \"succinct punctured program\" technique, mirroring the powerful \"punctured program\" technique of Sahai and Waters (ePrint\'13), and present several other applications of this new technique.

*19:17* [Pub][ePrint]
Symmetric Digit Sets for Elliptic Curve Scalar Multiplication without Precomputation, by Clemens Heuberger and Michela Mazzoli
We describe a method to perform scalar multiplication on two classes ofordinary elliptic curves, namely $E: y^2 = x^3 + Ax$ in prime characteristic

$p\\equiv 1$ mod~4, and $E: y^2 = x^3 + B$ in prime characteristic $p\\equiv 1$

mod 3. On these curves, the 4-th and 6-th roots of unity act as (computationally

efficient) endomorphisms. In order to optimise the scalar multiplication, we consider a width-$w$-NAF (non-adjacent form) digit expansion of positive integers to the complex base of $\\tau$, where $\\tau$ is a zero of the characteristic polynomial $x^2 - tx + p$ of the Frobenius endomorphism associated to the curve. We provide a precomputationless algorithm by means of a convenient factorisation of the unit group of residue classes modulo $\\tau$ in the endomorphism ring, whereby we construct a digit set consisting of powers of subgroup generators, which are chosen as efficient endomorphisms of the curve.

*19:17* [Pub][ePrint]
A reduction of semigroup DLP to classic DLP, by Matan Banin and Boaz Tsaban
We present a polynomial-time reduction of the discrete logarithm problem in any periodic (a.k.a. torsion)semigroup (SGDLP) to the same problem in a subgroup of the same semigroup.

It follows that SGDLP can be solved in polynomial time by quantum computers, and that

SGDLP has subexponential algorithms whenever the classic DLP in the corresponding groups has subexponential algorithms.

*19:17* [Pub][ePrint]
Key Derivation Without Entropy Waste, by Yevgeniy Dodis and Krzysztof Pietrzak and Daniel Wichs
We revisit the classical problem of converting an imperfect source of randomness into a usable cryptographic key. Assume that we have some cryptographic application $P$ that expects a uniformly random $m$-bit key $R$ and ensures that the best attack (in some complexity class) against $P(R)$ has success probability at most $\\delta$. Our goal is to design a key-derivation function (KDF) $h$ that converts any random source $X$ of min-entropy $k$ into a sufficiently ``good\'\' key $h(X)$,guaranteeing that $P(h(X))$ has comparable security $\\delta\'$ which is `close\' to $\\delta$.

Seeded randomness extractors provide a generic way to solve this problem for \\emph{all} applications $P$, with resulting security $\\delta\' = O(\\delta)$, provided that we start with entropy $k\\ge m+2\\logdel-O(1)$. By a result of Radhakrishnan and Ta-Shma, this bound on $k$ (called the ``RT-bound\'\') is also known to be tight in general. Unfortunately, in many situations the loss of $2\\logdel$ bits of entropy is unacceptable. This motivates the study KDFs with less entropy waste by placing some restrictions on the source $X$ or the application $P$.

In this work we obtain the following new positive and negative results in this regard:

- Efficient samplability of the source $X$ does not help beat the RT-bound for general applications. This resolves the SRT (samplable RT) conjecture of Dachman-Soled et al.~\\cite{DGKM12} in the affirmative, and also shows that the existence of computationally-secure extractors beating the RT-bound implies the existence of one-way functions.

- We continue in the line of work initiated by Barak et al. \\cite{BDK+11} and construct new information-theoretic KDFs which beat the RT-bound for large but restricted classes of applications. Specifically, we design efficient KDFs that work for all unpredictability applications $P$ (e.g., signatures, MACs, one-way functions, etc.) and can either: (1) extract \\emph{all} of the entropy $k = m$ with a very modest security loss $\\delta\'=O(\\delta\\cdot \\log (1/\\delta))$, or alternatively, (2) achieve essentially optimal security $\\delta\' = O(\\delta)$ with a very modest entropy loss $k \\ge m+\\log\\log(1/\\delta)$. In comparison, the best prior results from \\cite{BDK+11} for this class of applications would only guarantee $\\delta\'=O(\\sqrt{\\delta})$ when $k=m$, and would need $k\\ge m+\\logdel$ to get $\\delta\'=O(\\delta)$.

- The weaker bounds of \\cite{BDK+11} hold for a larger class of so-called ``square-friendly\'\' applications (which includes all unpredictability, but also some important indistinguishability, applications). Unfortunately, we show that these weaker bounds are tight for the larger class of applications.

- We abstract out a clean, information-theoretic notion of $(k,\\delta,\\delta\')$-unpredictability extractors, which guarantee ``induced\'\' security $\\delta\'$ for any $\\delta$-secure unpredictability application $P$, and characterize the parameters achievable for such unpredictability extractors. Of independent interest, we also relate this notion to the previously-known notion of (min-entropy) condensers, and improve the state-of-the-art parameters for such condensers.

*19:17* [Pub][ePrint]
An Approach to Reduce Storage for Homomorphic Computations, by Jung Hee Cheon and Jinsu Kim
We introduce a hybrid homomorphic encryption by combining public key encryption (PKE) and somewhat homomorphic encryption (SHE) to reduce storage for most applications of somewhat or fully homomorphic encryption (FHE). In this model, one encrypts messages with a PKE and computes on encrypted data using a SHE or a FHE after homomorphic decryption. To obtain efficient homomorphic decryption, our hybrid schemes is constructed by combining IND-CPA PKE schemes without complicated message paddings with SHE schemes with large integer message space. Furthermore, we remark that if the underlying PKE is multiplicative on a domain closed under addition and multiplication, this scheme has an important advantage that one can evaluate a polynomial of arbitrary degree without recryption.

We propose such a scheme by concatenating ElGamal and Goldwasser-Micali scheme over a ring $\\Z_N$ for a composite integer $N$ whose message space is $\\Z_N^\\times$.

To be used in practical applications, homomorphic decryption of the base PKE is too expensive. We accelerate the homomorphic evaluation of the decryption by introducing a method to reduce the degree of exponentiation circuit at the cost of additional public keys. Using same technique, we give an efficient solution to the open problem~\\cite{KLYC13} partially.

As an independent interest, we obtain another generic conversion method from private key SHE to public key SHE. Differently from Rothblum~\\cite{RothTCC11}, it is free to choose the message space of SHE.