International Association
for Cryptologic Research

We propose a public key encryption scheme based on the Boolean Satisfiability Problem (SAT). The public key is given by a SAT formula and the private key is the satisfying assignment. Encryption is a probabilistic algorithm that takes the bits of the message to randomly generated Boolean functions, represented in algebraic normal form. Those are implied to be true or false by the public key, hence bit-wise decryption is done by applying each function to the private key. Our scheme does not provide signatures.

In a seminal paper, Dolev et al. (STOC\'91) introduced the notion of non-malleable encryption (NM-CPA). This notion is very intriguing since it suffices for many applications of chosen-ciphertext secure encryption (IND-CCA), and, yet, can be generically built from semantically secure (IND-CPA) encryption, as was shown in another seminal paper of Choi et al. (TCC\'08). In this paper we investigate three questions related to NM-CPA security:

- Can the rate of the construction by Choi et al. of NM-CPA from IND-CPA be improved?

- Is it possible to achieve multi-bit NM-CPA security more efficiently from a single-bit NM-CPA scheme than from IND-CPA?

- Is there a notion stronger than NM-CPA that has natural applications and can be achieved from IND-CPA security?

We answer all three questions in the positive. First, we improve the rate in the construction of Choi et al. by a factor O(k), where k is the security parameter. Still, encrypting a message of size O(k) would require ciphertext and keys of size O(k^2) times that of the IND-CPA scheme, even in our improved scheme. Therefore, we show a more efficient domain extension technique for building a k-bit NM-CPA scheme from a single-bit NM-CPA scheme with keys and ciphertext of size O(k) times that of the NM-CPA one-bit scheme. To achieve our goal, we define and construct a novel type of continuous non-malleable code (NMC), called secret-state NMC, as we show that standard continuous NMCs are not enough for the natural \"encode-then-encrypt-bit-by-bit\" approach to work.

Finally, we introduce a new security notion for public-key encryption (PKE) that we dub non-malleability under (chosen-ciphertext) self-destruct attacks (NM-SDA). After showing that NM-SDA is a strict strengthening of NM-CPA and allows for more applications, we nevertheless show that both of our results---(faster) construction from IND-CPA and domain extension from one-bit scheme---also hold for our stronger NM-SDA security. In particular, the notions of IND-CPA, NM-CPA, and NM-SDA security are all equivalent, lying (plausibly, strictly?) below IND-CCA security.

Submission: 23 February 2016
From July 4 to July 6
Location: Melbourne, Australia
More Information: http://anss.org.au/ACISP2016

The Fiat-Shamir (FS) transform is a popular technique for obtaining practical zero-knowledge argument systems. It uses a hash function to generate, without any overhead, NIZK argument systems from public-coin honest-verifier zero-knowledge (HVZK) proof systems. In the proof of zero knowledge the hash function is modeled as a programmable random oracle (PRO).

In TCC 2015, Lindell embarked in the challenging task of obtaining a similar transform with improved heuristic security. Lindell showed that, for several interesting and practical languages, there exists an efficient transform in the non-programmable random oracle (NPRO) model, using also a common reference string (CRS).

A major contribution of Lindell\'s transform is that zero knowledge is proved without random oracles and this is an important step towards achieving efficient NIZK arguments in the CRS model without random oracles.

In this work, we analyze the efficiency and generality of Lindell\'s transform and notice a significant gap w.r.t. the FS transform. We then propose a new transform that aims at filling this gap. Indeed ourtransform is almost as efficient as the FS transform and can be applied to a broad class of public-coin HVZK proof systems.

Our transform requires a CRS and an NPRO in the proof of soundness,

similarly to Lindell\'s transform.

As part of the revelations about the NSA activities,

the notion of interdiction has become known to the public:

the interception of deliveries to manipulate hardware in a way

that backdoors are introduced. Manipulations can occur on

the firmware or at hardware level. With respect to hardware,

FPGAs are particular interesting targets as they can be altered

by manipulating the corresponding bitstream which configures

the device. In this paper, we demonstrate the first successful

real-world FPGA hardware Trojan insertion into a commercial

product. On the target device, a FIPS-140-2 level 2 certified USB

flash drive from Kingston, the user data is encrypted using AES-256 in XTS mode, and the encryption/decryption is processed by

an off-the-shelf SRAM-based FPGA. Our investigation required

two reverse-engineering steps, related to the proprietary FPGA

bitstream and to the firmware of the underlying ARM CPU. In

our Trojan insertion scenario the targeted USB flash drive is

intercepted before being delivered to the victim. The physical

Trojan insertion requires the manipulation of the SPI flash

memory content, which contains the FPGA bitstream as well

as the ARM CPU code. The FPGA bitstream manipulation

alters the exploited AES-256 algorithm in a way that it turns

into a linear function which can be broken with 32 known

plaintext-ciphertext pairs. After the manipulated USB flash drive

has been used by the victim, the attacker is able to obtain all

user data from the ciphertexts. Our work indeed highlights the

security risks and especially the practical relevance of bitstream

modification attacks that became realistic due to FPGA bitstream

manipulations.

We show the following reductions from the learning with errors problem (LWE) to the learning with rounding problem (LWR): (1) Learning the secret and (2) distinguishing samples from random strings is at least as hard for LWR as it is for LWE for efficient algorithms if the number of samples is no larger than O(q/Bp), where q is the LWR modulus, p is the rounding modulus and the noise is sampled from any distribution supported over the set {-B,...,B}.

Our second result generalizes a theorem of Alwen, Krenn, Pietrzak and Wichs (CRYPTO 2013) and provides an alternate proof of it. Unlike Alwen et al., we do not impose any number theoretic restrictions on the modulus q. The first result also extends to variants of LWR and LWE over polynomial rings.

As additional results we show that (3) distinguishing any number of LWR samples from random strings is of equivalent hardness to LWE whose noise distribution is uniform over the integers in the range [-q/2p,...,q/2p) provided q is a multiple of p and (4) the \"noise flooding\" technique for converting faulty LWE noise to a discrete Gaussian distribution can be applied whenever q = \\Omega(B\\sqrt{m}).

All our reductions preserve sample complexity and have time complexity at most polynomial in q, the dimension, and the number of samples.

Inquiries are invited for externally-funded post-doc and PhD student positions in applied cryptography at NJIT in Newark, NJ, USA. NJIT is a rapidly expanding R1 research university in metro New York City.

Research topics are on applied homomorphic encryption, lattice encryption systems, encrypted program obfuscation, software engineering and high-assurance software design. The overall aim of the positions are to develop high-quality open-source software and working prototypes related to network and system security.

The ideal candidate will have working knowledge of network security and C++ programming. Software engineering, software testing, high-performance computing, computer engineering and parallel programming experience would be beneficial but not critical.

The candidates will be supervised by Prof. Kurt Rohloff in the department of computer science at NJIT. The post-doc position can be renewed annually subject to continued external funding and success in the position.

As an Assistant Professor of Privacy Engineering in the Faculty of Science at Radboud University, Nijmegen, you will conduct research that fits into the existing research lines, which include the following topics:

• integration of law and policy compliance into the development process;
• privacy impact assessment, privacy risk management models, and accountability;
• technical standards, heuristics and best practices for privacy engineering;
• user privacy and data protection requirements, especially in big data analysis;
• privacy-preserving data mining;
• privacy architectures, and privacy validation and evaluation methods and tools;
• organizational, legal, political and economic aspects of privacy engineering.

In addition, you will act as a daily PhD supervisor and regularly publish scientific articles about your research results and developments in your field in international journals and proceedings. You will disseminate results in the field to a wider audience, consisting of professionals, policy makers, journalists, and the public at large. Furthermore, you will actively acquire external research funding from commercial and non-commercial sources. In this position you will turn scientific knowledge into economical and societal value, for example, through industrial applications and outreach.

You will teach courses in the Master’s degree programme in Information Science, develop, re-develop and evaluate courses of the Institute for Computing and Information Sciences (and the faculty at large), and supervise Master’s thesis projects. You will coordinate the Master’s programme in Information Science, which involves developing and implementing a new profile for the programme, setting up international contacts, creating collaboration and exchan

Physically unclonable functions (PUFs) provide data that can be used for cryptographic purposes: on the one hand randomness for the initialization of random-number generators; on the other hand individual fingerprints for unique identification of specific hardware components. However, today\'s off-the-shelf personal computers advertise randomness and individual fingerprints only in the form of additional or dedicated hardware.

This paper introduces a new set of tools to investigate whether intrinsic PUFs can be found in PC components that are not advertised as containing PUFs. In particular, this paper investigates AMD64 CPU registers as potential PUF sources in the operating-system kernel, the bootloader, and the system BIOS; investigates the CPU cache in the early boot stages; and investigates shared memory on Nvidia GPUs. This investigation found non-random non-fingerprinting behavior in several components but revealed usable PUFs in Nvidia GPUs.

The encryption mode of the Tweakable Block Cipher (TBC) of the SCREAM Authenticated Cipher is implemented in the MSP430 microcontroller. Assembly language versions of the TBC are prepared using both precomputed tweak keys and tweak keys computed \"on-the-fly.\" Both versions are compared against published results for the assembly language version of SCREAM on the ATMEL AVR microcontroller, and against the C reference implementation in terms of performance and size. The assembly language version using precomputed tweak keys achieves a speedup of 1.7 and memory savings of 9 percent over the reported SCREAM implementation in the ATMEL AVR. The assembly language version using tweak keys computed \"on-the-fly\" achieves a speedup of 1.6 over the ATMEL AVR version while reducing memory usage by 15 percent.

Kalyna is an SPN-based block cipher that was selected during Ukrainian national public cryptographic competition (2007-2010), and its slight modification was approved as the new encryption standard of Ukraine (DSTU 7624:2014) in 2015. The cipher supports a block size and a key length of 128, 256 and 512 bits where the size of the key can be either double or equal to that of the block length. According to its designers, the cipher provides strength to several cryptanalytic methods after the fifth and sixth rounds of the 128-bit and 256-bit block versions, respectively. In this paper, we present a meet-in-the-middle attack on the 7-round reduced versions of Kalyna where the key size is double the block length. Our attack is based on the differential enumeration approach where we carefully deploy a four round distinguisher in the first four rounds to bypass the effect of the carry bits resulting from the pre-whitening modular key addition. We also exploit the linear relation between consecutive odd and even indexed round keys which enables us to attack seven rounds and recover all the round keys incrementally. The attack on Kalyna with 128-bit block has a data complexity of $2^{89}$ chosen plaintexts, time complexity of $2^{230.2}$ and a memory complexity of $2^{202.64}$. The data, time and memory complexities of our attack on Kalyna with 256-bit block are $2^{233}$, $2^{502.2}$ and $2^{170}$, respectively.

This paper proposes a compact and efficient $GF(2^8)$ inversion

circuit design based on a combination of non-redundant and redundant

Galois Field (GF) arithmetic. The proposed design utilizes redundant

GF representations, called Polynomial Ring Representation (PRR)

and Redundantly Represented Basis (RRB), to implement GF(28) inversion

using a tower field $GF((2^4)2)$. In addition to the redundant representations,

we introduce a specific normal basis that makes it possible

to map the former components for the 16th and 17th powers of

input onto logic gates in an efficient manner. The latter components

for $GF(2^4)$ inversion and $GF(2^4)$ multiplication are then implemented

by PRR and RRB, respectively. The flexibility of the redundant representations

provides efficient mappings from/to the $GF(2^8)$. This paper

also evaluates the efficacy of the proposed circuit by means of gate

counts and logic synthesis with a 65 nm CMOS standard cell library and

comparisons with conventional circuits, including those with tower fields

$GF(((2^2)^2)^2)$. Consequently, we show that the proposed circuit achieves

approximately 40% higher efficiency in terms of area-time product than

the conventional best $GF(((2^2)^2)^2)$ circuit excluding isomorphic mappings.

We also demonstrate that the proposed circuit achieves the best

efficiency (i.e., area-time product) for an AES encryption S-Box circuit

including isomorphic mappings.

A method of generating coset representatives of $PGL_2(\\F_q)$ in $PGL_2(\\F_{q^2})$ is presented, which has applications

in solving discrete logarithms and finding primitive elements in finite fields of small characteristic.

We initiate the study of sanitizable signatures over encrypted data. While previous solutions for sanitizable signatures require the sanitizer to know, in clear, the original message-signature pair in order to generate the new signature, we investigate the case where these data should be hidden from the sanitizer and how this can be achieved with encryption. We call this primitive sanitizable signcryption, and argue that there are two options concerning what the sanitizer learns about the sanitized output: in semi-oblivious sanitizable signcryption schemes the sanitizer may get to know the sanitized message-signature pair, while fully oblivious sanitizable signcryption schemes even protect the output data. Depending on

the application, either notion may be preferable.

We continue to show that semi-oblivious sanitizable signcryption schemes can be constructed in principle, using the power of multi-input functional encryption. To this end, we wrap a regular sanitizable signature scheme into a multi-input functional encryption scheme, such that functional decryption corresponds to the sanitization process. Remarkably, the multi-input functional encryption scheme cannot easily be transferred to a fully oblivious sanitizable signcryption version, so we give a restricted solution based on fully homomorphic encryption for this case.

Universal hash functions (UHFs) have been extensively used in the design of cryptographic schemes. But if we consider related-key attack against the schemes, some of them may not be secure, especially when the key of UHF is a part of the key of scheme. In order to solve the issue, we propose a new concept of related-key almost universal hash function, which is a natural extension to almost universal hash function in the related-key scenario. We define related-key almost universal (RK-AU) hash function and related-key almost XOR universal (RK-AXU) hash function. However almost all the existing UHFs do not satisfy the new definitions. We construct fixed-input-length universal hash functions such as RH1 and variable-input-length related-key universal hash functions such as RH2, RH3. We show that RH1 and RH2 are both RK-AXU, and RH3 is RK-AU. Furthermore, RH1, RH2 and RH3 are nearly as efficient as previous similar constructions. RK-AU (AXU) hash functions can be used as components with related-key property in the design of cryptographic schemes. If we replace the universal hash functions in the schemes with our corresponding constructions, the problems about related-key attack can be solved. More specifically, we give four concrete applications of RK-AU and RK-AXU in MACs and TBCs.

Dual EC is an algorithm to compute pseudorandom numbers starting from some random input. Dual EC was standardized by NIST, ANSI, and ISO among other algorithms to generate pseudorandom numbers. For a long time this algorithm was considered suspicious -- the entity designing the algorithm could have easily chosen the parameters in such a way that it can predict all outputs -- and on top of that it is much slower than the alternatives and the numbers it provides are more biased, i.e., not random.

The Snowden revelations, and in particular reports on Project Bullrun and the SIGINT Enabling Project, have indicated that Dual EC was part of a systematic effort by NSA to subvert standards.

This paper traces the history of Dual EC including some suspicious changes to the standard, explains how the back door works in real-life applications, and explores the standardization and patent ecosystem in which the standardized back door stayed under the radar.

MISTY1 is a block cipher designed by Matsui in 1997. It is widely deployed in Japan, and is recognized internationally as a European

NESSIE-recommended cipher and an ISO standard. After almost 20 years of unsuccessful cryptanalytic attempts, a first attack on the full MISTY1 was presented at CRYPTO 2015 by Todo. The attack, using a new technique called {\\it division property}, requires almost the full codebook and has time complexity of 2^{107.3} encryptions.

In this paper we present a new attack on the full MISTY1. It is based on a modified variant of Todo\'s division property, along with a variety of refined key-recovery techniques. Our attack requires the full codebook, but allows to retrieve 49 bits of the secret key in time complexity of only 2^{64} encryptions, and the full key in time complexity of 2^{69.5} encryptions.

While our attack is clearly impractical due to its large data complexity, it shows that MISTY1 provides security of only 2^{70} --- significantly less than what was considered before.

The bilinear map whose domain and range are identical is called self-bilinear map. Once such kind of bilinear map exists, the multi-linear map can be constructed easily by using self bilinear map as a component. Yamakawa et al. have introduced the first secure self-bilinear map with auxiliary information based on the integer factoring assumption in Crypto 2014. Inspired by their work, we find that any encoding system with particular properties could be used to build self-bilinear map. We generalize them as one way encoding system and propose a generic construction of self-bilinear map. For cryptographic use, we define a new encoding division assumption to make the analog DDHP hard. We show that one level encoding of graded encoding system which is used to build multilinear map nowadays satisfy all the properties of one way encoding system. We also present an instance that is build on GGH graded encoding scheme and analyze how hard the encoding division problem is. Our self-bilinear map is believed to be quantum resistance. It seems more secure than the scheme of Yamakawa et al. Moreover, the encoding size of $n$-multilinear built on our self-bilinear map is smaller than that of GGH scheme.

At CRYPTO 2014 Bellare, Paterson, and Rogaway (BPR) presented a formal treatment of symmetric encryption in the light of algorithm substitution attacks (ASAs), which may be employed by `big brother\' entities for the scope of mass surveillance. Roughly speaking, in ASAs big brother may bias ciphertexts to establish a covert channel to leak vital cryptographic information. In this work, we identify a seemingly benign assumption implicit in BPR\'s treatment and argue that it artificially (and severely) limits big brother\'s capabilities. We then demonstrate the critical role that this assumption plays by showing that even a slight weakening of it renders the security notion completely unsatisfiable by any, possibly deterministic and/or stateful, symmetric encryption scheme. We propose a refined security model to address this shortcoming, and use it to restore the positive result of BPR, but caution that this defense does not stop most other forms of covert-channel attacks.

Motivated by the development of Side-Channel Analysis (SCA) countermeasures which can provide security up to a certain order, defeating higher-order attacks has become amongst the most challenging issues. For instance, Threshold Implementation (TI) which nicely solves the problem of glitches in masked hardware designs is able to avoid first-order leakages. Hence, its extension to higher orders aims at counteracting SCA attacks at higher orders, that might be limited to univariate scenarios. Although with respect to the number of traces as well as sensitivity to noise the higher the order, the harder it is to mount the attack, a d-order TI design is vulnerable to an attack at order d+1. In this work we look at the feasibility of higher-order attacks on first-order TI from another perspective. Instead of increasing the order of resistance by employing higher-order TIs, we go toward introducing structured randomness into the implementation.

Our construction, which is a combination of masking and hiding, is dedicated to TI designs and deals with the concept of \"affine equivalence\" of Boolean functions. Such a combination hardens a design practically against higher-order attacks so that these attacks cannot be successfully mounted. We show that the area overhead of our construction is paid off by its ability to avoid higher-order leakages to be practically exploitable.