International Association
for Cryptologic Research

GOST 28147-89 is a well-known Russian government encryption standard. Its large key size of 256 bits at a particularly low implementation cost make that it is widely implemented and used, in OpenSSL and elsewhere. In 2010 GOST was submitted to ISO to become an international standard. GOST was analysed by Schneier, Biham, Biryukov, Dunkelman, Wagner, various Australian, Japanese, and Russian scientists, and all researchers seemed to agree that it looks quite secure. Though the internal structure of GOST seems quite weak compared to DES, and in particular the diffusion is not quite as good, it is always stipulated that this should be compensated by a large number of 32 rounds and by the additional non-linearity and diffusion provided by modular additions. At Crypto 2008 the hash function based on this cipher was broken. Yet as far as traditional encryption applications with keys generated at random are concerned, until 2011 no cryptographically significant attack on GOST was found. In this paper we present several new attacks on full 32-rounds GOST. Our methodology is derived from the idea of conditional algebraic attacks on block ciphers which can be defined as attacks in which the problem of key recovery is written as a problem of solving a large system of algebraic equations, and where the attacker makes some \"clever\" assumptions on the cipher which lead to an important simplification in the algebraic description of the problem, which makes it solvable in practice if the assumptions hold. Our methods work by black box reduction and allow to literally break the cipher apart into smaller pieces and reduce breaking GOST to a low data complexity software/algebraic/MITM attack on 8 or less rounds. Overall we obtain some 60 distinct attacks faster than brute force on the full 32-round GOST and we provide five nearly practical attacks on two major 128-bit variants of GOST (cf. Table 6). Our single key attacks are summarized in Table 3 p.53 and Table 7 p.153 and attacks with multiple keys in Table 4 page 128.

Beimel and Orlov proved that all information inequalities on four or five variables, together with all information inequalities on more than five variables that are known to date, provide lower bounds on the size of the shares in secret sharing schemes that are at most linear on the number of participants. We present here another two negative results about the power of information inequalities in the search for lower bounds in secret sharing. First, we prove that all information inequalities on a bounded number of variables can only provide lower bounds that are polynomial on the number of participants. And second, we prove that the rank inequalities that are derived from the existence of two common informations can provide only lower bounds that are at most cubic in the number of participants.

We study homomorphic hash functions into SL(2,q), the 2x2 matrices with determinant 1 over the

field with $q$ elements.

Modulo a well supported number theoretic hypothesis, which holds in particular for concrete

homomorphisms proposed thus far, we provide a worst case to average case reduction for these hash functions:

upto a logarithmic factor, a random homomorphism is as secure as _any_ concrete homomorphism.

For a family of homomorphisms containing several concrete proposals in the literature,

we prove that collisions of length O(log(q)) can be found in running time O(sqrt(q)).

For general homomorphisms we offer an algorithm that, heuristically and according to experiments,

in running time O(sqrt(q)) finds collisions of length O(log(q)) for q even, and length O(log^2(q)/loglog(q))$ for arbitrary q.

While exponetial time, our algorithms are faster in practice than all earlier generic algorithms,

and produce much shorter collisions.

Goldwasser and Micali (1984) highlighted the importance of randomizing the plaintext for public-key encryption and introduced the notion of semantic security. They also realized a cryptosystem meeting this security notion under the standard complexity assumption of deciding quadratic residuosity modulo a composite number. The Goldwasser-Micali cryptosystem is simple and elegant but is quite wasteful in bandwidth when encrypting large messages. A number of works followed to address this issue and proposed various modifications.

This paper revisits the original Goldwasser-Micali cryptosystem using 2^k-th power residue symbols. The so-obtained cryptosystems appear as a very natural generalization for k >= 2 (the case k = 1 corresponds exactly to the Goldwasser-Micali cryptosystem). Advantageously, they are efficient in both bandwidth and speed; in particular, they allow for fast decryption. Further, the cryptosystems described in this paper inherit the useful features of the original cryptosystem (like its homomorphic property) and are shown to be secure under a similar complexity assumption. As a prominent application, this paper describes an efficient lossy trapdoor function based thereon.

We propose constructions of fully homomorphic encryption completely different from the previous work, using special kinds of non-commutative finite groups. Unlike the existing schemes, our ciphertexts involve no \"noise\" terms, hence the inefficient \"bootstrapping\" procedures are not necessary. Our first scheme is based on improved results on embeddings of logic gates into (almost) simple groups [Ostrovsky and Skeith III, CRYPTO 2008]. Our second scheme is based on properties of the commutator operator (analogous to those used in Barrington\'s theorem) and a new idea of input rerandomization for commutators, effective for some (almost) simple matrix groups. Our main idea is to conceal the concrete structures of the underlying groups by randomly applying some special transformations famous in combinatorial group theory, called Tietze transformations, to a kind of symbolic representations of the groups. Ideally, the resulting group is expected to behave like a black-box group where only an abstract group structure is available; a detailed analysis of the true effect of random Tietze transformations on the security is a future research topic. We emphasize that such a use of Tietze transformations in cryptology has no similar attempts in the literature and would have rich potential for further applications to other areas in cryptology.

