International Association
for Cryptologic Research

We show the first positive results for the indifferentiability security of the confusion-diffusion networks (which are extensively used in the design of block ciphers and hash functions). In particular, our result shows that a constant number of confusion-diffusion rounds is sufficient to extend the domain of a public random permutation.

A secure ad-hoc survey scheme enables a survey authority to independently (without any interaction) select an ad-hoc group of registered users based only on their identities (e.g., their email addresses), and create a survey where only selected users can anonymously submit exactly one response.

We present a formalization of secure ad-hoc surveys and present:

* an abstract provably-secure implementation based on standard cryptographic building blocks (which in particular are implied by the existence of enhanced trapdoor permutations in the CRS model);

* a practical instantiation of our abstract protocol, called ANONIZE, which is provably-secure in the random oracle model based on cryptographic assumptions on groups with bilinear maps.

As far as we know, ANONIZE constitutes the first implementation of a large-scale secure computation protocol (of non-trivial functionalities) that can scale to millions of users.

MISTY1 is a block cipher designed by Matsui in 1997. It was well evaluated and standardized by projects, such as CRYPTREC, ISO/IEC, and NESSIE. In this paper, we propose a key recovery attack on the full MISTY1, i.e., we show that 8-round MISTY1 with 5 FL layers does not have 128-bit security. Many attacks against MISTY1 have been proposed, but there is no attack against the full MISTY1. Therefore, our attack is the first cryptanalysis against the full MISTY1. We construct a new integral characteristic by using the propagation characteristic of the division property, which was proposed in 2015. We first improve the division property by optimizing a public S-box and then construct a 6-round integral characteristic on MISTY1. Finally, we recover the secret key of the full MISTY1 with $2^{63.58}$ chosen plaintexts and $2^{121}$ time complexity. Moreover, if we can use $2^{63.994}$ chosen plaintexts, the time complexity for our attack is reduced to $2^{107.9}$. Note that our cryptanalysis is a theoretical attack. Therefore, the practical use of MISTY1 will not be affected by our attack.

