International Association
for Cryptologic Research

Local pseudorandom generators allow to expand a short random string into a long pseudo-random string, such that each output bit depends on a constant number d of input bits. Due to its extreme efficiency features, this intriguing primitive enjoys a wide variety of applications in cryptography and complexity. In the polynomial regime, where the seed is of size n and the output of size n^s for s > 1, the only known solution, commonly known as Goldreich's PRG, proceeds by applying a simple d-ary predicate to public random size-d subsets of the bits of the seed. While the security of Goldreich's PRG has been thoroughly investigated, with a variety of results deriving provable security guarantees against class of attacks in some parameter regimes and necessary criteria to be satisfied by the underlying predicate, little is known about its concrete security and efficiency. Motivated by its numerous theoretical applications and the hope of getting practical instantiations for some of them, we initiate a study of the concrete security of Goldreich's PRG, and evaluate its resistance to cryptanalytic attacks. Along the way, we develop a new guess-and-determine-style attack, and identify new criteria which refine existing criteria and capture the security guarantees of candidate local PRGs in a more fine-grained way.

A central challenge in the study of MPC is to balance between security guarantees, hardness assumptions, and resources required for the protocol. In this work, we study the cost of tolerating adaptive corruptions in MPC protocols under various corruption thresholds.

In the strongest setting, we consider adaptive corruptions of an arbitrary number of parties (potentially all) and achieve the following results: 1) two-round secure function evaluation (SFE) protocol in the CRS model, assuming LWE and iO for circuits. The communication, the CRS size, and the online-computation are independent of the size of the function. The iO assumption can be replaced by secure erasures. Previous results required either the communication or the CRS size to be polynomial in the function size. 2) Under the same assumptions, we construct a "Bob-optimized" 2PC (where Alice talks first, Bob second, and Alice learns the output). That is, the communication complexity and total computation of Bob are sublinear in the function size and in Alice's input size. We prove impossibility of "Alice-optimized" protocols. 3) Assuming LWE, we bootstrap adaptively secure NIZK arguments to achieve proof size only depending on the witness size, and independent of the NP-relation.

