International Association
for Cryptologic Research

Qin, Liu, Yuen, Deng, and Chen (PKC 2015) gave a new security notion of key-derivation function (KDF), continuous non-malleability with respect to $\\Phi$-related-key attacks ($\\Phi$-CNM), and its application to RKA-secure public-key cryptographic primitives. They constructed a KDF from cryptographic primitives and showed that the obtained KDF is $\\Phi_{hoe\\&iocr}$-CNM, where $\\Phi_{hoe\\&iocr}$ contains the identity function, the constant functions, and functions that have high output-entropy (HOE) and input-output collision-resistance (IOCR) simultaneously.

This short note disproves the security of their KDF by giving $\\Phi_{hoe\\&iocr}$-RKAs by exploiting the components of their KDF. We note that their proof is still correct for $\\Phi$-CNM for a subset of $\\Phi_{hoe\\&iocr}$; for example the KDF satisfies $\\Phi_{poly(d)}$-CNM, in which an adversary can tamper with a secret by using polynomials of degree at most $d$.

We present a novel method for constructing linear secret sharing schemes (LSSS) from linear error correcting codes and linear universal hash functions in a blackbox way. The main advantage of this new construction is that the privacy property of the resulting secret sharing scheme essentially becomes independent of the code we use, only depending on its rate. This allows us to fully harness the algorithmic properties of recent code constructions such as efficient encoding and decoding or efficient list-decoding. Choosing the error correcting codes and universal hash functions involved carefully, we obtain solutions to the following open problems:

- A linear near-threshold secret sharing scheme with both linear time sharing and reconstruction algorithms and large secrets (i.e. secrets of size Omega(n)). Thus, the computational overhead per shared bit in this scheme is constant.

- An efficiently reconstructible robust secret sharing scheme for n/3 0) with shares of optimal size O(1 + sec / n) and secrets of size Omega(n + sec), where sec is the security parameter.

The exact hardness of computing a Nash equilibrium is a fundamental open question in algorithmic game theory. This problem is complete for the complexity class \\ppad. It is well known that problems in PPAD cannot be \\np-complete unless NP=coNP. Therefore, a natural direction is to reduce the hardness of PPAD to the hardness of problems used in cryptography.

Bitansky, Paneth, and Rosen [FOCS 2015] prove the hardness of PPAD assuming the existence of quasi-polynomially hard indistinguishability obfuscation and sub-exponentially hard one-way functions. This leaves open the possibility of basing PPAD hardness on simpler, polynomially hard, computational assumptions.

We make further progress in this direction and reduce PPAD hardness directly to polynomially hard assumptions.

Our first result proves hardness of PPAD assuming the existence of *polynomially hard* indistinguishability obfuscation (IO) and one-way permutations. While this improves upon Bitansky et al.\'s work, it does not give us a reduction to simpler, polynomially hard computational assumption because constructions of IO inherently seems to require assumptions with sub-exponential hardness. In contrast, {\\em public key functional encryption} is a much simpler primitive and does not suffer from this drawback. Our second result shows that $\\ppad$ hardness can be based on {\\em polynomially hard} public key functional encryption and one-way permutations. Our results further demonstrate the power of polynomially hard public key functional encryption which is believed to be weaker than indistinguishability obfuscation.

We consider the symmetric Feedback Shift Registers (FSRs), especially a special class of symmetric FSRs (we call them scattered symmetric FSRs), and construct a large class of De Bruijn sequences from them. It is shown that, at least O(2^((n-6)(logn)/2)) De Bruijn sequences of order n can be constructed from just one n-stage scattered symmetric FSR. To generate the next bit in the De Bruijn sequence from the current state, it requires no more than 2n comparisons and n+1 FSR shifts. By further analyse the cycle structure of the scattered symmetric FSRs, other methods for constructing De Bruijn sequences are suggested.

A seminal result of Cleve (STOC 1986) showed that fairness, in general, is impossible to achieve in case of two-party computation if one of them is malicious. Later, Gordon et al. (STOC 2008) observed that there exist some functions for which fairness can be achieved even though one of the two parties is malicious. One of the functions considered by Gordon et al. is exactly the millionaires\' problem (Yao, FOCS 1982) or, equivalently, the `greater-than\' function. Interestingly, Gordon et al. (JACM, 2011) showed that any function over polynomial-size domains which does not contain an ``embedded XOR\" can be converted into the greater than function. In the same paper, they also demonstrated feasibility for certain functions that do contain an embedded XOR. In this paper, we revisit both the classes of two-party computation under rational players for the first time. We show that Gordon\'s protocols no longer remain fair when the players are rational. Further, we design two protocols, one without embedded XOR (the greater-than function) and the other with embedded XOR, and show that with rational players, our protocols achieve fairness under suitable choice of parameters.

