International Association
for Cryptologic Research

Many information theoretically secure protocols are known for general secure multi-party computation, both in the honest majority setting, and in the dishonest majority setting with preprocessing. All known protocols that are efficient in the circuit size of the evaluated function follow the same typical ``gate-by-gate\'\' design pattern: we work our way through a boolean or arithmetic circuit, maintaining as an invariant that after we process a gate, the output of the gate is represented as a random secret sharing among the players. Finally, all shares for the outputs are revealed. This approach usually allows non-interactive processing of addition gates but requires communication for every multiplication gate.

This means that while information theoretically secure protocols are very efficient in terms of computational work, they (seem to) require more communication and more rounds than computationally secure protocols. Whether this is inherent is an open and probably very hard problem. However, in this work we show that it is indeed inherent for protocols that follow the ``gate by gate\'\' design pattern. In particular, we present the following results:

- In the honest majority setting, any gate-by-gate protocol must communicate for every multiplication gate, even if only semi-honest security is required.

- For dishonest majority with preprocessing, a different proof technique is needed. We again show that any gate-by-gate protocol must communicate for every multiplication gate when the underlying secret sharing scheme is the additive one. We obtain similar results for arbitrary secret sharing schemes.

- In the honest majority setting, we also show that amortising over several multiplication gates can at best save an O(n) factor on the computational work.

All our lower bounds are met up to a constant factor by known protocols that follow the typical gate-by-gate paradigm.

Our results imply that a fundamentally new approach must be found in order to improve the communication complexity of known protocols that are efficient in the circuit size of the function, such as GMW, SPDZ etc.

Abstract. This article introduces a method of hiding transaction amounts in the strongly decentralized anonymous cryptocurrency Monero. Similar to Bitcoin, Monero is cryptocurrency which is distributed through a proof of work \"mining\" process. The original Monero protocol was based on CryptoNote, which uses Ring Signatures and one-time keys to hide the destination and origin of transactions. Recently the technique of using a commitment scheme to hide the amount of a transaction has been discussed and implemented by Bitcoin Core Developer Gregory Maxwell. In this article, a new type of ring signature, A Multi-layed Linkable Spontaneous ad-hoc group signature is described which allows for hidden amounts, origins and destinations of transactions with reasonable efficiency. The previous draft of this article has been publicized in the Monero Community for a couple of months now and the new content here are some slightly updated proofs- see [Snoe] for earlier blockchain timestamped drafts. A longer expository version will follow.

We study the cryptographic complexity of two-party differentially-private protocols for a large natural class of boolean functionalities. Information theoretically, McGregor et al. [FOCS 2010] and Goyal et al. [Crypto 2013] demonstrated several functionalities for which the maximal possible accuracy in the distributed setting is significantly lower than that in the client-server setting. Goyal et al. [Crypto 2013] further showed that ``highly accurate\'\' protocols in the distributed setting for any non-trivial functionality in fact imply the existence of one-way functions. However, it has remained an open problem to characterize the exact cryptographic complexity of this class. In particular, we know that semi-honest oblivious transfer helps obtain optimally accurate distributed differential privacy. But we do not know whether the reverse is true.

We study the following question: Does the existence of optimally accurate distributed differentially private protocols for any class of functionalities imply the existence of oblivious transfer? We resolve this question in the affirmative for the class of boolean functionalities that contain an XOR embedded on adjacent inputs.

- We construct a protocol implementing oblivious transfer from any optimally accurate, distributed differentially private protocol for any functionality with a boolean XOR embedded on adjacent inputs.

- While the previous result holds for optimally accurate protocols for any privacy parameter \\epsilon > 0, we also give a reduction from oblivious transfer to distributed differentially private protocols computing XOR, for a constant small range of non-optimal accuracies and a constant small range of values of privacy parameter \\epsilon.

At the heart of our techniques is an interesting connection between optimally-accurate two-party protocols for the XOR functionality and noisy channels, which were shown by Crepeau and Kilian [FOCS 1988] to be sufficient for oblivious transfer.

Sequences generated by maximum-period nonlinear feedback shift registers are known as de Bruijn sequences. The problem of designing

de Bruijn sequences has received considerable attention. There is only one full cycle in the state graph of de Bruijn sequences. Most

popular algorithms for generating de Bruijn sequences start from a nonsingular linear feedback shift register producing several shorter

cycles in its state graph, then join them into one cycle. Unfortunately, the order $n$ of the resulting de Bruijn sequence by using

this kind of algorithms is small so far (usually $n \\le 40$). We introduce a new concept of correlated cycles between the cycles