On a technical level, our results are based on laconic function evaluation (LFE) (Quach, Wee, and Wichs, FOCS'18) and shed light on an interesting duality between LFE and FHE.

Next, we analyze adaptive corruptions of all-but-one of the parties, and show a two-round SFE protocol in the threshold PKI model, assuming LWE and NIZK, with communication complexity only depending on the input and output of the parties. Finally, we consider the honest-majority setting, and show a two-round SFE protocol with guaranteed output delivery under the same constraints.

Our results highlight that the asymptotic cost of adaptive security can be reduced to be comparable to, and in many settings almost match, that of static security, with only a little sacrifice to the concrete round complexity and asymptotic communication complexity.

Maximally nonlinear Boolean functions in $n$ variables, where n is even, are called bent functions. There are several ways to represent Boolean functions. One of the most useful is via algebraic normal form (ANF). What can we say about ANF of a bent function? We try to collect all known and new facts related to ANF of a bent function. A new problem in bent functions is stated and studied: is it true that a linear, quadratic, cubic, etc. part of ANF of a bent function can be arbitrary? The case of linear part is well studied before. In this paper we prove that a quadratic part of a bent function can be arbitrary too.

To determine the dimension of null space of any given linearized polynomial is one of vital problems in finite field theory, with concern to design of modern symmetric cryptosystems. But, the known general theory for this task is much far from giving the exact dimension when applied to a specific linearized polynomial. The first contribution of this paper is to give a better general method to get more precise upper bound on the root number of any given linearized polynomial. We anticipate this result would be applied as a useful tool in many research branches of finite field and cryptography. Really we apply this result to get tighter estimations of the lower bounds on the second order nonlinearities of general cubic Boolean functions, which has been being an active research problem during the past decade, with many examples showing great improvements. Furthermore, this paper shows that by studying the distribution of radicals of derivatives of a given Boolean functions one can get a better lower bound of the second-order nonlinearity, through an example of the monomial Boolean function $g_{\mu}=Tr(\mu x^{2^{2r}+2^r+1})$ over any finite field $\mathbb F_{n}$.

Property-preserving hashing is a method of compressing a large input x into a short hash h(x) in such a way that given h(x) and h(y), one can compute a property P(x, y) of the original inputs. The idea of property-preserving hash functions underlies sketching, compressed sensing and locality-sensitive hashing.

Property-preserving hash functions are usually probabilistic: they use the random choice of a hash function from a family to achieve compression, and as a consequence, err on some inputs. Traditionally, the notion of correctness for these hash functions requires that for every two inputs x and y, the probability that h(x) and h(y) mislead us into a wrong prediction of P(x, y) is negligible. As observed in many recent works (incl. Mironov, Naor and Segev, STOC 2008; Hardt and Woodruff, STOC 2013; Naor and Yogev, CRYPTO 2015), such a correctness guarantee assumes that the adversary (who produces the offending inputs) has no information about the hash function, and is too weak in many scenarios.

We initiate the study of adversarial robustness for property-preserving hash functions, provide definitions, derive broad lower bounds due to a simple connection with communication complexity, and show the necessity of computational assumptions to construct such functions. Our main positive results are two candidate constructions of property-preserving hash functions (achieving different parameters) for the (promise) gap-Hamming property which checks if x and y are “too far” or “too close”. Our first construction relies on generic collision-resistant hash functions, and our second on a variant of the syndrome decoding assumption on low-density parity check codes.

We generalize and abstract the problem of extracting a witness from a prover of a special sound protocol into a combinatorial problem induced by a sequence of matroids and a predicate, and present a parametrized algorithm for solving this problem.

The parametrization provides a tight tradeoff between the running time and the extraction error of the algorithm, which allows optimizing the parameters to minimize: the soundness error for interactive proofs, or the extraction time for proofs of knowledge.

In contrast to previous work we bound the distribution of the running time and not only the expected running time. Tail bounds give a tighter analysis when applied recursively and concentrated running time.

Multikey fully homomorphic encryption (MFHE) allows homomorphic operations between ciphertexts encrypted under different keys. In applications for secure multiparty computation (MPC)protocols, MFHE can be more advantageous than usual fully homomorphic encryption (FHE) since users do not need to agree with a common public key before the computation when using MFHE. In EUROCRYPT 2016, Mukherjee and Wichs constructed a secure MPC protocol in only two rounds via MFHE which deals with a common random/reference string (CRS) in key generation. After then, Brakerski et al.. replaced the role of CRS with the distributed setup for CRS calculation to form a four round secure MPC protocol. Thus, recent improvements in round complexity of MPC protocols have been made using MFHE. In this paper, we go further to obtain round-ecient and secure MPC protocols. The underlying MFHE schemes in previous works still involve the common value, CRS, it seems to weaken the power of using MFHE to allow users to independently generate their own keys. Therefore, we resolve the issue by constructing an MFHE scheme without CRS based on LWE assumption, and then we obtain a secure MPC protocol against semi-malicious security in three rounds.

We use an RLWE-based key exchange scheme to construct a simple and efficient post-quantum oblivious transfer based on the Ring Learning with Errors assumption. We prove that our protocol is secure in the Universal Composability framework against static malicious adversaries in the random oracle model. The main idea of the protocol is that the receiver and the sender interact using the RLWE-based key exchange in such a way that the sender computes two keys, one of them shared with the receiver. It is infeasible for the sender to know which is the shared key and for the receiver to get information about the other one. The sender encrypts each message with each key using a symmetric-key encryption scheme and the receiver can only decrypt one of the ciphertexts. The protocol is extremely efficient in terms of computational and communication complexity, and thus a strong candidate for post-quantum applications.

A secret sharing scheme allows a dealer to share a secret among a set of $n$ parties such that any authorized subset of the parties can recover the secret, while any unauthorized subset of the parties learns no information about the secret. A local leakage-resilient secret sharing scheme (introduced in independent works by (Goyal and Kumar, STOC 18) and (Benhamouda, Degwekar, Ishai and Rabin, Crypto 18)) additionally requires the secrecy to hold against every unauthorized set of parties even if they obtain some bounded local leakage from every other share. The leakage is said to be local if it is computed independently for each share. So far, the only known constructions of local leakage resilient secret sharing schemes are for threshold access structures for very low ($O(1)$) or very high ($n -o(\log n)$) thresholds.

In this work, we give a compiler that takes a secret sharing scheme for any monotone access structure and produces a local leakage resilient secret sharing scheme for the same access structure, with only a constant-factor blow-up in the sizes of the shares. Furthermore, the resultant secret sharing scheme has optimal leakage-resilience rate i.e., the ratio between the leakage tolerated and the size of each share can be made arbitrarily close to $1$. Using this secret sharing scheme as the main building block, we obtain the following results:

1. Rate Preserving Non-Malleable Secret Sharing: We give a compiler that takes any secret sharing scheme for a 4-monotone access structure with rate $R$ and converts it into a non-malleable secret sharing scheme for the same access structure with rate $\Omega(R)$. The prior such non-zero rate construction (Badrinarayanan and Srinivasan, 18) only achieves a rate of $\Theta(R/{t_{\max}\log^2 n})$, where $t_{\max}$ is the maximum size of any minimal set in the access structure. As a special case, for any threshold $t \geq 4$ and an arbitrary $n \geq t$, we get the first constant rate construction of $t$-out-of-$n$ non-malleable secret sharing.

2. Leakage-Tolerant Multiparty Computation for General Interaction Pattern: For any function, we give a reduction from constructing leakage-tolerant secure multi-party computation protocols obeying any interaction pattern to constructing a secure (and not necessarily leakage-tolerant) protocol for a related function obeying the star interaction pattern. This improves upon the result of (Halevi et al., ITCS 2016), who constructed a protocol that is secure in a leak-free environment.

We explore a Byzantine Consensus protocol called Dfinity Consensus, recently published in a technical report. Dfinity Consensus solves synchronous state machine replication among $n = 2f + 1$ replicas with up to $f$ Byzantine faults. We provide a succinct explanation of the core mechanism of Dfinity Consensus to the best of our understanding. We prove the safety and liveness of the protocol specification we provide. Our complexity analysis of the protocol reveals the follows. The protocol achieves expected $O(f \times \Delta)$ latency against an adaptive adversary, (where \Delta is the synchronous bound on message delay), and expected $O(\Delta)$ latency against a mildly adaptive adversary. In either case, the communication complexity is unbounded. We then explain how the protocol can be modified to reduce the communication complexity to $O(n^3)$ in the former case, and to $O(n^2)$ in the latter.

P2P file sharing systems require proper incentive mechanisms to encourage active data sharing. However, traditional incentives based on reputation, credit or tit-for-tat are still challenged by free riding and whitewashing. We explore solutions based on blockchain, which is the new emerged decentralized trustful public ledger, and propose a blockchain-based file sharing incentive mechanism leveraged by cryptocurrency and smart contracts. In the proposed scheme, a file is sliced into pieces. A user who downloads data will request pieces with randomized order and directly pay for each piece. With the analysis in game theoretic models, rational players intend to cooperate in the procedure. We also evaluate the approach with simulations and experiments.

We envision that our solution is not only promising for P2P file sharing but also a stepping stone for general data sharing applications over the public blockchain.

In the Journal of Cryptology (25(1): 158-193. 2012), Shai Halevi and Yael Kalai proposed a general framework for constructing two-message oblivious transfer protocols using smooth projective hashing. The authors asserts that this framework gives a simulation-based security guarantee when the sender is corrupted. Later this work has been believed to be half-simulatable in literatures. In this paper, we show that the assertion is not true and present our ideas to construct a fully-simulatable oblivious transfer framework.

Formulating and designing unforgeable authentication of classical messages in the presence of quantum adversaries has been a challenge, as the familiar classical notions of unforgeability do not directly translate into meaningful notions in the quantum setting. A particular difficulty is how to fairly capture the notion of ``predicting an unqueried value'' when the adversary can query in quantum superposition. In this work, we uncover serious shortcomings in existing approaches, and propose a new definition. We then support its viability by a number of constructions and characterizations. Specifically, we demonstrate a function which is secure according to the existing definition by Boneh and Zhandry, but is clearly vulnerable to a quantum forgery attack, whereby a query supported only on inputs that start with $0$ divulges the value of the function on an input that starts with $1$. We then propose a new definition, which we call ``blind-unforgeability'' (or BU.) This notion matches ``intuitive unpredictability'' in all examples studied thus far. It defines a function to be predictable if there exists an adversary which can use ``partially blinded'' oracle access to predict values in the blinded region. Our definition (BU) coincides with standard unpredictability (EUF-CMA) in the classical-query setting. We show that quantum-secure pseudorandom functions are BU-secure MACs. In addition, we show that BU satisfies a composition property (Hash-and-MAC) using ``Bernoulli-preserving'' hash functions, a new notion which may be of independent interest. Finally, we show that BU is amenable to security reductions by giving a precise bound on the extent to which quantum algorithms can deviate from their usual behavior due to the blinding in the BU security experiment.

An important prerequisite for Side-channel Attack (SCA) is leakage sampling where the side-channel measurements (e.g. power traces) of the cryptographic device are collected for further analysis. However, as the operating frequency of cryptographic devices continues to increase due to advancing technology, leakage sampling will impose higher requirements on the sampling equipment. This paper undertakes the first study to show that effective leakage sampling can be achieved without relying on sophisticated equipments through Compressive Sensing (CS). In particular, CS can obtain low-dimensional samples from high-dimensional power traces by simply projecting the useful information onto the observation matrix. The leakage information can then be reconstructed in a workstation for further analysis. With this approach, the sampling rate to obtain the side-channel measurements is no longer limited by the operating frequency of the cryptographic device and Nyquist sampling theorem. Instead it depends on the sparsity of the leakage signal. Our study reveals that there is large amount of information redundancy in power traces obtained from the leaky device. As such, CS can employ a much lower sampling rate and yet obtain equivalent leakage sampling performance, which significantly lowers the requirement of sampling equipments. The feasibility of our approach is verified theoretically and through experiments.

In this paper we present an extension of Pseudonymous Signature introduced by the German Federal BSI authority as a part of technical recommendations for electronic identity documents. Without switching to pairing friendly groups we enhance the scheme so that: (a) the issuer does not know the private keys of the citizen (so it cannot impersonate the citizen), (b) a powerful adversary that breaks any number of ID cards created by the Issuer cannot forge new cards that could be proven as fake ones, (c) deanonymization of the pseudonyms used by a citizen is a multi-party protocol, where the consent of each authority is necessary to reveal the identity of a user. (d) we propose extended features concerning fully anonymous signatures and a pragmatic revocation approach. (e) we present an argument for unlinkability (cross-domain anonymity) of the presented schemes. In this way we make a step forwards to overcome the substantial weaknesses of the Pseudonymous Signature scheme. Moreover, the extension is on top of the original scheme with relatively small number of changes, following the strategy of reusing the previous schemes -- thereby reducing the costs of potential technology update.

In this work we present a collection of compilers that take secret sharing schemes for an arbitrary access structures as input and produce either leakage-resilient or non-malleable secret sharing schemes for the same access structure. A leakage-resilient secret sharing scheme hides the secret from an adversary, who has access to an unqualified set of shares, even if the adversary additionally obtains some size-bounded leakage from all other secret shares. A non-malleable secret sharing scheme guarantees that a secret that is reconstructed from a set of tampered shares is either equal to the original secret or completely unrelated. To the best of our knowledge we present the first generic compiler for leakage-resilient secret sharing for general access structures. In the case of non-malleable secret sharing, we strengthen previous definitions, provide separations between them, and construct a non-malleable secret sharing scheme for general access structures that fulfills the strongest definition with respect to independent share tampering functions. More precisely, our scheme is secure against concurrent tampering: The adversary is allowed to (non-adaptively) tamper the shares multiple times, and in each tampering attempt can freely choose the qualified set of shares to be used by the reconstruction algorithm to re-construct the tampered secret. This is a strong analogue of the multiple-tampering setting for split-state non-malleable codes and extractors.

We show how to use leakage-resilient and non-malleable secret sharing schemes to construct leakage-resilient and non-malleable threshold signatures. Classical threshold signatures allow to distribute the secret key of a signature scheme among a set of parties, such that certain qualified subsets can sign messages. We construct threshold signature schemes that remain secure even if an adversary leaks from or tampers with all secret shares.

This paper proposes Functional Analysis attacks on state of the art Logic Locking algorithms (abbreviated as FALL attacks). FALL attacks have two stages. The first stage identifies nodes involved in the locking functionality and analyzes functional properties of these nodes to shortlist a small number of candidate locking keys. In many cases, this shortlists exactly one locking key, so no further analysis is needed. However, if more than one key is shortlisted, the second stage introduces a SAT-based algorithm to identify the correct locking key from a list of alternatives using simulations on an unlocked circuit.

In comparison to past work, the FALL attack is more practical as it can often succeed (90% of successful attempts in our experiments) by only analyzing the locked netlist, without requiring oracle access to an unlocked circuit. Further, FALL attacks successfully defeat Secure Function Logic Locking (SFLL), the only locking algorithm that is resilient to known attacks on logic locking. Our experimental evaluation shows that FALL is able to defeat 65 out of 80 (81%) circuits locked using SFLL.

With the rapid development of information technology and the continuous evolution of personalized services, huge amounts of data are accumulated by the large Internet company in the process of serving users. Moreover, dynamic data interactions increase the intentional/unintentional privacy persistence in different information systems. However, the following problems such as the short board effect of privacy information preservation among different information systems and the difficulty of tracing the source of privacy violations are becoming more and more serious. Therefore, existing privacy preserving schemes cannot provide a systematic preservation. In this paper, we pay attention to the links of information lifecycle, such as information collection, storage, processing, distribution and destruction. Then we propose the theory of privacy computing and the key technology system, including privacy computing framework, formal definition of privacy computing, four principles that should be followed in privacy computing, algorithm design criteria, evaluation of privacy preserving effect, privacy computing language and so on. Finally, we employ four application scenarios to describe the universal application of privacy computing and prospect of the future research trends. It is expected to guide the theoretical research on user's privacy preservation under open environments.

A threshold secret sharing scheme (with threshold $t$) allows a dealer to share a secret among a set of parties such that any group of $t$ or more parties can recover the secret and no group of at most $t-1$ parties learn any information about the secret. A non-malleable threshold secret sharing scheme, introduced in the recent work of Goyal and Kumar (STOC'18), additionally protects a threshold secret sharing scheme when its shares are subject to tampering attacks. Specifically, it guarantees that the reconstructed secret from the tampered shares is either the original secret or something that is unrelated to the original secret.

In this work, we continue the study of threshold non-malleable secret sharing against the class of tampering functions that tamper each share independently. We focus on achieving greater efficiency and guaranteeing a stronger security property. We obtain the following results:

- Rate Improvement. We give the first construction of a threshold non-malleable secret sharing scheme that has rate $> 0$. Specifically, for every $n,t \geq 4$, we give a construction of a $t$-out-of-$n$ non-malleable secret sharing scheme with rate $\Theta(\frac{1}{t\log ^2 n})$. In the prior constructions, the rate was $\Theta(\frac{1}{n\log m})$ where $m$ is the length of the secret and thus, the rate tends to 0 as $m \rightarrow \infty$. Furthermore, we also optimize the parameters of our construction and give a concretely efficient scheme.

- Multiple Tampering. We give the first construction of a threshold non-malleable secret sharing scheme secure in the stronger setting of bounded tampering wherein the shares are tampered by multiple (but bounded in number) possibly different tampering functions. The rate of such a scheme is $\Theta(\frac{1}{k^3t\log^2 n})$ where $k$ is an apriori bound on the number of tamperings. We complement this positive result by proving that it is impossible to have a threshold non-malleable secret sharing scheme that is secure in the presence of an apriori unbounded number of tamperings.

- General Access Structures. We extend our results beyond threshold secret sharing and give constructions of rate-efficient, non-malleable secret sharing schemes for more general monotone access structures that are secure against multiple (bounded) tampering attacks.

Data Science Program Director

Yeshiva University’s Katz School seeks a dynamic director to serve as academic and administrative lead for its graduate initiatives in Data Science and related programs.

Position Responsibilities:

• Provide transformative direction and oversight in teaching, research and community

• Oversee curriculum development, academic policies, and assessment

• Ensure student academic and professional success

• Lead faculty recruitment, hiring, development, and evaluation

• Recruit highly qualified students, with an expectation of significant program growth

• Obtain relevant industry affiliations and designations

• Raise the visibility of the Katz School and University

• Establish partnerships with local, regional, national, and international organizations

• Develop grants, contracts, philanthropy, and research development

• Manage budgets and resources

Required Experience & Educational Background:

• Master’s degree in data science, computer science, or related field

• Professional experience in data science or related fields

To apply, visit: http://apptrkr.com/1336277

About Us:

Founded in 1886, Yeshiva University (YU) has a strong tradition of combining Jewish scholarship with academic excellence and achievement in the liberal arts, sciences, medicine, law, business, social work, Jewish studies, education, psychology, and more. We seek to attract and retain engaged and committed individuals who contribute to an exciting working environment, where there is a sense of community and belonging, balanced with a significant cross section of people from diverse backgrounds working and studying together.

Yeshiva University is an equal opportunity employer committed to hiring minorities, women, individuals with disabilities and protected veterans.

Closing date for applications:

More information: http://apptrkr.com/1336277