text:
## CryptoDB

### Papers from PKC 2018

Year
Venue
Title
2018
PKC
2018
PKC
2018
PKC
Improved (Almost) Tightly-Secure Structure-Preserving Signatures
Structure Preserving Signatures (SPS) allow the signatures and the messages signed to be further encrypted while retaining the ability to be proven valid under zero-knowledge. In particular, SPS are tailored to have structure suitable for Groth-Sahai NIZK proofs. More precisely, the messages, signatures, and verification keys are required to be elements of groups that support efficient bilinear-pairings (bilinear groups), and the signature verification consists of just evaluating one or more bilinear-pairing product equations. Since Groth-Sahai NIZK proofs can (with zero-knowledge) prove the validity of such pairing product equations, it leads to interesting applications such as blind signatures, group signatures, traceable signatures, group encryption, and delegatable credential systems.In this paper, we further improve on the SPS scheme of Abe, Hofheinz, Nishimaki, Ohkubo and Pan (CRYPTO 2017) while maintaining only an $O(\lambda )$ O(λ)-factor security reduction loss to the SXDH assumption. In particular, we compress the size of the signatures by almost 40%, and reduce the number of pairing-product equations in the verifier from fifteen to seven. Recall that structure preserving signatures are used in applications by encrypting the messages and/or the signatures, and hence these optimizations are further amplified as proving pairing-product equations in Groth-Sahai NIZK system is not frugal. While our scheme uses an important novel technique introduced by Hofheinz (EuroCrypt 2017), i.e. structure-preserving adaptive partitioning, our approach to building the signature scheme is different and this leads to the optimizations mentioned. Thus we make progress towards an open problem stated by Abe et al. (CRYPTO 2017) to design more compact SPS-es with smaller number of group elements.
2018
PKC
Fully Homomorphic Encryption from the Finite Field Isomorphism Problem
If q is a prime and n is a positive integer then any two finite fields of order $q^n$qn are isomorphic. Elements of these fields can be thought of as polynomials with coefficients chosen modulo q, and a notion of length can be associated to these polynomials. A non-trivial isomorphism between the fields, in general, does not preserve this length, and a short element in one field will usually have an image in the other field with coefficients appearing to be randomly and uniformly distributed modulo q. This key feature allows us to create a new family of cryptographic constructions based on the difficulty of recovering a secret isomorphism between two finite fields. In this paper we describe a fully homomorphic encryption scheme based on this new hard problem.
2018
PKC
Weakly Secure Equivalence-Class Signatures from Standard Assumptions
Structure-preserving signatures on equivalence classes, or equivalence-class signatures for short (EQS), are signature schemes defined over bilinear groups whose messages are vectors of group elements. Signatures are perfectly randomizable and given a signature on a vector, anyone can derive a signature on any multiple of the vector; EQS thus sign projective equivalence classes. Applications of EQS include the first constant-size anonymous attribute-based credentials, efficient round-optimal blind signatures without random oracles and efficient access-control encryption.To date, the only existing instantiation of EQS is proven secure in the generic-group model. In this work we show that by relaxing the definition of unforgeability, which makes it efficiently verifiable, we can construct EQS from standard assumptions, namely the Matrix-Diffie-Hellman assumptions. We then show that our unforgeability notion is sufficient for most applications.
2018
PKC
Hybrid Encryption in a Multi-user Setting, Revisited
This paper contributes to understanding the interplay of security notions for PKE, KEMs, and DEMs, in settings with multiple users, challenges, and instances. We start analytically by first studying (a) the tightness aspects of the standard hybrid KEM+DEM encryption paradigm, (b) the inherent weak security properties of all deterministic DEMs due to generic key-collision attacks in the multi-instance setting, and (c) the negative effect of deterministic DEMs on the security of hybrid encryption.We then switch to the constructive side by (d) introducing the concept of an augmented data encapsulation mechanism (ADEM) that promises robustness against multi-instance attacks, (e) proposing a variant of hybrid encryption that uses an ADEM instead of a DEM to alleviate the problems of the standard KEM+DEM composition, and (f) constructing practical ADEMs that are secure in the multi-instance setting.
2018
PKC
Simple and Generic Constructions of Succinct Functional Encryption
We propose simple and generic constructions of succinct functional encryption. Our key tool is exponentially-efficient indistinguishability obfuscator (XIO), which is the same as indistinguishability obfuscator (IO) except that the size of an obfuscated circuit (or the running-time of an obfuscator) is slightly smaller than that of a brute-force canonicalizer that outputs the entire truth table of a circuit to be obfuscated. A “compression factor” of XIO indicates how much XIO compresses the brute-force canonicalizer. In this study, we propose a significantly simple framework to construct succinct functional encryption via XIO and show that XIO is a powerful enough to achieve cutting-edge cryptography. In particular, we prove the followings:Single-key weakly succinct secret-key functional encryption (SKFE) is constructed from XIO (even with a bad compression factor) and one-way function.Single-key weakly succinct public-key functional encryption (PKFE) is constructed from XIO with a good compression factor and public-key encryption.Single-key weakly succinct PKFE is constructed from XIO (even with a bad compression factor) and identity-based encryption. Our new framework has side benefits. Our constructions do not rely on any number theoretic or lattice assumptions such as decisional Diffie-Hellman and learning with errors assumptions. Moreover, all security reductions incur only polynomial security loss. Known constructions of weakly succinct SKFE or PKFE from XIO with polynomial security loss rely on number theoretic or lattice assumptions.
2018
PKC
KEM Combiners
Key-encapsulation mechanisms (KEMs) are a common stepping stone for constructing public-key encryption. Secure KEMs can be built from diverse assumptions, including ones related to integer factorization, discrete logarithms, error correcting codes, or lattices. In light of the recent NIST call for post-quantum secure PKE, the zoo of KEMs that are believed to be secure continues to grow. Yet, on the question of which is the most secure KEM opinions are divided. While using the best candidate might actually not seem necessary to survive everyday life situations, placing a wrong bet can actually be devastating, should the employed KEM eventually turn out to be vulnerable.We introduce KEM combiners as a way to garner trust from different KEM constructions, rather than relying on a single one: We present efficient black-box constructions that, given any set of ‘ingredient’ KEMs, yield a new KEM that is (CCA) secure as long as at least one of the ingredient KEMs is.As building blocks our constructions use cryptographic hash functions and blockciphers. Some corresponding security proofs require idealized models for these primitives, others get along on standard assumptions.
2018
PKC
Making Public Key Functional Encryption Function Private, Distributively
We put forth a new notion of distributed public key functional encryption. In such a functional encryption scheme, the secret key for a function f will be split into shares $\mathsf {sk}_i^f$ skif. Given a ciphertext $\mathsf {ct}$ ct that encrypts a message x, a secret key share $\mathsf {sk}_i^f$ skif, one can evaluate and obtain a shared value $y_i$ yi. Adding all the shares up can recover the actual value of f(x), while partial shares reveal nothing about the plaintext. More importantly, this new model allows us to establish function privacy which was not possible in the setting of regular public key functional encryption. We formalize such notion and construct such a scheme from any public key functional encryption scheme together with learning with error assumption.We then consider the problem of hosting services in the untrusted cloud. Boneh, Gupta, Mironov, and Sahai (Eurocrypt 2014) first studied such application and gave a construction based on indistinguishability obfuscation. Their construction had the restriction that the number of corrupted clients has to be bounded and known. They left an open problem how to remove such restriction. We resolve this problem by applying our function private (distributed) public key functional encryption to the setting of hosting service in multiple clouds. Furthermore, our construction provides a much simpler and more flexible paradigm which is of both conceptual and practical interests.Along the way, we strengthen and simplify the security notions of the underlying primitives, including function secret sharing.
2018
PKC
Revisiting Proxy Re-encryption: Forward Secrecy, Improved Security, and Applications
We revisit the notion of proxy re-encryption ($\mathsf {PRE}$PRE), an enhanced public-key encryption primitive envisioned by Blaze et al. (Eurocrypt’98) and formalized by Ateniese et al. (NDSS’05) for delegating decryption rights from a delegator to a delegatee using a semi-trusted proxy. $\mathsf {PRE}$PRE notably allows to craft re-encryption keys in order to equip the proxy with the power of transforming ciphertexts under a delegator’s public key to ciphertexts under a delegatee’s public key, while not learning anything about the underlying plaintexts.We study an attractive cryptographic property for $\mathsf {PRE}$PRE, namely that of forward secrecy. In our forward-secret $\mathsf {PRE}$PRE (fs-$\mathsf {PRE}$PRE) definition, the proxy periodically evolves the re-encryption keys and permanently erases old versions while he delegator’s public key is kept constant. As a consequence, ciphertexts for old periods are no longer re-encryptable and, in particular, cannot be decrypted anymore at the delegatee’s end. Moreover, delegators evolve their secret keys too, and, thus, not even they can decrypt old ciphertexts once their key material from past periods has been deleted. This, as we will discuss, directly has application in short-term data/message-sharing scenarios.Technically, we formalize fs-$\mathsf {PRE}$PRE. Thereby, we identify a subtle but significant gap in the well-established security model for conventional $\mathsf {PRE}$PRE and close it with our formalization (which we dub fs-$\mathsf {PRE} ^+$PRE+). We present the first provably secure and efficient constructions of fs-$\mathsf {PRE}$PRE as well as $\mathsf {PRE}$PRE (implied by the former) satisfying the strong fs-$\mathsf {PRE} ^+$PRE+ and $\mathsf {PRE} ^+$PRE+ notions, respectively. All our constructions are instantiable in the standard model under standard assumptions and our central building block are hierarchical identity-based encryption ($\mathsf {HIBE}$HIBE) schemes that only need to be selectively secure.
2018
PKC
Full-Hiding (Unbounded) Multi-input Inner Product Functional Encryption from the k-Linear Assumption
This paper presents two non-generic and practically efficient private key multi-input functional encryption (MIFE) schemes for the multi-input version of the inner product functionality that are the first to achieve simultaneous message and function privacy, namely, the full-hiding security for a non-trivial multi-input functionality under well-studied cryptographic assumptions. Our MIFE schemes are built in bilinear groups of prime order, and their security is based on the standard k-Linear (k-LIN) assumption (along with the existence of semantically secure symmetric key encryption and pseudorandom functions). Our constructions support polynomial number of encryption slots (inputs) without incurring any super-polynomial loss in the security reduction. While the number of encryption slots in our first scheme is apriori bounded, our second scheme can withstand an arbitrary number of encryption slots. Prior to our work, there was no known MIFE scheme for a non-trivial functionality, even without function privacy, that can support an unbounded number of encryption slots without relying on any heavy-duty building block or little-understood cryptographic assumption.
2018
PKC
Hedged Nonce-Based Public-Key Encryption: Adaptive Security Under Randomness Failures
Nowadays it is well known that randomness may fail due to bugs or deliberate randomness subversion. As a result, the security of traditional public-key encryption (PKE) cannot be guaranteed any more. Currently there are mainly three approaches dealing with the problem of randomness failures: deterministic PKE, hedged PKE, and nonce-based PKE. However, these three approaches only apply to different application scenarios respectively. Since the situations in practice are dynamic and very complex, it’s almost impossible to predict the situation in which a scheme is deployed, and determine which approach should be used beforehand.In this paper, we initiate the study of hedged security for nonce-based PKE, which adaptively applies to the situations whenever randomness fails, and achieves the best-possible security. Specifically, we lift the hedged security to the setting of nonce-based PKE, and formalize the notion of chosen-ciphertext security against chosen-distribution attacks (IND-CDA2) for nonce-based PKE. By presenting two counterexamples, we show a separation between our IND-CDA2 security for nonce-based PKE and the original NBP1/NBP2 security defined by Bellare and Tackmann (EUROCRYPT 2016). We show two nonce-based PKE constructions meeting IND-CDA2, NBP1 and NBP2 security simultaneously. The first one is a concrete construction in the random oracle model, and the second one is a generic construction based on a nonce-based PKE scheme and a deterministic PKE scheme.
2018
PKC
Related Randomness Security for Public Key Encryption, Revisited
Motivated by the history of randomness failures in practical systems, Paterson, Schuldt, and Sibborn (PKC 2014) introduced the notion of related randomness security for public key encryption. In this paper, we firstly show an inherent limitation of this notion: if the family of related randomness functions is sufficiently rich to express the encryption function of the considered scheme, then security cannot be achieved. This suggests that achieving security for function families capable of expressing more complex operations, such as those used in random number generation, might be difficult. The current constructions of related randomness secure encryption in the standard model furthermore reflect this; full security is only achieved for function families with a convenient algebraic structure. We additionally revisit the seemingly optimal random oracle model construction by Paterson et al. and highlight its limitations.To overcome this difficulty, we propose a new notion which we denote related refreshable randomness security. This notion captures a scenario in which an adversary has limited time to attack a system before new entropy is added. More specifically, the number of encryption queries with related randomness the adversary can make before the randomness is refreshed, is bounded, but the adversary is allowed to make an unbounded total number of queries. Furthermore, the adversary is allowed to influence how entropy is added to the system. In this setting, we construct an encryption scheme which remains secure in the standard model for arbitrary function families of size $2^p$2p (where p is polynomial in the security parameter) that satisfy certain collision-resistant and output-unpredictability properties. This captures a rich class of functions, which includes, as a special case, circuits of polynomial size. Our scheme makes use of a new construction of a (bounded) related-key attack secure pseudorandom function, which in turn is based on a new flavor of the leftover hash lemma. These technical results might be of independent interest.
2018
PKC
Local Non-malleable Codes in the Bounded Retrieval Model
In a recent result, Dachman-Soled et al. (TCC ’15) proposed a new notion called locally decodable and updatable non-malleable codes, which informally, provides the security guarantees of a non-malleable code while also allowing for efficient random access. They also considered locally decodable and updatable non-malleable codes that are leakage-resilient, allowing for adversaries who continually leak information in addition to tampering.The bounded retrieval model (BRM) (cf. Alwen et al. (CRYPTO ’09) and Alwen et al. (EUROCRYPT ’10)) has been studied extensively in the setting of leakage resilience for cryptographic primitives. This threat model assumes that an attacker can learn information about the secret key, subject only to the constraint that the overall amount of leaked information is upper bounded by some value. The goal is then to construct cryptosystems whose secret key length grows with the amount of leakage, but whose runtime (assuming random access to the secret key) is independent of the leakage amount.In this work, we combine the above two notions and construct local non-malleable codes in the split-state model, that are secure against bounded retrieval adversaries. Specifically, given leakage parameter $\ell$ℓ, we show how to construct an efficient, 3-split-state, locally decodable and updatable code (with CRS) that is secure against one-time leakage of any polynomial time, 3-split-state leakage function whose output length is at most $\ell$ℓ, and one-time tampering via any polynomial-time 3-split-state tampering function. The locality we achieve is polylogarithmic in the security parameter.
2018
PKC
New Constructions of Identity-Based and Key-Dependent Message Secure Encryption Schemes
Recently, Döttling and Garg (CRYPTO 2017) showed how to build identity-based encryption (IBE) from a novel primitive termed Chameleon Encryption, which can in turn be realized from simple number theoretic hardness assumptions such as the computational Diffie-Hellman assumption (in groups without pairings) or the factoring assumption. In a follow-up work (TCC 2017), the same authors showed that IBE can also be constructed from a slightly weaker primitive called One-Time Signatures with Encryption (OTSE).In this work, we show that OTSE can be instantiated from hard learning problems such as the Learning With Errors (LWE) and the Learning Parity with Noise (LPN) problems. This immediately yields the first IBE construction from the LPN problem and a construction based on a weaker LWE assumption compared to previous works.Finally, we show that the notion of one-time signatures with encryption is also useful for the construction of key-dependent-message (KDM) secure public-key encryption. In particular, our results imply that a KDM-secure public key encryption can be constructed from any KDM-secure secret-key encryption scheme and any public-key encryption scheme.
2018
PKC
SOFIA: $\mathcal {MQ}$MQ-Based Signatures in the QROM
We propose SOFIA, the first $\mathcal {MQ}$MQ-based signature scheme provably secure in the quantum-accessible random oracle model (QROM). Our construction relies on an extended version of Unruh’s transform for 5-pass identification schemes that we describe and prove secure both in the ROM and QROM.Based on a detailed security analysis, we provide concrete parameters for SOFIA that achieve 128-bit post-quantum security. The result is SOFIA-4-128 with parameters carefully optimized to minimize signature size and maximize performance. SOFIA-4-128 comes with an implementation targeting recent Intel processors with the AVX2 vector-instruction set; the implementation is fully protected against timing attacks.
2018
PKC
Non-malleability vs. CCA-Security: The Case of Commitments
In this work, we settle the relations among a variety of security notions related to non-malleability and CCA-security that have been proposed for commitment schemes in the literature. Interestingly, all our separations follow from two generic transformations. Given two appropriate security notions X and Y from the class of security notions we compare, these transformations take a commitment scheme that fulfills notion X and output a commitment scheme that still fulfills notion X but not notion Y.Using these transformations, we are able to show that some of the known relations for public-key encryption do not carry over to commitments. In particular, we show that, surprisingly, parallel non-malleability and parallel CCA-security are not equivalent for commitment schemes. This stands in contrast to the situation for public-key encryption where these two notions are equivalent as shown by Bellare et al. at CRYPTO ‘99.
2018
PKC
Subversion-Zero-Knowledge SNARKs
Subversion zero knowledge for non-interactive proof systems demands that zero knowledge (ZK) be maintained even when the common reference string (CRS) is chosen maliciously. SNARKs are proof systems with succinct proofs, which are at the core of the cryptocurrency Zcash, whose anonymity relies on ZK-SNARKs; they are also used for ZK contingent payments in Bitcoin.We show that under a plausible hardness assumption, the most efficient SNARK schemes proposed in the literature, including the one underlying Zcash and contingent payments, satisfy subversion ZK or can be made to at very little cost. In particular, we prove subversion ZK of the original SNARKs by Gennaro et al. and the almost optimal construction by Groth; for the Pinocchio scheme implemented in libsnark we show that it suffices to add 4 group elements to the CRS. We also argue informally that Zcash is anonymous even if its parameters were set up maliciously.
2018
PKC
Key Dependent Message Security and Receiver Selective Opening Security for Identity-Based Encryption
We construct two identity-based encryption (IBE) schemes. The first one is IBE satisfying key dependent message (KDM) security for user secret keys. The second one is IBE satisfying simulation-based receiver selective opening (RSO) security. Both schemes are secure against adaptive-ID attacks and do not have any a-priori bound on the number of challenge identities queried by adversaries in the security games. They are the first constructions of IBE satisfying such levels of security.Our constructions of IBE are very simple. We construct KDM secure IBE by transforming KDM secure secret-key encryption using IBE satisfying only ordinary indistinguishability against adaptive-ID attacks (IND-ID-CPA security). Our simulation-based RSO secure IBE is based only on IND-ID-CPA secure IBE.We also demonstrate that our construction technique for KDM secure IBE is used to construct KDM secure public-key encryption. More precisely, we show how to construct KDM secure public-key encryption from KDM secure secret-key encryption and public-key encryption satisfying only ordinary indistinguishability against chosen plaintext attacks.
2018
PKC
A Unified Framework for Trapdoor-Permutation-Based Sequential Aggregate Signatures
We give a framework for trapdoor-permutation-based sequential aggregate signatures (SAS) that unifies and simplifies prior work and leads to new results. The framework is based on ideal ciphers over large domains, which have recently been shown to be realizable in the random oracle model. The basic idea is to replace the random oracle in the full-domain-hash signature scheme with an ideal cipher. Each signer in sequence applies the ideal cipher, keyed by the message, to the output of the previous signer, and then inverts the trapdoor permutation on the result. We obtain different variants of the scheme by varying additional keying material in the ideal cipher and making different assumptions on the trapdoor permutation. In particular, we obtain the first scheme with lazy verification and signature size independent of the number of signers that does not rely on bilinear pairings.Since existing proofs that ideal ciphers over large domains can be realized in the random oracle model are lossy, our schemes do not currently permit practical instantiation parameters at a reasonable security level, and thus we view our contribution as mainly conceptual. However, we are optimistic tighter proofs will be found, at least in our specific application.
2018
PKC
Interactively Secure Groups from Obfuscation
We construct a mathematical group in which an interactive variant of the very general Uber assumption holds. Our construction uses probabilistic indistinguishability obfuscation, fully homomorphic encryption, and a pairing-friendly group in which a mild and standard computational assumption holds. While our construction is not practical, it constitutes a feasibility result that shows that under a strong but generic, and a mild assumption, groups exist in which very general computational assumptions hold. We believe that this grants additional credibility to the Uber assumption.
2018
PKC
Public-Key Encryption Resistant to Parameter Subversion and Its Realization from Efficiently-Embeddable Groups
We initiate the study of public-key encryption (PKE) schemes and key-encapsulation mechanisms (KEMs) that retain security even when public parameters (primes, curves) they use may be untrusted and subverted. We define a strong security goal that we call ciphertext pseudo-randomness under parameter subversion attack (CPR-PSA). We also define indistinguishability (of ciphertexts for PKE, and of encapsulated keys from random ones for KEMs) and public-key hiding (also called anonymity) under parameter subversion attack, and show they are implied by CPR-PSA, for both PKE and KEMs. We show that hybrid encryption continues to work in the parameter subversion setting to reduce the design of CPR-PSA PKE to CPR-PSA KEMs and an appropriate form of symmetric encryption. To obtain efficient, elliptic-curve-based KEMs achieving CPR-PSA, we introduce efficiently-embeddable group families and give several constructions from elliptic-curves.
2018
PKC
Graded Encoding Schemes from Obfuscation
We construct a graded encoding scheme (GES), an approximate form of graded multilinear maps. Our construction relies on indistinguishability obfuscation, and a pairing-friendly group in which (a suitable variant of) the strong Diffie–Hellman assumption holds. As a result of this abstract approach, our GES has a number of advantages over previous constructions. Most importantly: We can prove that the multilinear decisional Diffie–Hellman (MDDH) assumption holds in our setting, assuming the used ingredients are secure (in a well-defined and standard sense). Hence, our GES does not succumb to so-called “zeroizing” attacks if the underlying ingredients are secure.Encodings in our GES do not carry any noise. Thus, unlike previous GES constructions, there is no upper bound on the number of operations one can perform with our encodings. Hence, our GES essentially realizes what Garg et al. (EUROCRYPT 2013) call the “dream version” of a GES. Technically, our scheme extends a previous, non-graded approximate multilinear map scheme due to Albrecht et al. (TCC 2016-A). To introduce a graded structure, we develop a new view of encodings at different levels as polynomials of different degrees.
2018
PKC
A Practical Cryptanalysis of WalnutDSA$^{\text {TM}}$TM
We present a practical cryptanalysis of WalnutDSA, a digital signature algorithm trademarked by SecureRF. WalnutDSA uses techniques from permutation groups, matrix groups and braid groups, and is designed to provide post-quantum security in lightweight IoT device contexts. The attack given in this paper bypasses the E-Multiplication$^{\text {TM}}$TM and cloaked conjugacy search problems at the heart of the algorithm and forges signatures for arbitrary messages in approximately two minutes. We also discuss potential countermeasures to the attack.
2018
PKC
Hashing Solutions Instead of Generating Problems: On the Interactive Certification of RSA Moduli
Certain RSA-based protocols, for instance in the domain of group signatures, require a prover to convince a verifier that a set of RSA parameters is well-structured (e.g., that the modulus is the product of two distinct primes and that the exponent is co-prime to the group order). Various corresponding proof systems have been proposed in the past, with different levels of generality, efficiency, and interactivity.This paper proposes two new proof systems for a wide set of properties that RSA and related moduli might have. The protocols are particularly efficient: The necessary computations are simple, the communication is restricted to only one round, and the exchanged messages are short. While the first protocol is based on prior work (improving on it by reducing the number of message passes from four to two), the second protocol is novel. Both protocols require a random oracle.
2018
PKC
Speed-Ups and Time–Memory Trade-Offs for Tuple Lattice Sieving
In this work we study speed-ups and time–space trade-offs for solving the shortest vector problem (SVP) on Euclidean lattices based on tuple lattice sieving.Our results extend and improve upon previous work of Bai–Laarhoven–Stehlé [ANTS’16] and Herold–Kirshanova [PKC’17], with better complexities for arbitrary tuple sizes and offering tunable time–memory trade-offs. The trade-offs we obtain stem from the generalization and combination of two algorithmic techniques: the configuration framework introduced by Herold–Kirshanova, and the spherical locality-sensitive filters of Becker–Ducas–Gama–Laarhoven [SODA’16].When the available memory scales quasi-linearly with the list size, we show that with triple sieving we can solve SVP in dimension n in time $2^{0.3588n + o(n)}$ 20.3588n+o(n) and space $2^{0.1887n + o(n)}$ 20.1887n+o(n), improving upon the previous best triple sieve time complexity of $2^{0.3717n + o(n)}$ 20.3717n+o(n) of Herold–Kirshanova. Using more memory we obtain better asymptotic time complexities. For instance, we obtain a triple sieve requiring only $2^{0.3300n + o(n)}$ 20.3300n+o(n) time and $2^{0.2075n + o(n)}$ 20.2075n+o(n) memory to solve SVP in dimension n. This improves upon the best double Gauss sieve of Becker–Ducas–Gama–Laarhoven, which runs in $2^{0.3685n + o(n)}$ 20.3685n+o(n) time when using the same amount of space.
2018
PKC
Two-Factor Authentication with End-to-End Password Security
We present a secure two-factor authentication (TFA) scheme based on the possession by the user of a password and a crypto-capable device. Security is “end-to-end” in the sense that the attacker can attack all parts of the system, including all communication links and any subset of parties (servers, devices, client terminals), can learn users’ passwords, and perform active and passive attacks, online and offline. In all cases the scheme provides the highest attainable security bounds given the set of compromised components. Our solution builds a TFA scheme using any Device-Enhanced PAKE, defined by Jarecki et al., and any Short Authenticated String (SAS) Message Authentication, defined by Vaudenay. We show an efficient instantiation the modular, generic construction we give is not PAKE-agnostic because it doesn’t even use PAKE, but the instantiation of this scheme which instantiates DE-PAKE with PTR+PAKE is PAKE-agnostic as you say of this modular construction which utilizes any password-based client-server authentication method, with or without reliance on public-key infrastructure. The security of the proposed scheme is proven in a formal model that we formulate as an extension of the traditional PAKE model.We also report on a prototype implementation of our schemes, including TLS-based and PKI-free variants, as well as several instantiations of the SAS mechanism, all demonstrating the practicality of our approach.
2018
PKC
Fast Lattice Basis Reduction Suitable for Massive Parallelization and Its Application to the Shortest Vector Problem
The hardness of the shortest vector problem for lattices is a fundamental assumption underpinning the security of many lattice-based cryptosystems, and therefore, it is important to evaluate its difficulty. Here, recent advances in studying the hardness of problems in large-scale lattice computing have pointed to need to study the design and methodology for exploiting the performance of massive parallel computing environments. In this paper, we propose a lattice basis reduction algorithm suitable for massive parallelization. Our parallelization strategy is an extension of the Fukase–Kashiwabara algorithm (J. Information Processing, Vol. 23, No. 1, 2015). In our algorithm, given a lattice basis as input, variants of the lattice basis are generated, and then each process reduces its lattice basis; at this time, the processes cooperate and share auxiliary information with each other to accelerate lattice basis reduction. In addition, we propose a new strategy based on our evaluation function of a lattice basis in order to decrease the sum of squared lengths of orthogonal basis vectors. We applied our algorithm to problem instances from the SVP Challenge. We solved a 150-dimension problem instance in about 394 days by using large clusters, and we also solved problem instances of dimensions 134, 138, 140, 142, 144, 146, and 148. Since the previous world record is the problem of dimension 132, these results demonstrate the effectiveness of our proposal.
2018
PKC
Reusing Tamper-Proof Hardware in UC-Secure Protocols
Universally composable protocols provide security even in highly complex environments like the Internet. Without setup assumptions, however, UC-secure realizations of cryptographic tasks are impossible. Tamper-proof hardware tokens, e.g. smart cards and USB tokens, can be used for this purpose. Apart from the fact that they are widely available, they are also cheap to manufacture and well understood.Currently considered protocols, however, suffer from two major drawbacks that impede their practical realization:The functionality of the tokens is protocol-specific, i.e. each protocol requires a token functionality tailored to its need.Different protocols cannot reuse the same token even if they require the same functionality from the token, because this would render the protocols insecure in current models of tamper-proof hardware. In this paper we address these problems. First and foremost, we propose formalizations of tamper-proof hardware as an untrusted and global setup assumption. Modeling the token as a global setup naturally allows to reuse the tokens for arbitrary protocols. Concerning a versatile token functionality we choose a simple signature functionality, i.e. the tokens can be instantiated with currently available signature cards. Based on this we present solutions for a large class of cryptographic tasks.
2018
PKC
Bootstrapping the Blockchain, with Applications to Consensus and Fast PKI Setup
The Bitcoin backbone protocol (Eurocrypt 2015) extracts basic properties of Bitcoin’s underlying blockchain data structure, such as “common prefix” and “chain quality,” and shows how fundamental applications including consensus and a robust public transaction ledger can be built on top of them. The underlying assumptions are “proofs of work” (POWs), adversarial hashing power strictly less than 1/2 and no adversarial pre-computation—or, alternatively, the existence of an unpredictable “genesis” block.In this paper we first show how to remove the latter assumption, presenting a “bootstrapped” Bitcoin-like blockchain protocol relying on POWs that builds genesis blocks “from scratch” in the presence of adversarial pre-computation. Importantly, the round complexity of the genesis block generation process is independent of the number of participants.Next, we consider applications of our construction, including a PKI generation protocol and a consensus protocol without trusted setup assuming an honest majority (in terms of computational power). Previous results in the same setting (unauthenticated parties, no trusted setup, POWs) required a round complexity linear in the number of participants.
2018
PKC
On Composable Security for Digital Signatures
A digital signature scheme (DSS), which consists of a key-generation, a signing, and a verification algorithm, is an invaluable tool in cryptography. The first and still most widely used security definition for a DSS, existential unforgeability under chosen-message attack, was introduced by Goldwasser, Micali, and Rivest in 1988.As DSSs serve as a building block in numerous complex cryptographic protocols, a security definition that specifies the guarantees of a DSS under composition is needed. Canetti (FOCS 2001, CSFW 2004) as well as Backes, Pfitzmann, and Waidner (CCS 2003) have described ideal functionalities for signatures in their respective composable-security frameworks. While several variants of these functionalities exist, they all share that the verification key and signature values appear explicitly.In this paper, we describe digital signature schemes from a different, more abstract perspective. Instead of modeling all aspects of a DSS in a monolithic ideal functionality, our approach characterizes a DSS as a construction of a repository for authentically reading values written by a certain party from certain assumed repositories, e.g., for transmitting verification key and signature values. This approach resolves several technical complications of previous simulation-based approaches, captures the security of signature schemes in an abstract way, and allows for modular proofs.We show that our definition is equivalent to existential unforgeability. We then model two example applications: (1) the certification of values via a signature from a specific entity, which with public keys as values is the core functionality of public-key infrastructures, and (2) the authentication of a session between a client and a server with the help of a digitally signed assertion from an identity provider. Single-sign-on mechanisms such as SAML rely on the soundness of the latter approach.
2018
PKC
Efficient Adaptively Secure Zero-Knowledge from Garbled Circuits
Zero-knowledge (ZK) protocols are undoubtedly among the central primitives in cryptography, lending their power to numerous applications such as secure computation, voting, auctions, and anonymous credentials to name a few. The study of efficient ZK protocols for non-algebraic statements has seen rapid progress in recent times, relying on secure computation techniques. The primary contribution of this work lies in constructing efficient UC-secure constant round ZK protocols from garbled circuits that are secure against adaptive corruptions, with communication linear in the size of the statement. We begin by showing that the practically efficient ZK protocol of Jawurek et al. (CCS 2013) is adaptively secure when the underlying oblivious transfer (OT) satisfies a mild adaptive security guarantee. We gain adaptive security with little to no overhead over the static case. A conditional verification technique is then used to obtain a three-round adaptively secure zero-knowledge argument in the non-programmable random oracle model (NPROM). Our three-round protocol yields a proof size that is shorter than the known UC-secure practically-efficient schemes in the short-CRS model with the right choice of security parameters.We draw motivation from state-of-the-art non-interactive secure computation protocols and leveraging specifics of ZK functionality show a two-round protocol that achieves static security. It is a proof, while most known efficient ZK protocols and our three round protocol are only arguments.
2018
PKC
Equational Security Proofs of Oblivious Transfer Protocols
We exemplify and evaluate the use of the equational framework of Micciancio and Tessaro (ITCS 2013) by analyzing a number of concrete Oblivious Transfer protocols: a classic OT transformation to increase the message size, and the recent (so called “simplest”) OT protocol in the random oracle model of Chou and Orlandi (Latincrypt 2015), together with some simple variants. Our analysis uncovers subtle timing bugs or shortcomings in both protocols, or the OT definition typically employed when using them. In the case of the OT length extension transformation, we show that the protocol can be formally proved secure using a revised OT definition and a simple protocol modification. In the case of the “simplest” OT protocol, we show that it cannot be proved secure according to either the original or revised OT definition, in the sense that for any candidate simulator (expressible in the equational framework) there is an environment that distinguishes the real from the ideal system.
2018
PKC
Compact Zero-Knowledge Proofs of Small Hamming Weight
We introduce a new technique that allows to give a zero-knowledge proof that a committed vector has Hamming weight bounded by a given constant. The proof has unconditional soundness and is very compact: It has size independent of the length of the committed string, and for large fields, it has size corresponding to a constant number of commitments. We show five applications of the technique that play on a common theme, namely that our proof allows us to get malicious security at small overhead compared to semi-honest security: (1) actively secure k-out-of-n OT from black-box use of 1-out-of-2 OT, (2) separable accountable ring signatures, (3) more efficient preprocessing for the TinyTable secure two-party computation protocol, (4) mixing with public verifiability, and (5) PIR with security against a malicious client.
2018
PKC
Extending Oblivious Transfer with Low Communication via Key-Homomorphic PRFs
We present a new approach to extending oblivious transfer with communication complexity that is logarithmic in the security parameter. Our method only makes black-box use of the underlying cryptographic primitives, and can achieve security against an active adversary with almost no overhead on top of passive security. This results in the first oblivious transfer protocol with sublinear communication and active security, which does not require any non-black-box use of cryptographic primitives.Our main technique is a novel twist on the classic OT extension of Ishai et al. (Crypto 2003), using an additively key-homomorphic PRF to reduce interaction. We first use this to construct a protocol for a large batch of 1-out-of-n OTs on random inputs, with amortized o(1) communication. Converting these to 1-out-of-2 OTs on chosen strings requires logarithmic communication. The key-homomorphic PRF used in the protocol can be instantiated under the learning with errors assumption with exponential modulus-to-noise ratio.
2018
PKC
Efficient Batch Zero-Knowledge Arguments for Low Degree Polynomials
Bootle et al. (EUROCRYPT 2016) construct an extremely efficient zero-knowledge argument for arithmetic circuit satisfiability in the discrete logarithm setting. However, the argument does not treat relations involving commitments, and furthermore, for simple polynomial relations, the complex machinery employed is unnecessary.In this work, we give a framework for expressing simple relations between commitments and field elements, and present a zero-knowledge argument which, by contrast with Bootle et al., is constant-round and uses fewer group operations, in the case where the polynomials in the relation have low degree. Our method also directly yields a batch protocol, which allows many copies of the same relation to be proved and verified in a single argument more efficiently with only a square-root communication overhead in the number of copies.We instantiate our protocol with concrete polynomial relations to construct zero-knowledge arguments for membership proofs, polynomial evaluation proofs, and range proofs. Our work can be seen as a unified explanation of the underlying ideas of these protocols. In the instantiations of membership proofs and polynomial evaluation proofs, we also achieve better efficiency than the state of the art.
2018
PKC
Constant-Size Group Signatures from Lattices
Lattice-based group signature is an active research topic in recent years. Since the pioneering work by Gordon, Katz and Vaikuntanathan (Asiacrypt 2010), ten other schemes have been proposed, providing various improvements in terms of security, efficiency and functionality. However, in all known constructions, one has to fix the number N of group users in the setup stage, and as a consequence, the signature sizes are dependent on N.In this work, we introduce the first constant-size group signature from lattices, which means that the size of signatures produced by the scheme is independent of N and only depends on the security parameter $\lambda$λ. More precisely, in our scheme, the sizes of signatures, public key and users’ secret keys are all of order $\widetilde{\mathcal {O}}(\lambda )$O~(λ). The scheme supports dynamic enrollment of users and is proven secure in the random oracle model under the Ring Short Integer Solution (RSIS) and Ring Learning With Errors (RLWE) assumptions. At the heart of our design is a zero-knowledge argument of knowledge of a valid message-signature pair for the Ducas-Micciancio signature scheme (Crypto 2014), that may be of independent interest.
2018
PKC
Committed MPC
We present a new multiparty computation protocol secure against a static and malicious dishonest majority. Unlike most previous protocols that were based on working on MAC-ed secret shares, our approach is based on computations on homomorphic commitments to secret shares. Specifically we show how to realize MPC using any additively-homomorphic commitment scheme, even if such a scheme is an interactive two-party protocol.Our new approach enables us to do arithmetic computation over arbitrary finite fields. In addition, since our protocol computes over committed values, it can be readily composed within larger protocols, and can also be used for efficiently implementing committing OT or committed OT. This is done in two steps, each of independent interest:1.Black-box extension of any (possibly interactive) two-party additively homomorphic commitment scheme to an additively homomorphic multiparty commitment scheme, only using coin-tossing and a “weak” equality evaluation functionality.2.Realizing multiplication of multiparty commitments based on a lightweight preprocessing approach. Finally we show how to use the fully homomorphic commitments to compute any functionality securely in the presence of a malicious adversary corrupting any number of parties.
2018
PKC
On the Security of Classic Protocols for Unique Witness Relations
We revisit the problem of whether the known classic constant-round public-coin argument/proof systems are witness hiding for languages/distributions with unique witnesses. Though strong black-box impossibility results are known, we provide some less unexpected positive results on the witness hiding security of these classic protocols:We give sufficient conditions on a hard distribution over unique witness NP relation for which all witness indistinguishable protocols (including all public-coin ones, such as ZAPs, Blum protocol and GMW protocol) are indeed witness hiding. We also show a wide range of cryptographic problems with unique witnesses satisfy these conditions, and thus admit constant-round public-coin witness hiding proof system.For the classic Schnorr protocol (for which the distribution of statements being proven seems not to satisfy the above sufficient conditions), we develop an embedding technique and extend the result of Bellare and Palacio to base the witness hiding property of the Schnorr protocol in the standalone setting on a relaxed version of one-more like discrete logarithm (DL) assumption, which essentially assumes there does not exist instance compression scheme for the DL problem, and show that breaking this assumption would lead to some surprising consequences, such as zero knowledge protocols for the AND-DL language with extremely efficient communication and highly non-trivial hash combiner for hash functions based on the DL problem. Similar results hold for the Guillou-Quisquater protocol.
2018
PKC
New (and Old) Proof Systems for Lattice Problems
We continue the study of statistical zero-knowledge (SZK) proofs, both interactive and noninteractive, for computational problems on point lattices. We are particularly interested in the problem $\textsf {GapSPP}$GapSPP of approximating the $\varepsilon$ε-smoothing parameter (for some $\varepsilon < 1/2$ε<1/2) of an n-dimensional lattice. The smoothing parameter is a key quantity in the study of lattices, and $\textsf {GapSPP}$GapSPP has been emerging as a core problem in lattice-based cryptography, e.g., in worst-case to average-case reductions. We show that $\textsf {GapSPP}$GapSPP admits SZK proofs for remarkably low approximation factors, improving on prior work by up to roughly $\sqrt{n}$n. Specifically:There is a noninteractive SZK proof for $O(\log (n) \sqrt{\log (1/\varepsilon )})$O(log(n)log(1/ε))-approximate $\textsf {GapSPP}$GapSPP. Moreover, for any negligible $\varepsilon$ε and a larger approximation factor $\widetilde{O}(\sqrt{n \log (1/\varepsilon )})$O~(nlog(1/ε)), there is such a proof with an efficient prover.There is an (interactive) SZK proof with an efficient prover for $O(\log n + \sqrt{\log (1/\varepsilon )/\log n})$O(logn+log(1/ε)/logn)-approximate coGapSPP. We show this by proving that $O(\log n)$O(logn)-approximate $\textsf {GapSPP}$GapSPP is in $\mathsf {coNP}$coNP. In addition, we give an (interactive) SZK proof with an efficient prover for approximating the lattice covering radius to within an $O(\sqrt{n})$O(n) factor, improving upon the prior best factor of $\omega (\sqrt{n \log n})$ω(nlogn).
2018
PKC
Tightly SIM-SO-CCA Secure Public Key Encryption from Standard Assumptions
Selective opening security (SO security) is desirable for public key encryption (PKE) in a multi-user setting. In a selective opening attack, an adversary receives a number of ciphertexts for possibly correlated messages, then it opens a subset of them and gets the corresponding messages together with the randomnesses used in the encryptions. SO security aims at providing security for the unopened ciphertexts. Among the existing simulation-based, selective opening, chosen ciphertext secure (SIM-SO-CCA secure) PKEs, only one (Libert et al. Crypto’17) enjoys tight security, which is reduced to the Non-Uniform LWE assumption. However, their public key and ciphertext are not compact.In this work, we focus on constructing PKE with tight SIM-SO-CCA security based on standard assumptions. We formalize security notions needed for key encapsulation mechanism (KEM) and show how to transform these securities into SIM-SO-CCA security of PKE through a tight security reduction, while the construction of PKE from KEM follows the general framework proposed by Liu and Paterson (PKC’15). We present two KEM constructions with tight securities based on the Matrix Decision Diffie-Hellman assumption. These KEMs in turn lead to two tightly SIM-SO-CCA secure PKE schemes. One of them enjoys not only tight security but also compact public key.
2018
PKC
Fast Garbling of Circuits over 3-Valued Logic
In the setting of secure computation, a set of parties wish to compute a joint function of their private inputs without revealing anything but the output. Garbled circuits, first introduced by Yao, are a central tool in the construction of protocols for secure two-party computation (and other tasks like secure outsourced computation), and are the fastest known method for constant-round protocols. In this paper, we initiate a study of garbling multivalent-logic circuits, which are circuits whose wires may carry values from some finite/infinite set of values (rather than only $\mathsf {True}$True and $\mathsf {False}$False). In particular, we focus on the three-valued logic system of Kleene, in which the admissible values are $\mathsf {True}$True, $\mathsf {False}$False, and $\mathsf {Unknown}$Unknown. This logic system is used in practice in SQL where some of the values may be missing. Thus, efficient constant-round secure computation of SQL over a distributed database requires the ability to efficiently garble circuits over 3-valued logic. However, as we show, the two natural (naive) methods of garbling 3-valued logic are very expensive.In this paper, we present a general approach for garbling three-valued logic, which is based on first encoding the 3-value logic into Boolean logic, then using standard garbling techniques, and final decoding back into 3-value logic. Interestingly, we find that the specific encoding chosen can have a significant impact on efficiency. Accordingly, the aim is to find Boolean encodings of 3-value logic that enable efficient Boolean garbling (i.e., minimize the number of AND gates). We also show that Boolean AND gates can be garbled at the same cost of garbling XOR gates in the 3-value logic setting. Thus, it is unlikely that an analogue of free-XOR exists for 3-value logic garbling (since this would imply free-AND in the Boolean setting).
2018
PKC
Efficient Covert Two-Party Computation
Covert computation strengthens secure computation by hiding not only participants’ inputs (up to what the protocol outputs reveal), but also the fact of computation taking place (up to the same constraint). Existing maliciously-secure covert computation protocols are orders of magnitude more costly than non-covert secure computation, and they are either non-constant round [5] or they use non-black-box simulation [10]. Moreover, constant-round covert computation with black-box simulation is impossible in the plain model [10].We show that constant-round Covert Two-Party Computation (2PC) of general functions secure against malicious adversaries is possible with black-box simulation under DDH in the Common Reference String (CRS) model, where the impossibility result of [10] does not apply. Moreover, our protocol, a covert variant of a “cut-and-choose over garbled circuits” approach to constant-round 2PC, is in the same efficiency ballpark as standard, i.e. non-covert, 2PC protocols of this type. In addition, the proposed protocol is covert under concurrent self-composition.An essential tool we use is a covert simulation-sound Conditional KEM (CKEM) for arithmetic languages in prime-order groups, which we realize in CRS or ROM at costs which are either the same (in ROM) or very close (in CRS) to known HVZK’s for such languages.
2018
PKC
Hash Proof Systems over Lattices Revisited
Hash Proof Systems or Smooth Projective Hash Functions (SPHFs) are a form of implicit arguments introduced by Cramer and Shoup at Eurocrypt’02. They have found many applications since then, in particular for authenticated key exchange or honest-verifier zero-knowledge proofs. While they are relatively well understood in group settings, they seem painful to construct directly in the lattice setting.Only one construction of an SPHF over lattices has been proposed in the standard model, by Katz and Vaikuntanathan at Asiacrypt’09. But this construction has an important drawback: it only works for an ad-hoc language of ciphertexts. Concretely, the corresponding decryption procedure needs to be tweaked, now requiring q many trapdoor inversion attempts, where q is the modulus of the underlying Learning With Errors (LWE) problem.Using harmonic analysis, we explain the source of this limitation, and propose a way around it. We show how to construct SPHFs for standard languages of LWE ciphertexts, and explicit our construction over a tag-IND-CCA2 encryption scheme à la Micciancio-Peikert (Eurocrypt’12). We then improve our construction and our analysis in the case where the tag is known in advance or fixed (in the latter case, the scheme is only IND-CPA) with a super-polynomial modulus, to get a stronger type of SPHF, which was never achieved before for any language over lattices.Finally, we conclude with applications of these SPHFs: password-based authenticated key exchange, honest-verifier zero-knowledge proofs, and a relaxed version of witness encryption.
2018
PKC
Towards Characterizing Securely Computable Two-Party Randomized Functions
A basic question of cryptographic complexity is to combinatorially characterize all randomized functions which have information-theoretic semi-honest secure 2-party computation protocols. The corresponding question for deterministic functions was answered almost three decades back, by Kushilevitz [Kus89]. In this work, we make progress towards understanding securely computable randomized functions. We bring tools developed in the study of completeness to bear on this problem. In particular, our characterizations are obtained by considering only symmetric functions with a combinatorial property called simplicity [MPR12].Our main result is a complete combinatorial characterization of randomized functions with ternary output kernels, that have information-theoretic semi-honest secure 2-party computation protocols. In particular, we show that there exist simple randomized functions with ternary output that do not have secure computation protocols. (For deterministic functions, the smallest output alphabet size of such a function is 5, due to an example given by Beaver [Bea89].)Also, we give a complete combinatorial characterization of randomized functions that have 2-round information-theoretic semi-honest secure 2-party computation protocols.We also give a counter-example to a natural conjecture for the full characterization, namely, that all securely computable simple functions have secure protocols with a unique transcript for each output value. This conjecture is in fact true for deterministic functions, and – as our results above show – for ternary functions and for functions with 2-round secure protocols.
2018
PKC
Privately Constraining and Programming PRFs, the LWE Way
Constrained pseudorandom functions allow for delegating “constrained” secret keys that let one compute the function at certain authorized inputs—as specified by a constraining predicate—while keeping the function value at unauthorized inputs pseudorandom. In the constraint-hiding variant, the constrained key hides the predicate. On top of this, programmable variants allow the delegator to explicitly set the output values yielded by the delegated key for a particular set of unauthorized inputs.Recent years have seen rapid progress on applications and constructions of these objects for progressively richer constraint classes, resulting most recently in constraint-hiding constrained PRFs for arbitrary polynomial-time constraints from Learning With Errors (LWE) [Brakerski, Tsabary, Vaikuntanathan, and Wee, TCC’17], and privately programmable PRFs from indistinguishability obfuscation (iO) [Boneh, Lewi, and Wu, PKC’17].In this work we give a unified approach for constructing both of the above kinds of PRFs from LWE with subexponential $\exp (n^{\varepsilon })$exp(nε) approximation factors. Our constructions follow straightforwardly from a new notion we call a shift-hiding shiftable function, which allows for deriving a key for the sum of the original function and any desired hidden shift function. In particular, we obtain the first privately programmable PRFs from non-iO assumptions.
2018
PKC
On the Message Complexity of Secure Multiparty Computation
We study the minimal number of point-to-point messages required for general secure multiparty computation (MPC) in the setting of computational security against semi-honest, static adversaries who may corrupt an arbitrary number of parties.We show that for functionalities that take inputs from n parties and deliver outputs to k parties, $2n+k-3$2n+k-3 messages are necessary and sufficient. The negative result holds even when given access to an arbitrary correlated randomness setup. The positive result can be based on any 2-round MPC protocol (which can in turn can be based on 2-message oblivious transfer), or on a one-way function given a correlated randomness setup.
2018
PKC
Learning with Errors and Extrapolated Dihedral Cosets
The hardness of the learning with errors (LWE) problem is one of the most fruitful resources of modern cryptography. In particular, it is one of the most prominent candidates for secure post-quantum cryptography. Understanding its quantum complexity is therefore an important goal.We show that under quantum polynomial time reductions, LWE is equivalent to a relaxed version of the dihedral coset problem (DCP), which we call extrapolated DCP (eDCP). The extent of extrapolation varies with the LWE noise rate. By considering different extents of extrapolation, our result generalizes Regev’s famous proof that if DCP is in BQP (quantum poly-time) then so is LWE (FOCS 02). We also discuss a connection between eDCP and Childs and Van Dam’s algorithm for generalized hidden shift problems (SODA 07).Our result implies that a BQP solution for LWE might not require the full power of solving DCP, but rather only a solution for its relaxed version, eDCP, which could be easier.
2018
PKC
Rounded Gaussians
This paper suggests to use rounded Gaussians in place of discrete Gaussians in rejection-sampling-based lattice signature schemes like BLISS or Lyubashevsky’s signature scheme. We show that this distribution can efficiently be sampled from while additionally making it easy to sample in constant time, systematically avoiding recent timing-based side-channel attacks on lattice-based signatures.We show the effectiveness of the new sampler by applying it to BLISS, prove analogues of the security proofs for BLISS, and present an implementation that runs in constant time. Our implementation needs no precomputed tables and is twice as fast as the variable-time CDT sampler posted by the BLISS authors with precomputed tables.
2018
PKC
Attribute-Based Signatures for Unbounded Circuits in the ROM and Efficient Instantiations from Lattices
Attribute-based signature (ABS), originally introduced by Maji et al. (CT-RSA’11), represents an essential mechanism to allow for fine-grained authentication. A user associated with an attribute x can sign w.r.t. a given public policy C only if his attribute satisfies C, i.e., $C(x)=1$ C(x)=1. So far, much effort on constructing bilinear map-based ABS schemes have been made, where the state-of-the-art scheme of Sakai et al. (PKC’16) supports the very wide class of unbounded circuits as policies. However, construction of ABS schemes without bilinear maps are less investigated, where it was not until recently that Tsabary (TCC’17) showed a lattice-based ABS scheme supporting bounded circuits as policies, at the cost of weakening the security requirement.In this work, we affirmatively close the gap between ABS schemes based on bilinear maps and lattices by constructing the first lattice-based ABS scheme for unbounded circuits in the random oracle model. We start our work by providing a generic construction of ABS schemes for unbounded-circuits in the rand om oracle model, which in turn implies that one-way functions are sufficient to construct ABS schemes. To prove security, we formalize and prove a generalization of the Forking Lemma, which we call “general multi-forking lemma with oracle access”, capturing the situation where the simulator is interacting with some algorithms he cannot rewind, and also covering many features of the recent lattice-based ZKPs. This, in fact, was a formalization lacking in many existing anonymous signatures from lattices so far (e.g., group signatures). Therefore, this formalization is believed to be of independent interest. Finally, we provide a concrete instantiation of our generic ABS construction from lattices by introducing a new $\varSigma$ Σ-protocol, that highly departs from the previously known techniques, for proving possession of a valid signature of the lattice-based signature scheme of Boyen (PKC’10).
2018
PKC
Multi-Key Searchable Encryption, Revisited
We consider a setting where users store their encrypted documents on a remote server and can selectively share documents with each other. A user should be able to perform keyword searches over all the documents she has access to, including the ones that others shared with her. The contents of the documents, and the search queries, should remain private from the server.This setting was considered by Popa et al. (NSDI ’14) who developed a new cryptographic primitive called Multi-Key Searchable Encryption (MKSE), together with an instantiation and an implementation within a system called Mylar, to address this goal. Unfortunately, Grubbs et al. (CCS ’16) showed that the proposed MKSE definition fails to provide basic security guarantees, and that the Mylar system is susceptible to simple attacks. Most notably, if a malicious Alice colludes with the server and shares a document with an honest Bob then the privacy of all of Bob’s search queries is lost.In this work we revisit the notion of MKSE and propose a new strengthened definition that rules out the above attacks. We then construct MKSE schemes meeting our definition. We first give a simple and efficient construction using only pseudorandom functions. This construction achieves our strong security definition at the cost of increasing the server storage overhead relative to Mylar, essentially replicating the document each time it is shared. We also show that high server storage overhead is not inherent, by giving an alternate (albeit impractical) construction that manages to avoid it using obfuscation.


