International Association
for Cryptologic Research

In this paper, we show implementation results of various algorithms that sort data encrypted with Fully Ho- momorphic Encryption scheme based on Integers. We analyze the complexities of sorting algorithms over encrypted data by considering Bubble Sort, Insertion Sort, Bitonic Sort and Odd- Even Merge sort. Our complexity analysis together with imple- mentation results show that Odd-Even Merge Sort has better performance than the other sorting techniques. We observe that complexity of sorting in homomorphic domain will always have worst case complexity independent of the nature of input. In addition, we show that combining different sorting algorithms to sort encrypted data does not give any performance gain when compared to the application of sorting algorithms individually.

Three recent proposals for standardization of next-generation ECC signatures have included \"key prefixing\" modifications to Schnorr\'s signature system. Bernstein, Duif, Lange, Schwabe, and Yang stated in 2011 that key prefixing is \"an inexpensive way to alleviate concerns that several public keys could be attacked simultaneously\".

However, a 2002 theorem by Galbraith, Malone-Lee, and Smart states that, for the classic Schnorr signature system, single-key security tightly implies multi-key security. Struik and then Hamburg, citing this theorem, argued that key prefixing was unnecessary for multi-user security and should not be standardized.

This paper identifies an error in the 2002 proof, and an apparently insurmountable obstacle to the claimed theorem. The proof idea does, however, lead to a different theorem, stating that single-key security of the classic Schnorr signature system tightly implies multi-key security of the key-prefixed variant of the system. This produces exactly the opposite conclusion regarding standardization.

Recent advances in program obfuscation suggest that it is possible to create software that can provably safeguard secret information. However, software systems usually contain large executable code that is updated multiple times and sometimes very frequently. Freshly obfuscating the program for every small update will lead to a considerable efficiency loss. Thus, an extremely desirable property for obfuscation algorithms is {\\em incrementality}: small changes to the underlying program translate into small changes to the corresponding obfuscated program.

We initiate a thorough investigation of {\\em incremental program obfuscation}. We show that the strong simulation-based notions of program obfuscation, such as ``virtual black-box\'\' and ``virtual grey-box\'\' obfuscation, cannot be incremental even for very simple functions such as point functions. We then turn to the indistinguishability-based notions, and present two security definitions of varying strength. To understand the overall strength of our definitions, we formulate the notion of {\\em incremental best-possible obfuscation} and show that it is equivalent to our (stronger) indistinguishability-based notion.

Finally, we present constructions for incremental program obfuscation satisfying both our security notions. We first give a construction achieving the weaker security notion based on the existence of general purpose indistinguishability obfuscation. Next, we present a generic transformation using {\\em oblivious RAM} to amplify security from weaker to stronger, while maintaining the incrementality property.

We continue a study of unconditionally secure all-or-nothing transforms (AONT) begun in \\cite{St}. An AONT is a bijective mapping that constructs $s$ outputs from $s$ inputs. We consider the security of $t$ inputs, when $s-t$ outputs are known. Previous work concerned the case $t=1$; here we consider the problem for general $t$, focussing on the case $t=2$. We investigate constructions of binary matrices for which the desired properties hold with the maximum probability. Upper bounds on these probabilities are obtained via a quadratic programming approach, while lower bounds can be obtained from combinatorial constructions based on symmetric BIBDs and cyclotomy. We also report some results on exhaustive searches and random constructions for small values of $s$.

A popular approach to tweakable blockcipher design is via masking, where a certain primitive (a blockcipher or a permutation) is preceded and followed by an easy-to-compute tweak-dependent mask. In this work, we revisit the principle of masking. We do so alongside the introduction of the tweakable Even-Mansour construction MEM. Its masking function combines the advantages of word-oriented LFSR- and powering-up-based methods. We show in particular how recent advancements in computing discrete logarithms over finite fields of characteristic 2 can be exploited in a constructive way to realize highly efficient, constant-time masking functions. If the masking satisfies a set of simple conditions, then MEM is a secure tweakable blockcipher up to the birthday bound. The strengths of MEM are exhibited by the design of fully parallelizable authenticated encryption schemes OPP (nonce-respecting) and MRO (misuse-resistant). If instantiated with a reduced-round BLAKE2b permutation, OPP and MRO achieve speeds up to 0.55 and 1.06 cycles per byte on the Intel Haswell microarchitecture, and are able to significantly outperform their closest competitors.

In order to remove any suspicion we have published a note on constants origin some time ago. If someone does not now about it yet - there is the link below: http://www.tc26.ru/en/ISO_IEC/streebog/streebog_constants_eng.pdf From: 2015-13-10 21:01:58 (UTC)