Zk-SNARKs (succinct non-interactive zero-knowledge arguments of knowledge) are needed in many applications. Unfortunately, all previous zk-SNARKs for interesting languages are either inefficient for prover, or are non-adaptive and based on an commitment scheme that does depend both on the prover\'s input and on the language, i.e., they are not commit-and-prove (CaP) SNARKs. We propose a proof-friendly extractable commitment scheme, and use it to construct prover-efficient adaptive CaP succinct zk-SNARKs for different languages, that can all reuse committed data. In new zk-SNARKs, the prover computation is dominated by a linear number of cryptographic operations. We use batch-verification to decrease the verifier\'s computation.

The adjacency graphs of feedback shift registers (FSRs) with characteristic function of the form g=(x_0+x_1)*f are considered in this paper. Some properties about these FSRs are given. It is proved that these FSRs contains only prime cycles and these cycles can be divided into two sets such that each set contains no adjacent cycles. When f is a linear function, more properties about these FSRs are derived. It is shown that, when f is a linear function and contains an odd number of terms, the adjacency graph of \\mathrm{FSR}((x_0+x_1)*f) can be determined directly from the adjacency graph of \\mathrm{FSR}(f). As an application of these results, we determine the adjacency graphs of \\mathrm{FSR}((1+x)^4p(x)) and \\mathrm{FSR}((1+x)^5p(x)), where p(x) is a primitive polynomial, and construct a large class of de Bruijn sequences from them.

In this paper, a general way to determine the adjacency graph of linear feedback shift registers (LFSRs) with characteristic polynomial (1+x)c(x) from the adjacency graph of LFSR with characteristic polynomial c(x) is discussed, where c(x) can be any polynomial. As an application, the adjacency graph of LFSRs with characteristic polynomial (1+x)^4p(x) are determined, where p(x) is a primitive polynomial. Besides, some properties about the cycles in LFSRs are presented.

The adjacency graph of LFSRs with characteristic polynomial (1+x)^mp(x) are also discussed.

This report summarizes our results from security

analysis covering all 57 CAESAR first round candidates and over 210

implementations. We have manually

identified security issues with three candidates, two of which are

more serious, and these ciphers been withdrawn from the competition.

We have developed a testing framework, BRUTUS, to facilitate automatic

detection of simple security lapses and susceptible statistical

structures across all ciphers.

From this testing we have security usage notes on four submissions and

statistical notes on a further four. We highlight that some of the CAESAR

algorithms pose an elevated risk if employed in real-life protocols due

to a class of adaptive chosen plaintext attacks. Although AEADs are often

defined (and are best used) as discrete primitives that authenticate and

transmit only complete messages, in practice these algorithms are

easily implemented in a fashion that outputs observable ciphertext data

when the algorithm has not received all of the (attacker-controlled)

plaintext. For an implementor, this strategy

appears to offer seemingly harmless and compliant storage and latency

advantages. If the algorithm uses the same state for secret

keying information, encryption, and integrity protection, and the

internal mixing permutation is not cryptographically strong, an attacker

can exploit the ciphertext-plaintext feedback loop to reveal secret

state information or even keying material. We conclude that

the main advantages of exhaustive, automated cryptanalysis is that it

acts as a very necessary sanity check for implementations and gives the

cryptanalyst insights that can be used to focus more specific attack

methods on given candidates.

This paper provides the first efficient, standard-model, fully-secure schemes for some related and challenging forms of public-key encryption (PKE), namely deterministic and hedged PKE. These forms of PKE defend against subversion of random number generators, an end given new urgency by recent revelations on the nature and extent of such subversion. We resolve the (recognized) technical challenges in reaching these goals via a new paradigm that combines UCEs (universal computational extractors) with LTDFs (lossy trapdoor functions). Crucially, we rely only on a weak form of UCE, namely security for statistically (rather than computationally) unpredictable sources. We then define and achieve unique-ciphertext PKE as a way to defend against implementation subversion via algorithm-substitution attacks.