text:
Home

>

English

>

Class 12

>

Physics

>

Chapter

>

Gravitation

>

If g is acceleration due to gr...

Updated On: 27-06-2022

Get Answer to any question, just click a photo and upload the photo and get the answer completely free,

Text Solution

2.6xx10^6 m 6.4xx10^6 m 9.0xx10^6 m 1.6xx10^6 m

Solution : g'=g/((1+h/"Re")^2) " " 4.9=9.8/((1+h/"Re")^2) rArr (1+h/"Re") =sqrt2=1.414 <br> rArr h/(Re)=0.414 rArr h = 0.414xxRe=0.414xx6.4xx10^6=2.6xx10^6

Step by step solution by experts to help you in doubt clearance & scoring excellent marks in exams.

Transcript

Hanuman Ji B to talk about the acceleration due to gravity at a height 1 decide the radius is we want the height at which acceleration due to gravity hi tech radius of earth

+ height we want to see here we know that small so you can calculate now I will write oneplus whole square its equal to if you compare these two new this will get cancel out any you will get this is goes to half and I will write one plus it is the road to write from here I can write

that is 1.414 -1 from I can write down this is equals to our time this Queen 414 and are you already know it is 6.3 into 10 to the power 6 m so I will write it is 6.3 1 2 6 1 3 7 into 10 to the power 6 metre this is the hour into this this will be the apps now you can multiply these 2.37

