 # Efficient recovering of operation tables of black box groups and rings

Zumbraegel, J; Maze, G; Rosenthal, J (2008). Efficient recovering of operation tables of black box groups and rings. In: IEEE. Information Theory, 2008.ISIT 2008. Toronto: IEEE, 639-643.

## Abstract

People have been studying the following problem: Given a finite set S with a hidden (black box) binary operation ∗ : S × S → S which might come from a group law, and suppose you have access to an oracle that you can ask for the operation x ∗ y of single pairs (x, y) ∈ S2 you choose. What is the minimal number of queries to the oracle until the whole binary operation is recovered, i.e. you know x ∗ y for all x, y ∈ S? This problem can trivially be solved by using |S|2 queries to the oracle, so the question arises under which circumstances you can succeed with a significantly smaller number of queries. In this presentation we give a lower bound on the number of queries needed for general binary operations. On the other hand, we present algorithms solving this problem by using |S| queries, provided that ∗ is an abelian group operation. We also investigate black box rings and give lower und upper bounds for the number of queries needed to solve product recovering in this case.

## Abstract

People have been studying the following problem: Given a finite set S with a hidden (black box) binary operation ∗ : S × S → S which might come from a group law, and suppose you have access to an oracle that you can ask for the operation x ∗ y of single pairs (x, y) ∈ S2 you choose. What is the minimal number of queries to the oracle until the whole binary operation is recovered, i.e. you know x ∗ y for all x, y ∈ S? This problem can trivially be solved by using |S|2 queries to the oracle, so the question arises under which circumstances you can succeed with a significantly smaller number of queries. In this presentation we give a lower bound on the number of queries needed for general binary operations. On the other hand, we present algorithms solving this problem by using |S| queries, provided that ∗ is an abelian group operation. We also investigate black box rings and give lower und upper bounds for the number of queries needed to solve product recovering in this case.

## Statistics

### Citations

Dimensions.ai Metrics
2 citations in Web of Science®
2 citations in Scopus®