We present Onion ORAM, an Oblivious RAM (ORAM) with constant worst-case bandwidth blowup that leverages poly-logarithmic server computation to circumvent the logarithmic lower bound on ORAM bandwidth blowup. Our construction does not require fully homomorphic encryption, but employs an additively homomorphic encryption scheme such as the Damgard-Jurik cryptosystem, or alternatively a BGV-style somewhat homomorphic encryption scheme without bootstrapping. At the core of our construction is an ORAM scheme that has \"shallow circuit depth\" over the entire history of ORAM accesses. We also propose novel techniques to achieve security against a malicious server, without resorting to expensive and non-standard techniques such as SNARKs. To the best of our knowledge, Onion ORAM is the first concrete instantiation of a constant bandwidth blowup ORAM under standard assumptions (even for the

semi-honest setting).

Lattice based encryption schemes and linear code based encryption schemes have received extensive attention in recent years since they have been considered as post-quantum candidate encryption schemes. Though LLL reduction algorithm has been one of the major cryptanalysis techniques for lattice based cryptographic systems, key recovery cryptanalysis techniques for linear code based cryptographic systems are generally scheme specific. In recent years, several important techniques such as Sidelnikov-Shestakov attack, filtration attacks, and algebraic attacks have been developed to crypt-analyze linear code based encryption schemes. Though most of these cryptanalysis techniques are relatively new, they prove to be very powerful and many systems have been broken using them. Thus it is important to design linear code based cryptographic systems that are immune against these attacks. This paper proposes linear code based encryption schemes RLCE and bRLCE which share many characteristics with random linear codes. Our analysis shows that the schemes RLCE and bRLCE are secure against existing attacks and we hope that the security of the RLCE/bRLCE schemes is equivalent to the hardness of decoding random linear codes. Example parameters for different security levels are recommended for the schemes RLCE and bRLCE. It is expected that the scheme RLCE with Reed-Solomon code has smaller public key sizes and is more efficient than Goppa code based McEliece encryption scheme.

This paper describes the design, implementation, and evaluation of Popcorn, a media content delivery system that provably hides clients\' media consumption. Popcorn relies on a powerful cryptographic primitive: private information retrieval (PIR). With novel refinements that leverage the properties of PIR protocols and of media streaming, we have developed a system that cheaply hides media consumption, scales to the size of Netflix\'s library (8,000 movies), and respects current controls on media dissemination. The per-request cost in Popcorn is 3.87x the per-request cost of a non-private system.

We propose a decentralized cryptocurrency called Spacemint, which is based on a block chain

ledger similar to that of Bitcoin, but where the wasteful proofs of

work are replaced by efficient \\emph{proofs of space}, recently introduced by

Dziembowski et al. Instead of requiring that a majority of the network\'s

computing power is controlled by honest miners (as in Bitcoin), our

currency requires that honest miners dedicate more net disk space than a

potential adversary.

In Spacemint, once a miner has dedicated and initialized some space,

participating in the mining process is very cheap. A new block is

added to the chain every fixed period of time, and in every period a

miner just has to make a small number of lookups to the stored space

to check if she ``wins\", and thus can efficiently add the next block

to the chain and get the mining reward. In this paper, we detail the

construction of Spacemint, analyze its security and

game-theoretic properties, and study its performance.

Our prototype shows that it takes approximately 25 seconds to prove

over a terabyte of space, and it takes a fraction of a second to verify the proof.

Functional encryption is a modern public-key paradigm where a master

secret key can be used to derive sub-keys $SK_F$ associated with

certain functions $F$ in such a way that the decryption operation

reveals $F(M)$, if $M$ is the encrypted message, and nothing

else. Recently, \\mbox{Abdalla} {\\it et al.} gave simple and

efficient realizations of the primitive for the computation of

linear functions on encrypted data: given an encryption of a vector

$\\vec{y}$ over some specified base ring, a secret key $SK_{\\vec{x}}$ for the vector $\\vec{x}$ allows computing $\\langle \\vec{x} ,\\vec{y} \\rangle$. Their technique surprisingly allows for instantiations under standard assumptions, like the hardness of the Decision Diffie-Hellman (DDH) and Learning-with-Errors (LWE) problems. Their constructions, however, are only proved secure against selective adversaries, which have to declare the challenge messages $M_0$ and $M_1$ at the outset of the game.

In this paper, we provide constructions that provably achieve security

against more realistic {\\it adaptive} attacks (where the messages

$M_0$ and $M_1$ may be chosen in the challenge phase, based on the

previously collected information) for the same inner product functionality. Our constructions are obtained from hash proof systems endowed with homomorphic properties over the key space. They are (almost) as efficient as those of Abdalla {\\it et al.} and rely on the same hardness assumptions.

In addition, we obtain a solution based on Paillier\'s composite

residuosity assumption, which was an open problem even in the case

of selective adversaries. We also propose $\\LWE$-based schemes that

allow evaluation of inner products modulo a prime~$p$, as opposed to

the schemes of Abdalla {\\it et al.} that are restricted to evaluations of integer inner products of short integer vectors. We finally propose a solution based on Paillier\'s composite residuosity