what we wrote here we don't hear S is equals to root 2 minus 18 and after falling award 2.6 into 10 power 6 theta as the option is

format: plain


text:
# 6 Interface Design Principles and Tips Every Web Designer Should Know

Good interface design is like the air we breathe - it's there when you need it and you use it without thinking. If you've ever used a bad interface design, struggled to get around a site, clicked away because you couldn't figure out what was going on, not been able to complete a task you had in mind, or just been plain confused, you'll know the perils of going wrong in this area.

Websites are not pretty pictures, they are there to be used and consumed, so it's pretty important that as web designers we spend a good portion of time thinking about usability. In this article we'll consider some of the big usability issues and my tips for being a better interface designer.

This Post is Day 7 of our Web Design Session. Creative Sessions

## 1 - Analysing Audiences

When laying out Psdtuts+ we take into consideration the different ways people will be using the site

In any website there are at least three distinct parties involved - the client or owner of the site, the users of the site and the designer or builder of the site. In fact often there are multiple groups of users, a few different client representatives and possibly a few people on the design team. These are all what people like to refer to as stakeholders (a word that makes me imagine a bunch of people holding t-bones).

Now the thing about stakeholders is, everyone usually wants something different. Your client(s) have an agenda - whether it's pleasing the boss, making the logo bigger, and of course getting their message across. Your users have an agenda - the tasks they are trying to perform, the information they are trying to find. And of course you have an agenda - getting your design featured on a favourite CSS gallery, pleasing your boss, fitting in a quick design before 5pm when you're going out ...