In this paper we analyse two variants of SIMON family of light-weight block ciphers against

linear cryptanalysis and present the best linear cryptanalytic results on these variants of reduced-round SIMON to date.

We propose a time-memory trade-off method that finds differential/linear trails for any permutation allowing

low Hamming weight differential/linear trails. Our method combines low Hamming weight trails found by the correlation matrix representing the target permutation with heavy Hamming weight trails

found using a Mixed Integer Programming model representing the target differential/linear trail. Our method enables us to find a 17-round linear approximation for

SIMON-48 which is the best current linear approximation for SIMON-48. Using only the correlation matrix method, we are able to find a 14-round linear approximation for SIMON-32 which is also the current best linear approximation for SIMON-32.

The presented linear approximations allow us to mount a 23-round key recovery attack on SIMON-32 and a 24-round Key recovery attack on SIMON-48/96 which are the current best results on SIMON-32 and SIMON-48. In addition we have an attack on 24 rounds of SIMON-32 with marginal complexity.

We present an actively secure multi-party computation the of the Advanced Encryption Standard (AES). To the best of our knowledge it is the fastest of its kind to date. We start from an efficient actively secure evaluation of general binary circuits that was implemented by the authors of [DLT14]. They presented an optimized implementation of the so-called MiniMac protocol [DZ13] that runs in the pre-processing model, and applied this to a binary AES circuit.

In this paper we describe how to dedicate the pre-processing to the structure of AES, which improves significantly the throughput and latency of previous actively secure implementations. We get a latency of about 6 ms and amortised time about 0.4 ms per AES block,

which seems completely adequate for practical applications such as verification of 1-time passwords.

We put forth a novel cryptographic primitive: encryption switching protocol (ESP), allowing to switch between two encryption schemes. Intuitively, this two-party protocol converts given ciphertexts from one scheme into ciphertexts of the same messages in the other scheme, for any polynomial number of switches, in any direction.

Although ESP is a special kind of two-party computation protocol, it turns out that ESP implies general two-party computation under natural conditions. In particular, our new paradigm is tailored to the evaluation of functions over rings. Indeed, assuming the compatibility of two additively and multiplicatively homomorphic encryption schemes, switching ciphertexts makes it possible to efficiently reconcile the two internal laws.

Since no such pair of schemes appeared in the literature, except for the non-interactive case of fully homomorphic encryption which still remains prohibitive in practice, we build the first ElGamal-like encryption scheme over (Zn;x) as a complement to the Paillier encryption scheme over (Zn;+), where n is a strong RSA modulus. Eventually, we also instantiate secure ESP between the two schemes, in front of malicious adversaries. Thanks to a pre-processing step, we manage to get an online communication in terms of group elements which neither depends on the security parameter nor on the modulus n. This makes use of a new technique called refreshable twin-ciphertext pool that is of independent interest.

We propose a new Elliptic curve at a security level significantly greater than the standard 128 bits, that fills a gap in current proposals while bucking the expected security vs cost curve by exploiting the new trick recently described by Granger and Scott. This essentially reduces the cost of field multiplication to that of a field squaring.

Cryptographic multilinear map is a useful tool for constructing numerous secure protocols and Graded Encoding System (GES) is an {\\em approximate} concept of multilinear map. In multilinear map context, there are several important issues, mainly about security and efficiency. All early stage candidate multilinear maps are recently broken by so-called zeroizing attack, so that it is highly required to develop reliable mechanisms to prevent zeroizing attacks. Moreover, the encoding size in all candidate multilinear maps grows quadratically in terms of multilinearity parameter $\\kappa$ and it makes them less attractive for applications requiring large $\\kappa$.

In this paper, we propose a new integer-based multilinear map that has several advantages over previous schemes. In terms of security, we expect that our construction is resistant to the zeroizing attack. In terms of efficiency, the bit-size of an encoding grows sublinearly with $\\kappa$, more precisely $O((\\log_2\\kappa)^2)$.

To this end, we essentially utilize a technique of the multiplication procedure in {\\em scale-invariant} fully homomorphic encryption (FHE), which enables to achieve sublinear complexity in terms of multilinearity and at the same time security against the zeroizing attacks (EUROCRYPT 2015, IACR-Eprint 2015/934, IACR-Eprint 2015/941), which totally broke Coron, Lepoint, and Tibouchi\'s integer-based construction (CRYPTO 2013, CRYPTO2015). We find that the technique of scale-invariant FHE is not very well harmonized with previous approaches of making GES from (non-scale-invariant) FHE. Therefore, we first devise a new approach for approximate multilinear maps, called {\\em Ring Encoding System (RES)}, and prove that a multilinear map built via RES is generically secure. Next, we propose a new efficient scale-invariant FHE with special properties, and then construct a candidate RES based on a newly proposed scale-invariant FHE.