assumption that enables evaluation of inner products modulo an RSA integer $N = pq$.

We demonstrate that the functionality of inner products over a prime field is very powerful and can be used to construct bounded collusion FE for all circuits.

We study the question of how much interaction is needed for unconditionally secure multiparty computation. We first consider the number of messages that need to be sent to compute a Boolean function with semi-honest security, where all n parties learn the result. We consider two classes of functions called t-difficult and t-very difficult functions, here t refers to the number of corrupted players. One class is contained in the other. For instance, the AND of an input bit from each player is t-very difficult while the XOR is t- difficult but not t-very difficult. We show lower bounds on the message complexity of both types of functions, considering two notions of message complexity called conservative and liberal, where the conservative one is the more standard one. In all cases the bounds are Ω(nt). We also show upper bounds for t = 1 and functions in deterministic log-space, as well as a stronger upper bound for the XOR function. This matches the lower bound for conservative complexity, so we find that the conservative message complexity of 1-very difficult functions in deterministic log space is 2n, while the conservative message complexity for XOR (and t = 1) is 2n − 1.

Next, we consider round complexity. It is a long-standing open problem to determine whether all efficiently computable functions can also be efficiently computed in constant-round with unconditional security. Motivated by this, we consider the question of whether we can compute any function securely, while minimizing the interaction of some of the players? And if so, how many players can this apply to? Note that we still want the standard security guarantees (correctness, privacy, termi- nation) and we consider the standard communication model with secure point-to-point channels. We answer the questions as follows: for passive security, with n = 2t + 1 players and t corruptions, up to t players can have minimal interaction, i.e., they send 1 message in the first round to each of the t + 1 remaining players and receive one message from each of them in the last round. Using our result on message complexity, we show that this is (unconditionally) optimal. For malicious security with n = 3t + 1 players and t corruptions, up to t players can have minimal interaction, and we show that this is also optimal.

Many cryptographic schemes have been established based on the hardness of lattice problems. For the asymptotic efficiency, ideal lattices in the ring of cyclotomic integers are suggested to be used in most such schemes. On the other hand in computational algebraic number theory one of the main problem is the principal ideal problem (PIP). Its goal is to find a generator of any principal ideal in the ring of algebraic integers in any number field. In this paper we give a polynomial time reduction from approximate shortest lattice vector problem for principal ideal lattices to their PIP\'s in cyclotomic integer rings of extension degrees $\\phi(n)=2^{k-1}, k=2,3,\\ldots$. Thus if a polynomial time quantum algorithm for PIP of arbitrary number fields could be proposed, this would implies that approximate SVP problem for principal ideal lattices within a polynomial factor in this kind cyclotomic integer rings can be solved by a polynomial time quantum algorithm.

Universal hash functions (UHFs) have been extensively used in the design of cryptographic schemes. If we consider the related-key attack against these UHF-based schemes, some of them may not be secure, especially those using the key of UHF as a part of the whole key of scheme, due to the weakness of UHF in the related-key setting. 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 setting. 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 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 (RK-AXU) hash functions can be used as components in the related-key secure 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 related-key secure MACs and TBCs.

The purpose of this paper is to compare side-by-side the NTRU and BGV schemes in their non-scale invariant (messages in the lower bits), and their scale invariant (message in the upper bits) forms. The scale invariant versions are often called the FV and YASHE schemes. As an additional optimization, we also investigate the affect of modulus reduction on the scale-invariant schemes. We compare the schemes using the ``average case\'\' noise analysis presented by Gentry et al. In addition we unify notation and techniques so as to show commonalities between the schemes. We find that the BGV scheme appears to be more efficient for large plaintext moduli, whilst YASHE seems more efficient for small plaintext moduli (although the benefit is not as great as one would have expected).

Security parameters and attack countermeasures for Lattice-based

cryptosystems have not yet matured to the level that we now expect

from RSA and Elliptic Curve implementations.

Many modern Ring-LWE and other lattice-based public key algorithms

require high precision random sampling from the Discrete Gaussian

distribution. The sampling procedure often represents the biggest

implementation bottleneck due to its memory and computational requirements.

We examine the stated requirements of precision for Gaussian

samplers, where statistical distance to the theoretical distribution is

typically expected to be below $2^{-90}$ or $2^{-128}$ for

90 or 128 ``bit\'\' security level.

We argue that such precision is excessive and give precise

theoretical arguments why half of the precision of the security parameter

is almost always sufficient. This leads to faster and more

compact implementations; almost halving implementation size in both

hardware and software.

We observe that many of the proposed algorithms for discrete Gaussian

sampling may leak significant amounts of secret information in easily

mounted timing attacks. We further offer new recommendations for practical

samplers.