Well in the world of stakeholders, it's always important to remember that users come first. If you want a successful site you have to negotiate your own plans with your client's needs in such a way that the users are happy and find what they need. This is why one of the first things you do in planning a website is to figure out who the target audience is.

#### Audience Classes

The words target audience seem to imply that it's a group of people we are targetting for use of the site. The reality is more like there's a bunch of people who are going to use the site whether we like it or not, and it's up to us to figure out how to serve these people. So I prefer to think of Audience Classes, that is different groups of people who are going to use a site.

Each audience class will have a set of tasks they are trying to perform and information they are interested in. As a web designer your task is to figure out who these classes of people are, what they want and how they are going to use the site. To complicate matters, you can generally break up an audience in several different ways, some of which will be more helpful than others.

So for example on Psdtuts+ you could say we have these four audience classes:

1. Photoshop and Design Amateurs
2. Web and Graphic Designers
3. Computer Graphics Artists
4. Casual Interest Visitors

Now this is probably a good audience segmentation method if I was interested in what types of content to put on the site - e.g. should we have more web design tutorials or more 3d blending tutorials? But in terms of the usability of the site it's not very helpful. Another way to break up the audience is to say we have these groups:

1. People on a mission to learn Photoshop
2. Regular readers just keeping up their skills
3. Regular readers looking to kill time
4. Regular readers participating in the community
5. Occasional or casual visitors