in the state graph of a LFSR. Based on this concept we present a algorithm for constructing de Bruijn sequences with large orders (such

as $n=128$). This is the first publication for designing de Bruijn sequences with such large orders.

Earlier in 2015, Bos, Costello, Naehrig, and Stebila (IEEE Security & Privacy 2015) proposed an instantiation of Peikert\'s ring-learning-with-errors (Ring-LWE) based key-exchange protocol (PQCrypto 2014), together with an implementation integrated into OpenSSL, with the affirmed goal of providing post-quantum security for TLS. In this work we revisit their instantiation and stand-alone implementation. Specifically, we propose new parameters and a better suited error distribution, analyze the scheme\'s hardness against attacks by quantum computers in a conservative way, introduce a e and more efficient error-reconciliation mechanism, and propose a defense against backdoors and all-for-the-price-of-one attacks. By these measures and for the same lattice dimension, we more than double the security parameter, halve the communication overhead, and speed up computation by more than a factor of 8 in a portable C implementation and by more than a factor of 20 in an optimized implementation targeting current Intel CPUs. These speedups are achieved with comprehensive protection against timing attacks.

The past several years have seen tremendous advances in practical, general-purpose, non-interactive proof systems called SNARKs. These building blocks are efficient and convenient, with multiple publicly available implementations, including tools to compile high-level code

(e.g., written in C) to arithmetic circuits, the native representation used by SNARK constructions. However, while we would like to use these primitives in UC-secure protocols --- which are provably-secure even when composed with other arbitrary concurrently-executing protocols --- the SNARK definition is not directly compatible with this framework, due to its use of non black-box knowledge extraction. We show several constructions to transform SNARKs into UC-secure NIZKs, along with benchmarks and an end-to-end application example showing that the

added overhead is tolerable. Our constructions rely on embedding cryptographic algorithms into the SNARK proof system. Ordinarily, cryptographic constructions are chosen and tuned for implementation on CPUs or in hardware, not as arithmetic circuits. We therefore also initiate the study of SNARK-friendly cryptography, describing several protocol parameterizations, implementations, and performance comparisons for encryption, commitments, and other tasks. This is also of independent interest for use in other SNARK-based applications.

The study of seeded randomness extractors is a major line of research in theoretical computer science. The goal is to construct deterministic algorithms which can take a ``weak\" random source $X$ with min-entropy $k$ and a uniformly random seed $Y$ of length $d$, and outputs a string of length close to $k$ that is close to uniform and independent of $Y$. Dodis and Wichs~\\cite{DW09} introduced a generalization of randomness extractors called non-malleable extractors ($\\nmExt$) where $\\nmExt(X,Y)$ is close to uniform and independent of $Y$ and $\\nmExt(X,f(Y))$ for any function $f$ with no fixed points.

We relax the notion of a non-malleable extractor and introduce what we call an affine-malleable extractor ($\\AmExt: \\F^n \\times \\F^d \\mapsto \\F$) where $\\AmExt(X,Y)$ is close to uniform and independent of $Y$ and has some limited dependence of $\\AmExt(X,f(Y))$ - that conditioned on $Y$, $(\\AmExt(X,Y), \\AmExt(X,f(Y)))$ is close to $(U, A \\cdot U + B)$ where $U$ is uniformly distributed in $\\F$ and $A, B \\in \\F$ are random variables independent of $\\F$.

We show under a plausible conjecture in additive combinatorics (called the Spectrum Doubling Conjecture) that the inner-product function $\\IP{\\cdot,\\cdot}:\\F^n \\times \\F^n \\mapsto \\F$ is an affine-malleable extractor. As a modest justification of the conjecture, we show that a weaker version of the conjecture is implied by the widely believed Polynomial Freiman-Ruzsa conjecture.

We also study the classical problem of privacy amplification, where two parties Alice and Bob share a weak secret $X$ of min-entropy $k$, and wish to agree on secret key $R$ of length $m$ over a public communication channel completely controlled by a computationally unbounded attacker Eve. The main application of non-malleable extractors and its many variants has been in constructing secure privacy amplification protocols.

We show that affine-malleable extractors along with affine-evasive sets can also be used to construct efficient privacy amplification protocols. We show that our protocol, under the Spectrum Doubling Conjecture, achieves near optimal parameters and achieves additional security properties like source privacy that have been the focus of some recent results in privacy amplification.

