International Association
for Cryptologic Research

Non-malleable codes, introduced as a relaxation of error-correcting codes by Dziembowski, Pietrzak and Wichs (ICS \'10), provide the security guarantee that the message contained in a tampered codeword is either the same as the original message or is set to an unrelated value. Various applications of non-malleable codes have been discovered, and one of the most significant applications among these is the connection with tamper-resilient cryptography. There is a large body of work considering security against various classes of tampering functions, as well as non-malleable codes with enhanced features such as leakage resilience.

In this work, we propose combining the concepts of non-malleability, leakage resilience, and locality in a coding scheme. The contribution of this work is three-fold:

1. As a conceptual contribution, we define a new notion of locally decodable and updatable non-malleable code that combines the above properties.

2. We present two simple and efficient constructions achieving our new notion with different levels of security.

3. We present an important application of our new tool--securing RAM computation against memory tampering and leakage attacks. This is analogous to the usage of traditional non-malleable codes to secure implementations in the circuit model against memory tampering and leakage attacks.

Koblitz curves have been a nice subject of consideration for both theoretical and practical interests. The window $\\tau$-adic algorithm of Solinas (window $\\tau$NAF) is the most powerful method for computing point multiplication for Koblitz curves. Pre-computation plays an important role in improving the performance of point multiplication. In this paper, the concept of optimal pre-computation for window $\\tau$NAF is formulated. In this setting, an optimal pre-computation has some mathematically natural and clean forms, and requires $2^{w-2}-1$ point additions and two evaluations of the Frobenius map $\\tau$, where $w$ is the window width. One of the main results of this paper is to construct an optimal pre-computation scheme for each window width $w$ from $4$ to $15$ (more than practical needs). These pre-computations can be easily incorporated into implementations of window $\\tau$NAF. The ideas in the paper can also be used to construct other suitable pre-computations. This paper also includes a discussion of coefficient sets for window $\\tau$NAF and the divisibility by powers of $\\tau$ through different approaches.

Secure elements, such as smartcards or trusted platform modules (TPMs), must be protected against implementation-level attacks.

Those include side-channel and fault injection attacks.

We introduce ODSM, Orthogonal Direct Sum Masking, a new computation paradigm that achieves protection against those two kinds of attacks.

A large vector space is structured as two supplementary orthogonal subspaces.

One subspace (called a code $\\mathcal{C}$) is used for the functional computation,

while the second subspace carries random numbers.

As the random numbers are entangled with the sensitive data, ODSM ensures a protection against (monovariate) side-channel attacks.

The random numbers can be checked either occasionally, or globally, thereby ensuring a fine or coarse detection capability.

The security level can be formally detailed:

it is proved that monovariate side-channel attacks of order up to $d_\\mathcal{C}-1$, where $d_\\mathcal{C}$ is the minimal distance of $\\mathcal{C}$, are impossible,

and that any fault of Hamming weight strictly less than $d_\\mathcal{C}$ is detected.

A complete instantiation of ODSM is given for AES.

In this case, all monovariate side-channel attacks of order strictly less than $5$ are impossible,

and all fault injections perturbing strictly less than $5$ bits are detected.

Previously known functional encryption (FE) schemes for general circuits relied on indistinguishability obfuscation, which in turn either relies on an exponential number of assumptions (basically, one per circuit), or a polynomial set of assumptions, but with an exponential loss in the security reduction. Additionally these schemes are proved in an unrealistic selective security model, where the adversary is forced to specify its target before seeing the public parameters. For these constructions, full security can be obtained but at the cost of an exponential loss in the security reduction.

In this work, we overcome the above limitations and realize a fully secure functional encryption scheme without using indistinguishability obfuscation. Specifically the security of our scheme relies only on the polynomial hardness of simple assumptions on multilinear maps.

Protocols for secure two-party computation enable a pair of mistrusting parties to compute a joint function of their private inputs without revealing anything but the output. One of the fundamental techniques for obtaining secure computation is that of Yao\'s garbled circuits. In the setting of malicious adversaries, where the corrupted party can follow any arbitrary (polynomial-time) strategy in an attempt to breach security, the cut-and-choose technique is used to ensure that the garbled circuit is constructed correctly. The cost of this technique is the construction and transmission of multiple circuits; specifically, $s$ garbled circuits are used in order to obtain a maximum cheating probability of $2^{-s}$.

In this paper, we show how to reduce the amortized cost of cut-and-choose based secure two-party computation to ${\\cal O}\\(\\frac{s}{\\log N}\\)$ garbled circuits when $N$ secure computations are run. We use this method to construct a secure protocol in the batch setting. Next, we show how the cut-and-choose method on garbled circuits can be used in an online/offline setting in order to obtain a very fast online phase with very few exponentiations, and we apply our amortization method to this setting as well. Our online/offline protocols are competitive with the TinyOT and SPDZ protocols due to the minimal interaction in the online phase (previous protocols require only information-theoretic operations in the online phase and are therefore very efficient; however, they also require many rounds of communication which increases latency). Although ${\\cal O}(\\frac{s}{\\log N})$ may seem to be a mild efficiency improvement asymptotically, it is a \\emph{dramatic improvement} for concrete parameters since $s$ is a statistical security parameter and so is typically small. Specifically, instead of $40$ circuits to obtain an error of $2^{-40}$, when running $2^{10}$ executions we need only $7.06$ circuits on average per secure computation, and when running $2^{20}$ executions this is reduced to an average of just $4.08$. In addition, in the online/offline setting, the online phase per secure computation consists of evaluating only $6$ garbled circuits for $2^{10}$ executions and $4$ garbled circuits for $2^{20}$ executions (plus some small additional overhead). In practice, when using fast implementations (like the JustGarble framework of Bellare et al.), the resulting protocol is remarkably fast.

We present a number of variants of our protocols with different assumptions and efficiency levels. Our basic protocols rely on the DDH assumption alone, while our most efficient variants are proven secure in the random-oracle model. Interestingly, the variant in the random-oracle model of our protocol for the online/offline setting has online communication that is independent of the size of the circuit in use. None of the previous protocols in the online/offline setting achieves this property, which is very significant since communication is usually a dominant cost in practice.

In the setting of secure multiparty computation, a set of parties wish to compute a joint function of their private inputs. The computation should preserve security properties such as privacy, correctness, independence of inputs, fairness and guaranteed output delivery. In the case of no honest majority, fairness and guaranteed output delivery cannot always be obtained. Thus, protocols for secure multiparty computation are typically of two disparate types: protocols that assume an honest majority (and achieve all properties \\emph{including} fairness and guaranteed output delivery), and protocols that do not assume an honest majority (and achieve all properties \\emph{except for} fairness and guaranteed output delivery). In addition, in the two-party case, fairness and guaranteed output delivery are equivalent. As a result, the properties of fairness (which means that if corrupted parties receive output then so do the honest parties) and guaranteed output delivery (which means that corrupted parties cannot prevent the honest parties from receiving output in any case) have typically been considered to be the same.

In this paper, we initiate a study of the relation between fairness and guaranteed output delivery in secure multiparty computation. We show that in the multiparty setting these properties are distinct and proceed to study under what conditions fairness implies guaranteed output delivery (the opposite direction always holds). We also show the existence of non-trivial functions for which complete fairness is achievable (without an honest majority) but guaranteed output delivery is not, and the existence of non-trivial functions for which complete fairness and guaranteed output delivery are achievable. Our study sheds light on the role of broadcast in fairness and guaranteed output delivery, and shows that these properties should sometimes be considered separately.

We study the communication complexity of secure function evaluation (SFE). Consider a setting where Alice has a short input $x_A$, Bob has an input $x_B$ and we want Bob to learn some function $y = f(x_A, x_B)$ with large output size. For example, Alice has a small secret decryption key, Bob has a large encrypted database and we want Bob to learn the decrypted data without learning anything else about Alice\'s key. In a trivial insecure protocol, Alice can just send her short input $x_A$ to Bob. However, all known SFE protocols have communication complexity that scales with size of the output $y$, which can potentially be much larger. Is such ``output-size dependence\'\' inherent in SFE?

Surprisingly, we show that output-size dependence can be avoided in the \\emph{honest-but-curious} setting. In particular, using indistinguishability obfuscation (iO) and fully homomorphic encryption (FHE), we construct the first honest-but-curious SFE protocol whose communication complexity only scales with that of the best insecure protocol for evaluating the desired function, independent of the output size. Our construction relies on a novel way of using iO via a new tool that we call a ``somewhere statistically binding (SSB) hash\'\', and which may be of independent interest.

On the negative side, we show that output-size dependence is inherent in the \\emph{fully malicious} setting, or even already in an \\emph{honest-but-deterministic} setting, where the corrupted party follows the protocol as specified but fixes its random tape to some deterministic value. Moreover, we show that even in an offline/online protocol, the communication of the online phase must have output-size dependence. This negative result uses an incompressibility argument and it generalizes several recent lower bounds for functional encryption and (reusable) garbled circuits, which follow as simple corollaries of our general theorem.

An encryption relation $f \\subseteq {\\mathbb Z} \\times {\\mathbb Z}$ with decryption function $f^{-1}$ is {\\it ``group-homomorphic\'\'} if, for any suitable plaintexts $x_1$ and $x_2$, $\\, x_1+x_2 = f^{-1} ( f(x_1) + f(x_2) )$. It is {\\it ``ring-homomorphic\'\'} if furthermore $x_1 x_2 = f^{-1} ( f(x_1) f(x_2) )$; it is {\\it ``field-homomorphic\'\'} if furthermore $1/x_1 = f^{-1} ( f(1/x_1) )$. Such relations would support oblivious processing of encrypted data.

We propose a simple randomized encryption relation~$f$ over the integers, called\\linebreak {\\it \\mbox{DoubleMod}}, which is ``bounded ring-homomorphic\'\' or what some call \"somewhat homomorphic.\" Here, ``bounded\'\' means that the number of additions and multiplications that can be performed, while not allowing the encrypted values to go out of range, is limited~(any pre-specified bound on the operation-count can be accommodated). Let $R$ be any large integer. For any plaintext $x \\in {\\mathbb Z}_R$, DoubleMod encrypts $x$ as $f(x) = x + au + bv$, where $a$ and $b$ are randomly chosen integers in some appropriate interval, while $(u,v)$ is the secret key. Here $u>R^2$ is a large prime and the smallest prime factor of $v$ exceeds $u$. With knowledge of the key, but not of $a$ and $b$, the receiver decrypts the ciphertext by computing $f^{-1}(y) =(y \\bmod v) \\bmod u$.

DoubleMod generalizes an independent idea of van Dijk {\\it et al.} 2010. We present and refine a new CCA1 chosen-ciphertext attack that finds the secret key of both systems (ours and van Dijk {\\it et al.}\'s) in linear time in the bit length of the security parameter. Under a known-plaintext attack, breaking DoubleMod is at most as hard as solving the {\\it Approximate GCD (AGCD)} problem. The complexity of AGCD is not known.

We also introduce the \\mbox{{\\it SingleMod}} {field}-homomorphic cryptosystems. The simplest\\linebreak \\mbox{SingleMod} system based on the integers can be broken trivially. We had hoped, that if SingleMod is implemented inside non-Euclidean quadratic or higher-order fields with large discriminants, where GCD computations appear difficult, it may be feasible to achieve a desired level of security. We show, however, that a variation of our chosen-ciphertext attack works against SingleMod even in non-Euclidean fields.

CloudFlare is looking for a talented cryptography engineer to join our team. We are working on a number of ambitious projects to secure the web and protect our customers from threats of all sorts. At CloudFlare we deal with cryptography at scale, and tackle projects that shape the future of the Web.

The role of cryptography engineer at CloudFlare is more that of a builder than a breaker. You will have to approach problems with creativity and flexibility and be able to identify and use the best tools for the job or build better ones from scratch. At CloudFlare, we are serious about protecting our customers and advancing the state of the art in computer security.

Requirements:

Expertise in theory and implementation of white-box cryptography

Experience building code obfuscation tools

Experience writing cryptographic libraries and APIs

Experience implementing production-grade cryptographic algorithms

Expert in C/C++/Go and performance analysis

Familiarity with compilers or code generation tools

Bonus Points:

Contributions to the open source community

Experience with cryptographic hardware (TPM, HSM, etc.)

Healthy sense of paranoia

From September 18 to September 19
Location: Amsterdam, The Netherlands
More Information: https://www.cwi.nl/crypto/TOC2014/

Provably secure e-voting

We are looking for one postdoctoral researcher to join the ProSecure project at Loria, Nancy, in the Cassis team, for 1 or 2 years.

Context

One important family of protocols is e-voting. Electronic voting protocols should offer the same guarantees than more traditional voting systems. In particular, they should offer both vote privacy and verifiability : anyone should be able to check that the result corresponds to the votes. Surprisingly, even defining a crucial property such as vote privacy has not yet reached a consensus in the scientific community. Moreover, existing voting systems should still be improved in terms of verifiability, coercion-resistance, or usability. To achieve a high level of trust, these systems should be proved secure rigorously.

Objectives

One objective is to propose well-founded definitions of crucial properties in e- voting such as privacy, receipt-freeness, coercion-resistance, and verifiability and apply them on various e-voting protocols including well-known schemes such as Helios or Civitas. In particular, our team is developing a variant of Helios named Belenios. This scheme has been proved to be ballot private and fully verifiable. More security properties are yet to be proved and several enhancement of the protocol are planned. Belenios benefits from the support of an engineer that develops and maintains it.

The post-doc researcher is expected to contribute autonomously to the development of new results for defining and proving cryptographic security properties and for designing a both practical and secure voting scheme. The postdoc researcher should have a good publication record and a strong expertise in cryptography.

The combination of software-as-a-service and the increasing use of mobile devices gives rise to a considerable difference in computational power between servers and clients. Thus, there is a desire for clients to outsource the evaluation of complex functions to an external server. Servers providing such a service may be rewarded per computation, and as such have an incentive to cheat by returning garbage rather than devoting resources and time to compute a valid result.

In this work, we introduce the notion of Revocable Publicly Verifiable Computation (RPVC), where a cheating server is revoked and may not perform future computations (thus incurring a financial penalty). We introduce a Key Distribution Center (KDC) to efficiently handle the generation and distribution of the keys required to support RPVC. The KDC is an authority over entities in the system and enables revocation. We also introduce a notion of blind verification such that results are verifiable (and hence servers can be rewarded or punished) without learning the value.

We present a rigorous definitional framework, define a number of new security models and present a construction of such a scheme built upon Key-Policy Attribute-based Encryption.

In this short paper, we propose a variant of the Number Field Sieve to compute discrete logarithms in medium characteristic finite fields.

We propose an algorithm that combines two recent ideas, namely the Multiple variant of the Number Field Sieve taking advantage of a large number of number fields in the sieving phase and the Conjugation Method giving a new polynomial selection for the classical Number Field Sieve. The asymptotic complexity of our improved algorithm is L_Q (1/3, (8 (9+4 \\sqrt{6})/15)^1/3), where F_Q is the target finite field and (8 (9+4 \\sqrt{6})/15)^1/3) is approximately equal to 2.156. This has to be compared with the complexity of the previous state-of-the-art algorithm for medium characteristic finite fields, the Number Field Sieve with Conjugation Method, that has a complexity of approximately L_Q(1/3, 2.201).

The $r$-rounds Even-Mansour block cipher uses $r$ public permutations of $\\{0, 1\\}^n$ and $r+1$ secret keys. An attack on this construction was described in \\cite{DDKS}, for $r = 2, 3$. Although this attack is only marginally better than brute force, it is based on an interesting observation (due to \\cite{NWW}): for a \"typical\" permutation $P$, the distribution of $P(x) \\oplus x$ is not uniform.

To address this, and other potential threats that might stem from this observation in this (or other) context, we introduce the notion of a ``balanced permutation\'\' for which the distribution of $P(x) \\oplus x$ is uniform, and show how to generate families of balanced permutations from the Feistel construction.

This allows us to define a $2n$-bit block cipher from the $2$-rounds Even-Mansour scheme. The cipher uses public balanced permutations of $\\{0, 1\\}^{2n}$, which are based on two public permutations of $\\{0, 1\\}^{n}$.

By construction, this cipher is immune against attacks that rely on the non-uniform behavior of $P(x) \\oplus x$. We prove that this cipher is indistinguishable from a random permutation of $\\{0, 1\\}^{2n}$,

for any adversary who has oracle access to the public permutations and to an encryption/decryption oracle, as long as the number of queries is $o (2^{n/2})$. As a practical example, we discuss the properties and the performance of a $256$-bit block cipher that is based on AES.

In 2013, Althobaiti et al. proposed an efficient biometric-based user authentication scheme for wireless sensor networks. We analyze their scheme for the security against known attacks. Though their scheme is efficient in computation, in this paper we show that their scheme has some security pitfalls such as (1) it is not resilient against node capture attack, (2) it is insecure against impersonation attack and (3) it is insecure against man-in-the-middle attack. Finally, we give some pointers for improving their scheme so that the designed scheme needs to be secure against various known attacks.

Over a decade, cryptographers are more attentive on designing lightweight ciphers in focus to compact cryptographic devices. More often, the security of these algorithms are defined in terms of its resistance to mathematical cryptanalysis methods. Nevertheless, designers are well aware of implementation attacks and concentrating on new design strategies to improve the defence quality against implementation attack. \\texttt{PRINCE}~\\cite{Julia2012} and \\texttt{RECTANGLE}~\\cite{cryptoeprint:2014:084} lightweight block ciphers are designed using new design strategies for efficiency and security. In this paper we analyse the security of \\texttt{PRINCE} and \\texttt{RECTANGLE} against a type of implementation attack called Differential Power Analysis (DPA) attack. Our attack reduces key search space from $2^{128}$ to $33008$ for \\texttt{PRINCE} and $2^{80}$ to $288$ for \\texttt{RECTANGLE}. To the best of our knowledge, this is the first DPA attack on \\texttt{PRINCE} and \\texttt{RECTANGLE}.

Graded multilinear encodings have found extensive applications in cryptography ranging from

non-interactive key exchange protocols, to broadcast and attribute-based encryption, and even to software obfuscation.

Despite seemingly unlimited applicability, essentially only two candidate constructions are known (GGH and CLT). In this work, we describe a new graded multilinear encoding scheme from lattices.

Our construction encodes Learning With Errors (LWE) samples

in short square matrices of higher dimensions. Addition and multiplication of the encodings corresponds naturally to addition and multiplication

of the LWE secrets. Comparisons of any two encodings

can be performed publicly at any level.

The security of our scheme relies on a hardness of a natural problem which can be thought of as analogous to standard LWE problem.

Polynomial multiplication is the basic and most computationally intensive operation in ring-Learning With Errors (ring-LWE) encryption and ``Somewhat\" Homomorphic Encryption (SHE) cryptosystems. In this paper, the Fast Fourier Transform (FFT) with a linearithmic complexity of $O(n\\log n)$, is exploited in the design of a high-speed polynomial multiplier. A constant geometry FFT datapath is used in the computation to simplify the control of the architecture. The contribution of this work is three-fold. First, parameter sets which support both an efficient modular reduction design and the security requirements for ring-LWE encryption and SHE are provided. Second, a versatile pipelined architecture accompanied with an improved dataflow are proposed to obtain a high-speed polynomial multiplier. Third, the proposed architecture supports polynomial multiplications for different lengths $n$ and moduli $p$. The experimental results on a Spartan-6 FPGA show that the proposed design results in a speedup of 3.5 times on average when compared with the state of the art. It performs a polynomial multiplication in the ring-LWE scheme ($n = 256, p = 1049089$) and the SHE scheme ($n = 1024, p = 536903681$) in only 6.3$\\mu$s and 33.1$\\mu$s, respectively.

This paper analyzes group communication within the universally

composable framework. We first propose the group communication

model, identity-based signcrytion model and group key distribution model in the UC framework by

designing the ideal functionality $\\mathcal {F}_{SAGCOM}$, $\\mathcal

{F}_{IDSC}$ and $\\mathcal {F}_{GKD}$, respectively. Then, we construct

a UC secure identity-based signcryption protocol $\\pi_{IDSC}$. Moreover,

we shows that the identity-based signcryption $\\pi_{IDSC}$ securely realizes the ideal functionality $\\mathcal {F}_{IDSC}$ if

and only if the corresponding protocol IDSC is secure. Finally, based on the identity-based protocol, we propose a group communication scheme

$\\pi_{SAGCOM}$, which can securely realizes the ideal functionality

$\\mathcal {F}_{SAGCOM}$ in the $(\\mathcal {F}_{IDSC},\\mathcal

{F}_{GKD})$-hybrid model.

Differentially 4-uniform permutations on $\\gf_{2^{2k}}$ with high nonlinearity are often chosen as Substitution boxes in block ciphers. Recently, Qu et al. used the powerful switching method to construct such permutations from the inverse function [9],[10]. More precisely, they studied the functions of the form G(x)=1/x+f(1/x),

where f is a Boolean function. They proved that if f is a preferred Boolean function (PBF), then G is a permutation polynomial over $\\gf_{2^n}$ whose differential uniformity is at most 4. However, as pointed out in [9],f is a PBF is a sufficient but not necessary condition. In this paper, a sufficient and necessary condition for G to be a differentially 4-uniform permutation is presented. We also show that G can not be an almost perfect nonlinear (APN) function. As an application, a new class of differentially 4-uniform permutations where f are not PBFs are constructed. By comparing this family with previous constructions, the number of permutations here is much bigger. The obtained functions in this paper may provide more choices for the design of Substitution boxes.