Looking at it this way you see that different audience types come to Psdtuts+ with a different goal in mind. From this breakup we might deduce that people in categories 1 and 2 are most likely to hit our Plus system, categories 1 and 4 will be interested in the Flickr group, and so on. Then you would estimate different audience group sizes and you'll have an idea of what is most and least important on the site.

Once you've identified sets of users, figured out what they want to do on the site and roughly how big and important the different sets are, you can work out priorities for the different user tasks. Importantly your client/owner goals come into play here as they will weight the importance of different user groups.

So back to our Psdtuts+ example, one of the most important user tasks is signing up to the Plus system because it's what pays for the site, so even though "People on a mission to learn Photoshop" isn't as big an audience group as "Regular readers looking to kill time" and "Regular readers participating in the community", they are more important nevertheless. Consequently we give some of our best screen space (top right of the sidebar) to a box about joining Plus.

"Regular readers participating in the community" on the other hand is quite a large group but also happens to be a group of people who are both familiar with the site and willing to do a little bit more work, so something like the Flickr group can sit low on the sidebar where it is accessible but not immediately obvious.

#### Part Instinct, Part Analysis, Part Common Sense

At the end of the day figuring out audience groups, what they want and will do is a mix of instinct, analysis and common sense. I often feel like I'm making educated guesses, while I'm sure on projects with a big budget you could conduct surveys and be a little more sure. I think whatever your skill and budget level though it is a good habit to write out a short analysis of the different groups. Often it forces you to see relationships and issues you might not think of otherwise.