A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the classical and quantum settings. Here, we show how to use quantum information, together with the assumption of stateless (i.e., reusable) hardware tokens, to build statistically secure OTMs. This is in sharp contrast with the classical case, where stateless hardware tokens alone cannot yield OTMs. In addition, our scheme is technologically simple. We prove security in the quantum universal composability framework, employing semi-definite programming results of Molina, Vidick and Watrous [TQC 2013] and combinatorial techniques of Pastawski et al. [Proc. Natl. Acad. Sci. 2012].

Witness encryption (WE) is a recent powerful encryption paradigm. It greatly extends the scope of encryption as it allows to encrypt a message using the description of a hard problem (a word in some language) and someone who knows a solution to this problem (a witness) is able to decrypt. Recent work thereby focuses on constructing WE for NP-complete languages (and thus obtaining WE for any language in NP). While this is an interesting challenge, it is also the main source for inefficiency and requires non-standard assumptions related to multilinear maps and obfuscation. We ask whether it is possible to come up with practically efficient WE schemes, which are still expressive enough to provide a solution to the following problem. Assume that an anonymous whistleblower, say Edwarda, wants to leak authoritative secrets in a way that the public will be convinced of its authenticity, but she wants to stay anonymous. Therefore, she signs the leaked document using a ring signature. Such a signature hides her identity unconditionally among other carefully selected people in an ad-hoc group and does not require getting their approval or assistance. But now the question arises as how to confidentially reply to such an unknown (anonymous) whistleblower.

In this paper we answer this question and introduce practical constructions of WE that are expressive enough to elegantly solve the seeming paradox sketched above. To this end, we restrict the class of supported languages from any NP-language to algebraic languages (defined over bilinear groups). In doing so, we obtain simple generic constructions, which only rely on smooth projective hash functions and can be instantiated from standard assumptions. Based on our generic constructions, we then show how to encrypt a message with respect to a given ring signature. Thereby, we only use information from a given ring signature (specifying an NP-language) such that only the anonymous signer behind the ring signature can decrypt (as only she holds the respective witness). In particular, we provide efficient instantiations for any ring signature scheme obtained from EUF-CMA-secure signature schemes and witness-indistinguishable Groth-Sahai proofs.

We show how to garble a large persistent database and then garble, one by one, a sequence of adaptively and adversarially chosen RAM programs that query and modify the database in arbitrary ways. Still, it is guaranteed that the garbled database and programs reveal only the outputs of the programs when run in sequence on the database. The runtime, space requirements and description size of the garbled programs are proportional only to those of the plaintext programs and the security parameter. We assume indistinguishability obfuscation for circuits and poly-to-one collision-resistant hash functions. The latter can be constructed based on standard algebraic assumptions such as the hardness of discrete log or factoring. In contrast, all previous garbling schemes with persistent data were shown secure only in the static setting where all the programs are known in advance.

As an immediate application, our scheme is the first to provide a way to outsource large databases to untrusted servers, and later query and update the database over time in a private and verifiable way, with complexity and description size proportional to those of the unprotected queries.

Our scheme extends the non-adaptive RAM garbling scheme of Canetti and Holmgren [ITCS 2016]. We also define and use a new primitive, called adaptive accumulators, which is an adaptive alternative to the positional accumulators of Koppula et al [STOC 2015] and somewhere statistical binding hashing of Hubacek and Wichs [ITCS 2015]. This primitive might well be useful elsewhere.

Quantum computers will break currently deployed public-key cryptography, and significantly weaken symmetric key cryptography, which are pillars of modern-day cybersecurity. Thus, before large-scale quantum computers are built, we need to migrate our systems and practices to ones that cannot be broken by quantum computers. For systems that aim to provide long-term confidentiality, this migration should happen even sooner.

There are viable options for quantum-proofing our cryptographic infrastructure, but the road ahead is neither easy nor fast.

Impressive progress in developing the building blocks of a fault-tolerant scalable quantum computer indicates that the prospect of a large-scale quantum computer is a medium-term threat. For example, I estimate a $1/2$ chance of breaking RSA-2048 by $2031$.