Motivated by the goal of removing trusted setup assumptions from cryptography, we introduce the notion of witness signatures. This primitive allows any party with a valid witness to an NP statement to sign a message on behalf of that statement. We also require these signatures to be unforgeable: that is, producing a signature on a new message (even given several message, signature pairs) should be as hard as computing a witness to the NP statement itself. Witness signatures are closely related to previously well-studied notions such as non-malleable non-interactive zero knowledge arguments, and signatures of knowledge.

In this work, we formalize this notion and show that most natural definitions are impossible in the plain model without any setup assumptions. While still wanting to avoid a central trusted setup, we turn to the tamper proof hardware token model of Katz (Eurocrypt 2007). Interestingly, we show witness signatures in the hardware token model are closely related to what we call non-malleable multi-prover zero-knowledge proofs in the plain model (i.e. without hardware tokens). We initiate the study of non-malleable multi-prover zero-knowledge proofs, and, provide an unconditional construction of single round non-malleable two-prover zero-knowledge proofs. We then use this primitive to obtain an unconditional construction of witness signatures in the hardware token model.

Our construction makes a novel use of non-malleable codes. In particular, we crucially rely on the notion of many-many non-malleable codes introduced recently by Chattopadhyay, Goyal and Li (ECCC 2015). Our construction is unconditional, is extremely efficient (in terms of computation, number of tokens, and rounds of interaction with the token), and, only relies on elementary computations such as inner products.

Finally, this construction yields signatures which can only be verified a bounded number of times. Towards that end, we show how to extend it to get the unbounded (polynomial) verification property relying on the minimal additional assumption of one-way functions. We also show that obtaining unconditional unbounded-verifiable witness signatures under black-box extraction, is impossible even with access to an unbounded number of stateful tamper-proof hardware tokens- thereby giving a matching lower bound. This is done by relying on the techniques from the work of Goyal et al (Crypto 2012) (which in turn builds on techniques from the black-box separation literature). In particular, we rely on the notion of ``inaccessible entropy\" introduced in prior works.

A watermarking scheme for programs embeds some information called a mark into a program while preserving its functionality. No adversary can remove the mark without damaging the functionality of the program. In this work, we study the problem of watermarking various cryptographic programs such as pseudorandom function (PRF) evaluation, decryption, and signing. For example, given a PRF $F$, we create a marked program $\\widetilde{C}$ that evaluates $F(\\cdot)$. An adversary that gets $\\widetilde{C}$ cannot come up with \\emph{any} program $C^*$ in which the mark is removed but which still evaluates the PRF correctly on even a small fraction of the inputs.