You can then present your analysis to the client. In most cases you should find they can tell you things about the audience groups you never would have known otherwise. And the more you know about the users, the better you can design a site for them.

## 2 - You can learn a lot by watching people

It's quite fascinating (and infuriating) watching what people actually do on a site

The best way to know how people are going to use a website is to watch them do it. This is called user testing and for a long time I was under the impression that it was something only big, fancy interactive agencies got to do. Sure, to do formal user testing is probably something that is out of the budget of most web design projects, but there are quite a few things you can do even if you're just one guy sitting in a basement taking web projects over eLance.

#### User Testing is Good for You as a Web Designer

The first thing you need to recognize is that when you carry out any sort of user testing, it's going to make you a better web designer. You'll get to see exactly how people use your web designs and there's a good chance you'll be surprised at how they do so. Things you think are obvious often aren't, text you thought explained something - doesn't even get read, and generally speaking users do things they weren't supposed to do. Even if the only user testing you ever do is asking some friends to use a site while you observe them, you'll already be better for it, regardless of the project itself.

#### There's Proper User Testing

If you want to conduct formal user testing, one of the simplest and least costly methods is to use Jakob Neilsen's Heuristic Evaluation. Despite the scary name, this is basically getting a set of guinea pigs to use a site and then evaluating them against a bunch of special criteria called heuristics. The set of heuristics most commonly used is Neilsen's set of 10 Usability Heuristics and the actual process of how you conduct the testing is explained by Neilsen in a reasonably easy to understand article.

