The Experts below are selected from a list of 183 Experts worldwide ranked by ideXlab platform
Marc Fischlin - One of the best experts on this subject based on the ideXlab platform.
-
Analysis of random-oracle Instantiation scenarios for OAEP and other practical schemes. Full version of this paper. Available at http://www.cc.gatech.edu/~aboldyre/publications.html
2013Co-Authors: Ra Boldyreva, Marc FischlinAbstract:Abstract. We investigate several previously suggested scenarios of instantiating random oracles (ROs) with “realizable ” primitives in cryptographic schemes. As candidates for such “instantiating ” primitives we pick perfectly one-way hash functions (POWHFs) and verifiable pseudorandom functions (VPRFs). Our analysis focuses on the most practical encryption schemes such as OAEP and its variant PSS-E and the Fujisaki-Okamoto hybrid encryption scheme. We also consider the RSA Full Domain Hash (FDH) signature scheme. We first show that some previous beliefs about Instantiations for some of these schemes are not true. Namely we show that, contrary to Canetti’s conjecture, in general one cannot instantiate either one of the two ROs in the OAEP encryption scheme by POWHFs without losing security. We also confirm through the FDH signature scheme that the straightforward Instantiation of ROs with VPRFs may result in insecure schemes, in contrast to regular pseudorandom functions which can provably replace ROs (in a well-defined way). But unlike a growing number of papers on negative results about ROs, we bring some good news. We show that one can realize one of the two ROs in a variant of the PSS-E encryption scheme and either one of the two ROs in the Fujisaki-Okamoto hybrid encryption scheme through POWHFs, while preserving the IND-CCA security in both cases (still in the RO model). Although this Partial Instantiation in form of substituting only one RO does not help to break out of the random oracle model, it yet gives a better understanding of the necessary properties of the primitives and also constitutes a better security heuristic.
-
CRYPTO - Analysis of random oracle Instantiation scenarios for OAEP and other practical schemes
Advances in Cryptology – CRYPTO 2005, 2005Co-Authors: Alexandra Boldyreva, Marc FischlinAbstract:We investigate several previously suggested scenarios of instantiating random oracles (ROs) with “realizable” primitives in cryptographic schemes. As candidates for such “instantiating” primitives we pick perfectly one-way hash functions (POWHFs) and verifiable pseudorandom functions (VPRFs). Our analysis focuses on the most practical encryption schemes such as OAEP and its variant PSS-E and the Fujisaki-Okamoto hybrid encryption scheme. We also consider the RSA Full Domain Hash (FDH) signature scheme. We first show that some previous beliefs about Instantiations for some of these schemes are not true. Namely we show that, contrary to Canetti's conjecture, in general one cannot instantiate either one of the two ROs in the OAEP encryption scheme by POWHFs without losing security. We also confirm through the FDH signature scheme that the straightforward Instantiation of ROs with VPRFs may result in insecure schemes, in contrast to regular pseudorandom functions which can provably replace ROs (in a well-defined way). But unlike a growing number of papers on negative results about ROs, we bring some good news. We show that one can realize one of the two ROs in a variant of the PSS-E encryption scheme and either one of the two ROs in the Fujisaki-Okamoto hybrid encryption scheme through POWHFs, while preserving the IND-CCA security in both cases (still in the RO model). Although this Partial Instantiation in form of substituting only one RO does not help to break out of the random oracle model, it yet gives a better understanding of the necessary properties of the primitives and also constitutes a better security heuristic.
Marcel Jackson - One of the best experts on this subject based on the ideXlab platform.
-
CP - All or nothing: toward a promise problem dichotomy for constraint problems
Lecture Notes in Computer Science, 2017Co-Authors: Lucy Ham, Marcel JacksonAbstract:We show that intractability of the constraint satisfaction problem over a fixed finite constraint language can, in all known cases, be replaced by an infinite hierarchy of intractable promise problems of increasingly disparate promise conditions. The instances are guaranteed to either have no solutions at all, or to be k-robustly satisfiable (for any fixed k), meaning that every “reasonable” Partial Instantiation on k variables extends to a solution.
-
All or nothing: toward a promise problem dichotomy for constraint problems
arXiv: Computational Complexity, 2016Co-Authors: Lucy Ham, Marcel JacksonAbstract:A finite constraint language $\mathscr{R}$ is a finite set of relations over some finite domain $A$. We show that intractability of the constraint satisfaction problem $\mathsf{CSP}(\mathscr{R})$ for $\mathscr{R}$ can, in all known cases, be replaced by an infinite hierarchy of intractable promise problems of increasingly disparate promise conditions: where instances are guaranteed to be either have no solutions, or are $k$-robustly satisfiable (for any fixed $k$), meaning that every "reasonable" Partial Instantiation on $k$ variables extends to a solution. For example, subject to the assumption $\texttt{P}\neq \texttt{NP}$, then for any $k$, we show that there is no polynomial time algorithm that can distinguish non-$3$-colorable graphs, from those for which any reasonable $3$-coloring of any $k$ of the vertices can extend to a full $3$-coloring. The enormous flexibility granted by $k$-robust satisfiability enables the complexity of a large number of other computational problems for $\mathscr{R}$ to be tied precisely to that of $\mathsf{CSP}(\mathscr{R})$. A key example is the problem of deciding if an instance has \emph{implied constraints}: constraints not given explicitly, but which are preserved under any solution. Our results show that such instances cannot be efficiently distinguished from those with no solutions at all. Our result holds wherever the algebraic dichotomy conjecture has been shown to hold. In particular they are true for list homomorphism problems, for graphs, and for constraint languages on small domains.
Changhe Yuan - One of the best experts on this subject based on the ideXlab platform.
-
Hierarchical beam search for solving most relevant explanation in Bayesian networks
Journal of Applied Logic, 2017Co-Authors: Xiaoyuan Zhu, Changhe YuanAbstract:Most Relevant Explanation (MRE) is an inference problem in Bayesian networks that finds the most relevant Partial Instantiation of target variables as an explanation for given evidence. It has been shown in recent literature that it addresses the overspecification problem of existing methods, such as MPE and MAP. In this paper, we propose a novel hierarchical beam search algorithm for solving MRE. The main idea is to use a second-level beam to limit the number of successors generated by the same parent so as to limit the similarity between the solutions in the first-level beam and result in a more diversified population. Three pruning criteria are also introduced to achieve further diversity. Empirical results show that the new algorithm outperforms local search and regular beam search.
-
An Exact Algorithm for Solving Most Relevant Explanation in Bayesian Networks
2016Co-Authors: Xiaoyuan Zhu, Changhe YuanAbstract:Most Relevant Explanation (MRE) is a new inference task in Bayesian networks that finds the most relevant Partial Instantiation of target variables as an explana-tion for given evidence by maximizing the Generalized Bayes Factor (GBF). No exact algorithms have been de-veloped for solving MRE previously. This paper fills the void and introduces a breadth-first branch-and-bound MRE algorithm based on a novel upper bound on GBF. The bound is calculated by decomposing the computa-tion of the score to a set of Markov blankets of subsets of evidence variables. Our empirical evaluations show that the proposed algorithm makes exact MRE inference tractable in Bayesian networks that could not be solved previously
-
Exact algorithms for MRE inference
Journal of Artificial Intelligence Research, 2016Co-Authors: Xiaoyuan Zhu, Changhe YuanAbstract:Most Relevant Explanation (MRE) is an inference task in Bayesian networks that finds the most relevant Partial Instantiation of target variables as an explanation for given evidence by maximizing the Generalized Bayes Factor (GBF). No exact MRE algorithm has been developed previously except exhaustive search. This paper fills the void by introducing two Breadth-First Branch-and-Bound (BFBnB) algorithms for solving MRE based on novel upper bounds of GBF. One upper bound is created by decomposing the computation of GBF using a target blanket decomposition of evidence variables. The other upper bound improves the first bound in two ways. One is to split the target blankets that are too large by converting auxiliary nodes into pseudo-targets so as to scale to large problems. The other is to perform summations instead of maximizations on some of the target variables in each target blanket. Our empirical evaluations show that the proposed BFBnB algorithms make exact MRE inference tractable in Bayesian networks that could not be solved previously.
-
FLAIRS Conference - Hierarchical Beam Search for Solving Most Relevant Explanation in Bayesian Networks.
2015Co-Authors: Xiaoyuan Zhu, Changhe YuanAbstract:Most Relevant Explanation (MRE) is an inference problem in Bayesian networks that finds the most relevant Partial Instantiation of target variables as an explanation for given evidence. It has been shown in recent literature that it addresses the overspecification problem of existing methods, such as MPE and MAP. In this paper, we propose a novel hierarchical beam search algorithm for solving MRE. The main idea is to use a second-level beam to limit the number of successors generated by the same parent so as to limit the similarity between the solutions in the first-level beam and result in a more diversified population. Three pruning criteria are also introduced to achieve further diversity. Empirical results show that the new algorithm typically outperforms local search and regular beam search.
-
AAAI - An exact algorithm for solving most relevant explanation in bayesian networks
2015Co-Authors: Xiaoyuan Zhu, Changhe YuanAbstract:Most Relevant Explanation (MRE) is a new inference task in Bayesian networks that finds the most relevant Partial Instantiation of target variables as an explanation for given evidence by maximizing the Generalized Bayes Factor (GBF). No exact algorithm has been developed for solving MRE previously. This paper fills the void and introduces a breadth-first branch-and-bound MRE algorithm based on a novel upper bound on GBF. The bound is calculated by decomposing the computation of the score to a set of Markov blankets of subsets of evidence variables. Our empirical evaluations show that the proposed algorithm scales up exact MRE inference significantly.
Azuma Ohuchi - One of the best experts on this subject based on the ideXlab platform.
-
A reduction method for theorem proving based on the Partial-Instantiation technique
Decision Support Systems, 1998Co-Authors: Masahito Yamamoto, Azuma OhuchiAbstract:Abstract Logical inference is of central importance in the information and decision science. First-order predicate inference (theorem proving) provides more powerful representation of models and of knowledge, but presents a hard computational problem. We extend Jeroslow's theorem-proving procedure in function-free formulas to be applicable to full first-order predicate formulas. Therefore, proposed theorem-proving procedure can be more flexible tool for data handling and inferences. Our proposed procedure is based on the Partial-Instantiation technique, which reduces a first-order predicate clausal-form formula to an incrementally augmented propositional formula and proves the theorem by checking the satisfiability of the propositional formula. We also show the completeness of the proposed procedure, i.e., it can detect the unsatisfiability of an input formula. Furthermore, we compare it with resolution-style theorem-proving program otter and show the efficiency of the proposed procedure.
-
Theorem proving based on the Partial Instantiation technique
Electronics and Communications in Japan (Part III: Fundamental Electronic Science), 1996Co-Authors: Masahito Yamamoto, Azuma Ohuchi, Toshio OhyanagiAbstract:For studies toward the automated theorem proving, various methods and strategies have been presented based on the resolution principle proposed by Robinson in 1965. Most of the theorem-proving systems at present are based on this resolution principle. In constrast to this, Jeroslow proposed the Partial Instantiation technique in 1988. the method proposed by Jeroslow, however, has a problem in that only the formula not containing function symbols is considered and the efficiency is low since the clause form is not assumed. the authors improved Jeroslow's method. A procedure was proposed where satisfiability is decided for the formula of the clause form not containing function sysmbols, and the effectiveness of the method is demonstrated. This paper extends the above procedure and proposes a theorem-proving procedure so that the formula containing function symbols can be handled. A proof is given that the proposed procedure is complete. A comparison experiment is executed, and the effectiveness of the proposed procedure is investigated.
-
Theorem proving based on the Partial instatiation technique
SICE '95. Proceedings of the 34th SICE Annual Conference. International Session Papers, 1Co-Authors: Masahito Yamamoto, Toshio Ohyanagi, Azuma OhuchiAbstract:We present a new theorem proving procedure based on the Partial Instantiation technique, which is developed by Jeroslow. The proposed procedure is applicable to clausal form formulas in the first-order logic, as well as other resolution-based methods. We also show its completeness, i.e., it can verify that a given set of clauses is unsatisfiable if indeed it is unsatisfiable.
Lucy Ham - One of the best experts on this subject based on the ideXlab platform.
-
CP - All or nothing: toward a promise problem dichotomy for constraint problems
Lecture Notes in Computer Science, 2017Co-Authors: Lucy Ham, Marcel JacksonAbstract:We show that intractability of the constraint satisfaction problem over a fixed finite constraint language can, in all known cases, be replaced by an infinite hierarchy of intractable promise problems of increasingly disparate promise conditions. The instances are guaranteed to either have no solutions at all, or to be k-robustly satisfiable (for any fixed k), meaning that every “reasonable” Partial Instantiation on k variables extends to a solution.
-
All or nothing: toward a promise problem dichotomy for constraint problems
arXiv: Computational Complexity, 2016Co-Authors: Lucy Ham, Marcel JacksonAbstract:A finite constraint language $\mathscr{R}$ is a finite set of relations over some finite domain $A$. We show that intractability of the constraint satisfaction problem $\mathsf{CSP}(\mathscr{R})$ for $\mathscr{R}$ can, in all known cases, be replaced by an infinite hierarchy of intractable promise problems of increasingly disparate promise conditions: where instances are guaranteed to be either have no solutions, or are $k$-robustly satisfiable (for any fixed $k$), meaning that every "reasonable" Partial Instantiation on $k$ variables extends to a solution. For example, subject to the assumption $\texttt{P}\neq \texttt{NP}$, then for any $k$, we show that there is no polynomial time algorithm that can distinguish non-$3$-colorable graphs, from those for which any reasonable $3$-coloring of any $k$ of the vertices can extend to a full $3$-coloring. The enormous flexibility granted by $k$-robust satisfiability enables the complexity of a large number of other computational problems for $\mathscr{R}$ to be tied precisely to that of $\mathsf{CSP}(\mathscr{R})$. A key example is the problem of deciding if an instance has \emph{implied constraints}: constraints not given explicitly, but which are preserved under any solution. Our results show that such instances cannot be efficiently distinguished from those with no solutions at all. Our result holds wherever the algebraic dichotomy conjecture has been shown to hold. In particular they are true for list homomorphism problems, for graphs, and for constraint languages on small domains.