The work of Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang (CRYPTO\'01 and Journal of ACM 59(2)) shows that, assuming indistinguishability obfuscation (iO), such watermarking is \\textit{impossible} if the marked program $\\widetilde{C}$ evaluates the original program with {perfect correctness}. In this work we show that, assuming iO, such watermarking is \\textit{possible} if the marked program $\\widetilde{C}$ is allowed to err with even a negligible probability, which would be undetectable to the user.

Our watermarking schemes are {\\em public key}, meaning that we use a secret marking key to embed marks in programs, and a public detection key that allows anyone to detect marks in programs. Our schemes are secure against {\\em chosen program attacks} where the adversary is given oracle access to the marking functionality. We emphasize that our security notion of watermark non-removability considers arbitrary adversarial strategies to modify the marked program, in contrast to the prior works (Nishimaki, EUROCRYPT \'13).

At University College London (UCL), we just opened a 2-year post-doc position to work on Privacy-Preserving Techniques for Web-based Infectious Disease Surveillance.

Application deadline: 10 December 2015.

Details and instructions on how to apply are available from http://preview.tinyurl.com/ovr6sfm

[For more information about security and privacy research at UCL, please visit http://sec.cs.ucl.ac.uk/people/]

•Develop the implement encryption technologies

•Develop cryptographic systems

•Develop mobile security solutions

•Develop and implement cyber intelligence and defense technologies

•Study new security threats in the cloud infrastructure

•Perform security review and assessment on information security and e-commerce systems

•Conduct R&D on various in information security

Requirements:

•Bachelor degree or above in computer science, electrical engineering or other relevant disciplines

•Experience in hands-on R&D projects, especially on software systems

•Experience in planning, organizing, leading and implementing novel R&D projects, especially on information security and data analytics related areas

•Preferably with certificates or formal training in information security or with experience in security assessment, but not a necessity

•Good knowledge of OS security and virtualization security

•Implementation experience on the cloud an advantage

•Strong interpersonal and communications skills

We are looking for excellent candidates with strong background in Computer Science, Mathematics or Engineering.

Our research focus is on practice-oriented provable security. Topics of interest may include (but are not limited to):

- Provable security of cryptographic implementations

- Randomness generation

- Cryptographic protocols (e.g. cryptocurrencies)

Starting date: earliest possible

A competitive salary is offered.

Send your documents to sebastian (dot) faust (at) rub (dot) de

Applicants are required to have completed (or be close to completing) a Master or Diploma with excellent grades in Computer Science, Mathematics, or closely related areas. Additional knowledge in related disciplines such as, e.g., complexity theory or IT security is welcome.

Please send your application to Sebastian Faust via e-mail. Applications should contain a CV, a 1-page letter of motivation, copies of transcripts and certificates, and (if possible) names of references. Review of applications will start immediately until the position has been filled.

Founded in 2001, the Horst-Görtz Institute at Ruhr-University Bochum is a leading interdisciplinary research center dedicated to research and education covering all aspects of IT security, with an excellent record of research in cryptography. The Horst-Görtz Institute has 15 professors and over 80 PhD students from more than 20 different countries.

Contact: Sebastian Faust, sebastian (dot) faust (at) rub (dot) de

Closing Date for Applications: 2015-12-10

The Cryptographics Algorithms AES and Twofish guarantee a high diffusion

with the use of fixed MDS matrices of size 4 x 4. In this article variations to the Cryptographics Algorithms AES and Twofish are made. They allow that the process of cipher-decipher come true with MDS matrices selected randomly from an algorithm that obtaining an MDS matrix of set of all the MDS matrices possible. A new Schedule of key with a high diffusion is designed for the Algorithm Cryptographic AES. Besides it is proposed a new S-box that he varies in function of the key.

Recently, ARM NEON architecture has occupied a significant

share of tablet and smartphone markets due to its low cost

and high performance. This paper studies efficient techniques of

lattice-based cryptography on ARM processor and presents the

first implementation of ring-LWE encryption on ARM NEON

architecture. In particular, we propose a vectorized version of

Iterative Number Theoretic Transform (NTT) for high-speed

computation. We present a 32-bit variant of SAMS2 technique,

original proposed in CHES\'15, for fast reduction. A combination

of proposed and previous optimizations results in a very efficient

implementation. For 128-bit security level, our ring-LWE implementation

requires only 145; 200 clock cycles for encryption

and 32; 800 cycles for decryption. These result are more than

17:6 times faster than the fastest ECC implementation on ARM

NEON with same security level.

We consider the problem of delegating RAM computations over persistent databases: A user wishes to delegate a sequence of computations over a database to a server, where each compuation may read and modify the database and the modifications persist between computations. For the efficiency of the server, it is important that computations are modeled as RAM programs, for their runtime may be sub-linear in the size of the database.

Two security needs arise in this context: Ensuring {\\em Intergrity}, by designing means for the server to compute short proofs that allows the user to efficiently verify the correctness of the server computation, and {\\em privacy}, providing means for the user to hide his private databases and programs from a malicious server. In this work, we aim to address both security needs, especially in the stringent, {\\em adaptive}, setting, where the sequence of RAM

computations are (potentially) chosen adaptively by a malicious server depending on the messages from an honest user.

To this end, we construct the first RAM delegation scheme achieving both {\\em adaptive integrity} (a.k.a.\\ soundness) and {\\em adaptive privacy}, assuming the existence of indistinguishability obfuscation for circuits and a variant of the two-to-one somewhere perfectly binding hash [Okamoto et al. ASIACRYPT\'15] (the latter can be based on the decisional Diffie-Hellman assumption). Prior works focused either only on adaptive soundness [Kalai and Paneth, ePrint\'15] or on the weaker variant, selective soundness and privacy [Chen et al. ITCS\'16, Canetti and Holmgren ITCS\'16]. Our result extends to delegate parallel RAM (PRAM) computation as well.

At a high-level, our result is obtained by applying a generic ``{\\em security lifting technique}\'\' to the delegation scheme of Chen et al.\\ and its proof of selective soundness and privacy. The security lifting technique formalizes an abstract framework of selective security proofs, and generically ``lifts\'\' such proofs into proofs of adaptive security. We believe that this technique can potentially be applied to other cryptographic schemes and is of independent interest.

Post-quantum cryptographic schemes have been developed in the last decade in response to the rise of quantum computers. Fortunately, several schemes have been developed with quantum resistance. However, there is very little effort in evaluating and comparing these schemes in the embedded settings. Low cost embedded devices represents a highly-constraint environment that challenges all post-quantum cryptographic schemes. Moreover, there are even fewer efforts in evaluating the security of these schemes against implementation attacks including side-channel and fault attacks. It is commonly accepted that, any embedded cryptographic module that is built without a sound countermeasure, can be easily broken. Therefore, we investigate the question: Are we ready to implement post-quantum cryptographic schemes on embedded systems? We present an exhaustive survey of research efforts in designing embedded modules of post-quantum cryptographic schemes and the efforts in securing these modules against implementation attacks. Unfortunately, the study shows that: we are not ready yet to implement any post-quantum cryptographic scheme in practical embedded systems. There is still a considerable amount of research that needs to be conducted before reaching a satisfactory level of security.

In this work, we introduce patchable obfuscation: our notion

adapts the notion of indistinguishability obfuscation (iO) to a very general setting where

obfuscated software evolves over time. We model this broadly by considering

software patches P as arbitrary Turing Machines that take as input the description of a

Turing Machine M, and output a new Turing Machine description M\' = P(M).

Thus, a short patch P can cause changes everywhere in the description of M and

can even cause the description length of the machine to increase by an arbitrary polynomial amount.

We further consider the setting where a patch is applied not just to a single

machine M, but to an unbounded set of machines (M_1, \\dots, M_t) to

yield (P(M_1), \\dots, P(M_t). We call this multi-program patchable obfuscation.

We consider both patchable obfuscation and multi-program patchable obfuscation

in a setting where there are an unbounded number of patches that can be adaptively

chosen by an adversary.

We show that sub-exponentially secure iO for circuits and sub-exponentially secure one-way functions imply patchable obfuscation; and we show that

sub-exponentially secure iO for circuits, sub-exponentially secure one-way functions,

and sub-exponentially secure DDH imply multi-program patchable obfuscation.

Finally, we exhibit some simple applications

of multi-program patchable obfuscation, to demonstrate how these concepts

can be applied.

In this paper, we investigate Keccak --- the cryptographic hash function adopted as the SHA-3 standard. We propose a malicious variant of the function, where new round constants are introduced. We show that for such the variant, collision and preimage attacks are possible. We also identify a class of weak keys for the malicious Keccak working in the MAC mode. Ideas presented in the paper were verified by implementing the attacks on the function with the 128-bit hash.

Side-channel and fault injection analysis are well-known domains that have been used for years to evaluate the resistance of hardware based products. These techniques remain a threat for the secret assets embedded in products like smart cards or System On Chip. But most of these products contain nowadays several strong protections rendering side-channel and fault attacks difficult or not efficient.

For two decades now embedded cryptography for payment, pay tv, identity areas have been mainly focused on secure elements. However recently, alternative solutions on mobile phones appeared to offer services including payment and security solutions as the HCE and DRM products. Cryptographic operations running in such applications are then executed most often on unprotected hardware devices. Therefore the binary code is accessible to attackers who can use static and dynamic reverse engineering techniques to extract and analyse operations including data modification as faults. Hence, hiding or obfuscating secrets and/or obfuscated or whitebox-ed cryptography becomes mainly the alternatives to secure element storage for assets. Although not proven secure, attacking such implementations in practice on a binary is another story.

We explain in this paper how directly from the binary or with the extracted source code we can perform statistical and fault analysis in a manner that seems familiar with hardware side channel and fault attacks knowledge. The main difference is, using our tool and virtualization technique, an attacker can emulate and trace and modify any chosen computational data (memory or register manipulation, any machine language operation) executed in the mobile application. It means the attacker is not restricted any-more by any physical limitations as the Hamming leakage model (and additional noise) and the difficulty to fault a dedicated operation.

Hence statistical and fault attacks becomes more efficient than in standard physical devices. As a consequence, complex techniques like high order, collision and horizontal statistical attacks becomes very efficient and can be easily performed on the computational data execution traces. A similar consequence applies for fault injection attacks. Hence the word statistical and fault analysis on computational data becomes more appropriate and one can wonder who has been the first between computational data or physical attack techniques? Chicken or the Egg?

Compared to the classical cryptography, lattice-based cryptography is more secure, flexible and simple, and it is believed to be secure against quantum computers. In this paper, an efficient signature scheme is proposed from the ring learning with errors (R-LWE), which avoids sampling from discrete Gaussians and has the characteristics of the much simpler description etc. Then, the scheme is implemented in C/C++ and makes a comparison with the RSA signature scheme in detail. Additionally, a linearly homomorphic signature scheme without trapdoor is proposed from the R-LWE assumption. The security of the above two schemes are reducible to the worst-case hardness of shortest vectors on ideal lattices. The security analyses indicate the proposed schemes are unforgeable under chosen message attack model, and the efficiency analyses also show that the above schemes are much more efficient than other correlative signature schemes.