The neat thing about Heuristic Evaluation is you don't need very many people to test, in fact 5 people should find around 75% of all usability problems, while doubling that to 10 will only get you up to 85%. I imagine the 5 people need to be reasonably diverse however because the idea is that different people will tend to find different problems.

According to one case study, the "benefit-cost ratio for a heuristic evaluation project of 48: The cost of using the method was about $10,500 and the expected benefits were about$500,000" (Neilsen 1994) - which sounds pretty amazing, though I know I haven't worked on very many projects where I could have swung an extra 10 grand past the client.

Just because you don't have a cool $10,500 to throw around, doesn't mean you can't benefit from user testing though! At the end of the day, all you really need is a few people (a.k.a. friends) who you can get to spend 10 minutes with. Beforehand you need to organise something to test them on. This can be anything from paper & pen wireframes to Photoshop mockups to a half-working website. Next you should figure out some ideas about what you're looking for, what tasks a person will be attempting on the site and make it clear in your own mind what you are expecting to see. Now sit your guinea pig down, brief them so that they understand what they are trying to accomplish - i.e. "You're trying to buy a ticket to Fiji and you've arrived at this page ...", then show them the set of JPEGs or pieces of paper or the bare bones site. If it's not something that is actually functional (i.e. a set of JPGs or papers) then you produce the functionality - either by explaining what happens when they "click" somewhere or by changing to the next screen they see. Personally I think JPGs are best because you can watch where the person's mouse moves, they are seeing something that approaches what they will actually see, but at the same time you don't need to have gone and built a full site. While you're testing you shouldn't be saying too much, remember you're observing! At the end you spend another couple minutes asking them any questions you have "Why the heck did you click there you dimwit?" and making any notes you need "Note to self, make that button much bigger". And that's it! You don't need a white lab coat, you don't need special equipment, you don't really need anything ... except some friends or people you can bribe - who aren't web designers themselves. #### 3rd Party Paid Services After writing all this it occurred to me that there might be some relatively cheap third party services who can provide user testing. Sure enough, there's a company called UserTesting.com who will provide you a video and written summary of a real person using your site starting at$19 for a single tester all the way up to 100 testers for $1,699. I can't say how objective these people are, but I have to say spending$100 to get 5 people to run through a site isn't too bad for a small-medium sized project. If nothing else it sure does sound impressive when you tell your client you're going to organise a set of user testing!

You should keep in mind that you can only really use a service like this with an actual working website. If you're trying to do testing at the Photoshop mockup stage or at the paper and pen wireframe stage, then you're going to have some difficulties!

#### Post Launch Analysis Tools

In this day and age there are a lot of statistical tools you can use to test how people use a site. Here are a few tools for analysing:

1. Click analysis - CrazyEgg, Google Analytics Site Overlay, ClickHeat
With these services you can see heatmaps of where people click. The only one I've really used is the one in Google Analytics (click on Content > Site Overlay in the side menu). These are pretty neat for seeing roughly where most people are going on a given page, but of course you don't know much else about what the users are doing or trying to achieve, so it really is only half the story.
2. Path analysis -Most good analytics packages
Figuring out what paths users take through a site can be determined by stats packages like Google Analytics. Between setting up goals, funnels and events, tracking exit pages, as well as just browsing by content and looking at navigation paths, there really is more information than you can shake a stick at. Personally I find it a bit overwhelming sometimes and only really use goals and funnels, but I guess it's better to have more than you need, than be needy.
3. Split Testing - Most good analytics packages
Split testing is when you alternate between two different versions of a page to see how each one converts. It's a pretty handy technique for figuring out how to optimize sales and landing pages in particular, but you could use it on pretty much any type of interface design.

## 3 - "Don't Make Me Think" ... too much

What a title! What a book!

Don't Make Me Think is the title of a famous book by usability expert Steve Krug and pretty much sums up usability into that one statement. A usable design shouldn't involve thought, it should be obvious what to do and when to do it. In the book Krug explains that people use sites in a very different manner to how we'd like to believe they do (something that will become clear when you do a bit of user testing!) and that it's important to know this so you can design them appropriately. By not overcomplicating text, designing for scanning, accepting that people aren't going to read your lengthy instructions, and so on, you can work with the reality of user habits and behavior to produce more usable designs.

You may be wondering why I added "... too much" to this heading. Well I have to admit that it bugs me that the websites of usability experts like Steve Krug and Jakob Neilsen are just so damn, basic looking. I suppose I understand why they do it, but I don't mind making users think a little bit if it means making a better visual impact. I guess I'm more of a 37Signals usability guy than a Jakob Neilsen devotee.

## 4 - Navigation and Orientation

Adobe.com does a good job with its breadcrumb trail to keep you informed on where the heck you are in their giant site.

I don't think I could write an article about interface design without touching on the subject of getting around a site. The cardinal rules of navigation are:

1. Users should always be able to work out where they are on a site
This is called orientation and you can achieve a good result through highlighted menu items, breadcrumb trails, and headings. Being able to orient yourself on a site is key to making it understandable and usable. In the real world the physical equivalent of orientation are street signs, they let you know where you are right now.
There is nothing more confusing than having a menu bar move somewhere else, change dramatically or just disappear. A site's navigation is one of the most important tools visitors use to understand a site. In the real world the physical equivalent of navigation is a street map, it let's you figure out where you can go.

The best way to understand why navigation and orientation are so important is to imagine if you were suddenly transported to a remote foreign city and told to get somewhere, the catch being that there were no street signs, and periodically your map would rearrange itself, vanish and re-appear. The pain is less on a website, but only because one mouse click gets you out of there!