Following the line of work presented recently by Bellare, Paterson and Rogaway, we formalize and investigate the resistance of linear secret-sharing schemes to mass surveillance. This primitive is widely used to design IT systems in the modern computer world, and often it is implemented by a proprietary code that the provider (\"big brother\") could manipulate to covertly violate the privacy of the users (by implementing Algorithm-Substitution Attacks or ASAs). First, we formalize the security notion that expresses the goal of big brother and prove that for any linear secret-sharing scheme there exists an undetectable subversion of it that efficiently allows surveillance. Second, we formalize the security notion that assures that a sharing scheme is secure against ASAs and construct the first sharing scheme that meets this notion. This work could serve as an important building block towards constructing systems secure against mass surveillance.

We present the first information-theoretic steganographic protocol with an asymptotically optimal ratio of key length to message length that operates on arbitrary covertext distributions with constant min-entropy. Our results are also applicable to the computational setting: our stegosystem can be composed over a pseudorandom generator to send longer messages in a computationally secure fashion. In this respect our scheme offers a significant improvement in terms of the number of pseudorandom bits generated by the two parties in comparison to previous results known in the computational setting. Central to our approach for improving the overhead for general distributions is the use of combinatorial constructions that have been found to be useful in other contexts for derandomization: almost $t$-wise independent function families.

For $q$ a prime power, the discrete logarithm problem (DLP) in $\\mathbb{F}_{q}^{\\times}$ consists in finding, for any $g \\in \\mathbb{F}_{q}^{\\times}$ and $h \\in \\langle g \\rangle$, an integer $x$ such that $g^x = h$. For each prime $p$ we exhibit infinitely many extension fields $\\mathbb{F}_{p^n}$ for which the DLP in $\\mathbb{F}_{p^n}^{\\times}$ can be solved in expected quasi-polynomial time.

Multi-server authentication is going to be an integral part of remote authentication with the passage of time. The remote authentication has been part and parcel of internet based communication. In the last decade several multi-server authentication techniques has been presented. However there is still a need of more efficient and robust techniques. Lately, Saraswathi et al., presented a multi-server authentication scheme that has been found under much vulnerability like stolen card attack, misrepresentation attack, and forward secrecy attacks. This paper presents the cryptanalysis for Saraswathi et al. scheme and shows the review analysis.

Cryptographic protocols, such as protocols for secure function evaluation (SFE), have played a crucial role in the development of modern cryptography. The extensive theory of these protocols, however, deals almost exclusively with classical attackers. If we accept that quantum information processing is the most realistic model of physically feasible computation, then we must ask: what classical protocols remain secure against quantum attackers?

Our main contribution is showing the existence of classical two-party protocols for the secure evaluation of any polynomial-time function under reasonable computational assumptions (for example, it suffices that the learning with errors problem be hard for quantum polynomial time). Our result shows that the basic two-party feasibility picture from classical cryptography remains unchanged in a quantum world.

In this paper, we show efficient implementations of binary field multiplication over ARMv8.

We exploit an advanced 64-bit polynomial multiplication (\\texttt{PMULL}) supported by ARMv8

and conduct multiple levels of asymptotically faster Karatsuba multiplication.

Finally, our method conducts binary field multiplication within 57 and 153 clock cycles for B-251 and B-571, respectively.

Our proposed method on ARMv8 improves the performance by a factor of $5.5 \\sim 7.2$ times than previous techniques on ARMv7.

Side channels provide additional information to skilled adversaries that reduce the effort to determine an unknown key. If sufficient side channel information is available, identification of the secret key can even become trivial. However, if not enough side information is available, some effort is still required to find the key in the key space (which now has reduced entropy). To understand the security implications of side channel attacks it is then crucial to evaluate this remaining effort in a meaningful manner. Quantifying this effort can be done by looking at two key questions: first, how `deep\' (at most) is the unknown key in the remaining key space, and second, how `expensive\' is it to enumerate keys up to a certain depth?

We provide results for these two challenges. Firstly, we show how to construct an extremely efficient algorithm that accurately computes the rank of a (known) key in the list of all keys, when ordered according to some side channel attack scores. Secondly, we show how our approach can be tweaked such that it can be also utilised to enumerate the most likely keys in a parallel fashion. We are hence the first to demonstrate that a smart and parallel key enumeration algorithm exists.

Dividing last level caches into slices is a popular method to prevent memory accesses from becoming a bottleneck on modern multicore processors. In order to assess and understand the benefits of cache slicing in detail, a precise knowledge of implementation details such as the slice selection algorithm are of high importance.

However, slice selection methods are mostly unstudied, and processor manufacturers choose not to publish their designs, nor their design rationale.

In this paper, we present a tool that allows to recover the slice selection algorithm for Intel processors. The tool uses cache access information to derive equations that allow the reconstruction of the applied slice selection algorithm. Thereby, the tool provides essential information for performing last level cache attacks and enables further exploration of the behavior of modern caches.

The tool is successfully applied to a range of Intel CPUs with different slices and architectures. Results show that slice selection algorithms have become more complex over time by involving an increasing number of bits of the physical address. We also demonstrate that among the most recent processors, the slice selection algorithm depends on the number of CPU cores rather than the processor model.

Emerging applications such as the Internet of Things require security solutions that are small and low cost, yet feature solid protection against a wide range of sophisticated attacks. Lightweight cryptographic schemes such as the Speck cipher that was recently proposed by the NSA aim to solve some of these challenges. However, before using Speck in any practical application, sound protection against side-channel attacks must be in place. In this work, we propose a bit-serialized implementation of Speck, to achieve minimal area footprint. We further propose a Speck core that is provably secure against first-order side-channel attacks using a threshold implementation technique which depends on secure multiparty computation. The resulting design is a tiny crypto core that provides AES-like security in under 45 slices on a low-cost Xilinx Spartan 3 FPGA. The first-order side-channel resistant version of the same core needs less than 100 slices. The security of the protected core is validated by state-of-the-art side-channel leakage detection tests.

We explicitly present a homomorphic encryption scheme with a flexible encoding of plaintexts. We prove its security under the LWE assumption, and innovatively show how the scheme can be used to handle computations over both binary strings and real numbers. In addition, using the scheme and its features, we build fast and secure systems of

- linear regression using gradient descent, namely finding a reasonable linear relation between data items which remain encrypted. Compared to the best previous work over a simulated dataset of $10^8$ records each with 20 features, our system dramatically reduces the server running time from about 8.75 hours (of the previous work) to only about 10 minutes.

- biometric authentication, in which we show how to reduce ciphertext sizes by half and to do the computation at the server very fast, compared with the state-of-the-art.

Moreover, as key rotation is a vital task in practice and is recommended by many authorized organizations for key management,

- we show how to do key rotation over encrypted data, without any decryption involved, and yet homomorphic properties of ciphertexts remain unchanged. In addition, our method of doing key rotation handles keys of different security levels (e.g., 80- and 128-bit securities), so that the security of ciphertexts and keys in our scheme can be \"updated\", namely can be changed into a higher security level.

Garbled circuits is a cryptographic technique, which has been used among other

things

for the construction of two and three-party secure computation, private

function evaluation and secure outsourcing. Garbling schemes is a primitive

which formalizes the syntax and security properties of garbled circuits.

We define a generalization of garbling schemes called \\emph{reactive garbling

schemes}.

We consider functions and garbled functions taking multiple inputs and giving

multiple outputs.

Two garbled functions can be linked together:

an encoded output of one garbled function can be transformed

into an encoded input of the other garbled function without communication

between the parties.

Reactive garbling schemes also allow partial evaluation of garbled functions

even when only some of the encoded inputs are provided.

It is possible to further evaluate the linked garbled functions

when more garbled inputs become available.

It is also possible to later garble more functions and link them to the

ongoing garbled evaluation.

We provide rigorous definitions for reactive garbling schemes.

We define a new notion of security for reactive garbling schemes called

confidentiality.

We provide both simulation based and indistinguishability based notions of

security.

We also show that the simulation based notion of security

implies the indistinguishability based notion of security.

We present an instantiation of reactive garbling schemes. We present an

application of reactive garbling schemes to reactive

two-party computation secure against a malicious adversary. We demonstrate

how garbling schemes can be used to give abstract black-box descriptions and

proof of several advanced applications of garbled circuits in the literature,

including Minilego

and Lindell\'s forge-and-loose technique.

We present a new constant round additively homomorphic commitment scheme with (amortized) computational and communication complexity linear in the size of the string committed to. Our scheme is based on the non-homomorphic commitment scheme of Cascudo \\emph{et al.} presented at PKC 2015. However, we manage to add the additive homomorphic property, while at the same time reducing the constants. In fact, when opening a large enough batch of commitments we achieve an amortized communication complexity converging to the length of the message committed to, i.e., we achieve rate $1$ as the commitment protocol by Garay \\emph{et al.} from Eurocrypt 2014. A main technical improvement over the scheme mentioned above, and other schemes based on using error correcting codes for UC commitment, we develop a new technique which allows to based the extraction property on erasure decoding as opposed to error correction. This allows to use a code with significantly smaller minimal distance and allows to use codes without efficient decoding.

Our scheme only relies on standard assumptions. Specifically we require a pseudorandom number generator, a linear error correcting code and an ideal oblivious transfer functionality. Based on this we prove our scheme secure in the Universal Composability (UC) framework against a static and malicious adversary corrupting any number of parties.

On a practical note, our scheme improves significantly on the non-homomorphic scheme of Cascudo \\emph{et al.} Based on their observations in regards to efficiency of using linear error correcting codes for commitments we conjecture that our commitment scheme might in practice be more efficient than all existing constructions of UC commitment, even non-homomorphic constructions and even constructions in the random oracle model. In particular, the amortized price of computing one of our commitments is less than that of evaluating a hash function once.

Kleptography, originally introduced by Young and Yung [Crypto \'96],

studies how to steal information securely and subliminally from cryptosystems.

Secure cryptosystems can be broken if they are maliciously implemented

since the adversary may have some backdoors embedded in the implementation.

Although kleptographic attacks have been investigated about two decades ago,

for too long the possibility of kleptographic attacks have been dismissed and

been viewed only as a far-fetched theoretical concept.

This is dramatically changed when real-world examples were recently revealed

by Edward Snowden, demonstrating that such deliberate attacks

(directly inspired by the original work) exist and probably have been used for massive surveillance. In light of such possible failures of basic protective technology,

the security community started to seriously re-investigate this important issue: one notable example is the work of

Bellare, Paterson, and Rogaway [Crypto \'14], which initiated the formal studies of attacks on symmetric key encryption algorithms.

Motivated by the original examples of subverting key generation algorithms in the kleptography papers from Young and Yung [Crypto \'96, Eurocrypt \'97], we initiate the study of cryptography in the case that {\\em all} algorithms are subject to kleptographic attacks---we call it {\\bf cliptography}. As a first step, we formally study the fundamental primitives of one-way function and trapdoor one-way function in this complete subversion model. And more interesting, we investigate the general immunization strategy to clip the power of kleptographic subversions; concretely, we propose a general framework for sanitizing the (trapdoor) one-way function generation algorithm by hashing the function index, and prove that such procedure indeed destroys the connection between a subverted function generation procedure and any possible backdoor. Along the way, we propose a split program model for practical deployment.

We then examine the applications of (trapdoor) one way function secure in the complete subversion model in two ways. First we consider to build ``higher level\" primitives via black-box reductions. In particular, we consider how to use our trapdoor one-way function to defend against key generation sabotage, and showcase a digital signature scheme that preserves existential unforgeability when {\\em all} algorithms (including key generation, which was not considered to be under attack before) are subject to kleptographic attacks.

Also we demonstrate that the classic Blum-Micali pseudorandom generator (PRG) using our ``unforgeable\" one-way function yields a backdoor-free PRG. Second, we generalize our immunizing technique for one way functions, and

propose a new public immunization strategy to randomize the public parameters of a (backdoored) PRG. Since the previous result by Dodis, Ganesh, Golovnev, Juels, and Ristenpart~[Eurocrypt \'15] requires an honestly generated random key, construction of secure PRG in the complete subversion model was also open until our paper.

This report describes the design and implementation results in FPGAs of a scalable hardware architecture for computing modular multiplication in prime fields GF($p$), based on the Montgomery multiplication (MM) algorithm. Starting from an existing digit-serial version of the MM algorithm, a novel {\\it digit-digit} based MM algorithm is derived and two hardware architectures that compute that algorithm are described. In the proposed approach, the input operands (multiplicand, multiplier and modulus) are represented using as radix $\\beta = 2^k$. Operands of arbitrary size can be multiplied with modular reduction using almost the same hardware since the multiplier\'s kernel module that performs the modular multiplication depends only on $k$. The novel hardware architectures proposed in this paper were verified by modeling them using VHDL and implementing them in the Xilinx FPGAs Spartan and Virtex5. Design trade-offs are analyzed considering different operand sizes commonly used in cryptography and different values for $k$. The proposed designs for MM are well suited to be implemented in modern FPGAs, making use of available dedicated multiplier and memory blocks reducing drastically the FPGA\'s standard logic while keeping an acceptable performance compared with other implementation approaches. From the Virtex5 implementation, the proposed MM multiplier reaches a throughput of 242Mbps using only 219 FPGA slices and achieving a 1024-bit modular multiplication in 4.21$\\mu$secs.

Recently, in Journal of Security and Communication Networks (5(12):1363-1374, DOI: 10.1002/sec.429), Wang et al. proposed a group key distribution scheme with self-healing property for wireless networks in which resource is constrained. They claimed that their key distribution scheme satisfies forward security, backward security and can resist collusion attack. Unfortunately, we found some security flaws in their scheme. In this paper, we present a method to attack this scheme. The attack illustrates that this scheme does not satisfy forward security, which also directly breaks the collusion resistance capability.

Recently, ChaCha20 (the stream cipher ChaCha with 20 rounds) is in the process of being a standard and thus it attracts serious interest in cryptanalysis. The most significant effort to analyse Salsa and ChaCha had been explained by Aumasson et al long back (FSE 2008) and further, only minor improvements could be achieved. In this paper, first we revisit the work of Aumasson et al to provide a clearer insight of the existing attack (2^{248} complexity for ChaCha7, i.e., 7 rounds) and showing certain improvements (complexity around 2^{243}) by exploiting additional Probabilistic Neutral Bits. More importantly, we describe a novel idea that explores proper choice of IVs corresponding to the keys, for which the complexity can be improved further (2^{239}). The choice of IVs corresponding to the keys is the prime observation of this work. We systematically show how a single difference propagates after one round and how the differences can be reduced with proper choices of IVs. For Salsa too (Salsa20/8, i.e., 8 rounds), we get improvement in complexity, reducing it to 2^{245.5} from 2^{247.2} reported by Aumasson et al.

This paper proposes design of a Fully Homomorphic Ultimate RISC (FURISC) based

processor. The FURISC architecture supports arbitrary operations on data encrypted

with Fully Homomorphic Encryption (FHE) and allows the execution of encrypted programs stored in processors with encrypted memory addresses. The FURISC architecture is designed based on fully homomorphic single RISC instructions like {\\em Subtract Branch if Negative} (SBN) and {\\em MOVE}. This paper explains how the use of FHE for designing the ultimate RISC processor is better in terms of security compared to previously proposed somewhat homomorphic encryption (SHE) based processor. The absence of randomization in SHE can lead to Chosen Plaintext Attacks (CPA) which is alleviated by the use of the FHE based Ultimate RISC instruction. Furthermore, the use of FURISC helps to develop fully homomorphic applications by tackling the {\\em termination} problem, which is a major obstacle for FHE processor design. The paper compares the MOVE based FHE RISC processor with the SBN alternative, and shows that the later is more efficient in terms of number of instructions and time required for the execution of a program. Finally, an SBN based FURISC processor simulator has been designed

to demonstrate that various algorithms can indeed be executed on data encrypted with FHE, providing a solution to the termination problem for FHE based processors and the CPA insecurity of SHE processors simultaneously.