In this note, I briefly overview the problem, the solutions and some of the next steps.

This note can be seen as an appendix of a recent paper of

Kim [Kim15]. We show that the discrete logarithm problem in fields GF(Q) where Q = p n wit^ p of medium size and n having a factor of the good size (specified in the article) has a complexity of

L_Q(1/3, (48/9)^(1/3)).

LILI-128 is a clock controlled stream cipher based on two LFSRs with one clock control function and one non-linear filter function. The clocking of the second LFSR is controlled by the first LFSR. In this paper we propose a fault algebraic attack on LILI-128 stream cipher. We first recover the state bits of the first LFSR by injecting a single bit fault in the first LFSR. After that we recover the second LFSR state bits by following algebraic cryptanalysis technique. We also propose fault attack on Achterbahn stream cipher, which is based on 8 NLFSRs, 8 LFSRs and one non-linear combining function. We first inject a single bit fault into the NLFSR-A then observe the normal and faulty keystream bits to recover almost all the state bits of the NLFSR-A after key initialization phase. One can apply our technique to other NLFSR-B, C, D to recover their state bits also

Reducibility between different cryptographic primitives is a fundamental problem in modern cryptography. As one of the primitives, traitor tracing systems help content distributors recover the identities of users that collaborated in the pirate construction by tracing pirate decryption boxes. We present the first negative result on designing efficient traitor tracing systems via black-box constructions from symmetric cryptographic primitives, e.g. one-way functions. More specifically, we show that there is no secure traitor tracing scheme in the random oracle model, such that $\\ell_k\\cdot\\ell_c^2\\ge\\widetilde{\\Omega}(n)$, where $\\ell_k$ is the length of user key, $\\ell_c$ is the length of ciphertext and $n$ is the number of users, under the assumption that the scheme does not access the oracle to generate user keys. To our best knowledge, almost all the practical (non-artificial) cryptographic schemes (not limited to traitor tracing systems) via black-box constructions satisfy this assumption. Thus, our negative results indicate that most of the standard black-box reductions in cryptography cannot help construct a more efficient traitor tracing system.

We prove our results by extending the connection between traitor tracing systems and differentially private database sanitizers to the setting with random oracle access. After that, we prove the lower bound for traitor tracing schemes by constructing a differentially private sanitizer that only queries the random oracle polynomially many times. In order to reduce the query complexity of the sanitizer, we prove a large deviation bound for decision forests, which might be of independent interest.

We are hiring a tenured or tenure track faculty in Security Informatics at Indiana!!! Security informatics is interdisciplinary computer security. Research which connects with other Informatics groups is highly desirable (e.g., HCI, data science, social informatics, complex systems, or health informatics). We are a college town with a great security group. Bloomington punches above its weight, with an opera season, a ballet season, an off-Broadway season, four symphonic orchestras, four university stand-alone museums, and an annual world-class music festival.

****** Official Announcement **********

The School of Informatics and Computing (SoIC) at Indiana University Bloomington invites applications for a faculty position in Security Informatics. The position is open at all levels (assistant, associate, or full professor). Duties include teaching, research, and service.

Applications are welcome from information and computer scientists in a wide range of areas including but not limited to usable security, human-centered design, identity, social informatics of security, and design for privacy.

Applicants should have an established record (for senior level) or demonstrable potential for excellence (for junior level) in research and teaching, and a PhD in a relevant area or (for junior level) expected before 8/2016.

The SoIC is the first of its kind and among the largest in the country, with unsurpassed breadth. Its mission is to excel and lead in education, research, and outreach spanning and integrating the full breadth of computing and information technology. It includes Computer Science, Informatics, and Information and Library Science, with over 100 faculty, 900 graduate students, and 1500 undergraduate majors on the Bloomington Campus. It offers PhDs in Computer Science, Informatics, and Information Science.

Bloomington is a culturally thriving college town with a moderate cost of living

The covert security model (Aumann and Lindell, TCC 2007) offers an important security/efficiency trade-off: a covert player may arbitrarily cheat, but is caught with a certain fixed probability. This permits more efficient protocols than the malicious setting while still giving meaningful security guarantees. However, one drawback is that cheating cannot be proven to a third party, which prevents the use of covert protocols in many practical settings. Recently, Asharov and Orlandi (ASIACRYPT 2012) enhanced the covert model by allowing the honest player to generate a \\emph{proof of cheating}, checkable by any third party. Their model, which we call the PVC (\\emph{publicly verifiable covert}) model, offers a very compelling trade-off.