It is worth noting that, contrary to the CLT multilinear map (CRYPTO 2015), multiplication procedure in our construction does not add hidden constants generated by ladders of zero encodings, but mixes randoms in encodings in non-linear ways without using ladders of zero encodings. This feature is obtained by using the scale-invariant FHE and essential to prevent the Cheon et al.\'s zeroizing attack.

Deniable encryption (Canetti et al. CRYPTO \'97) is an intriguing primitive that provides a security guarantee against not only eavesdropping attacks as required by semantic security, but also stronger coercion attacks performed after the fact. The concept of deniability has later demonstrated useful and powerful in many other contexts, such as leakage resilience, adaptive security of protocols, and security against selective opening attacks. Despite its conceptual usefulness, our understanding of how to construct deniable primitives under standard assumptions is restricted. In particular, from standard assumptions such as Learning with Errors (LWE), we have only multi-distributional or non-negligible advantage deniable encryption schemes, whereas with the much stronger assumption of indistinguishable obfuscation, we can obtain at least fully-secure sender-deniable PKE and computation. How to achieve deniability for other more advanced encryption schemes under standard assumptions remains an interesting open question.

In this work, we construct a bi-deniable inner product encryption (IPE) in the multi-distributional model without relying on obfuscation as a black box. Our techniques involve new ways of manipulating Gaussian noise, and lead to a significantly tighter analysis of noise growth in Dual Regev type encryption schemes. We hope these ideas can give insight into achieving deniability and related properties for further, advanced cryptographic constructions under standard assumptions.

As the new SHA-3 standard, the side-channel security of Keccak has attracted a lot of attentions. Some works show that both software and hardware implementation of Keccak have strong side-channel leakages, and these leakages can be used easily by an attacker to recover secret key information. Secret sharing schemes are introduced to mask the leakages, while such schemes will incur large resource overhead. In this paper, we introduce another scheme based on the round rotation probability of Keccak to reduce the side-channel leakages. This scheme is easy to implement while it can efficiently help to reduce the side-channel leakages of Keccak.

Submission: 15 November 2015
Notification: 20 November 2015
From January 25 to January 29
Location: Darmstadt, Germany
More Information: https://www.crossing.tu-darmstadt.de/en/news-events/winter-school-2016/

Description: The University of Luxembourg is offering a Ph.D. student position in one of the topics:

• cryptofinance, cryptocurrencies
• anonymity and privacy
• cybersecurity

Applicants interested in symmetric cryptography, authenticated encryption will be also considered.

Profile:

• An M.Sc. in Computer Science or Applied Mathematics (some background in Economics/Finance is a plus)
• GPA > 80%
• Fluent written and verbal communication skills in English are mandatory.

We offer international research environment and competitive salary. The position is already available. Applications will be considered upon receipt, therefore applying before the deadline is encouraged.

Recently, several new techniques were presented to dramatically improve key parts of secure two-party computation (2PC) protocols that use the cut-and-choose paradigm on garbled circuits for 2PC with security against malicious adversaries. These include techniques for reducing the number of garbled circuits (Lindell 13, Huang et al.~13, Lindell and Riva 14, Huang et al.~14) and techniques for reducing the overheads besides garbled circuits (Mohassel and Riva 13, Shen and Shelat~13).

We design a highly optimized protocol in the offline/online setting that makes use of all state-of-the-art techniques, along with several new techniques that we introduce. A crucial part of our protocol is a new technique for enforcing consistency of the inputs used by the party who garbles the circuits. This technique has both theoretical and practical advantages over \\mbox{previous methods.}

We present a prototype implementation of our new protocol, which is also the first implementation of the amortized cut-and-choose technique of Lindell and Riva (Crypto 2014).

Our prototype achieves a speed of just \\emph{$7$ ms in the online stage} and just $74$ ms in the offline stage per 2PC invoked, for securely computing AES in the presence of malicious adversaries (using 9 threads on two 2.9GHz machines located in the same Amazon region). We note that no prior work has gone below one second overall on average for the secure computation of AES for malicious adversaries (nor below 20ms in the online stage). Our implementation securely evaluates SHA-256 (which is a \\emph{much bigger circuit}) with $33$ ms online time and $206$ ms offline time, per 2PC invoked.

Bent functions are maximally nonlinear Boolean functions. They are important functions introduced by Rothaus and studied firstly by Dillon and next by many researchers for four decades. Since the complete classification of bent functions seems elusive, many researchers turn to design constructions of bent functions.

In this note, we show that linear involutions (which are an important class of permutations) over finite fields give rise to bent functions in bivariate representations. In particular, we exhibit new constructions of bent functions involving binomial linear involutions whose dual functions are directly obtained without computation.

We give a general framework for uniform, constant-time one- and two-dimensional scalar multiplication algorithms for elliptic curves and Jacobians of genus~2 curves that operate by projecting to the \\(x\\)-line or Kummer surface, where we can exploit faster and more uniform pseudomultiplication, before recovering the proper ``signed\'\' output back on the curve or Jacobian.

This extends the work of L\\\'opez and Dahab, Okeya and Sakurai, and Brier and Joye to genus~2, and also to two-dimensional scalar multiplication.

Our results show that many existing fast pseudomultiplication implementations (hitherto limited to applications in Diffie--Hellman key exchange) can be wrapped with simple and efficient pre- and post-computations to yield competitive full scalar multiplication algorithms, ready for use in more general discrete logarithm-based cryptosystems, including signature schemes. This is especially interesting for genus~2, where Kummer surfaces can outperform comparable elliptic curve systems.

As an example, we construct an instance of the Schnorr signature scheme driven by Kummer surface arithmetic.

Semaev shows that under the first fall degree assumption, the complexity

of ECDLP over $\\bF_{2^n}$, where $n$ is the input size, is

$O(2^{n^{1/2+o(1)}})$.

In his manuscript, the cost for solving equations system is $O((nm)^{4w})$,

where $m$ ($2 \\le m \\le n$) is the number of decomposition

and $w \\sim 2.7$ is the linear algebra constant.

It is remarkable that the cost for solving equations system under the

first fall degree assumption, is poly in input size $n$.

He uses normal factor base and the revalance of \"Probability that

the decomposition success\" and \"size of factor base\" is done.

%So that the result is induced.

Here, using disjoint factor base to his method,

\"Probability that the decomposition success becomes $ \\sim 1$ and

taking the very small size factor

base is useful for complexity point of view.

Thus we have the result that states \\\\

\"Under the first fall degree assumption,

the cost of ECDLP over $\\bF_{2^n}$, where $n$ is the input size, is $O(n^{8w+1})$.\"

Moreover, using the authors results,

in the case of the field characteristic $\\ge 3$, the first fall

degree of desired equation system is estimated by $\\le 3p+1$.

(In $p=2$ case, Semaev shows it is $\\le 4$. But it is exceptional.)

So we have similar result that states \\\\

\"Under the first fall degree assumption,

the cost of ECDLP over $\\bF_{p^n}$, where $n$ is the input size and (small) $p$ is a constant, is $O(n^{(6p+2)w+1})$.

Koster shows that the problem for deciding whether the value of Semaev\'s formula $S_m(x_1,...,x_m)$ is $0$ or not, is NP-complete. This result directly does not means ECDLP being NP-complete, but, it suggests ECDLP being NP-complete. Further, Semaev shows that the equations system using $m-2$ number of $S_3(x_1,x_2,x_3)$, which is equivalent to decide whether the value of Semaev\'s formula

$S_m(x_1,...,x_m)$ is $0$ or not, has constant(not depend on $m$ and $n$) first fall degree. So, under the first fall degree assumption, its complexity is poly in $n$ ($O(n^{Const})$).And so, suppose $P\\ne NP$, which almost all researcher assume this, it has a contradiction and we see that first fall degree assumption is not true.

Koster shows the NP-completeness from the group belonging problem, which is NP-complete, reduces to the problem for deciding whether the value of Semaev\'s formula $S_m(x_1,...,x_m)$ is $0$ or not, in polynomial time.

In this paper, from another point of view, we discuss this situation.

Here, we construct some equations system defined over arbitrary field $K$ and its first fall degree is small, from any 3SAT problem.

The cost for solving this equations system is polynomial times under the first fall degree assumption. So, 3SAT problem, which is NP-complete, reduced to the problem in P under the first fall degree assumption.

Almost all researcher assume $P \\ne NP$, and so, it concludes that the first fall degree assumption is not true. However, we can take $K=\\bR$(not finite field. It means that 3SAT reduces to solving multivariable equations system defined over $\\R$ and there are many method for solving this by numerical computation.

So, I must point out the very small possibility that NP complete problem is reduces to solving cubic equations equations system over $\\bR$ which can be solved in polynomial time.