Hard to find a good rewriting rule

Rewrite rules are intended to convert ugly urls (containing with & and ?) into pretty urls not the countrary.

So I think you need a redirect more than a rewrite rule:

add_action('after_setup_theme', 'my_custom_redirect', 1);

function my_custom_redirect() {

  if ( filter_input(INPUT_GET, 'post_type', FILTER_SANITIZE_STRING) === 'portfolio' ) {
     $cat = filter_input( INPUT_GET, 'portfolio-category', FILTER_SANITIZE_STRING );
     $tag = filter_input(INPUT_GET, 'portfolio-tag', FILTER_SANITIZE_STRING );
     if ( empty($cat) || empty($tag) ) return;
     $baseurl = home_url('/my-search');
     $url = add_query_arg( array('your-category' => $cat, 'your-tag' => $tag), $baseurl );
     wp_safe_redirect($url);
     exit();
  }

}