Asharov and Orlandi (AO) propose a practical protocol in the PVC model, which, however, relies on a specific expensive oblivious transfer (OT) protocol incompatible with OT extension. In this work, we improve the performance of the PVC model by constructing a PVC-compatible OT extension as well as making several practical improvements to the AO protocol. As compared to the state-of-the-art OT extension-based two-party covert protocol, our PVC protocol adds relatively little: four signatures and an $\\approx 67\\%$ wider OT extension matrix. This is a significant improvement over the AO protocol, which requires public-key-based OTs per input bit. We present detailed estimates showing (up to orders of magnitude) concrete performance improvements over the AO protocol and a recent malicious protocol.

In 1982, Yao introduced a fundamental technique of ``circuit garbling\'\' that became a central building block in cryptography. Recently, the question of garbling general random-access memory (RAM) programs received a lot of attention in the literature where garbling an encrypted data can be done separately from garbling program(s) that execute on this (garbled) RAM. The most recent results of Garg, Lu, and Ostrovsky (FOCS 2015) achieve a garbled RAM with black-box use of any one-way functions and poly-log overhead of data and program garbling in all the relevant parameters, including program run-time. The advantage of their solution is that large data can be garbled first, and act as persistent garbled storage (e.g. in the cloud) and later programs can be garbled and sent to be executed on this garbled database in a non-interactive manner.

One of the main advantages of cloud computing is not only that it has large storage but also that it has a large number of parallel processors. Despite multiple successful efforts on parallelizing (interactive) Oblivious RAM, the non-interactive garbling of parallel programs remained open until very recently. Specifically, Boyle, Chung and Pass in their upcoming TCC 2016 paper (see their recently updated eprint version) have recently shown how to garbled PRAM program with poly-logarithmic (parallel) overhead assuming non-black-box use of identity-based encryption. The question whether such a strong assumption and non-black-box use of such a strong assumption are needed. In this paper, we resolve this important open question and show how to garble parallel programs, with only black-box use one one-way functions and with only poly-log overhead in the (parallel) running time. Our result works for any number of parallel processors.

We prove that a balanced 8-round Feistel network is indifferentiable

from a random permutation. This result comes on the heels of (and is

part of the same body of work as) a 10-round indifferentiability

result for Feistel network recently announced by the same team of

authors. The current 8-round simulator achieves similar security,

query complexity and runtime as the 10-round simulator and is not

significantly more involved. The security of our simulator is also

slightly better than the security of the 14-round simulator of

Holenstein et al. for essentially the same runtime and query

complexity.

The Coding and Cryptography Group at the Institute of Computer Science, the University of Tartu, Estonia, is looking for a Research Fellow for a project on algebraic coding theory and network coding. The ideal candidate will have strength in one or more of the following areas:

• Algebraic coding theory

• Combinatorial coding theory

• Network coding

• Any area related to coding theory

Salary is at least 2000 euro per month before taxes plus social benefits, depending on qualification and experience. Some travel money will also be provided. Cost of living in Estonia is quite low, see e.g. http://www.expatistan.com/cost-of-living. Employment contract is till 31st December 2017.

A successful candidate should:

• Hold a Ph.D. degree

• Have a strong background in coding theory or a related field

• Have an international publication record at outstanding venues

To apply, please submit the following documents (by email):

• Application letter

• Research statement

• Curriculum vitae

• Publication list

• Copies of documents about academic degrees

• Two letters of reference (make sure they reach us by the application deadline)

Deadline for applications: 2nd December 2015

In order to remove any suspicion we have published a note on constants origin some time ago. If someone does not know 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)

We present an identity-based encryption (IBE) scheme in composite-order bilinear groups with essentially optimal parameters: the ciphertext overhead and the secret key are one group element each and decryption requires only one pairing. Our scheme achieves adaptive security and anonymity under standard decisional subgroup assumptions as used in Lewko and Waters (TCC \'10). Our construction relies on a novel extension to the Deja Q framework of Chase and Meiklejohn (Eurocrypt \'14).

Known Oblivious RAM (ORAM) constructions achieve either optimal bandwidth blowup or optimal latency (as measured by online roundtrips), but not both. We are the first to demonstrate an ORAM scheme, called Bucket ORAM, which attains the best of both worlds. Bucket ORAM simultaneously achieves a single online roundtrip as well as constant overall bandwidth blowup.