There are lots of other conventions and ideas about what makes a good navigation/orientation - but everything else is subordinate to those two rules.

## 5 - Make the Problems Yours

Although more about web development than design, the 37signals book has some interesting sections about working on your own problems. And best of all the book is free to read online.

No problem is clearer than your own. This is one of the reasons why new entrepreneurs are always advised to start businesses that solve their own problem. Web designers too can benefit from solving problems they themselves have experienced. There's something about experiencing the pain first hand that makes it clear exactly how things could be better.

Since it's unlikely you'll get to choose only to work on websites you have direct experience with, a better method is to get experience with the websites you're working on. You can do this by either:

1. Using the current site (if one exists) for your client
2. Using competitor's sites that do similar things

The important thing to note is that when I say 'use', I don't mean just click around for a couple of seconds and then tick this off your to-do list. I mean really use a site. Figure out some typical tasks (e.g. "I need to contact the sales office in Delaware", "I want to make a booking") and then execute them completely. When you really understand the tasks and problems a user will be facing on a website, you'll be able to design a much better solution.

## 6 - Conventions are both familiar and easy

Icons are an excellent example of conventions. Look at the icons above and see how many automatically make you think of some task or action. Incidentally these icons are available on a Creative Commons license via Web Appers

It's been well over a decade since the web became mainstream and in that time there are lot of things about how websites look and work that have come to be generally accepted. For example when you click on a button that says "Home" you expect to go to the start page, you do not expect to go to a page that shows a person's house. It sounds obvious and dumb, but then that is what conventions are.

As a corollary to our earlier tip "Don't Make Me Think", using accepted standards means exactly that, users don't need to think. If you place your navigation bar in the footer of every page, you're going to have users getting confused, annoyed and leaving. If you use common icons for uncommon purposes, don't properly label items, fail to give "Are You Sure?" confirmations for irreversible actions, and so on, you risk alienating your users, and that is the last thing you want to do.

Sure there are times when you might not follow conventional methods, but you should have good reason to do so, and do whatever you can to make it clear what you are doing.

This Post is Day 7 of our Web Design Session. Creative Sessions


text:
# Seminar Archive

Event Code Date Speaker Seminar Title
ITSW03 13th September 2001 Discussion
ICB 13th September 2001 A Mogilner Molecular motors Tutorial
ITSW03 13th September 2001 H Braden Functional equations, difference equations and integrable systems
ITSW03 13th September 2001 F Nijhoff On some integrable discrete systems related to elliptic curves
ITSW03 13th September 2001 R Willox Integrable lattices from D-type algebras
ITSW03 13th September 2001 T Tokihiro Periodic box and ball systems
ICB 12th September 2001 HG Othmer Dicty Overview Tutorial
ITSW03 12th September 2001 J Sanders & JP Wang On recursion operators
ITSW03 12th September 2001 M Boiti Integrable discretization of sine- and sinh-Gordon equations: novelties and open problems
ITSW03 12th September 2001 F Pempinelli An Integrable discretization of kdV at large times
ITSW03 11th September 2001 Discussion
ITSW03 11th September 2001 J Hietarinta Tutorial on singularity confinements
ITSW03 11th September 2001 MD Kruskal Equivalent of the Painleve property for difference equations and study of their solvability
ITSW03 11th September 2001 R Halburd Difference equations in the complex domain
ITSW03 11th September 2001 C Viallet Complexity, singularity and integrability of maps
ITSW03 10th September 2001 Discussion
ITSW03 10th September 2001 V Papageorgiou Integrable lattice equations in 2D \& 3D posing initial-boundary value problems
ITSW03 10th September 2001 A Ramani Integrable Mappings with quadratic or quartic invarients
ITSW03 10th September 2001 JAG Roberts Interchanging parameters and integrals in discrete dynamical systems
ITSW03 10th September 2001 R Quispel Integrable Mapping
ITSW03 7th September 2001 M Noumi & A Veselov Discussion on birational represenations of affine Weyl groups
ITSW03 7th September 2001 P Hydon Direct construction of conservation laws for difference equations
ITSW03 7th September 2001 L Mansfield A variaional calculus for discursive systems with applications
ITSW03 7th September 2001 S Abenda On Algebraically integrable systems with deficiency
ITSW03 7th September 2001 V Kuznetsov Kowalevski top revisited
ITSW03 6th September 2001 Discussion
ITSW03 6th September 2001 M Nieszporski A discrete laplace ladder, the discrete Moutard equation and its adjoint. Asymptotic lattices and discrete weingarten congruences
ITSW03 6th September 2001 P Santini Analytical methods inthe study of Integrable Discrete Geometries
ITSW03 6th September 2001 W Schief Reciprocal figures, graphical statics and inversive geometry of the Schwarzian BKP hierarchy
ITSW03 6th September 2001 B Konopechenko Menelaus' theorem, Clifford configurations and inversive geometry of the discrete Schwarzian KP equation
ITSW03 5th September 2001 A Veselov Discrete hydrodynamics and Monge-Ampere equations
ITSW03 5th September 2001 A Shabat Discretization of spectral problems
ITSW03 5th September 2001 V Adler Discrete equations on planar graphs
ITSW03 4th September 2001 Discussion
ITSW03 4th September 2001 A Hone Backlund transformations for a new integrable system with peakons
ITSW03 4th September 2001 P Clarkson The Painleve and discrete Painleve equations - nonlinear and discrete special functions
ITSW03 4th September 2001 M Noumi q-Painleve equations arising from a q-version of the modified KP heirarchy
ITSW03 4th September 2001 K Kajiwara On the discrete dynamical systems with $W(A^{(1)}_1A^{(1)}_2)$ symmetry
ITSW03 3rd September 2001 Discussion
ITSW03 3rd September 2001 V Sokolov Laplace transform and integrable hyperbolic equations of Liouville type
ITSW03 3rd September 2001 J Van Diejen On the zeros of the solitude Baker-Akhiezer function for the Toda chain
ITSW03 3rd September 2001 S Ruijsenaars A new class of integrable quantum lattice systems
ITS 31st August 2001 B Konopelchenko Nonlinear dynamics on the plane, dispersionless integrable hierarchies and the quasi-classical D-BAR dressing method
SWWW01 31st August 2001 M Banner Overview of the issues raised at the programme and the future outlook
SWWW01 31st August 2001 M Onorato Freak waves in random oceanic sea states
SWWW01 31st August 2001 E Pelinovsky Freak wave phenomenon: theory and simulation
SWWW01 31st August 2001 S Galiev Trans-resonant evolution of standing harmonic waves into travelling jet-soliton waves
SWWW01 31st August 2001 MJ Cooker Flows associated with violent water waves
SWWW01 31st August 2001 ER Johnson Interfacial waves
SWWW01 31st August 2001 P Prasad Riemann problem for kinematical conservation laws and geometrical features of nonlinear wavefronts


text:
Comment
Share
Q)

# Verify that the given function(explicit or implicit)is a solution of the corresponding differential equation $y=x\sin x\qquad:xy'=y+x\sqrt{x^2-y^2} (x\neq0\;and\;x>y\;or\;x<-y)$

Comment
A)
Toolbox:
• Whenever the function is a product of two functions $u$ and $v$ , we apply the product rule which states differentiation of $uv = uv' + vu'.$
Step 1:
Here it is given $y = x\sin x$
We have two functions $x$ and $\sin x$
Applying product rule:
Let $u = x$. Hence $u' = 1$ and $v = \sin x$ and $v' = \cos x$
Product rule is $uv' + vu'$
Applying this we get
$x\cos x + \sin x.1$
$y' = x\cos x + \sin x$
Step 2:
Multiply by $x$ on both sides we get
$xy' = x^2\cos x + x\sin x$
But $x\sin x = y$ and $x^2\cos^2x$, but $\cos^2x = 1- sin^2x$
Hence $x^2 - y^2 = x^2 - x^2sin^2x$
Substituting this we get
$xy' = y + x \sqrt{x^2 - y^2}$.
Hence the answer is the solution for the given function.


text:
# FOM: Luzin hypothesis

Kanovei kanovei at wminf2.math.uni-wuppertal.de
Mon Oct 19 10:24:53 EDT 1998

```Thomas Forster wrote

>I haven't been keeping up with this, so this might be repetitious
>ort tardy.  Didn't Luzin have a hypothesis that \$2^{\elaph_0} =
>2^{\aleph_1}\$.   And why did he conjecture this?

Luzin mentioned the hypothesis near the end of 20s, it was known
as Lusin continuum hypothesis. There is more in my paper in
Russian Math Surveys 1995, 40, no 3, and Uspensky's article in
the same volume.
The LCH is a consequence of some other hypotheses which Luzin
was interested in, e.g. that any union of \$\aleph_1\$ many Borel
sets is A_2 -- this is I think why LSC also came into
consideration.


text:
# zbMATH — the first resource for mathematics

A dynamics research in a predator-prey system with a nonlinear growth rate. (Chinese. English summary) Zbl 1340.35156
Summary: This paper is concerned with dynamics of a predator-prey system subject to homogeneous Dirichlet boundary conditions, where the predator population reproduces by the nonlinear function $$1/(1+ev)$$. Existence and uniqueness of coexistence states for the predator-prey system are investigated. Moreover, some asymptotic behaviors of time-dependent solutions are shown and some numerical simulations are done to complement the analytical results. The main tools used here include an implicit function theorem, bifurcation theory and perturbation technique.
##### MSC:
 35K57 Reaction-diffusion equations 92D25 Population dynamics (general) 35A01 Existence problems for PDEs: global existence, local existence, non-existence 35A02 Uniqueness problems for PDEs: global uniqueness, local uniqueness, non-uniqueness
Full Text: